Najprej so tule rešitve vseh nalog - v neki ne-prezahtevni (včasih celo nekoliko okorni) obliki. Razlaga in druge, tudi boljše, različice so spodaj.

# 1
def cokolada(n, odlomki):
    sirina = visina = n
    for odlomek in odlomki:
        kje, koliko = odlomek[0], int(odlomek[:1])
        if kje in "<>":
            sirina -= koliko
        else:
            visina -= koliko
    return max(0, sirina) * max(0, visina)


# 2
from collections import defaultdict
def zdruzi(s):
    res = defaultdict(set)
    for i, e in enumerate(s):
        res[e].add(i)
    return res

def razmeci(s):
    naj = 0
    for indeksi in s.values():
        m = max(indeksi)
        if m > naj:
            naj = m
    res = [None] * (naj + 1)
    for e, places in s.items():
        for place in places:
            res[place] = e
    return res

# 3
def brez_jecljanja_rec(s):
    if len(s) < 2:
        return s
    if s[0] == s[1]:
        return brez_jecljanja_rec(s[1:])
    else:
        return [s[0]] + brez_jecljanja_rec(s[1:])

def brez_jecljanja_rec(s):
    return s if len(s) < 2 else s[:s[0] != s[1]] + brez_jecljanja_rec(s[1:])

# 4
def sopomena(stavek1, stavek2, sopomenke):
    stavek1, stavek2 = stavek1.split(), stavek2.split()
    if len(stavek1) != len(stavek2):
        return False
    for beseda1, beseda2 in zip(stavek1, stavek2):
        if beseda1 != beseda2:
            for so in sopomenke:
                if beseda1 in so and beseda2 in so:
                    break
            else:
                return False
    return True

# 5
class Picerija:
    pice = ["margerita", "klasika", "zelenjavna", "siri"]
    cene = dict(zip(pice, [1, 2, 1, 3]))

    def __init__(self):
        self.kup = []
        self._zasluzek = 0

    def speci(self):
        self.kup += self.pice

    def prodaj(self):
        if self.kup:
            z = self.kup.pop()
            self._zasluzek += self.cene[z]
            return z

    def zasluzek(self):
        return self._zasluzek

    def __getitem__(self, i):
        return self.kup[-i]

    def __str__(self):
        return " > ".join(self.kup)

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

1. Čokolada

Imamo kvadratno čokolado iz nxn koščkov. Kako jo lomimo, pove niz, katerega prvi znak je stran, na kateri jo lomimo, preostali znaki so število odlomljenih stolpcev oz. vrstic. Na primer,

  • "<3" pomeni, da odlomimo tri stolpce z leve,
  • ">12" pomeni, da odlomimo 12 stolpcev z desne,
  • "^1" pomeni, da odlomimo zgornjo vrstico,
  • "v5" pomeni, da odlomimo spodnjih 5 vrstic.

Če poskušamo odlomiti več, kot je možno (imamo pet vrstic in uporabimo "v7"), pač odlomimo, kolikor gre (samo pet vrstic)

Napiši funkcijo cokolada(n, odlomi), ki prejme velikost čokolade (n) in seznam lomljenj (odlomi, na primer ["<3", ">2", ">1", "v12", "<7"]). Funkcija naj pove, koliko kvadratkov čokolade je še ostalo. Klic cokolada(10, ["<3", "v5"]) vrne 35, saj je ostalo 7 stolpcev in 5 vrstic.

Rešitev

Tule je bilo potrebno najprej malo premisliti: ali lomimo čokolado z leve ali z desne, je vseeno. Potrebno je le opazovati, koliko vrstic in koliko stolpcev ostane.

def cokolada(n, odlomki):
    sirina = visina = n
    for odlomek in odlomki:
        kje, koliko = odlomek[0], int(odlomek[:1])
        if kje in "<>":
            sirina -= koliko
        else:
            visina -= koliko
    return max(0, sirina) * max(0, visina)

Bodite pozorni na to, kako elegantno razpakirati niz: vzeti moramo prvo črko (odlomek[0]) in ostanek (odlomek[:1]). Ostanek pretvorimo v število in da bi bilo bolj očitno, da gre za "razpakiranje" niza, obe prirejanji opravimo kar naenkrat - kje in koliko sta prvi znak niza in ostanek niza.

Nato zmanjšamo bodisi širino bodisi višino za koliko. Nekateri ste pred zmanjševanje dodali if in v primeru, da odtrgamo več, kot imamo, le nastavili širino oz. višino na 0. Tule smo ga lomili naprej in šele na koncu poskrbeli za primer, ko čokolade zmanjka.

Večina vas je končala z

if sirina * visina < 0:
    return 0

To ne deluje, kadar sta oba, širina in višina, manjša od 0. Če od čokolade velikosti 10x10 odlomimo 11 vrstic in 11 stolpcev, bomo imeli (-1) * (-1) = 1 košček? Prelepo, da bi bilo res. :)

Namesto tega bi morali pisati

if sirina < 0 or visina < 0:
    return 0
else:
    return sirina * visina

ali kako različico tega. V gornji rešitvi smo uporabili max(0, sirina). Če je sirina večja od 0, bo max(0, sirina) kar sirina; če je sirina negativna, pa bo max(0, sirina) vrnil 0.

Malo pospešena rešitev je

def cokolada(n, odlomki):
    return max(0, n - sum(int(x[1:]) for x in odlomki if x[0] in "<>")) * \
           max(0, n - sum(int(x[1:]) for x in odlomki if x[0] in "v^"))

2. Združi - razmeči

Napiši funkcijo zdruzi(s), ki prejme seznam s ter vrne slovar, katerega ključi so elementi s-a, pripadajoče vrednosti pa množice indeksov, kjer se ta element pojavlja. Klic zdruzi([3, 1, 12, 3, 7, 12]) mora vrniti {1: {1}, 3: {0, 3}, 7: {4}, 12: {2, 5}}.

Napiši še funkcijo razmeci(s), ki dela ravno obratno – prejme takšen slovar in vrne seznam.

Rešitev

S prvim delom naloge ste navadno opravili brez težav.

from collections import defaultdict
def zdruzi(s):
    res = defaultdict(set)
    for i, e in enumerate(s):
        res[e].add(i)
    return res

Večina se sicer ni spomnila na defaultdict, tako da ste potrebovali še malo čaranja z if.

Med napačnimi rešitvami moram izpostaviti tole:

def zdruzi(s):
    rdic = {}
    for number in s:
        if number in rdic:
            rdic[number].append(s.index(number))
        else:
            rdic[number] = [s.index(number)]
    return rdic

Na predavanjih sem svaril pred index. Če lahko vemo, kje v seznamu smo - in kadar gremo čez seznam, vedno lahko vemo, kje smo, saj imamo enumerate - ne uporabljamo index. Opozoril sem, da index ne bo deloval, če imamo v seznamu več enakih elementov, saj bo vračal prvega. Točno to se zgodi v tej funkciji. Še več, tu je očitno, da se bo ista vrednost pojavila večkrat, saj vsa naloga govori o tem. s.index(number) bo vedno vračal indeks prve pojavitve.

Kakorliko, z zdruzi niste imeli hujših problemov. Razmetavanje pa je bila druga pesem. V osnovi bi želeli napisati tole:

def razmeci(s):
    res = []
    for e, places in s.items():
        for place in places:
            res[place] = e  # Ne deluje!
    return res

Tole ne deluje, ker res[place] še ne obstaja. Pač pa bi delovalo, če bi vnaprej poznali dolžino novega seznama, saj bi potem lahko napisali

def razmeci(s):
    res = [None] * dolzina_novega_seznama  # Ne deluje!
    for e, places in s.items():
        for place in places:
            res[place] = e
    return res

No, lahko jo izračunamo. Lahko gremo, recimo, čez vse indekse in pogledamo največjega

def razmeci(s):
    naj = 0
    for indeksi in s.values():
        m = max(indeksi)
        if m > naj:
            naj = m
    res = [None] * (naj + 1)
    for e, places in s.items():
        for place in places:
            res[place] = e
    return res

To je nekoliko dolgo, pišemo lahko

def razmeci(s):
    res = [None] * (1 + max(max(indeksi) for indeksi in s.values()))
    for e, places in s.items():
        for place in places:
            res[place] = e
    return res

Nič od tega ne deluje, če je seznam prazen. To lahko rešimo z dodanim ifom na začetku, lahko pa namesto največjega indeksa preštejemo število indeksov in prazen seznam se uredi sam od sebe.

def razmeci(s):
    res = [None] * sum(map(len, s.values()))
    for e, places in s.items():
        for place in places:
            res[place] = e
    return res

Pri tej nalogi ste našli veliko ustvarjalnih rešitev. Ena lepših je tale:

def razmeci(s):
    rezultat = list()
    vmesni = []
    for number, index in s.items():
        for i in index:
            vmesni.append((i, number))
    for i, j in sorted(vmesni):
        rezultat.append(j)
    return rezultat

V seznam vmesni zložimo pare indeksov in vrednost. Nato ga uredimo (po indeksih) in v rezultat prepišemo vrednosti v prav tem vrstnem redu.

Rešitev v tej obliki kar kliče po tem, da jo zapišemo z izpeljanim seznamom.

def razmeci(s):
    return [v for i, v in sorted((i, v) for v, indeksi in s.items() for i in indeksi)]

3. Brez jecljanja

Napiši rekurzivno funkcijo brez_jecljanja_rec(s), ki prejme seznam s in vrne nov seznam, ki ne vsebuje zaporednih ponovitev istega elementa. Klic brez_jecljanja([1, 6, 3, 3, 1, 1, 1, 1, 2, 3, 5, 5, 1]) naj vrne [1, 6, 3, 1, 2, 3, 5, 1].

Napiši tudi (nerekurzivno) funkcijo brez_jecljanja_gen(s, e), ki počne isto, vendar je napisana tako, da vrne izpeljan seznam (vsa funkcija je torej le en sam return).

Rešitev

Splošni občutek pri tej nalogi je najbolj povzela naslednja (sicer žal ne pravilna) rešitev:

def brez_jecljanja_rec(s):
    pass

def brez_jecljanja_gen(s):
    pass

Škoda, saj ni tako težko. Najprej razmislimo rekurzivno.

def brez_jecljanja_rec(s):
    if len(s) < 2:
        return s
    if s[0] == s[1]:
        return brez_jecljanja_rec(s[1:])
    else:
        return [s[0]] + brez_jecljanja_rec(s[1:])

Najprej poglejmo drugi del. Če sta prva dva znaka enaka, prvega enostavno ignoriramo; rezultat funkcije je enak nejecljajočemu ostanku seznama. Če nista enaka, pa vzamemo prvi znak (kot seznam) in dodamo nejecljajoči ostanek seznama.

Rekurzija se konča, ko imamo le še en znak.

Namestno [s[0]] lahko pišemo tudi s[:1]. s[0] pa ne bo delovalo, ker je to prvi element seznama (in ne seznam, ki vsebuje prvi element seznama), zato k njemu ne morem prišteti preostanka seznama.

Bližnjica za vse to je

def brez_jecljanja_rec(s):
    return s if len(s) < 2 else s[:s[0] != s[1]] + brez_jecljanja_rec(s[1:])

Izraz s[0] != s[1] je resničen ali ne, torej je 0 ali 1. Torej je s[:s[0] != s[1]] bodisi s[:0] (prvih 0 elementov s-a) ali s[:1] (seznam, ki vsebuje prvi element s-a). Ostalo je očitno.

V izpeljanem seznamu uporabimo - kot skoraj vedno, kadar opazujemo zaporedne pare elementov - zip. Gremo čez vse pare in če se razlikujeta, ohranimo prvega. Ker na ta način najzadnejši nikoli ne bo dodan, ga dodamo. Tudi če je enak predzadnjemu (in ta mogoče še kateremu pred sabo), nič hudega: teh nismo obdržali, torej je prav, da zadnjega dodamo.

def brez_jecljanja_gen(s):
    return [e for e, f in zip(s, s[1:]) if e != f] + s[-1:]

Zelo pogosta (zmerno) napačna rešitev je bila

def brez_jecljanja_gen(s):
    return [e for i, e in enumerate(s) if s[i] != s[i-1]]

To ne deluje pravilno pri seznamu [1, 2, 3, 4, 5] - kot ste opazili, vrne [2, 3, 4, 5]. Element z indeksom i=0 primerja z i-1. Prvega torej primerja z zadnjim in ker sta enaka, ga zavrže.

Tudi tu so indeksi zelo slaba ideja: tole ne deluje.

def brez_jecljanja_gen(s):
    return [x for x in s if x != s[s.index(x)-1]]

4. Sopomenke

Sopomenke lahko predstavimo z množico besed, kot, recimo {"fant", "deček", "pob"}. Takšne množice lahko zberemo v seznam, recimo [{"fant", "deček", "pob"}, {"cesta", "pot", "kolovoz", "makadam"}, {"kis", "jesih"}].

Napišite funkcijo sopomena(stavek1, stavek2, sopomenke), ki pove, ali stavek1 in stavek2 pomenita isto. Tako mora, recimo

sopomena("fant in dekle sta vzela pot pod noge",
       "pob in punca sta vzela kolovoz pod tace",
       [{"fant", "deček", "pob"}, {"cesta", "pot", "kolovoz", "makadam"},
        {"kis", "jesih"}, {"dekle", "punca"}, {"noge", "tace"}])

vrniti True. Predpostavite lahko, da v stavku ni ločil. Ne vznemirjajte se zaradi sklonov.

Rešitev

O popravljanju te naloge sem se spraševal, ali sem vas preveč navezal na teste. Ti so koristni, ker vam pomagajo, kadar ne razumete dobro besedila naloge (seveda lahko kdaj tudi po moji krivdi). Tokrat pa je bila naloga jasna, za mnoge rešitve pa bi bilo, če premislite, kaj pišete, očitno, da teste preživijo le slučajno.

def sopomena(stavek1, stavek2, sopomenke):
    stavek1, stavek2 = stavek1.split(), stavek2.split()
    if len(stavek1) != len(stavek2):
        return False
    for beseda1, beseda2 in zip(stavek1, stavek2):
        if beseda1 != beseda2:
            for so in sopomenke:
                if beseda1 in so and beseda2 in so:
                    break
            else:
                return False
    return True

Najprej preverimo, ali imata stavka slučajno različno število besed in vrnemo False, če to ne drži. Tega primera ni bilo v testih, zato na to v resnici nisem bil posebej pozoren. Je tudi nekako "trivialno"; ideja naloge je bila drugje.

Zdaj gremo čez vse pare. Če sta besedi različni, gremo čez vse sopomenke. Če najdemo množico sopomenk, v kateri se pojavita obe besedi, zanko prekinemo. Če se zanka izteče, ne da bi jo prekinili, pa gre za različni besedi, ki nista sopomenki, torej vrnemo False.

Če se zanka for beseda1, beseda2 varno izteče, pa lahko vrnemo True.

Vaši programi so pogosto preverjali le, ali se vse besede pojavijo v kaki množici sopomenk - ne nujno v isti. Ali pa ste naredili kako drugo podobno logično napako. Popolnoma pravilnih rešitev je bilo res malo.

Želel sem si, vendar to le redko videl, da bi se izognili stalnemu sprehajanju po slovarju sopomenk. Lahko bi, recimo, sestavili slovar sopomenskih parov besed.

Po bližnjici se to naredi tako:

pari = {(b1, b2) for so in sopomenke for b1 in so for b2 in so}

V tem slovarju so zdaj, recimo {("pob", "fant"), ("fant", "pob"), ("pob", "pob"), ("fant", "fant"), ("dekle", "punca), ...}.

Zdaj pa naredimo pare besed iz obeh stavkov. zip(stavek1.split(), stavek2.split()). Pravzaprav jih moramo dati v množico: set(zip(stavek1.split(), stavek2.split())). Vsak par besed mora biti tudi v slovarju parov sopomenk. Z drugimi besedami, množica teh parov mora biti podmnožica množice sopomenk. Tako dobimo

def sopomena(stavek1, stavek2, sopomenke):
    return set(zip(stavek1.split(), stavek2.split())) <=
               {(b1, b2) for so in sopomenke for b1 in so for b2 in so}

Če hočemo paziti na dolžine, dodamo še

def sopomena(stavek1, stavek2, sopomenke):
    stavek1, stavek2 = stavek1.split(), stavek2.split()
    return len(stavek1) == len(stavek2) and \
        set(zip(stavek1, stavek2)) <=
            {(b1, b2) for so in sopomenke for b1 in so for b2 in so}

Nekateri ste, pohvalno, prišli kar daleč v to smer. Lep primer je

def sopomena(stavek1, stavek2, sopomenke):
    return all(prva == druga or
               any(prva in besede and druga in besede for besede in sopomenke)
                   for prva, druga in zip(stavek1.split(), stavek2.split()))

Mimogrede, mnogi ste pisali stvari kot

if (beseda1 in sopomenka and beseda2 not in sopomenka or
    beseda2 in sopomenka and beseda1 not in sopomenka):

Ker so logični izrazi izrazi kot katerikoli drugi in ker sta True in False vrednosti, kot katerakoli druga vrednost, lahko namesto tega pišemo kar

if beseda1 in sopomenka != beseda2 in sopomenka:

To bo res, kadar je ena v množici in druga ni ali obratno.

5. Picerija

Pek vedno speče štiri različne pice. Ko so pečene, jih da v škatle in da na vrh kupa že pečenih pic: najprej margerito, nato klasiko, potem zelenjavno in potem sire.

Prodajalec vedno proda pico, ki je na vrhu kupa. Kupec nima kaj izbirati; če je na vrhu zelenjavna, dobi zelenjavno.

Napiši razred Picerija z naslednjimi metodami

  • speci() da na kup pic štiri nove pice, kot je opisano zgoraj;

  • prodaj() vzame s kupa zgornjo pico in vrne njeno ime ("margerita", "klasika", "zelenjavna", "siri"). Če trenutno ni nobene pečene pice, naj vrne None.

  • zasluzek() vrne dosedanji zaslužek; z margerito zasluži en evro, s klasiko dva, z zelenjavo enega in s siri tri.

Poleg tega poskrbite za izpis, dolžino in indeksiranje. Če je p neka picerija, naj

  • len(p) vrne število trenutno pečenih pic,

  • p[3] ime pice, ki jo bo dobila tretja stranka, ki bo prišla (ob predpostavki, da pek medtem ne bo spekel ničesar,

  • print(p) izpiše trenutno zalogo pic v obliki, opisani spodaj.

    p = Picerija() p.speci() p.prodaj() p.prodaj() p.speci() print(p)

izpiše

margerita > klasika > margerita > klasika > zelenjavna > siri

Rešitev

class Picerija:
    pice = ["margerita", "klasika", "zelenjavna", "siri"]
    cene = dict(zip(pice, [1, 2, 1, 3]))

    def __init__(self):
        self.kup = []
        self._zasluzek = 0

    def speci(self):
        self.kup += self.pice

    def prodaj(self):
        if self.kup:
            z = self.kup.pop()
            self._zasluzek += self.cene[z]
            return z

    def zasluzek(self):
        return self._zasluzek

    def __getitem__(self, i):
        return self.kup[-i]

    def __str__(self):
        return " > ".join(self.kup)

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

Pice in cene sem postavil kar v razred, ne v __init__. O tem se nismo učili, vendar so cene in vrste pic, kot je pravilno komentiral tudi eden od vas, enake za vse picerije, torej sodijo tja. (Lahko si predstavljate, da je vse to v __init__u, če si želite. Če vam gre Programiranje 1 dobro od rok, pa si le oglejte to zadevo tudi v dokumentaciji za Python.)

Cene smo postavili tako, da smo pozipali skupaj imena in vrednosti.

Kakorkoli že to sestavimo, pomembno je, da imamo cene v slovarju, saj se tako izognemo gori if-ov.

Zaslužek shranjujemo v _zasluzek. Atribut se ne sme imenovati zasluzek, saj je to ime metode. Nekateri ste pisali profit, cvenk in podobno. Tole s podčrtajem je sicer kar običajno: tako označimo "zasebne" atribute razreda.

Bodite pozorni na prodaj: le redki ste se spomnili, da imajo seznami metodo pop, ki pobere zadnji element s "kupa". Namesto tega ste morali pisati

z = self.kup[-1]
del z[-1]

No, pop naredi isto.

Veliko vas ni znalo napisati __getitem__: ker pice pobiramo s konca, je tu elemente potrebno pobirati z desne, zato -i. Delo sem vam olajšal s tem, da sem dal prvi stranki število 1 in ne 0.

Veliko vas je pozabilo tudi na join in ste se zafrkavali s seštevanjem nizov.

V splošnem pa vam je šla ta naloga kar dobro.

Pa še ekspresne rešitve

Ker vas je kar nekaj, ki jih zanimajo takšne reči, so tu zbrane še hitre rešitve vseh nalog (razen zadnje, kjer nimamo kaj).

# 1
def cokolada(n, odlomki):
    return max(0, n - sum(int(x[1:]) for x in odlomki if x[0] in "<>")) * \
           max(0, n - sum(int(x[1:]) for x in odlomki if x[0] in "v^"))

# 2
# Ne spomnim se rešitve v eni vrsti, ki ne bi bila nespodobno grda. :(
from collections import defaultdict
def zdruzi(s):
    res = defaultdict(set)
    for i, e in enumerate(s):
        res[e].add(i)
    return res

def razmeci(s):
    return [v for i, v in sorted((i, v) for v, indeksi in s.items() for i in indeksi)]

# 3
def brez_jecljanja_rec(s):
    return s if len(s) < 2 else s[:s[0] != s[1]] + brez_jecljanja_rec(s[1:])

def brez_jecljanja_gen(s):
    return [e for e, f in zip(s, s[1:]) if e != f] + s[-1:]

# 4        
# Dalo bi se potlačiti v eno vrsto, ampak ... nima smisla, to je lepše
def sopomena(stavek1, stavek2, sopomenke):
    stavek1, stavek2 = stavek1.split(), stavek2.split()
    return len(stavek1) == len(stavek2) and \
        set(zip(stavek1, stavek2)) <=
            {(b1, b2) for so in sopomenke for b1 in so for b2 in so}
Zadnja sprememba: sobota, 30. januar 2016, 17.36