Covid-19

Požvižgale so se na prepovedi in skupaj kofetkale, telovadile ...

Takole lahko predstavimo, kdo je bil kje.

obiski = [("Ana", "kava"), ("Berta", "kava"), ("Cilka", "telovadba"),
          ("Dani", "zdravnik"), ("Ana", "zdravnik"), ("Cilka", "kava"),
          ("Ema", "telovadba"), ("Fanči", "telovadba"),
          ("Greta", "telovadba")]

Testi

Testi: testi-covid-19.py

Obvezna naloga

Napiši naslednje funkcije:

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

Dodatna naloga

Vse funkcije razen zadnjih treh (okuženi, zlati_prinasalec, korakov_do_vseh) napiši s pomočjo izpeljanih seznamov, množic, slovarjev, tako da bodo dolge le eno vrstico - vsebovale bodo samo return .... Pri tem seveda ne smeš definirati dodatnih funkcij, saj bi lahko potem goljufal tako, da bi vse delo opravil v njih.

Izziv

Naštudiraj funkcijo functools.reduce dodatne argumente funkcij, kot so min, max ali sort ... in v eni vrstici napiši vse funkcije razen korakov_do_vseh. (reduce seveda uporabi, kjer ga potrebuješ. Kjer ne, ne.)

Rešitev

Prve tri so res preproste. Zahtevajo samo, da znamo sestaviti slovar.

osebe, aktivnosti in udelezenci

def osebe(obiski):
    vse_osebe = set()
    for oseba, aktivnost in obiski:
        vse_osebe.add(oseba)
    return vse_osebe

def aktivnosti(obiski):
    vse_aktivnosti = set()
    for oseba, aktivnost in obiski:
        vse_aktivnosti.add(aktivnost)
    return vse_aktivnosti

def udelezenci(aktivnost, obiski):
    vsi_udelezenci = set()
    for oseba, aktivnost1 in obiski:
        if aktivnost1 == aktivnost:
            vsi_udelezenci.add(oseba)
    return vsi_udelezenci

Hitro jih še preskusimo.

osebe(obiski)
{'Ana', 'Berta', 'Cilka', 'Dani', 'Ema', 'Fanči', 'Greta'}
aktivnosti(obiski)
{'kava', 'telovadba', 'zdravnik'}
udelezenci("kava", obiski)
{'Ana', 'Berta', 'Cilka'}

Tudi v izpeljane sezname jih pretvorimo, ne da bi zašvicali.

def osebe(obiski):
    return {oseba for oseba, aktivnost in obiski}

def aktivnosti(obiski):
    return {aktivnost for oseba, aktivnost in obiski}

def udelezenci(aktivnost, obiski):
    return {oseba for oseba, aktivnost1 in obiski if aktivnost1 == aktivnost}

po_aktivnostih in skupine

Funkcija po_aktivnostih je preprosta, če uporabimo funkciji aktivnosti in udeleženci.

def po_aktivnostih(obiski):
    po_akt = {}
    for aktivnost in aktivnosti(obiski):
        po_akt[aktivnost] = udelezenci(aktivnost, obiski)
    return po_akt

Brez njiju nas čaka tole:

from collections import defaultdict

def po_aktivnostih(obiski):
    po_akt = defaultdict(set)
    for oseba, aktivnost in obiski:
        po_akt[aktivnost].add(oseba)
    return po_akt

Ali, če se ne domislimo defaultdict-a, celo tole:

def po_aktivnostih(obiski):
    po_akt = {}
    for oseba, aktivnost in obiski:
        if aktivnost not in po_akt:
            po_akt[aktivnost] = set()
        po_akt[aktivnost].add(oseba)
    return po_akt

Nobena od teh dveh tudi ne bo voljna zlesti v eno vrstico, v izpeljan slovar. Bistvena razlika med tema dvema funkcijama in prvo je, da tidve dodajata v slovar: vanj vstavita nek ključ in vrednost, kasneje pa k tej vrednosti še dodajata. Izpeljani slovarji pa so "deklarativni": povemo, kaj je ključ in kakšna je pripadajoča vrednost. Kasnejšega dodajanja ni.

Prva pa se kar sama ponuja, da bi šla v eno vrstico.

def po_aktivnostih(obiski):
    return {aktivnost: udelezenci(aktivnost, obiski) for aktivnost in aktivnosti(obiski)}

Preverimo, da res deluje.

po_aktivnostih(obiski)
{'zdravnik': {'Ana', 'Dani'},
 'telovadba': {'Cilka', 'Ema', 'Fanči', 'Greta'},
 'kava': {'Ana', 'Berta', 'Cilka'}}

Funkcija skupine pa je najpreprostejša od vseh: zahteva le, da vrnemo vse vrednosti v slovarju, kakršnega sestavi po_aktivnostih.

def skupine(obiski):
    return list(po_aktivnostih(obiski).values())

skupine(obiski)
[{'Ana', 'Dani'},
 {'Cilka', 'Ema', 'Fanči', 'Greta'},
 {'Ana', 'Berta', 'Cilka'}]

Bi se dalo drugače, brez te funkcije? Da, vendar ne brez slovarja. Vsaj ne prav lahko. Vsaka razumna rešitev, ki ne bi klicala funkcije aktivnosti, bi v bistvu ponavljala, kar smo napisali v eni od gornjih oblik te funkcije.

okuzeni in zlati_prinasalec

Funkcija okuzeni od študenta zahteva, da zna delati z množicami. Konkretno, računati preseke, unije in razlike. Iti mora čez vse skupine. Za vsako skupino preveri, ali je v njej kdo okužen (tako da izračuna presek članov te skupine in tistih, ki so bolni). Če je, potem mora člane te skupine dodati (unija) k novookuženim. Ker funkcija ne sme vrniti tudi imen tistih, ki so bili okuženi že od prej, mora na koncu od množice novookuženih odšteti množico tistih, ki so bili okuženi že prej.

def okuzeni(skupine, nosilci):
    vsi_okuzeni = set()
    for skupina in skupine:
        if skupina & nosilci:
            vsi_okuzeni |= skupina
    return vsi_okuzeni - nosilci
skupine = [{'Ana', 'Dani'},
           {'Ana', 'Berta', 'Cilka'},
           {'Cilka', 'Ema', 'Fanči', 'Greta'}]

okuzeni(skupine, {"Dani", "Berta"})
{'Ana', 'Cilka'}

Reševanje te naloge v eni vrstici je sodilo pod dodaten izziv. Mislil sem namreč, da bo potrebno zanj uporabiti funkcijo reduce. Poleg tega pa še uporabiti set.union, za katero niti ne vemo dobro, kaj je (v resnici: nevezana metoda, unbound method, kar je v sodobnem Pythonu praktično isto kot funkcija).

from functools import reduce

def okuzeni(skupine, nosilci):
    return reduce(set.union,
                  (skupina for skupina in skupine if skupina & nosilci),
                  set()
                 ) - nosilci

reduce se vam gotovo splača naštudirati. Eden od študentov pa je odkril, da set.union kot argument sprejme tudi poljubno število množi. To rešitev poenostavi v

def okuzeni(skupine, nosilci):
    return set.union(*(skupina for skupina in skupine if skupina & nosilci), set()) - nosilci

Za zlatega_prinasalca najprej potrebujemo seznam oseb. Potem pa za vsako od oseb preveri, koliko jih okuži in si zapomnimo tisto, ki jih okuži največ. To je preprosto, če se spomnimo (in znamo) uporabiti funkcijo okuzeni.

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

    zlatko = None
    zrtev = 0
    for oseba in vse_osebe:
        n_okuzenih = len(okuzeni(skupine, {oseba}))
        if n_okuzenih > zrtev or (n_okuzenih == zrtev and oseba < zlatko):
            zlatko = oseba
            zrtev = n_okuzenih
    return zlatko
zlati_prinasalec(skupine)
'Cilka'

Največji kamen spotike je bil, kako klicati funkcijo okuzeni z eno samo osebo. Klic okuzeni(skupine, oseba) ne bo deloval, ker okuzeni kot drugi argument pričakuje množico, oseba pa je niz. Klic okuzeni(skupine, set(oseba)), ker set("Cilka") ni množica, ki vsebuje niz Cilka, temveč

set("Cilka")
{'C', 'a', 'i', 'k', 'l'}

Množico, ki vsebuje niz "Cilka" zapišemo kot {"Cilka"}, množico, ki vsebuje niz, shranjen v spremenljivki oseba, pa kot {oseba}. Pravilni klic je torej takšen, kot ga vidimo zgoraj: okuzeni(skupine, {oseba}).

V eno vrstico - kar je bil spet le dodani izziv - ga najlažje spravimo tako, da sestavimo pare (-število_okuženih, ime) in poiščemo minimum. Na ta način bomo dobili tistega, ki jih je okužil največ (ker iščemo minimum negativne vrednosti), med tistimi, ki so jih okužili enako, pa tistega, ki je prej po abecedi. Če bi iskali maksimum parov (število okuženih, ime), bi med enako pridnimi prenašalci dobili tistega, ki je po abecedi kasneje.

Tudi s tem trikom rešitev v eni vrstici zahteva lambdo.

def zlati_prinasalec(skupine):
    return min(set.union(*skupine), key=lambda oseba: (-len(okuzeni(skupine, {oseba})), oseba))

Gre tudi brez, a ni nič lepše.

def zlati_prinasalec(skupine):
    return min((-len(okuzeni(skupine, {oseba})), oseba) for oseba in set.union(*skupine))[1]

korakov_do_vseh

Tale pa je študentom nepričakovano dala vetra.

Bistvo funkcije je, da širimo množico okuženih. V bistvu delamo vsi_okuzeni |= okuzeni(skupine, vsi_okuzeni) - k vsem okuženim v vsakem koraku dodamo vse, ki jih okužijo vsi, ki so okuženi.

V začetku potrebujemo množico vseh oseb. To lahko dobimo tako, kot v zlati_prinasalec, ali po bližnjici, ki smo jo odkrili zgoraj, vsi = set.union(*skupine). Množica prvotno okuženih je {prinasalec}.

Nato potrebujemo zanko, eno in edino. V njej bomo šteli korake. Zanka je lahko oblike

korakov = 0
while True:
    ...
    korakov += 1

po prejšnjih predavanjih pa vemo za itertools.count(), ki je v bistvu neskončen range, torej funkcija, ki šteje od 0 do neskončno. Gornjo zanko lahko torej zamenjamo z

for korakov in count():

Znotraj znake pa nam je ponavljati tole. Če so doslej_okuzeni že vsi, vrnemo število korakov. (To je lahko tudi 0, če je prinasalec edina oseba na svetu. Sicer izvemo, kdo so novookuzeni. Če jih ni, vrnemo None, ker še niso okuženi vsi, in tudi nikoli ne bodo. Če imamo kakega novookuženega, pa ga dodamo k doslej okuženim.

from itertools import count

def korakov_do_vseh(skupine, prinasalec):
    vsi = set.union(*skupine)
    doslej_okuzeni = {prinasalec}
    for i in count():
        if doslej_okuzeni == vsi:
            return i
        novookuzeni = okuzeni(skupine, doslej_okuzeni)
        print(novookuzeni)
        if not novookuzeni:
            return None

        doslej_okuzeni |= novookuzeni

Za primerjavo s tabelico iz opisa naloge, smo dodali še en print

korakov_do_vseh([{"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"}], "Ana")
{'Klara', 'Micka'}
{'Cilka', 'Dani'}
{'Ema', 'Lara', 'Saša', 'Špela', 'Petra', 'Jana'}
{'Iva', 'Berta', 'Greta', 'Fanči'}
{'Nina', 'Rebeka', 'Olga'}
5

Točno, kot mora biti:

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

Nekatere je zanimala še rešitev te naloge v eni vrstici - tega nisem namreč pisal niti v izziv.

Osnovni problem je, kako shraniti nekaj, kar si naračunal, v spremenljivko, da ne bo potrebno računati ponovno. Python 3.8 ima "walrus operator". Meni se zdi ogaben in ga nisem še nikoli uporabil. Spodnji trik ima vsaj neko lispovsko eleganco (spominja na let, ki ga imamo tudi v kotlinu): če hočeš neko naračunano vrednost uporabiti večkrat, napišeš lambdo in jo pokličeš s to vrednostjo. Se pravi, namesto f(x) * (1 + f(x)) napišeš (lambda y: y * (1 + y))(f(x)).

To naredi spodnjo funkcijo skoraj prebavljivo.

def korakov_do_vseh(skupine, doslej):
    return korakov_do_vseh(skupine, {doslej}) if isinstance(doslej, str) else (
        0 if set.union(*skupine) == doslej else
        (lambda novi:
             (lambda korakov: None if korakov is None else korakov + 1)(korakov_do_vseh(skupine, doslej | novi)) if novi else None)
        (okuzeni(skupine, doslej))
    )