Rešitve s komentarji
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 vrneNone.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}