Programiranje 1 (22/23)

Tokratna naloga bo spet za oceno. Funkcije boste pisali v obliki razreda (saj je čas, da pokažete, da to znate narediti tudi, ne da bi vam pripravil ogrodje), v resnici pa je naloga predvsem v premetavanju množic.

Predpostaviti smete, da nikoli ne bomo spraševali po neobstoječih osebah. Če Lovro ne uporablja Facebooka, ne bomo spraševali, koliko prijateljev ima.

Testni primeri uporabljajo tri mreže. Eno kaže spodnja slika. Druga vsebuje le osebi z imenoma Samo in Edini; sta prijatelja. Tretja je prazna.

Ocena 6

Definiraj razred Prijatelji, ki ima metode

• dodaj(a, b), ki zabeleži, da sta osebi a in b prijatelja
• pobrisi(a, b), ki zabeleži, da a in b nista (več) prijatelja (če tudi poprej nista bila, naj metoda tiho ne naredi ničesar), in
• sta_prijatelja(a, b), ki vrne True, če sta a in b prijatelja ter False, če nista.

Osebe so podane kot nizi. Če je fb objekt razreda prijatelji, bo fb("Ana", "Berta") zabeležil, da sta Ana in Berta prijateljici. Prijateljstva so vedno obojestranska: če je Ana Bertina prijateljica, je tudi Ana Bertina.

Način, na katerega shranite podatke o prijateljstvih, je prepuščen vam. Predvsem glede na naslednje naloge pa bi si človek morda predstavljal (in imel pri tem prav), da bi bilo najpreprosteje, če bi objekti razreda Prijatelji vsebovali kar slovar, katerega ključi bi bili imena, vrednosti pa prijatelji ljudi s temi imeni (podobno strukturo ste imeli pri drugi domači nalogi Naslovi). Vsako prijateljstvo zabeležite (in brišite) v obe smeri: klic fb.dodaj("Ana", "Berta") naj med Anine prijatelje doda Berto, med Bertine pa Ano.

Lahko pa seveda naredite tudi drugače, če želite.

Rešitev

Razred potrebuje nekaj, kamor bo shranjeval relacije. Daleč najbolj praktično je uporabiti slovar s privzetimi vrednostmi. Ključi bodo imena, vrednosti bodo množice prijateljev. Naloga konstruktorja je, da pripravi takšen slovar. Imenovali ga bomo self.graf.

Metoda dodaj(a, b) med a-jeve prijatelje dodata b in obratno. Metoda pobrisi(a, b) pobriše b izmed a-jevi prijateljev in obratno. Ker uporabljamo slovar s privzetimi vrednostmi, se bo začetni prazni slovar pojavil kar sam od sebe; ko vanj dodajamo, se delamo, da že obstaja. Metoda sta_prijatelja(a, b) le preveri, ali je b med a-jevimi prijatelji.

def __init__(self):
    self.graf = collections.defaultdict(set)

def dodaj(self, a, b):
    self.graf[a].add(b)
    self.graf[b].add(a)

def pobrisi(self, a, b):
    self.graf[a].remove(b)
    self.graf[b].remove(a)

def sta_prijatelja(self, a, b):
    return b in self.graf[a]

Ocena 7

Razredu dodajte metode

• prijatelji(a), ki vrne vse prijatelje osebe a
• skupni_prijatelji(a, b), ki vrne skupne prijatelje oseb a in b in
• skupni_prijatelj(a, b), ki pove, ali imata osebi kakega skupnega prijatelja (True) ali ne (False)

Če ste ubogali namig pri oceni za 6, so vse tri funkcije trivialne. Pri tretji lahko uporabljate drugo (oz. je to celo zaželeno).

Rešitev

Metoda prijatelji(a) je še smešnejša: le množico a-jevih prijateljev vrne. Skupni prijatelji so presek množic prijateljev (dej no, a res? ;) in dve osebi imata skupnega prijatelja, če presek njunih prijateljev in prazen (ma ne? ;)

Ocena 8

Razredu dodajte metodo priporoci(a), ki osebi a priporoči vse prijatelje njenih prijateljev razen tistih, s katerimi je a že zdaj prijatelj in, seveda, a-ja samega. Funkcija naj vrne množico.

Stvar je preprosta: vrniti je potrebno unijo množic prijateljev a-jevih prijateljev; od nje je potrebno odšteti a-jeve prijatelje in a.

Rešitev

Metodo priporoci(a) napišemo tako, kot sem priporočil: izračunamo unijo množic a-jevih prijateljev in od nje odštejemo a-jeve prijatelje (z njimi je že prijatelj), torej mu jih ne priporočajmo. Pa še njega samega mu moramo odsvetovati.

def priporoci(self, a):
    priporocila = set()
    for b in self.graf[a]:
        priporocila |= self.graf[b]
    priporocila -= self.graf[a]
    priporocila.remove(a)
    return priporocila

Ocena 9

Dodajte metodo klika(s), ki prejme seznam oseb in vrne True, če gre za gosto povezano skupino prijateljev. Skupina je gosto povezana, če je število prijateljskih relacij med njimi enako ali večje od 80% možnih. Če je v s, recimo, 10 oseb, je med njimi možnih 45 "prijateljstev". Če obstaja med temi osebami vsaj 0.8 * 45 = 36 prijateljskih relacij, funkcija vrne True, sicer False.

Rešitev

Kliko rešimo na dva načina. Gremo čez vse osebe v kliki in za vsako od njih spet čez vse osebe v kliki. Pogledamo torej pare, zanka v zanki. Če sta osebi prijatelja, dodamo prijateljstvo. Takšnih prijateljev mora biti vsaj 0.8 od toliko, kolikor bi jih lahko bilo.

def klika(self, s):
    povezav = 0
    for i in s:
        for j in s:
            if self.sta_prijatelja(i, j):
                povezav += 1
    return povezav >= 0.8 * len(s) * (len(s) - 1)

Zdaj pa pozorno poglejmo, kaj počnemo znotraj notranje zanke: self.sta_prijatelja bo vrnila True za tiste j-je, ki so i-evi prijatelji. Iščemo torej velikost preseka s-ja in i-jevih prijateljev - za vsak i iz s.

def klika(self, s):
    povezav = 0
    for i in s:
        povezav += len(set(s) & self.graf[i])
    return povezav >= 0.8 * len(s) * (len(s) - 1)

Gre pa še krajše:

def klika(self, s):
    return sum(len(set(s) & self.graf[i]) for i in s) >= 0.8 * len(s) * (len(s) - 1)

Ocena 10

Dodajte metodi

• bolj_priljubljen(a), ki vrne True, če ima a vsaj toliko (torej: več ali enako) prijateljev kot katerikoli njegov prijatelj in
• najbolj_priljubljeni(), ki vrne množico vseh najbolj priljubljenih oseb (torej vseh, za katere bi funkcija bolj_priljubljen vrnila True.

Rešitev

Tole je pa enostavnejše od naloge za 9: če med a-jevimi prijatelji naletimo na koga z več prijatelji, vrnemo False. Če ga ne, vrnemo True. V drugi metodi pa le naberemo vse takšne osebe v eno množico.

def bolj_priljubljen(self, a):
    n = len(self.graf[a])
    for i in self.graf[a]:
        if len(self.graf[i]) > n:
            return False
    return True

def najbolj_priljubljeni(self):
    s = set()
    for a in self.graf:
        if self.bolj_priljubljen(a):
            s.add(a)
    return s