Kosila

V prejšnji domači nalogi si je lahko vsaka punca izbrala le eno jed. Zdaj bo drugače: dobili bomo slovar, katerega ključi bodo imena deklet, pripadajoče vrednosti pa množice jedi, ki so jih izbirčnice pripravljene jesti, na primer

izbori = {
    "Ana": {"ričet", "jota", "pasulj"},
    "Berta": {"jota", "pasulj", "pleskavica"},
    "Cilka": {"kislo zelje", "jogurt"},
    "Dani": {"pasulj", "ričet"}
}

Ogrevalna naloga

Napiši funkcijo najpopularnejsa_jed(izbori), ki vrne najpopularnejšo jed (ali eno od njih, če jih je več). Za gornji primer vrne "pasulj".

Napiši funkcijo skupne_jedi(oseba1, oseba2, izbori), ki prejme imeni dve oseb in slovar, kakršen je gornji. Vrne naj množico vseh jedi, ki bi jih jedla tako oseba1 kot oseba2. Klic skupne_jedi("Ana", "Berta", izbori) vrne {"jota", "pasulj"}.

Napiši funkcijo zadovoljen(jedi, oseba, izbori), ki prejme množico razpoložljivih jedi, ime osebe in slovar, kot je gornji. Funkcija vrne True, če je med razpoložljivimi jedmi katera od teh, ki jo želi oseba, in False, če je ni. Klic zadovoljen({"makaroni", "jota", jogurt"}, "Ana", izbor) vrne True, saj je med razpoložljivimi jedmi tudi "jota". Če je ne bi bilo, bi funkcija vrnila False, saj Ana ne mara ne makaronov ne jogurta.

Rešitev

Prva naloga zahteva le preštevanje v slovar in, na koncu, iskanje ključa, ki pripada največji vrednosti. Oboje že znamo. Novo je le, da potrebujemo dvojno zanko: gremo prek vseh vrednosti v slovarju (ključi nas pri tej nalogi ne zanimajo), znotraj te zanke pa prek vseh elementov vrednosti (saj je vrednost množica).

from collections import defaultdict

def najpopularnejsa_jed(izbori):
    popularnost = defaultdict(int)
    for izbor in izbori.values():
        for jed in izbor:
            popularnost[jed] += 1
    return max(popularnost, key=popularnost.get)

Uporabili smo defaultdict s privzeto vrednostjo vrste int (torej: privzete vrednosti bodo 0). Ključ, ki pripada največji vrednosti, smo dobili z max(popularnost, key=popularnost.get); to si lahko privoščimo, ker sem na prejšnji predavanjih razložil, kako deluje. Kdor ne razume, pa naj pogleda v rešitev prejšnje domače naloge, Malice, in naredi tako, kot smo tam.

Skupne jedi so čisto navaden presek.

def skupne_jedi(oseba1, oseba2, izbori):
    return izbori[oseba1] & izbori[oseba2]

Tudi, da izvemo, ali je nekdo zadovoljen, moramo le izračunati presek jedi, ki jih je, in jedi, ki so na voljo. Če je neprazen, je jedec zadovoljen. Ali je neprazen, lahko preverimo z

def zadovoljen(jedi, oseba, izbori):
    return izbori[oseba] & jedi != set()

vendar je bolj običajno, da presek pretvorimo v bool. Prazne množice so neresnične, neprazne pa resnične - natančno tako, kot želimo.

def zadovoljen(jedi, oseba, izbori):
    return bool(izbori[oseba] & jedi)

Obvezna naloga

Napiši funkcijo vse_jedi(izbori), ki prejme slovar, kot je gornji, in vrne množico vseh jedi, ki se pojavijo v njem. V gornjem primeru vrne {"ričet", "jota", "pasulj", "pleskavica", "kislo zelje", "jogurt"}.

Napiši funkcijo zadovoljni(jed, izbori), ki vrne množico imen vseh, ki so pripravljeni jesti podano jed. Klic zadovoljni("ričet", izbori) vrne {"Ana", "Dani"}.

Napiši funkcijo zadovoljni_dve_jedi(jed1, jed2, izbori), ki je podobna prejšnji, le da vrne množico vseh, ki bi jedli jed1 ali pa jed2 (ali pa celo obe). Klic zadovoljni_dve_jedi("ričet", "jogurt", izbori) vrne {"Ana", "Cilka", "Dani"}.

Napiši funkcijo zadovoljni_jedi(jedi, izbori), ki prejme množico jedi in vrne množico vseh ljudi, ki bi bili pripravljeni jesti vsaj eno od podanih jedi.

Rešitev

Doslej smo videli le preseke; zdaj so na vrsti unije. Vse jedi dobimo tako, da sestavimo prazno množico, gremo čez vse vrednosti v slovarju, in jih priunijamo v ono množico.

def vse_jedi(izbori):
    vse = set()
    for izbor in izbori.values():
        vse |= izbor
    return vse

Gremo čez vse pare imen in želenih jedi; če se jed, ki je ponujena, nahaja v množici jedi, ki jih dotični mara, ga dodamo v množico zadovoljnih.

def zadovoljni(jed, izbori):
    zadovoljnezi = set()
    for oseba, izbor in izbori.items():
        if jed in izbor:
            zadovoljnezi.add(oseba)
    return zadovoljnezi

Množica tistih, ki so zadovoljni z eno ali drugo jedjo, je unija množic ljudi, ki so zadovoljni z eno in ljudi, ki so zadovoljni z drugo. Če je kdo z obema, bo v uniji vseeno le enkrat.

def zadovoljni_dve_jedi(jed1, jed2, izbori):
    return zadovoljni(jed1, izbori) | zadovoljni(jed2, izbori)

Če je jedi več, je eden od načinov, da dobimo zadovoljneže, ta, da za vsakega ugotovimo, ali bo zadovoljen s ponujenimi jedmi. Če je, ga dodamo v množico, ki jo na koncu vrnemo.

def zadovoljni_jedi(jedi, izbori):
    zadovoljnezi = set()
    for oseba in izbori:
        if zadovoljen(jedi, oseba, izbori):
            zadovoljnezi.add(oseba)
    return zadovoljnezi

Dodatna naloga

Napiši funkcijo najmanjsi_nabor_jedi(izbori), ki najmanjšo možno množico jedi, ki vsebuje vsaj eno jed za vsakega. V gornjem primeru je to {"pasulj", "jogurt"} ali {"pasulj", "kislo zelje"}.

Pri

{"Ana": {"jota", "pasulj", "jogurt"},
 "Berta": {"jota", "pasulj", "pleskavica"},
 "Cilka": {"jogurt", "kislo zelje"},
 "Dani": {"špageti", "ohrovt"},
 "Ema": {"ohrovt"}
}

pa je takšna množica, recimo, {'jota', 'kislo zelje', 'ohrovt'}.

Pri reševanju naloge priporočam uporabo funkcije combinations(iterable, r), ki jo kličite z vedno večjimi vrednostmi r.

Rešitev

Ta naloga pa je zanimiva, ker je hkrati čisto lahka in čisto težka. Rešimo jo lahko tako, da s funkcijo combinations sestavljamo kombinacije z eno, dvema, tremi, štirimi ... jedmi, dokler ne naletimo na kombinacijo, pri kateri so vsi zadovoljni. Ko jo najdemo, jo vrnemo.

from itertools import combinations

def najmanjsi_nabor_jedi(izbori):
    jedi = vse_jedi(izbori)
    for k in range(len(jedi) + 1):
        for izbor in combinations(jedi, k):
            if len(zadovoljni_jedi(set(izbor), izbori)) == len(izbori):
                return set(izbor)

Zakaj potem pravim, da je naloga težka? Program, ki smo ga dobili, je precej počasen. Z vsako novo jedjo se število vseh možnosti podvoji. To ne pomeni nujno, da je program dvakrat počasnejši, saj navadno ne preišče vseh kombinacij jedi, temveč le toliko, da najde kombinacijo. Vseeno pa je program v najslabšem primeru zelo počasen. Težava je v tem, da ne znamo napisati hitrejšega. Ne le mi, tule, pri tem predmetu: nihče ga ne zna. Še bolj frustrirajoče pa je, da nihče ne zna dokazati, da hitrejši program ne obstaja. A več o tem v tretjem letniku.