Rešitev
1. Kar je razkladal Močilar
Napiši funkcijo prelomi(s, sirina), ki prejme (kar dolg) niz s in število sirina. Funkcija vrne niz, prelomljen na podano širino: vsaka vrstica je čim daljša, a ne daljša od podane širine. Program
besedilo = "V Notranjem stoji vas, Vrh po imenu. ... in tako naprej
urejeno = prelomi(besedilo, 80)
print(urejeno)
izpiše
V Notranjem stoji vas, Vrh po imenu. V tej vasici je živel v starih časih Krpan,
močan in silen človek. Bil je neki tolik, da ga ni kmalu takega. Dela mu ni bilo
mar; ampak nosil je od morja na svoji kobilici angleško sol, kar je bilo pa že
tistikrat ostro prepovedano. Pazili so ga mejači, da bi ga kje nehotoma zalezli;
poštenega boja ž njim so se bali ravno tako kakor pozneje Štempiharja. Krpan se
je pa vedno umikal in gledal, da mu niso mogli do živega.
Prva, druga in četrta vrstica (slučajno) vsebujeta ravno 80 znakov, ostale manj.
Klic prelomi("abcčd efghi jklmn oprsš", 11) vrne "abcčd efghi\njklmn oprsš".
Pazi: funkcija ne vsebuje nobenega print-a, temveč vrne niz, ki je ustrezno prelomljen z znaki \n.
Rešitev
Tole je precej nerodna naloga, ki zahteva predvsem spretnost. Navdih zanjo sem dobil, ko sem moral sam programirati nekaj podobnega (le da nisem lomil besedila, temveč legendo pod nekim grafom). Rešil sem jo ekvivalentno temu:
def prelomi(besedilo, sirina):
vrstice = []
for beseda in besedilo.split():
if not vrstice or len(vrstice[-1] + " " + beseda) > sirina:
vrstice.append(beseda)
else:
vrstice[-1] += " " + beseda
return "\n".join(vrstice)
Vse vrstice zbiram v seznam vrstice, da jih bom na koncu združil \n. Grem čez besede. Pogoj preverja, ali je potrebno dodati novo vrstico. To storimo, če še ni nobene vrstice ali pa če trenutne besede (in presledka pred njo) ne smemo več dodati, saj bi tako dobili predolgo vrstico. Če je torej potrebno dodati novo vrstico, dodamo vrstico, ki vsebuje to besedo, vrstice.append(beseda). Če lahko dodamo besedo v trenutno zadnjo vrstico, pa jo dodamo (pa še presledek pred njo), vrstice[-1] += " " + beseda.
Da sem prišel do tako elegantne rešitve, sem moral kar nekaj časa vrteti program. Predvsem nadležen je presledek med besedami - ki ga ne sme biti pred prvo oz. pred zadnjo besedo. Seveda se da z njim opraviti tudi drugače, ampak tako, kot sem naredil tu, je nadloga še najmanjša.
2. Vojna brez vojn
Nadaljevanje poznamo. Priklati se veliki širokoustnež, kvartopirec Brdavs in po dunajskih kavarnah vse po vrsti izziva na igro Vojna. Kdor se je skusil ž njim, gotovo je bil zmagan. Pa je prišel Krpan branit čast dunajskega mesta. A ker se igra lahko vleče v nedogled, Krpanu pa se mudi domov za peč, sta jo nekoliko poenostavila.
V začetku vsak igralec dobi kupček kart (v Pythonu predstavljen s seznamom števil). V vsaki potezi vsak od njiju obrne gornjo karto. Tisti, čigar karta je višja, pobere obe karti – najprej svojo in nato še nasprotnikovo. Če sta karti (številki) enaki, pa se odstranita iz igre. Razlika med običajno igro in njuno je torej v tem, zadnjem.
Napiši funkcijo vojna(s, t), ki prejme dva seznama števil in odsimulira krog igre. Vrne kupčka kart, ki jih imata igralca po tem krogu. Če je imel eden od njiju več kart, so te po koncu kroga na začetku kupčka.
s = [5, 2, 7, 4, 8, 1, 3, 7]
t = [2, 6, 5, 4, 9]
s1, t1 = vojna(s, t)
print(s1)
print(t1)
izpiše
[1, 3, 7, 5, 2, 7, 5]
[6, 2, 9, 8]
Prvi ima preostanek kupčka (1, 3, 7), poleg tega pa je s 5 pobral 2 in s 7 je pobral 5. Drugi igralec je s 6 pobral 2 in z 9 8. Štirici sta bili odstranjeni.
Rešitev
Naloga vam ni povzročala hujših težav. Lepa rešitev je takšna:
def vojna(s, t):
s_novi = []
t_novi = []
for iz_s, iz_t in zip(s, t):
if iz_s > iz_t:
s_novi += [iz_s, iz_t]
elif iz_t > iz_s:
t_novi += [iz_t, iz_s]
s_novi = s[len(t):] + s_novi
t_novi = t[len(s):] + t_novi
return s_novi, t_novi
zip bo šel do dolžine krajšega seznama. V seznam moramo dodati dva elementa in za to je s_novi += [iz_s, iz_t] preprostejši od dveh appendov.
Na koncu dopolnimo seznama tako, da na začetek s_novi prilepimo vse elemente s, ki sledijo zadnjemu elementu t in obratno. Eno od teh dveh dodajanj (ali celo obe, če sta seznama enako dolga) nima učinka, a to nas ne moti.
V študentskih izdelkih sem opazil, da radi primerjate takole: if len(s) - len(t) > 0:. Mar ni to isto kot if len(s) > len(t):? Ali pa tudi namesto if a > b pišete if a - b > 0.
Zanimiv je tudi tale vzorec.
seznam = []
for i,j in zip(s,t):
seznam.append(i)
seznam.append(j)
seznam1.append(tuple(seznam))
seznam = []
for i, j in seznam1:
...
To kar radi počnete - v precej situacijah radi sestavite prazen seznam pred zanko in potem na koncu zanke. Veliko boljše je sestaviti prazen seznam na začetku zanke, pa nam ga ni treba na koncu.
for i,j in zip(s,t):
seznam = []
seznam.append(i)
seznam.append(j)
seznam1.append(tuple(seznam))
for i, j in seznam1:
...
Potem je seveda očitno, da bi bilo vseeno, če napišemo
for i,j in zip(s,t):
seznam = [i, j]
seznam1.append(tuple(seznam))
for i, j in seznam1:
...
kar pa je isto kot
for i,j in zip(s,t):
seznam1.append(tuple([i, j]))
for i, j in seznam1:
...
in kot
for i,j in zip(s,t):
seznam1.append((i, j))
for i, j in seznam1:
...
Vse skupaj pa ima isti učinek kot
for i, j in zip(s, t):
...
:)
3. Kdo se je skusil ž njo?
Brdavs je že davno izmolil očenašek ali dva in pa svojih grehov se je malo pokesal in Martin je tudi že za pečjo, Dunajčanke pa so se navadila igre in jo pridno igrajo po kavarnah.
Imamo seznam tekem v obliki [("Ana", "Berta"), ("Cilka", "Ema"), ("Ana", "Fanči"), ("Berta", "Ema"), ("Cilka", "Greta")], ki pomeni, da je Ana premagala Berto, Cilka Emo, Ana Fanči in Berta Emo. Vsak par igra le enkrat. V celem lajfu.
Napiši funkcijo relacije(tekme), ki prejme tak seznam in kot rezultat vrne (za gornji primer) {"Ana": {"Berta", "Fanči"}, "Berta": {"Ema"}, "Cilka": {"Ema", "Greta"}}, iz katere bo očitneje, da je Ana premagala Berto in Fanči, Berta Emo, Cilka pa Emo in Greto.
Rešitev
Ta naloga je marsikomu rešila oceno. :)
def relacije(tekme):
zmagovalci = defaultdict(set)
for kdo, koga in tekme:
zmagovalci[kdo].add(koga)
return zmagovalci
Namig za večjo eleganco vaših programov: v množico m dodamo element e z m.add(e) in ne tako, da sestavimo množico, ki vsebuje e in izračunamo unijo, m |= {e}. :)
4. Kdo bo koga
Nadaljujmo, kjer smo končali. Če je Ana boljša od Berte, Berta pa od Eme, vemo, da je Ana boljša od Eme.
Napiši funkcijo premaga(kdo, koga, relacije), ki prejme dve imeni in takšen slovar relacije, kot ga vrača prejšnja funkcija. Funkcija vrne True, če lahko vemo, da kdo premaga koga. Klic premaga("Ana", "Ema", relacije) vrne True, klic premaga("Ema", "Ana", relacije) pa False. Funkcija vrne False tudi v primeru, da relacija med kdo in koga ni znana. V gornjem primeru, recimo, tako klic premaga("Berta", "Cilka", relacije) kot klic premaga("Cilka", "Berta", relacije) vrne False, saj ne vemo, kdo od njiju je boljši.
Pazi, dolžina sklepanja je lahko tudi dolga: v testnih primerih je Cilka boljša od Ive, ker Cilka premaga Emo, Ema Dani in Dani Ivo.
Namig: četrta naloga na izpitu pogosto, dasiravno ne nujno, zahteva rekurzivno funkcijo. Po želji.
Rešitev
To se da rešiti rekurzivno ali nerekurzivno.
Rekurzivno:
def premaga(kdo, koga, relacije):
if kdo not in relacije:
return False
if koga in relacije[kdo]:
return True
for slabsi in relacije[kdo]:
if premaga(slabsi, koga, relacije):
return True
return False
Če kdo ni premagal nikogar (kdo not in relacije), se nimamo kaj pogovarjati (False). Če je kdo direktno premagal koga, je očitno boljši (True). Če je kdo premagal nekoga, ki je premagal koga, je kdo boljši (True). Sicer pa nič.
Taisto lahko zapišemo tudi krajše:
def premaga(kdo, koga, relacije):
return kdo in relacije and (
koga in relacije[kdo]
or any(premaga(slabsi, koga, relacije) for slabsi in relacije[kdo]))
To je, mimogrede, enako funkciji, v kateri smo preverjali, ali je določeno ime v rodbini določene osebe.
Zdaj pa nerekurzivno:
def premaga(kdo, koga, relacije):
preveriti = [kdo]
for oseba in preveriti:
if oseba == koga:
return True
if oseba in relacije:
preveriti += relacije[oseba]
return False
V seznam preveriti damo najprej kdo, potem pa za vsako osebo s tega seznama dodamo v ta seznam vse, ki jih je ta oseba premagala. Če pri tem naletimo na koga, vrnemo True. Če se to ne zgodi, pa False.
5. Dobro uravnotežena Kobilica
Kot je vsem znano, je Krpan na svoji Kobilici tovoril kresilno gobo in bruse. Kobilica je imela, kot dandanašnji kolesarji, dve torbi, eno na levi in eno na desni strani. Napiši razred Kobilica z metodami:
- dodaj(stran, ime, teza), ki kobilici na podano stran (0 = levo, 1 = desno) naloži stvar z imenom ime in težo teza. Predpostaviti smeš, da kobilica nikoli ne nosi dveh stvari z enakima imenoma;
- odvzemi(ime), ki kobilici odvzame stvar s podanim imenom;
- uravnotezenost(), ki vrne razliko med skupno težo desne in leve strani – razlika je pozitivna, če je desna stran težja in negativna, če je težja leva stran.
Morebitne druge metode dodaj po potrebi.
Rešitev
Recimo tako. V konstruktorju si pripravimo slovar, v katerega bomo za vsako ime zapisali njegovo težo. Trik: teža bo negativna, če je stvar na levi strani. Torej jo pomnožimo z (-1, 1)[stran]. Delovalo bi tudi self.tovor[ime] = teza * (-1 + 2 * stran). Brisanje in seštevanje je potem trivialno.
class Kobilica:
def __init__(self):
self.tovor = {}
def dodaj(self, stran, ime, teza):
self.tovor[ime] = teza * (-1, 1)[stran]
def odvzemi(self, ime):
del self.tovor[ime]
def uravnotezenost(self):
return sum(self.tovor.values())
Celotna rešitev
Še za občutek, kako malo je (lahko) vsega skupaj. :)
from collections import defaultdict
def prelomi(besedilo, sirina):
vrstice = []
for beseda in besedilo.split():
if not vrstice or len(vrstice[-1] + " " + beseda) > sirina:
vrstice.append(beseda)
else:
vrstice[-1] += " " + beseda
return "\n".join(vrstice)
def vojna(s, t):
s_novi = []
t_novi = []
for iz_s, iz_t in zip(s, t):
if iz_s > iz_t:
s_novi += [iz_s, iz_t]
elif iz_t > iz_s:
t_novi += [iz_t, iz_s]
s_novi = s[len(t):] + s_novi
t_novi = t[len(s):] + t_novi
return s_novi, t_novi
def relacije(tekme):
zmagovalci = defaultdict(set)
for kdo, koga in tekme:
zmagovalci[kdo].add(koga)
return zmagovalci
def premaga(kdo, koga, relacije):
return kdo in relacije and (
koga in relacije[kdo]
or any(premaga(slabsi, koga, relacije) for slabsi in relacije[kdo]))
class Kobilica:
def __init__(self):
self.tovor = {}
def dodaj(self, stran, ime, teza):
self.tovor[ime] = teza * (-1 + 2 * stran)
def odvzemi(self, ime):
del self.tovor[ime]
def uravnotezenost(self):
return sum(self.tovor.values())