Vrhovi valov

Naloga predstavlja nadaljevanje prve naloge s prejšnjega izpita (glej rešitve).

Epidemije prihajajo v valovih. V neki državi se je število okuženih po dnevih spreminjalo tako:

okuzbe = [1, 6, 5, 0, 0, 0, 2, 8, 5, 3, 0, 5, 8, 0, 0, 0, 5, 1, 1]

Tule vidimo štiri valove. Zanimajo nas vrhunci valov. V prvem valu je to drugi dan od treh (2, 3), v drugem prvi od štirih (1, 4), v tretjem drugi od dveh (2, 2), v četrtem prvi od treh (1, 3). Od obeh števil odštejemo 1 in ju delimo: tako izvemo, da so vrhovi ob [1 / 2, 1 / 3, 1 / 1, 0 / 3]. Tako odštevanje lepše opiše, kje se nahaja vrh: to se najlepše vidi v prvem valu, ko je vrh na polovici.

Če je val dolg 1, je vrh na položaju 0.

Na začetku in koncu seznama je lahko še poljubno število ničel. Med dvema valovoma je vsaj ena ničla.

Napiši funkcijo vrhovi(okuzbe), ki za podani seznam dnevnih okužb vrne položaje vrhov valov. Klic vrhovi([1, 6, 5, 0, 0, 0, 2, 8, 5, 3, 0, 5, 8, 0, 0, 0, 5, 1, 1]) torej vrne [0.5, 0.333, 1, 0].

Rešitev

Tu so bili v rahli prednosti študenti, ki so si že prej ogledali rešitve prejšnjega izpita. Logika funkcije je namreč enake, tako da jo lahko kar hitro predelamo - a le, če jo razumemo. Če ne, pa ne. :)

def vrhovi(s):
    v_valovih = []
    dan = -1
    naj = 0
    # Spredaj in zadaj dodamo 0, da se ni potrebno ukvarjati z začetkom in koncem
    for x in [0] + s + [0]:
        if x > 0:  # Val se nadaljuje
            # Pogledamo, ali je število višje od najvišjega in v tem primeru
            # zabeležimo število okuženih in dan
            if x > naj:
                naj = x
                najdan = dan
            dan += 1
        else:  # Vala je konec
            if naj > 0:  # Če ni bil prazen...
                if dan > 1: 
                    v_valovih.append(najdan / (dan - 1))
                else:  # Poseben primer, ko se je potrebno izogniti deljenju z 0
                    v_valovih.append(0)
            naj = 0
            najdan = 0
            dan = 0
    return v_valovih

vrhovi(okuzbe)
[0.5, 0.3333333333333333, 1.0, 0.0]

Nekaterih - mogoče celo vsi, ki so se naloge lotili in jo uspešno rešili - so raje nabrali cel val v seznam ter nato poiskali indeks maksimalnega elementa ter ga delili z dolžino seznama. Seveda gre tudi tako.

Najpodobnejši

Seve virusov primerjajo glede na markerje. Recimo, da bomo uporabljali naslednje markerje (vendar naj vaša rešitev deluje za poljuben nabor markerjev, ne le te, ki so v testih!)

markerji = {"ATTA", "GGT", "TTG", "TCCCTC"}

V genskem materialu vzorca virusa je vsak od teh markerjev prisoten ali pa ne. (Ali je prisoten enkrat ali večkrat, ne igra vloge). Podobnost sevov opazujemo glede na to, v koliko markerjih se ujemata.

Vzemimo, recimo

        markerji =                         {"ATTA", "GGT", "TTG", "TCCCTC"}
        vzorec = "GCGCATTAGCGGTCCCTCAAAGGT"  #  1     1      0       1
        sev4 = "ATTAATTAATTAATTA"            #  1     0      0       0   => 2

Njuno ujemanje je 2: oba vsebujeta ATTA in oba ne vsebujeta TTG. (Glede preostalih dveh markerjev pa se razlikujeta.)

Napiši funkcijo najpodobnejsi(vzorec, sevi, markerji), ki prejme nek vzorec, množico znanih sevov in množico markerjev. Vrniti mora tistega izmed znanih sevov, ki je najbolj podoben vzorcu. Če je enako podobnih več, naj vrne poljubnega izmed njih.

V testih je naštetih več sevov, v komentarjih pa so na enak način kot v gornjem primeru zapisane podobnosti.

Rešitev

Tu je bilo zelo zanimivo - morda bi moral napisati tudi nekoliko žalostno opazovati izdelke študentov. Pravilna rešitev gre prek vseh sevov in poišče tistega, ki se po markerjih najbolj ujema z vzorcem, torej

...
for sev in sevi:
    for marker in markerji:
        ...

Namesto tega so mnogi, morda celo večina, pisali

...
for marker in markerji:
    for sev in sevi:
        ...

Tako se stvar zelo zaplete; tisti, ki so uspeli priti po tej poti do cilja, so se iz jame, ki so si jo skopali, izvlekli s slovarji. Če zanki razporedimo pravilno, pa je rešitev preprosta.

def najpodobnejsi(vzorec, sevi, markerji):
    naj_podobnost = -1
    naj_sev = 0
    for sev in sevi:
        podobnost = 0
        for marker in markerji:
            if (marker in vzorec) == (marker in sev):
                podobnost += 1
        if podobnost > naj_podobnost:
            naj_podobnost = podobnost
            naj_sev = sev
    return naj_sev

Pogoj, ki preverja, ali oba vsebujeta ali ne vsebujeta markerja, je eleganten: to ali drži marker in vzorec mora biti enako temu, ali drži marker in sev. Oboje True ali oboje False. Brez tega bi pisali (in večina študentov tudi je pisala) (marker in vzorec and marker in sev) or (marker not in vzorec and marker not in sev), ali pa je napisala celo dva if-a. Bolj žalostno, in tudi nedelujoče, pa je pisati marker in sev and vzorec. To deluje v angleščini, v Pythonu pa ne.

        podobnost = 0
        for marker in markerji:
            if (marker in vzorec) == (marker in sev):
                podobnost += 1

lahko nadomestimo z

        podobnost = sum((marker in vzorec) == (marker in sev) for marker in markerji)

Odtod hitro pridemo do

def najpodobnejsi(vzorec, sevi, markerji):
    return max(sevi,
               key=lambda sev: sum((marker in sev) == (marker in vzorec)
                                   for marker in markerji))

Stanje regij

V datoteki obcine.txt je seznam občin s številom prebivalcev in regijo, ki ji občina pripada. Podatki so ločeni z vejicami.

Moravče, 5354, Osrednjeslovenska
Ljubljana, 288832, Osrednjeslovenska
Koper, 51828, Primorska
Kočevje ob gozdu, 16549, Južnoslovenska
Piran, 17613, Primorska
Kamnik, 13768, Osrednjeslovenska

V datoteki okuzbe.txt je dnevno število okužb po občinah, v takšni obliki:

Kamnik: 80
Kočevje ob gozdu: 50
Ljubljana: 90

Vse občine iz druge datoteke se pojavijo tudi v prvi. Obratno ni nujno: če nekje ni novih okužb, te občine v drugi datoteki ni.

Napiši funkcijo stanje_regij(), ki prebere tidve datoteki in vrne slovar, katerega ključi so vse regije, ki se pojavijo v prvi datoteki, pripadajoča vrednost pa je delež okuženih. V gornjem primeru ključu "Osrednjeslovenska" pripada vrednost (80 + 90) / (5354 + 288832 + 13768) (število okuženih v občinah iz te regije, deljeno s število prebivalcev v vseh občinah te regije). Ključu "Primorska" pa 0, ker v primorskih občinah ni bilo okužb.

(Datoteke niso priložene, ker se sestavijo kar znotraj testov.)

Rešitev

Naloga združuje dve veščini: branje datotek in uporabo slovarjev. Sicer pa je precej rutinska.

from collections import defaultdict

def stanje_regij():
    regije = {}
    populacija = defaultdict(int)
    for vrstica in open("obcine.txt"):
        ime, prebivalcev, regija = vrstica.strip().split(", ")
        regije[ime] = regija
        populacija[regija] += int(prebivalcev)

    okuzenost = dict.fromkeys(populacija, 0)
    for vrstica in open("okuzbe.txt"):
        obcina, okuzenih = vrstica.split(":")
        okuzenost[regije[obcina]] += int(okuzenih)

    for regija in okuzenost:
        okuzenost[regija] /= populacija[regija]

    return okuzenost

Komentarja je vreden klic dict.fromkeys(populacija, 0). Ta sestavi slovar, katerega ključi so iz seznama/terke/ključev slovarja/niza/...česarkoli populacija, vse vrednosti pa so 0. Če te funkcije ne poznamo, takšen slovar pač sestavimo z

okuzenost = {}
for regija in populacija:
    okuzenost[regija] = 0

Tipična napaka, ki so jo nekateri delali pri reševanju, je, da so delili število okuženih v regiji s skupnim številom prebivalcev občin, ki so imele vsaj eno okužbo, namesto s populacijo regije. Tega nisem kaznoval preveč strogo, kaznovati pa sem vendarle moral. Če ne bi imeli testov, bi lahko rekli, da niste dovolj natančno brali navodil; glede na to, da so testi povedali, da je nekaj narobe, pa bi morali odkriti, v čem je problem.

Položaj vrha

Variacija na prvo nalogo. Tokrat imamo le seznam za en val. Zanima nas, na kateri dan je bilo največ okužb in koliko.

Napiši rekurzivno funkcijo argmax(s), ki za podani neprazni seznam vrne indeks in vrednost največjega elementa. Klic argmax([5, 4, 7, 8, 5, 1]) vrne (3, 8), ker se največji element, 8, pojavi na indeksu 3. Če je največjih elementov več, vrne indeks prvega od njih.

Funkcija mora biti "prava rekurzivna funkcija": razen sebe naj ne kliče drugih funkcij, razen len, poleg tega naj ne vsebuje zank.

Rešitev

Če ima seznam le en element, se največji element nahaja na indeksu 0, in sicer je to kar ničti element.

Sicer poizvemo, kje se nahaja in kakšen je največji element ostanka. Če je večji od prvega, vrnemo le-tega, a z 1 večjim indeksom (ker je potrebno upoštevati še prvi element). Če je prvi element večji, pa je največji, očitno, prvi element.

def argmax(s):
    if len(s) == 1:
        return 0, s[0]
    naj_idx, naj = argmax(s[1:])
    if naj > s[0]:
        return naj_idx + 1, naj
    else:
        return 0, s[0]

argmax([5, 4, 7, 8, 5, 1])
(3, 8)

Sledilnik

Napiši razred Sledilnik, ki ima

Poleg tega naj ima atribute

Razen teh naj razred nima nobenih drugih atributov.

Poleg tega napiši razred Sledilnik2, ki je izpeljan iz razreda Sledilnik in doda še atribut

Sledilnik2 naj smiselno uporabi oz. spreminja podedovane metode in doda čim manj kode.

Recimo, da izvedemo naslednji program.

s = Sledilnik2()
s.nov_dan(10)
s.nov_dan(15)
s.nov_dan(0)
s.nov_dan(0)
s.nov_dan(0)
s.nov_dan(0)
s.nov_dan(2)
s.nov_dan(0)
s.nov_dan(0)

Po tem je s.naj_dnevnih enak 15, s.tekoce_brez_okuzb je 2, s.naj_brez_okuzb je 4. Ker gre za Sledilnik2, je s.skupno_okuzb enak 27.

Če bi program nadaljevali z

s.nov_dan(3)

je s.naj_dnevnih še vedno 15, s.tekoce_brez_okuzb je 0, s.naj_brez_okuzb je še vedno 4 in s.skupno_okuzb enak 30.

Rešitev

class Sledilnik:
    def __init__(self):
        self.naj_dnevnih = 0
        self.naj_brez_okuzb = 0
        self.tekoce_brez_okuzb = 0

    def nov_dan(self, okuzenih):
        if okuzenih > 0:
            self.tekoce_brez_okuzb = 0
            if okuzenih > self.naj_dnevnih:
                self.naj_dnevnih = okuzenih
        else:
            self.tekoce_brez_okuzb += 1
            if self.tekoce_brez_okuzb > self.naj_brez_okuzb:
                self.naj_brez_okuzb = self.tekoce_brez_okuzb

V konstruktorju nastavimo tri atribute na ustrezne začetne vrednosti.

V nov_dan nas zanima, ali kdo okužen. Če je tako, je tekoče število dni brez okužb enako 0, poleg tega pa preverimo, ali gre morda celo za dnevni rekord.

Če okuženih ni, povečamo tekoče število dni brez okužb, potem pa preverimo, ali je to slučajno rekord števila dni brez okužb.

Drugi del naloge je preverjal, ali znate iz tega razreda izpeljati preprost razred in pravilno klicati podedovane metode.

class Sledilnik2(Sledilnik):
    def __init__(self):
        super().__init__()
        self.skupno_okuzenih = 0

    def nov_dan(self, okuzenih):
        super().nov_dan(okuzenih)
        self.skupno_okuzenih += okuzenih