Covid-19 (skupine)

Obvezna naloga

Skupine

Vemo, kdo je bil kje. Na primer takole:

[("Ana", "kava"), ("Berta", "kava"), ("Cilka", "telovadba"),
 ("Dani", "zdravnik"), ("Ana", "zdravnik"), ("Cilka", "kava"),
 ("Ema", "telovadba")]

Napiši funkcijo skupine(kdo_kje), ki prejme seznam, kakršen je zgornji, in vrne seznam množic skupin ljudi, ki so bili kdaj skupaj. Za gornji seznam vrne [{"Ana", "Berta", "Cilka"}, {"Dani", "Ana"}, {"Cilka", "Ema"}] - prva množice ustreza kavopivkam, druga obiskovalkam zdravnika, tretja telovadkam.

Vrstni red množic v vrnjenem seznamu je lahko poljuben.

Rešitev

Tole ste nekateri reševali tako.

def skupine(obiski):
    kava = set()
    telovadba = set()
    zdravnik = set()
    for kdo, kje in obiski:
        if kje == "kava":
            kava.add(kdo)
        if kje == "telovadba":
            telovadba.add(kdo)
        if kje == "zdravnik":
            zdravnik.add(kdo)
    return [kava, telovadba, zdravnik]

To rešitev sem sprejel, ker pač preživi teste - in ker v besedilu nisem posebej težil, da se ne sme reševati tako. Ni pa dobro. Kaj, če bi bil v testih še frizer? Bi v funkcijo dodali še frizerja? To ni splošna funkcija.

Sprejemljiva -- a ne prav dobra -- rešitev je:

def skupine(obiski):
    aktivnosti = set()
    for kdo, kje in obiski:
        aktivnosti.add(kje)

    kdo_kje = []
    for aktivnost in aktivnosti:
        kdo_tam = set()
        for kdo, kje in obiski:
            if kje == aktivnost:
                kdo_tam.add(kdo)
        kdo_kje.append(kdo_tam)
    return kdo_kje

Od prejšnje se očitno razlikuje po tem, da sestavi množico vseh krajev, ki bi jih lahko osebe obiskovale, zato deluje tudi za frizerje in vulkanizerje. (15. marec je mimo. Že imamo letne gume?)

Nato gre prek vseh aktivnosti, za vsako sestavi množico vseh udeležencev in te množice zlaga v sezname.

Obstajajo tudi slabše različice istega. Prva je te, da namesto množice aktivnosti sestavljamo seznam aktivnosti. V tem primeru moramo namreč paziti, da se elementi ne bi ponavljali.

    aktivnosti = []
    for kdo, kje in obiski:
        if kje not in aktivnosti:
            aktivnosti.append(kje)

Pri množicah je to nepotrebno, saj množica ne more vsebovati enakih elementov. Niti če bi hoteli, ne. Zato je bilo tam dovolj le.

def skupine(obiski):
    aktivnosti = set()
    for kdo, kje in obiski:
        aktivnosti.add(kje)

    kdo_kje = []
    for aktivnost in aktivnosti:
        kdo_tam = set()
        for kdo, kje in obiski:
            if kje == aktivnost:
                kdo_tam.add(kdo)
        kdo_kje.append(kdo_tam)
    return kdo_kje

Slabost te funkcije je v tem, da ima gnezdene zanke -- brez potrebe, kot bomo videli. se pravi, za vsako aktivnost gre znova prek vseh oseb. Zdaj pa naredimo tako, kot je treba.

Vedno si je koristno predstavljati, kako bi to naredili ročno. Recimo, da bi nam nekdo bral listke ("Ana - kava" in tako naprej). Najbrž ga ne bi silili, da najprej prebere vse listke, mi pa bi beležili le, kdo je bil na kavi. In naslednjič bi ponovno bral vse listke, od začetka, mi pa bi beležili, kdo je telovadil. Ne, najbrž bi on bral le enkrat, mi pa bi vsakič, ko bi izvedeli za novo dejavnost, preprosto začeli nov stolpec, ne?

def skupine(obiski):
    kdo_kje = {}
    for kdo, kje in obiski:
        if kje not in kdo_kje:
            kdo_kje[kje] = set()
        kdo_kje[kje].add(kdo)
    return kdo_kje.values()

Vsakič torej, ko naletimo, na novo dejavnost, dodamo v slovar novo prazno množico,

        if kje not in kdo_kje:
            kdo_kje[kje] = set()

Še temu se lahko izognemo, če se spomnimo slovarjev s privzetimi vrednostmi.

from collections import defaultdict

def skupine(obiski):
    kdo_kje = defaultdict(set)
    for kdo, kje in obiski:
        kdo_kje[kje].add(kdo)
    return kdo_kje.values()

Funkcija vrača le vrednosti iz slovarja (katere skupine so bile na istem kraju), saj nas ključi (kraji) ne zanimajo. Zato kdo_kje.values(). To preživi teste, čeprav, striktno gledano, to ni seznam. Bolj prav bi bilo, če bi funkcija vračala list(kdo_kje.values()).

Skladno z izkušnjami iz prejšnjih generacij tudi vi nočete delati z množicami. Veliko raje namesto množic sestavljate sezname:

        if kje not in kdo_kje:
            kdo_kje[kje] = []
        kdo_kje[kje].append(kdo)

Vse, kar imate od tega, je, da morate potem kasneje te sezname spremeniti v množice.

    r = []
    for skupina in kdo_kje.values():
        r.append(set(skupina))
    return r

Okuženi

Napiši funkcijo okuzeni(skupine, kuzni), ki prejme seznam skupin, kakršnega vrača prejšnja funkcija, in množico vseh, ki so okuženi z virusom. Vrniti mora množico vseh, ki so bili vsaj enkrat v stiku s kom, ki je bil okužen.

Klic

okuzeni([{"Ana", "Berta", "Cilka"}, {"Dani", "Ana"}, {"Cilka", "Ema"}],
         {"Ema", "Dani"})

vrne {"Ana", "Cilka", "Dani", "Ema"}, saj Ema in Dani okužita Cilko in Dani.

Klic

okuzeni([{"Ana", "Berta", "Cilka"}, {"Dani", "Ana"}, {"Cilka", "Ema"}],
         {"Ana", "Ema"})

vrne {"Ana", "Berta", "Cilka", "Dani", "Ema"}, saj Ana osreči Berto, Cilko in Dani, Ema pa Cilko.

Rešitev

Z množicami se vam splača naučiti delati tudi zato, ker je potem vse preprosteje. Drugo funkcijo ste pretežno uspešno napisali, a pri tem komplicirali do onemoglosti. Funkcija zahteva le uporabo presekov in unij!

Skupina je okužena, če je kdo izmed njenih članov kužen. To ni nič drugega kot presek množic.

In če je skupina okužena, je potrebno njene člane dodati med te, ki so okuženi. "Dodati" pa pomeni "priunijati".

def okuzeni(skupine, kuzni):
    bolniki = set()
    for skupina in skupine:
        if skupina & kuzni:
            bolniki |= skupina
    return bolniki

Če niste delali z množicami temveč s seznami, ali pa če ste delali z množicami, vendar ste pozabili na presek in unijo, ste morali & in |= nadomestiti z zankama. Namesto, recimo bolniki |= skupina ste morali pisati

            for oseba in skupina:
                bolniki.add(oseba)

Zlati prinašalec

Napiši funkcijo zlati_prinasalec(skupine), ki vrne ime človeka, ki lahko okuži največ ljudi. Torej človeka, ki se je družil z največ drugimi ljudmi. Pazi, to ni nujno tisti, ki je v največ skupinah!

Če si prvo mesto delita dva, naj krona pripade tistemu, ki je prej po abecedi.

Rešitev

Najprej bo potrebno dobiti seznam vseh oseb. Ali, ker je to skoraj vseeno, množico vse oseb. No, ni povsem vseeno: množico vseh oseb je lahko sestaviti, saj je to preprosto unija vseh skupin.

    vsi = set()
    for skupina in skupine:
        vsi |= skupina

Potem je potrebno iti prek vseh oseb in za vsako izvedeti, koga je ta oseba okužila. Pri tem si lahko pomagamo kar s prejšnjo funkcijo, ki za množico okuženih (v tem primeru bo to pač le ena oseba) pove, koga ta množica okuži.

    for oseba in vsi:
        znanci = okuzeni(skupine, {oseba})

Celotna funkcija bo takšna:

def zlati_prinasalec(skupine):
    vsi = set()
    for skupina in skupine:
        vsi |= skupina

    naj_nosilec = None
    naj_velikost = 0
    for oseba in vsi:
        znanci = okuzeni(skupine, {oseba})
        if len(znanci) > naj_velikost \
                or len(znanci) == naj_velikost and oseba < naj_nosilec:
            naj_nosilec, naj_velikost = oseba, len(znanci)
    return naj_nosilec

Bodite pozorni na pogoj:

        if len(znanci) > naj_velikost \
                or len(znanci) == naj_velikost and oseba < naj_nosilec:

Zanima nas, ali je ta oseba okužila več ljudi kot katerakoli doslej, ali pa jih je okužila enako, vendar je prej po abecedi.

Ta rešitev velikokrat pokliče funkcijo okuzeni in ta gre vsakič prek vseh oseb. Temu se lahko izognemo tako, da sestavimo slovar žrtev posamezne osebe. Sestavljanje tega slovarja bomo dali v ločeno funkcijo, ker nam bo prišla prav pri dodatni nalogi.

def slovar_zrtev(skupine):
    zrtve = defaultdict(set)
    for skupina in skupine:
        for oseba in skupina:
            zrtve[oseba] |= skupina
    return zrtve

Za vsako skupino za vsako osebo dodamo vse ostale osebe iz te skupine med njene žrtve. Da to izgleda tako, kot da vsak okuži tudi samega sebe, nas ne moti, saj nas zanima le rekorder in ne število okuženih (ki bo pač za 1 preveliko).

Funkcija se tako skrajša - predvsem zato, ker nam ni več potrebno sestavljati množice vseh oseb. Vse osebe dobimo kar kot ključe tega slovarja. Ker bomo za vsako od njih morali vedeti tudi, koga je okužila, gremo prek items():

def zlati_prinasalec(skupine):
    zrtve = slovar_zrtev(skupine)
    naj_nosilec = None
    naj_velikost = 0
    for oseba, znanci in zrtve.items():
        if len(znanci) > naj_velikost \
                or len(znanci) == naj_velikost and oseba < naj_nosilec:
            naj_nosilec, naj_velikost = oseba, len(znanci)
    return naj_nosilec

Dodatna naloga

Tale je pa kar zahtevna. Piši za pomoč, če se zatakne, pa bom morda povedal tudi kaj o postopku.

Napiši funkcijo korakov_do_vseh(skupine, prvi), ki prejme skupine in prvega okuženega. Vrne število korakov po katerih bodo okuženi vsi.

Recimo, da imamo skupine

[{"Cilka", "Ema", "Jana", "Saša"},
 {"Ema"},
 {"Fanči", "Greta", "Saša"},
 {"Greta", "Nina"},
 {"Greta", "Olga", "Rebeka"},
 {"Micka", "Ana", "Klara"},
 {"Fanči", "Iva", "Berta", "Špela"},
 {"Klara", "Cilka", "Dani"},
 {"Petra", "Dani", "Lara", "Špela"}]

in da je prvookužena Ana. Ana bo okužila Micko in Klaro. V drugem koraku bosta tidve okužili Dani in Cilko. V tretjem koraku bosta tidve okužili Laro, Jano, Petro, Sašo, Emo in Špelo. V četrtem koraku bodo te okužile Berto, Fanči, Greto in Ivo. V petek bodo le-te okužile Olgo, Nino in Rebeko. Da bodo bolni vsi, bo torej potrebnih pet korakov - če začnemo z Ano. Funkcija zato v tem primeru vrne 5.

korak		okuženi
0		Ana
1		Micka, Klara
2		Dani, Cilka
3		Lara, Jana, Petra, Saša, Ema, Špela
4		Berta, Fanči, Greta, Iva
5		Olga, Nina, Rebeka

Če obstajajo tudi skupine, ki jih okužba nikoli ne doseže, ker se niso družili z drugimi, naj funkcija vrne None.

Rešitev

Nalogo je rešilo zgledno število študentov. Pretežno ste reševali tako, da ste sestavili množico okuženih, nato pa v neki zanki sestavljali vedno večje množice okuženih, v katerih so bili vsi tisti, ki so bili v stiku s temi, ki so bili okuženi doslej.

Zanko ste ponavljali, dokler niso bili okuženi vsi. Poleg tega pa ste jo prekinili in vrnili None, če v kakem krogu ni bilo nobenega novookuženega več.

Neka lepa različica take rešitve bi bila:

def korakov_do_vseh(skupine, zacetnik):
    okuzeni = {zacetnik}
    zrtve = slovar_zrtev(skupine)
    korakov = 0
    while len(okuzeni) != len(zrtve):
        novi_okuzeni = set()
        for oseba in okuzeni:
            novi_okuzeni |= zrtve[oseba]
        if novi_okuzeni == okuzeni:
            return None
        korakov += 1
        okuzeni = novi_okuzeni
    return korakov

To je čisto lepo, problem je le v tem, da v vsakem krogu dodaje "žrtve" tistih, ki so bili okuženi že davno. Lepše bi bilo, če bi v vsakem krogu dodali le "žrtve" tistih, ki so bili okuženi v prejšnjem krogu.

def korakov_do_vseh(skupine, zacetnik):
    zrtve = slovar_zrtev(skupine)
    okuzeni = []
    krog = [zacetnik]
    korakov = -1
    while krog and len(okuzeni) != len(zrtve):
        naslednji = set()
        for oseba in krog:
            naslednji |= zrtve[oseba]
        okuzeni += list(krog)
        krog = naslednji - set(okuzeni)
        korakov += 1
    if len(okuzeni) != len(zrtve):
        return None
    return korakov