Ker so bile naloge iz obeh terminov postavljene vzporedno -- bodisi z enako zgodbo, bodisi z različno zgodbo, a v bistvu enako nalogo -- tudi rešitve objavljam kar prepleteno.

Darila

Nekateri ljudje podarijo čokolade naprej, drugi jih pojejo. Če imamo seznam [(8, 2), (1, 8), (5, 1), (4, 42)], to pomeni, da oseba 8 daje čokolade osebi 2, oseba 1 osebi 8 in tako naprej.

Izpit ob 12.00: Napiši funkcijo dolzina_poti(s, o), ki prejme tak seznam in številko osebe, ki ji damo čokolado, ter vrne število podaj, preden bo čokolada pojedena. Klic dolzina_poti([(8, 2), (1, 8), (5, 1), (4, 42)], 5) vrne 3. Če namreč damo čokolado osebi 5, jo bo ta dala osebi 1, oseba 1 osebi 8 in oseba 8 osebi 2, ki jo poje. Torej tri podaje.

Izpit ob 14.30: Napiši funkcijo ne_daje_naprej(s), ki prejme takšen seznam in vrne množico številk oseb, ki čokolad ne dajejo naprej. V gornjem primeru je to {2, 5}.

Seznam lahko tudi zelo dolg; morda se ga splača znotraj funkcije pretvoriti v kaj prikladnejšega za to nalogo.

Rešitev

Naloga je izpolnjevala obljubo s predavanj, da bom nekoč dal nalogo, ki bo zahtevala, da pravilno uporabljate slovar. Tu moramo v obeh nalogah iskati, komu bo dala čokolado oseba z določeno številko. Če to počnemo brez slovarja, s seznamom parov

    for kdo, komu in pari:
        if kdo == iscemo:
            break

ali pa naredimo slovar, vendar ga uporabljamo, kot da bi bil seznam parov

    slovar_parov = dict(pari)
    for kdo, komu in slovar_parov.items():
        if kdo == iscemo:
            break

ne pridemo nikamor. Parov v testih je 100.000. Če 100.000-krat iščemo, komu nekdo da čokolado, se bo zanka obrnila 100.000 * 100000 / 2 = 5.000.000.000-krat.

Da lahko rešimo nalogo, se moramo torej spomniti, da obstajajo za take namene slovarji.

Funkcija dolzina_poti je lahko, recimo, takšna

def dolzina_poti(pari, x):
    pari = dict(pari)
    length = 0
    while x in pari:
        length += 1
        x = pari[x]
    return length

Bistvo je, da seznam parov pretvorimo v slovar. Če dict-u podamo seznam parov, jih uporabi kot ključe in vrednosti, torej pari = dict(pari). Potem čokoladi sledimo z

    while x in pari:
        x = pari[x]

K temu le še dodamo štetje, pa pridemo do gornje rešitve.

Če hočemo, lahko Python šteje namesto nas. Podaj bo kvečjemu toliko kot je parov, pa še 1 prištejemo, da v tem primeru ne preskočimo return-a.

def dolzina_poti(pari, x):
    pari = dict(pari)
    for i in range(len(pari) + 1):
        if x in pari:
            x = pari[x]
        else:
            return i

Funkcijo ne_daje_naprej najlažje sprogramiramo z množicami: sestavimo množico vseh, ki lahko dobijo čokolado in množico vseh, ki jo dajo. Funkcija vrne razliko teh množic.

def ne_daje_naprej(pari):
    dobi = set()
    daje = set()
    for kdo, komu in pari:
        dobi.add(komu)
        daje.add(kdo)
    return dobi - daje

Če se spomnimo na izpeljane množice, gre hitreje.

def ne_daje_naprej(pari):
    return {x for _, x in pari} - {x for x, _ in pari}

Do zanimive rešitve pridemo, če, tako kot v prejšnji nalogi, pretvorimo seznam v slovar. Potem moramo od množice vrednosti odšteti množico ključev.

def ne_daje_naprej(pari):
    pari = dict(pari)
    return set(pari.values()) - set(pari)

Filtriranje (ob 14.30)

Napiši funkcijo ne_3_po_2(s), ki prejme seznam števil in iz njega odstrani vsa tista števila, ki sledijo sodim številom in so deljiva s 3. Funkcija naj spremeni podani seznam in ne vrne ničesar.

Seznam [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] tako spremeni v [1, 2, 4, 5, 6, 7, 8, 10]. Seznam [5, 3, 1, 2, 6, 9, 8] spremeni v [5, 3, 1, 2, 9, 8]; funkcija odstrani šestico za dvojko, pri čemer se ne ozira na to, da je za dvojko zdaj devetka, ki je prav tako deljiva s 3.

Rešitev

Naloga je bila podobna nalogi Nikoli brez Jožeta, le da je s seznamom počela nekaj drugega. Poleg tega je izpolnjevala mojo obljubo, da bom poskrbel, da vas bo nekoč teplo, če boste uporabljali remove.

Rešitev je kolikor hočemo, skoraj vsem pa je skupno, da bomo sestavili nov seznam in elemente starega povozili z novim, tako da bomo prirejali rezini x[:].

Lahko gremo prek enumerate(s), tako da imamo vrednost in indeks elementa. Slednjega potrebujemo, da preverjamo prejšnji element. Trenutni element prepišemo v novi seznam, če gre za prvi element (i == 0) ali pa trenutni element ni deljiv s 3 (e % 3; spomnimo se, da so ne-ničelne vrednosti resnične, nič pa je neresnična) ali pa predhodni element ni deljiv z 2 (s[i - 1] % 2).

def ne_3_po_2(s):
    n = []
    for i, e in enumerate(s):
        if i == 0 or e % 3 or s[i - 1] % 2:
            n.append(e)
    s[:] = n

Če nočemo indeksov, si lahko zapomnimo prejšnji element.

def ne_3_po_2(s):
    prej = 1
    n = []
    for e in s:
        if e % 3 or prej % 2:
            n.append(e)
        prej = e
    s[:] = n

V začetku se delamo, da je bil prejšnji element enak 1. Ker je lih, bomo tako gotovo vzeli prvi element.

Vse to so bolj C-jevske rešitve. Prava, Pythonovska, je zip.

def ne_3_po_2(s):
    n = s[:1]
    for prej, e in zip(s, s[1:]):
        if e % 3 or prej % 2:
            n.append(e)
    s[:] = n

V novi seznam najprej damo prvih 1 elementov iz podanega seznama. Če bi napisali n = [s[0]] bi to skoraj delovalo - razen, ko bi bil s prazen. Če zahtevamo prvih 1 elementov in je s prazen, pa dobimo prazen seznam. Odtod naprej pa nič posebnega, le običajen trik, s katerim z zip-om dobimo zaporedne elemente, ki smo ga videli ničkolikokrat (glej, recimo, rešitev domače naloge s hrčkom).

To nas pripelje do kratke rešitve z izpeljanimi seznami.

def ne_3_po_2(s):
    s[:] = s[:1] + [b for a, b in zip(s, s[1:]) if b % 3 or a % 2]

Zdaj pa tisto, kar ne deluje: remove. Če bi naivno napisali

def ne_3_po_2(s):
    for prej, e in zip(s, s[1:]):
        s.remove(e)

to ne bi delovalo, ker se lahko isti element pojavi na več mestih, remove pa bo vedno pobrisal prvo pojavitev, čeprav bi moral morda drugo. No, pravzaprav to ne deluje že iz drugega razloga, ki ste ga prav tako velikokrat slišali na predavanjih: nikoli ne smemo z zanko for prek seznama, iz katerega medtem brišemo elemente.

Plus - minus - plus (ob 12.00)

Napiši funkcijo alterniraj(s), ki prejme seznam števil in ga spremeni tako, da za vsakim pozitivnim številom odstrani vsa števila do naslednjega negativnega števila, in za vsakim negativnim vsa števila do naslednjega pozitivnega. Funkcija naj spremeni podani seznam in ne vrne ničesar.

Z drugimi besedami, funkcija obdrži prvi element vsakega zaporedja pozitivnih ali negativnih števil.

Seznam [3, 4, -1, 1, -5, -2, -1, 7, -8] tako spremeni v [3, -1, 1, -5, 7, -8].

Rešitev

Spet imamo kup rešitev, kot pri nalogi Filtriranje. Tudi če vas zanimajo predvsem rešitve izpita ob 12.00, si preberite kar tisto, saj vse teče enako. Tule je rešitev na enega od gornjih načinov.

def alterniraj(x):
    n = []
    for e in x:
        if not n or e * n[-1] < 0:
            n.append(e)
    x[:] = n

Z not n poskrbibo, da bomo gotovo dodali prvi element. Z e * n[-1] < 0 pa preverimo, ali ima e drugačen predznak kot zadnji element n. Če imata namreč različne predznake, bo njun produkt negativen.

Seveda bi delovalo tudi kaj bolj zapletenega, na primer e < 0 and n[-1] > 0 or e > 0 and n[-1] < 0. A naj se vidi, da poznavanje matematike koristi.

V nalogi sem pozabil določiti, kaj naj se zgodi z ničlami. No, recimo, da jih ni. Vsaj v testih jih ni bilo in upam, da je to dovolj pregnalo skrbi.

Nima vhoda (ob 12.00)

V dveh domačih nalogah smo delali z mrežami botov. Recimo, da so opisane s slovarji, kot v prvih od teh domačih nalog. Napiši funkcijo nima_vhoda(boti), ki prejme takšen slovar in vrne dve množici: množico botov, ki ne prejmejo nobenega čipa od drugega bota in množico botov, ki prejme od drugega bota le en čip. Za mrežo na sliki mora vrniti množici {1, 2}, {3, 6}.

Rešitev

Tole je bila v bistvu naloga iz programiranja. Ne uporabe slovarjev, ne rekurzije, ne objektov, temveč programiranja kar tako. Zanke, pogoji in takšne stvari. Ker ima Python marsikatero prikladno reč, pa lahko tudi tole nalogo "prešpricamo". Tule zato ne bom kazal dolgoveznih rešitev, temveč le takšno, ki naredi le tisto, kar je potrebno.

def nima_vhoda(bots):
    from collections import Counter
    outs = [b for (o, b), (_, __) in bots.values() if o == "bot"] + \
           [b for (_, __), (o, b) in bots.values() if o == "bot"]
    cts = Counter(outs)
    return set(bots) - set(outs), {b for b, c in cts.items() if c == 1}

V outs zberemo številke vse botov, ki se pojavijo kot izhodi. V cts preštejemo, kolikokrat se kateri bot pojavi kot izhod.

Boti, ki nimajo vhodov, so tisti, ki se pojavijo v množici številk botov, ne pa tudi v množici številk izhodov. Druga množica, ki jo moramo vrniti, pa so vsi boti, ki se kot izhod pojavijo natančno enkrat.

Dolžine ladij (ob 14.30)

Recimo, da položaj pri igri Potapljanje ladjic predstavimo s seznamom nizov, kot, recimo

[".......XXX....X",
 "X..XX.......X..",
 "X......XXXXX...",
 "X..XX.........."]

Napiši funkcijo dolzina(plosca, x, y), ki prejme takšno ploščo in pove, kako dolga je ladja, ki se začne na koordinatah x, y in gre potem na desno ali navzdol. Poleg tega napiši funkcijo najdaljsa_ladja(plosca), ki vrne dolžino najdaljše ladje na plošči; v gornjem primeru je to 5.

Rešitev

Tole pa je bila programerska naloga za drugo skupino. Tudi to je bilo možno rešiti na različne zapletene načine. Tule se bomo spet malo znašli.

def dolzina(plosca, x, y):
    v = 1
    while x + v < len(plosca[y]) and plosca[y][x + v] == "X":
        v += 1
    s = 1
    while y + s < len(plosca) and plosca[y + s][x] == "X":
        s += 1
    return max(v, s)

Od podanega polja poskušamo riniti na desno in navzdol. Koliko desno lahko gremo, smo merili v v, koliko dol, pa v s. Eno od teh števil bo vedno 1. Vrnemo tisto, ki je večje.

Najdaljšo ladjo potem dobimo tako, da preverimo vse dolžine ladij. To lahko storimo na kak dolg način ali pa z izpeljanim seznamom (oziroma generatorjem).

def najdaljsa_ladja(plosca):
    return max(dolzina(plosca, x, y)
               for x in range(len(plosca[0])) for y in range(len(plosca))
               if plosca[y][x] == "X")

Na poti (ob 12.00)

Napiši rekurzivno funkcijo na_poti(oddajnik, sprejemnik, boti), ki pove (True ali False) ali je možno, da bo eden od čipov, ki jih oddaja oddajnik, prišel v roke sprejemniku. Zadnji argument je slovar botov, kakršnega smo vajeni iz domačih nalog.

V gornjem primeru je možno, da bo čip, ki ga oddaja bot 1, prišel do bota 6. Čip, ki ga oddaja 3, pa ne more do bota 6.

Rešitev

Funkcija mora očitno vrniti True, če je oddajnik enak sprejemnik-u. Sicer pa vrne True, če je sprejemnik na poti od prvega ali od drugega bota, ki mu podaja oddajnik. Če seveda podaja botom.

def na_poti(oddajnik, prejemnik, boti):
    (low_kam, low_n), (high_kam, high_n) = boti[oddajnik]
    return oddajnik == prejemnik \
           or low_kam == "bot" and na_poti(low_n, prejemnik, boti) \
           or high_kam == "bot" and na_poti(high_n, prejemnik, boti)

Simpatična (in malo krajša) je tudi nekoliko bolj zvita različica, ki bi delovala tudi, če bi boti dajali več drugim botom, ne le dvema.

def na_poti(oddajnik, prejemnik, boti):
    return oddajnik == prejemnik \
           or any(na_poti(kam, prejemnik, boti)
                  for kako, kam in boti[oddajnik] if kako == "bot")

Na poti (ob 14.30)

V dveh domačih nalogah smo delali z mrežami botov. Napiši rekurzivno funkcijo do_izhoda(oddajnik, izhod, boti), ki pove (True ali False) ali je možno, da bo eden od čipov, ki jih oddaja bot oddajnik, prišel na podani izhod. Zadnji argument, boti, je slovar z navodili za bote, kakršnega smo vajeni iz domačih nalog.

V gornjem primeru je možno, da bo čip, ki ga oddaja 3 prišel na izhod 2, ne more pa priti na izhod 4.

Rešitev

Ista finta kot prej, le z drugačnim pogojem: zdaj preverimo, ali bot daje na zahtevani izhod. Če ne, pa pogledamo, da bo čip do izhoda poslal kateri od botov, ki mu podaja ta bot.

def do_izhoda(oddajnik, izhod, boti):
    (low_kam, low_n), (high_kam, high_n) = boti[oddajnik]
    return low_kam == "output" and low_n == izhod or \
           high_kam == "output" and high_n == izhod or \
           low_kam == "bot" and do_izhoda(low_n, izhod, boti) or \
           high_kam == "bot" and do_izhoda(high_n, izhod, boti)

Mesto (ob 12.00)

Napiši razred Mesto, ki predstavlja mesto, postavljeno na koordinatno mrežo.

• Konstruktor prejme njegovo širino in višino.
• Metoda postavi(x, y) postavi hišo na koordinate x, y. Koordinate številčimo od 0 naprej. Če postavimo na isto mesto več hiš, je postavljena le ena.
• Metoda porusi(x0, y0, x1, y1) poruši vse hiše v pravokotniku med vključno x0, y0 in vključno x1, y1 (pri smeš predpostaviti, da velja x0 <= x1 in y0 <= y1).
• Klic len(mesto), pri čemer je mesto nek objekt vrste Mesto, naj vrne število zasedenih polj.
• Metoda prosto() naj vrne število prostih polj.

Rešitev

Čeprav naj bi bila to naloga iz objektnega programiranja, je le-to relativno preprosto. Razmisliti moramo predvsem, kako bomo shranili podatek o tem, kje so hiše.

Najpreprosteje bo, če jih damo kar v množico. Tako dobimo

class Mesto:
    def __init__(self, sirina, visina):
        self.sirina = sirina
        self.visina = visina
        self.polno = set()

    def postavi(self, x, y):
        self.polno.add((x, y))

    def porusi(self, x0, y0, x1, y1):
        self.polno -= {(x, y) for x in range(x0, x1 + 1) for y in range(y0, y1 + 1)}

    def prosto(self):
        return self.sirina * self.visina - len(self)

    def __len__(self):
        return len(self.polno)

V porusi smo uporabili izpeljano množico. Lahko bi napisali tudi dve zanki in odstranjevali hišo za hišo.

V postavi bi lahko preverili, ali so koordinate res na tej mreži. Vendar naloga tega ni zahtevala, torej ne bomo. Potemtakem pa pravzprav niti ne potrebujemo self.sirina in self.visina, temveč le njun produkt, ki je potreben za izračun števila prostih mest.

Ladja (ob 14.30)

Napiši razred Ladja, ki predstavlja ladjo iz igre Potapljanje ladjic.

• Konstruktor prejme tri argumente: prvi je terka s koordinama začetnega polja (x in y), drugi dolžina ladje in tretji smer, ki je lahko ">" (ladja je postavljena tako, da narašča koordinata x) ali "v" (narašča koordinata y).
• Metoda strel(x, y) pomeni, da je igralec ustrelil na polje s podanimi koordinatami. Pri tem je morda zadel ladjo, morda ne.
• Klic len(ladja), kjer je ladja nek objekt razreda Ladja, vrne število nepotopljenih delov ladje. Če je ladja v začetku dolga 5 in zadanemo dva dela, bo len(ladja) vrnil 3.

Rešitev

Tudi tole ni bistveno drugače kot v izpitu za prvo skupino: spet bi moralo iti za objektno programiranje, v resnici pa moramo razmisliti predvsem, kako bomo shranjevali podatke. In izkaže se, da enako, kot v izpitu za prvo skupino: v množici. Tokrat množici koordinat, na kateri se nahajajo deli ladje.

class Ladja:
    def __init__(self, zacetno, dolzina, smer):  # smer = >, v
        x, y = zacetno
        if smer == ">":
            self.polja = {(x + k, y) for k in range(dolzina)}
        else:
            self.polja = {(x, y + k) for k in range(dolzina)}

    def __len__(self):
        return len(self.polja)

    def strel(self, x, y):
        self.polja -= {(x, y)}

Rešitve celotnega izpita

Ob 12.30

# 1

def dolzina_poti(pari, x):
    pari = dict(pari)
    length = 0
    while x in pari:
        length += 1
        x = pari[x]
    return length

# 2

def alterniraj(x):
    n = []
    for e in x:
        if not n or e * n[-1] < 0:
            n.append(e)
    x[:] = n

# 3

def nima_vhoda(bots):
    from collections import Counter
    outs = [b for (o, b), (_, __) in bots.values() if o == "bot"] + \
           [b for (_, __), (o, b) in bots.values() if o == "bot"]
    cts = Counter(outs)
    return set(bots) - set(outs), {b for b, c in cts.items() if c == 1}

# 4

def na_poti(oddajnik, prejemnik, boti):
    (low_kam, low_n), (high_kam, high_n) = boti[oddajnik]
    return oddajnik == prejemnik \
           or low_kam == "bot" and na_poti(low_n, prejemnik, boti) \
           or high_kam == "bot" and na_poti(high_n, prejemnik, boti)

# 5

class Mesto:
    def __init__(self, sirina, visina):
        self.sirina = sirina
        self.visina = visina
        self.polno = set()

    def postavi(self, x, y):
        self.polno.add((x, y))

    def porusi(self, x0, y0, x1, y1):
        self.polno -= {(x, y) for x in range(x0, x1 + 1) for y in range(y0, y1 + 1)}

    def prosto(self):
        return self.sirina * self.visina - len(self)

    def __len__(self):
        return len(self.polno)

Ob 14.30

# 1

def ne_daje_naprej(pari):
    return {x for _, x in pari} - {x for x, _ in pari}

# 2

def ne_3_po_2(s):  # Gre tudi krajse, a ... OK
    n = s[:1]
    for prej, e in zip(s, s[1:]):
        if e % 3 or prej % 2:
            n.append(e)
    s[:] = n

# 3

def dolzina(plosca, x, y):
    v = 1
    while x + v < len(plosca[y]) and plosca[y][x + v] == "X":
        v += 1
    s = 1
    while y + s < len(plosca) and plosca[y + s][x] == "X":
        s += 1
    return max(v, s)

def najdaljsa_ladja(plosca):
    return max(dolzina(plosca, x, y)
               for x in range(len(plosca[0])) for y in range(len(plosca))
               if plosca[y][x] == "X")

# 4

def do_izhoda(oddajnik, izhod, boti):
    (low_kam, low_n), (high_kam, high_n) = boti[oddajnik]
    return low_kam == "output" and low_n == izhod or \
           high_kam == "output" and high_n == izhod or \
           low_kam == "bot" and do_izhoda(low_n, izhod, boti) or \
           high_kam == "bot" and do_izhoda(high_n, izhod, boti)

# 5

class Ladja:
    def __init__(self, zacetno, dolzina, smer):  # smer = >, v
        x, y = zacetno
        if smer == ">":
            self.polja = {(x + k, y) for k in range(dolzina)}
        else:
            self.polja = {(x, y + k) for k in range(dolzina)}

    def __len__(self):
        return len(self.polja)

    def strel(self, x, y):
        self.polja -= {(x, y)}