Požvižgale so se na prepovedi in skupaj kofetkale, telovadile ...
Takole lahko predstavimo, kdo je bil kje.
= [("Ana", "kava"), ("Berta", "kava"), ("Cilka", "telovadba"),
obiski "Dani", "zdravnik"), ("Ana", "zdravnik"), ("Cilka", "kava"),
("Ema", "telovadba"), ("Fanči", "telovadba"),
("Greta", "telovadba")] (
Testi: testi-covid-19.py
Napiši naslednje funkcije:
osebe(obiski)
prejme seznam, kot je gornji, in vrne
množico imen vseh oseb, ki se pojavljajo v njih; za gornje podatke vrne
{"Ana", "Berta", "Cilka", "Dani", "Ema", "Fanči", "Greta"}
.
aktivnosti(obiski)
prejme seznam, kot je gornji in
vrne množico vseh aktivnosti; v gornjem primeru
{"kava", "telovadba", "zdravnik"}
.
udelezenci(aktivnost, obiski)
prejme ime aktivnosti,
na primer "kava"
in seznam, kot je gornji, ter vrne množico
imen vseh, ki so sodelovali v tej aktivnosti (torej
{"Ana", "Berta", "Cilka"}
.)
po_aktivnostih(obiski)
prav tako prejme seznam, vrne
pa slovar, katerega ključi so aktivnosti, vrednosti pa osebe, ki so se
udeleževale te aktivnosti, na primer
"kava": {"Ana", "Berta", "Cilka"},
{"zdravnik": {"Ana", "Dani"},
"telovadba": {"Cilka", "Ema"}}
skupine(obiski)
vrne seznam množic ljudi, ki so se
družile ob posameznih aktivnostih. Za gornji primer vrne
[{"Ana", "Berta", "Cilka"}, {"Ana", "Dani"}, {"Cilka", "Ema"}]
.
Vrstni red množic v seznamu je lahko poljuben.
okuzeni(skupine, nosilci)
prejme seznam skupin, kot
ga vrača prejšnja funkcija, in množico ljudi, za katere vemo, da so
okuženi (nosilci
). Funkcija vrne množico imen vseh ljudi,
ki so jih nosilci
potencialno okužili. Za skupine iz
prejšnjega primera mora klic
okuzeni(skupine, {"Cilka", "Berta"})
vrniti
{"Ana", "Ema"}
.
zlati_prinasalec(skupine)
vrne ime osebe, 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! Kadar je enako
"zlatih" oseb več, je Zlatko tisti, ki je prej po abecedi. Za gornje
skupine lahko Ana in Cilka okužita po tri ljudi, zato funkcija vrne
"Ana"
.
korakov_do_vseh(skupine, prvi)
, ki prejme skupine in
prvega okuženega. Vrne število korakov, po katerih bodo okuženi vsi. Če
pa slučajno obstaja kdo (ali skupina ljudi), ki ga (jih) okužba nikoli
ne doseže, ker se ni(so) družil(i) z drugimi, naj funkcija vrne
None
.
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 |
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.
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.)
Prve tri so res preproste. Zahtevajo samo, da znamo sestaviti slovar.
osebe
,
aktivnosti
in udelezenci
def osebe(obiski):
= set()
vse_osebe for oseba, aktivnost in obiski:
vse_osebe.add(oseba)return vse_osebe
def aktivnosti(obiski):
= set()
vse_aktivnosti for oseba, aktivnost in obiski:
vse_aktivnosti.add(aktivnost)return vse_aktivnosti
def udelezenci(aktivnost, obiski):
= set()
vsi_udelezenci 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'}
"kava", obiski) udelezenci(
{'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):
= udelezenci(aktivnost, obiski)
po_akt[aktivnost] return po_akt
Brez njiju nas čaka tole:
from collections import defaultdict
def po_aktivnostih(obiski):
= defaultdict(set)
po_akt 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:
= set()
po_akt[aktivnost]
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):
= set()
vsi_okuzeni for skupina in skupine:
if skupina & nosilci:
|= skupina
vsi_okuzeni return vsi_okuzeni - nosilci
= [{'Ana', 'Dani'},
skupine 'Ana', 'Berta', 'Cilka'},
{'Cilka', 'Ema', 'Fanči', 'Greta'}]
{
"Dani", "Berta"}) okuzeni(skupine, {
{'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,
for skupina in skupine if skupina & nosilci),
(skupina 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):
= set()
vse_osebe for skupina in skupine:
|= skupina
vse_osebe
= None
zlatko = 0
zrtev for oseba in vse_osebe:
= len(okuzeni(skupine, {oseba}))
n_okuzenih if n_okuzenih > zrtev or (n_okuzenih == zrtev and oseba < zlatko):
= oseba
zlatko = n_okuzenih
zrtev 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
= 0
korakov while True:
...+= 1 korakov
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):
= set.union(*skupine)
vsi = {prinasalec}
doslej_okuzeni for i in count():
if doslej_okuzeni == vsi:
return i
= okuzeni(skupine, doslej_okuzeni)
novookuzeni print(novookuzeni)
if not novookuzeni:
return None
|= novookuzeni doslej_okuzeni
Za primerjavo s tabelico iz opisa naloge, smo dodali še en
print
"Cilka", "Ema", "Jana", "Saša"},
korakov_do_vseh([{"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)) )