import collections from functools import reduce

1. V karanteno

Aktivnosti oseb shranimo v slovar: {"Ana": ["kava", "trgovina", "burek"], "Berta": ["telovadba", "frizer"], "Ema": ["kava", "telovadba"], "Fanči": ["frizer"], "Greta": ["lokostrelstvo", "curling"]}.

Napiši funkcijo v_karanteno(aktivnosti, okuzene), ki prejme slovar, kakršen je gornji in seznam okuženih oseb. Vrne naj množico oseb, ki so se udeležile katere od aktivnosti, ki se jih je udeležila katera od okuženih oseb. Klic v_karanteno( aktivnosti, ["Ema", "Berta"]) vrne {"Ana", "Berta", "Ema", "Fanči"}; Ano vrne, ker sta bili obe z Emo na kavi, Fanči pa, ker sta bili z Berto pri frizerju. V množici morajo biti tudi vse osebe, ki so v podanem seznamu okuženih.

Rešitev

Ker iščemo preseke med aktivnostmi, ki so se jih udeležile osebe, bo najprejprosteje sestaviti množico vseh "okuženih aktivnosti". Nato gremo prek vseh oseb in vsako, ki se je udeležila katere od okuženih aktivnosti, dodamo v množico oseb za karanteno.

def v_karanteno(aktivnosti, okuzene):
    aktivnosti_okuzenih = set()
    for okuzena in okuzene:
        aktivnosti_okuzenih |= set(aktivnosti[okuzena])

    za_karanteno = set(okuzene)
    for oseba, aktivnost in aktivnosti.items():
        if set(aktivnost) & aktivnosti_okuzenih:
            za_karanteno.add(oseba)

    return za_karanteno

V prvem delu funkcije torej sestavljamo "okužene aktivnosti". Množica za_karanteno za začetek vsebuje vse okužene, nato pa vanjo dodajamo še te, ki so v stiku z njimi.

Drugi del je mogoče rešiti v enem zamahu.

def v_karanteno(aktivnosti, okuzene):
    aktivnosti_okuzenih = set()
    for okuzena in okuzene:
        aktivnosti_okuzenih |= set(aktivnosti[okuzena])

    return {oseba
            for oseba, aktivnost in aktivnosti.items()
            if set(aktivnost) & aktivnosti_okuzenih} | set(okuzene)

Prvega pa tudi, a brez posebnih točk za estetiko. Pa tudi učili se tega nismo.

from functools import reduce

def v_karanteno(aktivnosti, okuzene):
    aktivnosti_okuzenih = reduce(set.union, (set(aktivnosti[okuzena]) for okuzena in okuzene))
    return {oseba
            for oseba, aktivnost in aktivnosti.items()
            if set(aktivnost) & aktivnosti_okuzenih} | set(okuzene)

2. Genom SARS-Covid-19

Napiši funkcijo trojke(s, n), ki prejme zaporedje baz v mRNA in vrne n najpogostejših zaporednih trojk, urejenih po pogostosti. Če sta dve trojki enako pogosti, ima prednost tista, ki je kasneje po abecedi (ker je tako lažje sprogramirati!). Če je različnih trojk manj kot n, jih vrne pač, kolikor jih je.

V zaporedju "acgtacgatacgacg" je najpogostejša trojka acg (štirikrat), sledijo tac in cga (dvakrat), nato gta, gat, gac, cgt in ata (enkrat). Klic trojke("acgtacgatacgacg", 5) zato vrne ["acg", "tac", "cga", "gta", "gat"].

Rešitev

Potrebujemo zanko for i in range(len(s) - 2), preštejemo vse trojke s[i:i + 3] v slovar, katerega ključi so trojke, vrednosti pa pogostosti -- kot smo že velikokrat počeli. Rezultat premečemo v slovar parov (pogostost, trojka), ga padajoče uredimo. Zanima nas le prvih n elementov. V seznamu imamo pare, funkcija pa mora vrniti seznam drugih elementov, torej trojk. Torej potrebujemo še eno zanko, s katero jih poberemo.

def trojke(s, n):
    stevec = collections.defaultdict(int)
    for i in range(len(s) - 2):
        stevec[s[i:i + 3]] += 1

    pogostosti = [(frek, trojka) for trojka, frek in stevec.items()]
    pogostosti = sorted(pogostosti, reverse=True)
    najpogostejse = []
    for _, trojka in pogostosti[:n]:
        najpogostejse.append(trojka)
    return najpogostejse

Za štetje lahko uporabljamo tudi Counter iz modula collections, ki najbolj zablesti, če mu podamo kar generator.

Predvsem pa se z izpeljanim seznamom znebimo zadnje zanke, ki le prelaga druge elemente seznama v nov seznam.

def trojke(s, n):
    stevec = collections.Counter(s[i:i + 3] for i in range(len(s) - 2))

    pogostosti = [(frek, trojka) for trojka, frek in stevec.items()]
    pogostosti = sorted(pogostosti, reverse=True)
    return [trojka for _, trojka in pogostosti[:n]]

3. Statistika

Število okuženih v zadnjih dneh po posameznih državah je podano v nizih v naslednji obliki:

Slovenija:31,20,25,14,50,60
Hrvaška:150,170,200,220,221
Madžarska:100,70,35

Napiši funkcijo statistika(podatki, drzava, n), ki prejme takšen niz ter vrne število okuženih v zadnjih n dneh v podani državi. Za manjkajoče podatke predpostavi, da je bilo takrat okuženih 0 oseb.

Klic statistika(podatki, "Slovenija", 3) za gornje podatke vrne, 124 (to je 14 + 50 + 60), statistika(podatki, "Madžarska", 5) pa vrne 205.

Rešitev

Niz "splitamo" po vrsticah. Za to lahko uporabimo splitlines() ali split(\n). Vsako vrstico splitamo glede po ":", pa dobimo državo in številke. Če je država tista, ki jo iščemo, splitamo številke po ",", jih spremenimo v int in seštejemo ter tako, kar iz zanke, vrnemo rezultat.

Če države nismo našli, se zanka izteče. Vrnemo 0.

def statistika(podatki, drzava, dni):
    for vrstica in podatki.splitlines():
        kje, stevilke = vrstica.split(":")
        if kje == drzava:
            stevilke = [int(x) for x in stevilke.split(",")]
            return sum(stevilke[-dni:])
    return 0

4. Okuženi

Ana je bila okužena na dan 0. Na dan 6 je okužila Berto in Dani, na dan 12 pa Cilko. Berta ni okužila nikogar. Cilka je na dan 18 okužila Emo in na dan 30 Fanči. In tako naprej.

okuzbe = {"Ana": {"Berta": 6, "Cilka": 12, "Dani": 6},
          "Berta": {},
          "Cilka": {"Ema": 18, "Fanči": 30},
          "Dani": {"Greta": 9},
          "Ema": {"Helga": 24, "Iva": 36, "Jana": 27},
          "Fanči": {},
          "Greta": {"Klara": 12},
          "Helga": {},
          "Iva": {},
          "Jana": {},
          "Klara": {}}

Slediti želimo okužbam, ki izhajajo iz določene osebe. Napiši funkcijo okuzeni(dan, oseba, okuzbe), ki vrne množico oseb (vključno s podano osebo), ki so prek podane osebe okužene do (vključno) podanega dneva. Klic okuzeni(26, "Cilka", okuzbe) vrne {"Cilka", "Ema", "Helga"}; prek Cilke se okužita tudi Fanči in Jana, vendar šele po dnevu 26.

Rešitev

Običajno rekurzivno spuščanje po drevesu, čisto tako kot pri rodbini. Naloga je pravzaprav enaka nalogi, v kateri je potrebno vrniti množico vseh članov rodbine, le da se z vsakim ukvarjamo le, če je bil okužen pred določenim datumom.

Vsak doda na spisek sebe, med otroki pa pokliče le tiste, ki so bili okuženi "pravočasno".

def okuzeni(cas, okuzena, stiki):
    karantena = {okuzena}
    for oseba, kdaj in stiki[okuzena].items():
        if kdaj <= cas:
            karantena |= okuzeni(cas, oseba, stiki)
    return karantena

Ta rešitev predpostavlja, da je bila okuzena oseba okužena pravočasno. V resnici drugače ne more biti - in drugače ne moremo sprogramirati, saj podatka o tem, kdaj je bila okužena prva oseba (recimo Ana) niti nimamo.

Za tiste, ki jih takšne reči zanimajo, je tu še krajša rešitev, vendar uporablja funkcijo reduce, ki je na predavanjih nismo spoznali.

from functools import reduce

def okuzeni(cas, okuzena, stiki):
    return reduce(
        set.union,
        (okuzeni(cas, oseba, stiki)
         for oseba, kdaj in stiki[okuzena].items()
         if kdaj <= cas),
        {okuzena})

5. Sledilnik

Prva naloga je seveda naivna: pomemben je tudi čas aktivnosti in ne le aktivnost sama (kraj pa bomo zanemarili). Napiši razred Oseba, ki bo hranil aktivnosti določene osebe. Razred naj ima konstruktor brez argumentov in metode:

  • aktivnost(kaj, kdaj) zabeleži, da je oseba ob podanem času opravljala podano aktivnost;
  • vse_aktivnosti() vrne množico vseh aktivnosti, s katerimi se je ukvarjala oseba;
  • mozna_okuzba(druga_oseba) vrne True, če sta ta oseba in podana druga_oseba kdaj ob istem času opravljali isto aktivnost (npr. istočasno pili kavo), sicer pa False.

Iz razreda Oseba izpelji razred VarnaOseba, ki ima drugačen konstruktor in metodo mozna_okuzba. Konstruktor prejme množico aktivnosti, pri katerih podana oseba nosi masko. Metoda mozna_okuzba(druga_oseba) zdaj vrne True, če sta osebi kdaj ob istem času opravljala isto aktivnost, pri kateri druga_oseba (ki je prav tako objekt tipa VarnaOseba) ni nosila maske. Če jo je nosila ta oseba (self), to ne pomaga, ker maska ščiti druge in ne tistega, ki jo nosi.

Rešitev

Kot vedno v objektnem programiranju (pri Programiranju 1) se moramo odločiti le, kako bomo hranili podatke, pa je naloga že praktično rešena.

Tu bomo aktivnosti hranili kot množico parov (aktivnost, cas). Da ugotovimo, ali imata dve osebi kako skupno aktivnost ob istem času, tako le preverimo, ali je presek teh dveh množic neprazen.

class Oseba:
    def __init__(self):
        self.aktivnosti = set()

    def aktivnost(self, kaj, kdaj):
        self.aktivnosti.add((kaj, kdaj))

    def mozna_okuzba(self, druga_oseba):
        return self.aktivnosti & druga_oseba.aktivnosti) != set()

    def vse_aktivnosti(self):
        return {kaj for kaj, _ in self.aktivnosti}

V razredu VarnaOseba bo konstruktor shranil množico aktivnosti, pri katerih je oseba maskirana. Metoda mozna_okuzba tedaj preveri, ali obstaja kaka aktivnost iz preseka, pri kateri druga oseba ni nosila maske.

class VarnaOseba(Oseba):
    def __init__(self, maskirana):
        super().__init__()
        self.maskirana = maskirana

    def mozna_okuzba(self, druga_oseba):
        return any(aktivnost[0] not in druga_oseba.maskirana
                   for aktivnost in self.aktivnosti & oseba.aktivnosti)