Rešitev s komentarji

Zakladi

Neusmiljeni gusarji so se ves teden vozili po morju in na mimoidočih ladjah kradli toaletni papir. Potem so šli na nek otok, zakopali papir na različne lokacije in zdaj je potrebno sestaviti navodila za iskanje – saj poznate, dva koraka desno (kar zapišemo z ">2"), tri korake gor ("^3") in tako naprej. Začnemo na koordinatah (0, 0). Možne smeri so <, >, ^ in v.

Napiši funkcijo zakladi(koordinate), ki prejme seznam koordinat zakladov in vrne niz s potjo, ki gre po vrsti prek njih. Vsakič najprej povemo število korakov v vodoravni, nato v navpični smeri. Kadar je število korakov v kako smer enako 0, jih izpustimo. Klic zakladi([(2, 3), (4, 3), (-2, -1), (2, -4), (2, -1), (-2, 3)]) (to so koordinate zakladov na sliki), vrne ">2 ^3 >2 <6 v4 >4 v3 ^3 <4 ^4".

Rešitev

Rešitev bi bila lahko, recimo

def zakladi(koordinate):
    x = y = 0
    pot = []
    for xz, yz in koordinate:
        if xz > x:
            pot.append(f">{xz - x}")
        elif xz < x:
            pot.append(f"<{x - xz}")
        if yz > y:
            pot.append(f"^{yz - y}")
        elif yz < y:
            pot.append(f"v{y - yz}")
        x, y = xz, yz
    return " ".join(pot)

V pogojih if xz > x in potem elif x < xz ne morem zamenjati elif-a z else, saj je pomembno, da izključimo tretjo možnost, namreč x == xz. Seveda pa bi lahko namesto elif pisali kar if.

Če ne znamo oblikovati nizov z f"...", lahko seveda pišemo tudi pot.append(">" + str(xz - x)).

Vse nize zložimo v seznam in ga na koncu zlepimo z " ".join(pot). Namesto tega bi ga lahko lepili kar sproti, tako da bi imeli niz pot, ki bi bila v začetku prazna, pot = "", potem pa bi vanj dodajali korake z, recimo, pot += f">{xz - x} ". Ne spreglejte presledka na koncu niza - potreben je, da ne zbijemo nizov skupaj. Seveda pa bomo potem imeli na koncu odvečni presledek. Zato moramo return pot spremeniti v return pot[:-1] ali return pot.strip().

Mnogi ste se pozabili premakniti na novo lokacijo. Ko naredimo pet korakov desno in tri gor, smo prišli pet korakov desno in tri gor. Zato je pomembno, da imamo na koncu zanka x, y = xz, yz.

Hoarding

Pridejo časi, ko hodimo v štacuno manjkrat in takrat je dobro splanirati, kaj kupiti. Imamo recepte, pravzaprav spiske sestavin. V takšni obliki.

        recepti = {
            "Palačinke": {("Jajca", 4), ("Mleko", 1), ("Moka", 0.25)},
            "Kruh": {("Moka", 1), ("Kvas", 1)},
            "Pohani zrezki": {("Zrezek", 4), ("Jajca", 1)},
            "Mlečni riž": {("Riž", 0.125), ("Mleko", 0.5)},
        }

Recimo, da se odločimo, da bomo trikrat jedli palačinke in dvakrat mlečni riž, se pravi

        jedilnik = {("Palačinke", 3), ("Mlečni riž", 2)}

Napiši funkcijo spisek(jedilnik, recepti), ki prejme jedilnik in recepte v gornji obliki, vrne pa množico sestavin in količin, ki jih je potrebno kupiti. Če sta recepti in jedilnik takšna, kot smo določili zgoraj, klic funkcije vrne {("Jajca", 12), ("Mleko", 4), ("Moka", 0.75), ("Riž", 0.25)}. Jajc, recimo, potrebujemo 12 (palačinke delamo trikrat in vsakič porabimo štiri jajca), mleka pa potrebujemo štiri litre, namreč trikrat en liter za palačinke in še dvakrat po pol za mlečni riž. Poleg tega pa seveda še ustrezne količine moke in riža. Rešitev mora biti seveda takšna, da bi delovala tudi pri drugih receptih, ne le teh iz testov.

Rešitev

Bistvo te naloge je, da odkrijete, da se splača spisek sestavljati v slovar, ki ga potem šele na koncu spremenimo v množico. Zato v nalogi sami nisem nikjer uporabil slovarja -- da ne bi dobili preveč direktnega namiga.

def spisek(jedilnik, recepti):
    kupiti = collections.defaultdict(float)
    for hrana, kolikokrat in jedilnik:
        for sestavina, kolicina in recepti[hrana]:
            kupiti[sestavina] += kolicina * kolikokrat
    return set(kupiti.items())

Spisek je collections.defaultdict(float) in ne običajen dict. Na ta način se nam ni treba hecati z dodajanjem novih elementov, temveč lahko preprosto prištevamo. Sicer pa je naloga preprosta: za vsako hrano in število obrokov te hrane gremo čez vse sestavine in njihove količine, ter jih prištevamo k spisku.

Na koncu potrebujemo množico parov (sestavina, količina). Takšne pare dobimo s kupiti.items(), le v množico jih morajo pretvoriti. Zato set(kupiti.items()). Če se niste spomnili tega in ste to pretvorbo naredili z zanko, nisem zameril. To je pač bolj Pythonov trik. Recimo.

Pač pa sem bil bolj žalosten, če ste namesto, da bi do sestavin in količin prišli z recepti[hrana], pisali tole

    for hrana, kolikokrat in jedilnik:
        for jed, sestavine in recepti.items():
            if jed == hrana:
                for sestavina, kolicina in sestavine:
                    kupiti[sestavina] += kolicina * kolikokrat

To je veliko bolj žalostna napaka, ker pove, da ne razumete bistva slovarjev -- ki je prav v tem, da po njem ni potrebno iskati (kar počne for jed, sestavine in recepti.items():), temveč lahko do iskanega elementa pridemo z indeksiranjem (recepti[hrana]).

Športne aktivnosti

Robin je živel na robu občine, gozd, po katerem je imel navado trenirati tek in beg, pa je bil onstran občinske meje. Da ne bi plačeval kazni, je ostal doma in se uril v lokostrelstvu. Na lesen plot je s kredo narisal daljico in s precejšnje razdalje izmenično streljal v eno in drugo krajišče daljice. Za evidenco je v datoteko zabeležil koordinate strelov, recimo tako:

10.12 2.7
3.14 42
10.18 2.95
2.99 41.872
9.55 2.75
3.085 42.4
9.18 2.72
3.123 41.8

Ponoči je dež spral s kredo narisano daljico. Nas pa vseeno zanima: kako dolga je bila daljica?

Napiši funkcijo streli(ime_datoteke), ki prejme ime datoteke s koordinatami strelov in vrne ocenjene dolžino daljice. Predpostavimo lahko, da je bila x (oz. y) koordinata posamičnega oglišča približno enaka poprečju x-koordinat strelov v to oglišče. Tako je koordinata x prvega oglišča v gornjem primeru enaka poprečju števil 10.12, 10.18, 9.55 in 9.18, koordinata x drugega oglišča pa poprečju števil 3.14, 2.99, 3.085 in 3.123. Za y koordinate pa vzamemo druga števila v vrstici.

Rešitev

Po pričakovanjih je bilo tu najtežje ločiti med sodimi in lihimi vrsticami. Ena možnost je, da to počnemo sproti, ob branju

from math import sqrt

def streli(ime_datoteke):
    x = [0, 0]
    y = [0, 0]
    for i, vrstica in enumerate(open(ime_datoteke)):
        tx, ty = vrstica.split()
        tx = float(tx)
        ty = float(ty)
        x[i % 2] += tx
        y[i % 2] += ty
    return sqrt((x[0] - x[1]) ** 2 + (y[0] - y[1]) ** 2)

Seznam x tule vsebuje dve števili, ki ustrezata dvema krajiščema daljice. i je števila vrstice (ker z enumerate oštevilčimo vrstice datoteke). Potem je i % 2 bodisi 0 bodisi 1, torej eno ali drugo krajišče.

Če se ne spomnimo trika z indeksom, lahko pišemo tudi

def streli(ime_datoteke):
    x0 = x1 = 0
    y0 = y1 = 0
    for i, vrstica in enumerate(open(ime_datoteke)):
        tx, ty = vrstica.split()
        tx = float(tx)
        ty = float(ty)
        if i % 2 == 0:
            x0 += tx
            y0 += ty
        else:
            x1 += tx
            y1 += ty
    return sqrt((x0 - x1) ** 2 + (y0 - y1) ** 2)

Program je malo daljši, najbrž pa celo malo preglednejši. Tudi zato, ker v return-u ni več indeksov. Predvsem pa se v teh if-ih bolj jasno vidi, kaj se dogaja.

Če se ne spomnimo enumerate, bomo pisali

    i = 0
    for vrstica in open(ime_datoteke):
        ...
        i += 0

Ni tako elegantno, nič pa ni narobe.

Drugačna rešitev je, da vse skupaj preberemo v seznam.

def streli(ime_datoteke):
    xs = []
    ys = []
    for vrstica in open(ime_datoteke):
        x, y = vrstica.split()
        xs.append(float(x))
        ys.append(float(y))

    n = len(xs) // 2
    x0, x1 = sum(xs[::2]) / n, sum(xs[1::2]) / n
    y0, y1 = sum(ys[::2]) / n, sum(ys[1::2]) / n
    return sqrt((x0 - x1) ** 2 + (y0 - y1) ** 2)

Z xs[::2] dobimo vse elemente seznama na sodih indeksih in z xs[1::2] vse elemente na lihih.

PeF pa prazna

Recimo, da ima PeF tri stavbe. Prva je prazna. V drugi sta dve prazni sobi. V tretji pa so štiri sobe. V prvi so tri prazne mize, v drugi ena miza, na kateri je prazen zvezek, preostali sobi pa sta prazni.

V Pythonu bi to predstavili tako: [ [ ], [ [ ], [ ] ], [ [[], [], []], [[[]]], [ ], [ ] ] ]

Koliko praznih stvari imamo? Devet. 1 prazna stavba, 2 prazni sobi, 3 prazne mize, 1 prazen zvezek in še 2 prazni sobi. Napiši funkcijo praznih(s), ki prejme takšen trapast seznam in vrne število praznih seznamov (ki so lahko znotraj seznamov znotraj seznamov in tako naprej). Klic praznih([[], [[], []], [[[], [], []], [[[]]], [], []]]) torej vrne 9.

Razmisli tole: klic praznih([]) vrne 1, ker je prazna samo ena stvar (namreč svet :). Sicer pa imamo seznam. In ta vsebuje toliko praznih reči, kolikor praznih reči vsebujejo njegovi elementi. Zdaj sem pa že vse povedal. :)

Rešitev

Ni kaj: če je seznam prazen, vrnemo 1. Sicer pa ta ni prazen, pač pa seštejamo število praznih v vseh podseznamih.

def praznih(s):
    if not s:
        return 1
    p = 0
    for e in s:
        p += praznih(e)
    return p

Nekateri ste tule poskušali početi nekaj s s[0] in s[1:]. Ne, ta rekurzija ni takšnega tipa. Na predavanjih smo imeli tisto, ko smo šli z rekurzijo po seznamu, in tam je bilo res stalno nekaj v slogu s[0] in s[1:]. Tale naloga pa je bolj podobna tistim, rodbinskim. V bistvu je tako tako, kot da bi poskusili prešteti, koliko oseb v rodbini nima otrok.

Kdor je pisal s[0] in s[1:] kaže tendenco, da poskuša naloge iz rekurzije reševati po nekem vzorcu. Da v bistvu razmišlja "aha, po katerem receptu gre tole?" To gre ... do nekje. Včasih pa ni tako očitno, tako da je boljše, da znate rešiti iz nule, z lastnim razmislekom in ne z iskanjem vzorcev.

Sledilnik

Napiši razred Sledilnik z metodami zbolel(drzava) in ozdravel(drzava), s katerimi povemo, da je v tej državi zbolel oz. ozdravel en študent. Poleg tega ima metodi zbolelih(drzava) in ozdravelih(drzava), ki vrnejo skupno število vseh zbolelih in ozdravelih v podani državi. Poleg tega pa še metodo bolnih(drzava), ki vrne število vseh, ki so zboleli, a še niso ozdraveli.

Postorivši vse to, dodaj še metodo doloci_kontinent(drzava, kontinent), s katero povemo, da je podana država na podanem kontinentu (razred pa si to na nek način zapomni). Potem spremeni metode zbolelih(drzava), ozdravelih(drzava) in bolnih(drzava) tako, da bomo lahko namesto države podatli kontinent in dobili število zbolelih, ozdravelih ali bolnih na podanem kontinentu.

V testih piše (med drugim) to:

        s = Sledilnik()
        s.zbolel("Kitajska")
        s.zbolel("Kitajska")
        s.zbolel("Kitajska")
        s.zbolel("Italija")
        s.zbolel("Slovenija")
        s.zbolel("Kitajska")
        s.zbolel("Italija")
        s.zbolel("Kr ena ladja")

        s.doloci_kontinent("Italija", "Evropa")
        s.doloci_kontinent("Slovenija", "Evropa")
        s.doloci_kontinent("Kitajska", "Azija")

        s.ozdravel("Kitajska")
        s.ozdravel("Kitajska")
        s.ozdravel("Italija")

        self.assertEqual(s.zbolelih("Kitajska"), 4)
        self.assertEqual(s.ozdravelih("Kitajska"), 2)
        self.assertEqual(s.bolnih("Kitajska"), 2)

        self.assertEqual(s.zbolelih("Paragvaj"), 0)

        self.assertEqual(s.zbolelih("Evropa"), 3)
        self.assertEqual(s.ozdravelih("Evropa"), 1)
        self.assertEqual(s.bolnih("Evropa"), 2)

        self.assertEqual(s.zbolelih("Azija"), 4)
        self.assertEqual(s.ozdravelih("Azija"), 2))
        self.assertEqual(s.bolnih("Azija"), 2)

Rešitev

Bistvo je, kot navadno, v tem, da vemo, kako shraniti podatke. Potrebovali bomo tri slovarje: število zbolelih po državah, število ozdravelih po državah in množico držav na kontinentu. Te slovarje primerno nastavimo v konstruktorju. Spet bomo uporabljali defaultdict, da se ne zafrkavamo z dodajanjem elementov.

class Sledilnik:
    def __init__(self):
        self.zboleli = collections.defaultdict(int)
        self.ozdraveli = collections.defaultdict(int)
        self.kontinenti = collections.defaultdict(set)

    def doloci_kontinent(self, drzava, kontinent):
        self.kontinenti[kontinent].add(drzava)

    def zbolel(self, drzava):
        self.zboleli[drzava] += 1

    def ozdravel(self, drzava):
        self.ozdraveli[drzava] += 1

    def zbolelih(self, regija):
        if regija in self.kontinenti:
            return sum(self.zboleli[drzava] for drzava in self.kontinenti[regija])
        else:
            return self.zboleli[regija]

    def ozdravelih(self, regija):
        if regija in self.kontinenti:
            return sum(self.ozdraveli[drzava] for drzava in self.kontinenti[regija])
        else:
            return self.ozdraveli[regija]

    def bolnih(self, drzava):
        return self.zbolelih(drzava) - self.ozdravelih(drzava)

Metoda doloci_kontinent le doda državo med države podanega kontinenta.

Metodi zbolel in ozdravel povečata število bolnih in ozdravelih v podani državi.

Metoda zbolelih preveri, ali gre za kontinent. Če je tako, vrne vsoto zbolelih po vseh državah na tem kontinentu. Sicer vrne število zbolelih. Če v državi ni zbolel nihče, bo defaultdict prijazno vrnil 0.

Metoda ozdravelih je podobobna.

Metoda bolnih pa odšteje ozdravele od zbolelih. Na ta način se izognemo temu, da bi morali še enkrat razlikovati med državami in kontinenti -- s tem, ali gre za eno ali drugo, se bosta ukvarjali zbolelih in ozdravelih.

Metodo zbolelih je mogoče skrajšati s pomočjo trika (enako pa seveda tudi ozdravelih).

    def zbolelih(self, regija):
        return sum(self.zboleli[drzava] for drzava in self.kontinenti.get(regija, [regija]))

self.kontinenti(regija, [regija]) bo vrnil države kontinenta, če gre za kontinent. Če pa ne gre za kontinent temveč državo, bo get kot privzeto vrednost vrnil seznam, ki vsebuje le to državo. Zanka for bo potem torej šla bodisi čez države tega kontinenta bodisi čez podano državo.