Virus v eni vrstici z rešitvami

S to nalogo se vračamo za dva tedna nazaj. Napisati bo potrebno podobne funkcije, le da je zdaj finta v tem, da funkcije ne vsebujejo drugega kot en sam return. Če mora funkcija vrniti množico nečesa bo videti tako

def funkcija(...argumenti...):
    return { ...nekaj pametnega... }

Spet vemo, kdo je bil kje. Na primer takole:

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

Toplo priporočam, da se čez takšne sezname odpravite z zanko oblike

for oseba, aktivnost in obiski:

Če boste delali kaj bolj zapletenega, ste si sami krivi za posledice.

Obvezne naloge

Napiši naslednje funkcije.

• aktivnosti(obiski) vrne množico vseh aktivnosti. Za gornji primer vrne {"kava", "zdravnik", "telovadba"}.

• aktivnosti_osebe(oseba, obiski) vrne seznam vseh aktivnosti določene osebe v takšnem vrstnem redu, v kakršnem nastopajo v seznamu. Klic aktivnosti_osebe("Ana", obiski) vrne ["kava", "zdravnik"]. Nekatere osebe lahko gredo tudi večkrat na isto aktivnost. V enem od testov Ana dvakrat pije kavo.

• kdo_tam(kje, obiski) vrne množico vseh oseb, ki so se udeležile določene aktivnosti. Klic kdo_tam("kava", obiski) vrne {"Ana", "Berta", "Cilka"}.

• koliko_tam(kje, obiski) vrne število oseb, ki so bile na določenem kraju. Klic kdo_tam("kava", obiski) vrne 3, ker so bile na kavi tri osebe. Izjemoma tu želim, naj funkcija ne kliče funkcij, ki ste si jih napisali prej. Pač pa sme klicati druge Pythonove funkcije, če jih potrebuje.

Rešitev

V vseh funkcijah imamo zanko for kdo, kje in obiski. Ali pa for kdo, kdo in obiski, če je kje že ime argumenta, ali pa for _, kje in obiski, če nas kdo ne zanima in hočemo to jasneje povedati s tem, da damo spremenljivki neopazno ime. (V resnici je tak dogovor za takšne spremenljivke.)

Po tem se funkcije razlikujejo le po tem, kaj nabiramo skupaj -- kje ali kdo -- in ali imajo kakšen pogoj.

Malo posebna je le zadnja. Tam nabiramo skupaj True-je in False -- oseba je bila tam ali pa ne -- in jih seštejemo. Ker je True isto kot 1, bomo na ta način le sešteli osebe, ki so bile tam, kjer nas zanima.

def aktivnosti(obiski):
    return {kje for _, kje in obiski}

def aktivnosti_osebe(oseba, obiski):
    return [kje for kdo, kje in obiski if kdo == oseba]

def kdo_tam(kje, obiski):
    return {kdo for kdo, kod in obiski if kje == kod}

def koliko_tam(kje, obiski):  # Nekoliko narobe! Glej spodaj.
    return sum(kod == kje for kdo, kod in obiski)

Po objavi rešitev sem se lotil popravljanja in opazil, da so nekateri študenti zadnjo nalogo rešili drugače, tako:

def koliko_tam(kje, obiski):
    '''Vrne število oseb ki so bile na nekem določenem kraju'''
    return len({oseba for oseba, aktivnost in obiski if kje == aktivnost})

To je pravzaprav bolj prav. Gre za to, ali osebo, ki pride večkrat na isti kraj štejemo enkrat ali večkrat. Ta rešitev jo šteje le enkrat, moja pa večkrat. Tu besedilo naloge ni bilo eksplicitno, v testih pa se takšen primer tudi ni pojavil.

Dodatne naloge

Niso težke. Za razliko od zadnje obvezne naloge, funkcije tu smejo klicati ena drugo (in tudi funkcije iz obveznega dela). Pravzaprav je to celo zaželeno in priporočljivo.

• preberi_aktivnosti(ime_datoteke) dobi datoteko oblike

  Ana kava
  Berta kava
  Cilka telovadba
  Ana zdravnik
  

  in tako naprej. Funkcija vrne seznam obiskov v gornji obliki. Predpostaviti smeš, da so vsa imena oseb in aktivnosti dolga eno besedo (se pravi: imeni osebe in aktivnosti sta ločeni z enim in edinim presledkom).

  Datoteka ni priložena testom, temveč jo testi sproti sestavijo kar sami.

• slovar_skupin(obiski) naj vrne slovar, katerega ključi so aktivnosti, pripadajoče vrednosti pa množice oseb, ki so se je udeležile. Za gornji primer funkcija vrne slovar {"kava": {"Ana", "Berta", "Cilka"}, "zdravnik": {"Dani", "Ana"}, "telovadba": {"Cilka", "Ema"}}.

• skupine(obiski) naj vrne isto kot istoimenska funkcija pred dvema tednoma: seznam množic vseh oseb, ki so se srečale na posameznih aktivnostih. V gornjem primeru vrne [{"Ana", "Berta", "Cilka"}, {"Dani", "Ana"}, {"Cilka", "Ema"}]. Vrstni red elementov v seznamu ni pomemben. Če se znajdeš, je funkcija lahko precej trivialna.

• okuzen(stvari) prejme seznam stvari, ki se jih nekdo dotakne ter vrne True, če je ta oseba potem okužena in False, če ni. Človek je okužen, če se dotakne kljuke, ne da bi se takoj zatem dotaknil mila. (Izjema je le, če je kljuka zadnja stvar, za katero vemo, da se je je dotaknil. V tem primeru bomo predpostavili, da si je šel nato umit roke, torej ni okužen.) Klic okuzen(["miza", "kljuka", "stol", "milo", "kljuka", "milo"] vrne True, ker se je za kljuko dotaknil stola. Klic okuzen(["miza", "kljuka", "milo", "milo", "kljuka", "milo"] vrne False, ker si je po vsakem dotikanju kljuke umil roke.

Rešitev

Prva je bolj preprosta, kot bi si mislili: gremo čez vrstice datoteke. (Zato je dobro, da to počnemo z zanko for, ne s kakšnimi readline v while-u.) Vsako vrstico od-strip-amo, da se znebimo "\n", nato jo split-amo na osebo in aktivnost, na koncu pa to spremenimo v terko (tuple), ker naloga tako hoče.

Slovar skupin sestavimo tako, da gremo prek vseh aktivnosti; te bodo ključi, pripadajoče vrednosti pa dobimo s funkcijo kdo_tam. Tu je naloga dovolila in priporočala klicanje prejšnjih funkcij. Če si tega ne privoščimo, bomo pač morali prepisati vsebino funkcij v to funkcijo.

skupine dobimo kot vrednosti slovarja, ki jih sestavi slovar_skupin.

Edina "zanimiva" funkcija je okuženi. Gremo čez vse pare prej, potem. Oseba je okužena, če je katerikoli (any) od teh parov takšen, da je prej == kljuka in `potem != "milo"``.

def preberi_aktivnosti(ime_datoteke):
    return [tuple(vrstica.strip().split()) for vrstica in open(ime_datoteke)]

def slovar_skupin(obiski):
    return {kje: kdo_tam(kje, obiski) for kje in aktivnosti(obiski)}

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

def okuzen(aktivnosti):
    return any(prej == "kljuka" and potem != "milo" for prej, potem in zip(aktivnosti, aktivnosti[1:]))

Malo bolj dodatna

Tole ni tako težko, je pa najbolj kul reč v vsej domači nalogi, tako da se splača pogledati.

Preberi si dokumentacijo funkcije reduce iz modula functools.

Potem ko to razumeš, smeš vedeti, tole. Recimo, da imamo s = [{1, 2, 3}, {1, 5}, {2, 6, 10}]. Če pokličemo reduce(set.union, s) dobimo unijo vseh množic iz s. Če ne veš, zakaj, ponovno preberi dokumentacijo reduce.

Napiši funkcijo okuzeni(skupine, kuzni), ki počne isto kot pred dvema tednoma. Prejme torej 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.

Rešitev

Skupina je okužena, če je v njej kdo, ki je kužen, se pravi, če je presek skupina & kuzni neprazen. To nepraznost preverjamo kar z if skupina & kuzni, saj so neprazne množice resnične (prazne pa neresnične). Vse okužene skupine dobimo z (skupina for skupina in skupine if skupina & kuzni). Potem z reduce(set.union, ...) izračunamo unijo teh množic.

from functools import reduce

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