Rešitve in razlaga

Izpit je bil sestavljen takole:

1. Vstavi teže: telovadba z zankami, indeksiranje, pogoji
2. Trgovanje: zanke in množice; vzorec "vsi" in "kdorkoli"
3. Izmenjavanje: rekurzija
4. Figura: seznami seznamov, indeksiranje in splošna programerska spretnost
5. Blok: objektno programiranje

Vstavi teže

Tole je predvsem naloga iz spretnega dela z indeksi: eden se pomika naprej po seznamu imen, drugi pa se premakne na naslednjo težo le, ko se mora: vsakič, ko v prvem seznamu naletimo na žensko ime, vzamemo element iz drugega seznama.

def vstavi_teze(osebe, teze): i = 0 for j, ime in enumerate(osebe): if ime[-1] != "a": osebe[j] = teze[i] i += 1

Še kar dobra ideja bi bila, da se znebimo drugega števca tako, da teže pobiramo iz seznama tež - vzamemo in pobrišemo, z metodo pop.

def vstavi_teze(osebe, teze): for j, ime in enumerate(osebe): if ime[-1] != "a": osebe[j] = teze.pop(0)

Če naredite tako, testi javijo napako:

- [] + [87, 86, 75] : Ne spreminjaj seznama tež!

Seznama tež ne smemo spreminjati. Pač pa lahko naredimo kopijo in spreminjamo le-to.

def vstavi_teze(osebe, teze): teze = teze.copy() for j, ime in enumerate(osebe): if ime[-1] != "a": osebe[j] = teze.pop(0)

Tako pridemo do naslednje zanimive rešitve z izpeljanimi seznami.

Trgovanje

Ali obstaja kdo, ki menja to za ono, lahko preverimo tako, da se zapeljemo čez ponudbe in takrat, ko najdemo takšno, ki ustreza, vrnemo True. Če ni nobene, vrnemo False.

def obstaja(dam, dobim, ponudbe): for dobi, da in ponudbe: if dam in dobi and dobim in da: return True return False

Menjave gredo ravno obratno: čim najdem takšno, ki ni možna, vrnem False. Če takšne ni, vrnem True.

def menjave(zaporedje, ponudbe): for dam, dobim in zip(zaporedje, zaporedje[1:]): if not obstaja(dam, dobim, ponudbe): return False return True

Tu gre za dva vzorca, ki ju gledamo že od prvih tednov programiranja, odkar smo, recimo, iskali praštevila. Ko smo se učili o izpeljanih seznamih in generatorjih, smo izvedeli, da ta vzorec nadomestimo z generatorjem, ki ga damo funkciji any ali all. Če torej znamo uporabljati generatorje, se funkciji poenostavita v

def obstaja(dam, dobim, ponudbe): return any(dam in dobi and dobim in da for dobi, da in ponudbe) def menjave(zaporedje, ponudbe): return all(obstaja(dam, dobim, ponudbe) for dam, dobim in zip(zaporedje, zaporedje[1:]))

Izmenjavanje

Tole bi moral biti deja vu: nekoč smo preverjali, ali seznam izmenično vsebuje soda in liha števila.

Če ima seznam manj kot dva elementa, je v redu. Sicer morata biti prva dva elementa različna (to, ali se prvi konča z a mora biti različno od tega, ali se drugi), izmenjujoč pa mora biti tudi ostanek.

def izmenjavanje(imena): return len(imena) < 2 or (imena[0][-1] == "a") != (imena[1][-1] == "a") and izmenjavanje(imena[1:])

Preprostejši, a manj eleganten način je napisati tri funkcije. Ena pravi, da se na seznamu izmenjujejo moški in ženske (začenši z moškim), če je seznam praze, ali pa je prvi moški, v ostanku pa se izmenjujejo ženske in moški. Druga funkcija pravi obratno, le z zamenjanima spoloma. Funkciji torej kličeta ena drugo, zato je to rekurzija. Tretja funkcija pa vrne True, če se v seznamu izmenjujejo bodisi moški in ženske bodisi ženske in moški.

def moski_zenske(imena): return not imena or imena[0][-1] != "a" and zenske_moski(imena[1:]) def zenske_moski(imena): return not imena or imena[0][-1] == "a" and moski_zenske(imena[1:]) def izmenjavanje(imena): return moski_zenske(imena) or zenske_moski(imena)

Figura

Tole zahteva nekaj spretnosti. Funkcijo spremeni_smer lahko napišemo z goro ifov, s slovarji... ali pa s preprostim nizom. Ker je manj elegantnih rešitev kolikor hočemo, bomo pokazali le slednjo, elegantno.

# Tole ne deluje čisto pravilno def spremeni_smer(smer, obrat): smeri = "URDL" return smeri[smeri.index(smer) + {"F": 0, "L": -1, "R": 1}[obrat]]

V nizu je seznam smeri v smeri urinega kazalca. Ko se vrtimo v desno, gremo po tem seznamu naprej (gor, desno, dol, levo); ko se vrtimo levo, gremo po njem nazaj (levo, dol, desno, gor). Pogledamo indeks trenutnega znaka smeri.index(smer), k njem prištejemo 0, -1 ali 1, odvisno od tega, kam se vrtimo ({"F": 0, "L": -1, "R": 1}[obrat]). Potem iz niza vzamemo ustrezno črko - tisto, z novim indeksom.

Popaziti je potrebno le na robove. Če sem na 0 in grem levo, pridem na -1, kar je zadnji znak in vse je lepo. Če sem na zadnjem znaku (3) in grem desno, pa pridem na 4; moral bi na 0. To lahko rešim tako, da po prištevanju izračunamo ostanek po deljenju s 4, kar mi spremeni 4 v 0.

def spremeni_smer(smer, obrat): smeri = "URDL" return smeri[(smeri.index(smer) + {"F": 0, "L": -1, "R": 1}[obrat]) % 4]

Taka rešitev zahteva nekaj zaloge programerskih trikov. Na srečo pa naloga tudi za tiste, ki jih nimajo, ni tako težka, le malenkost daljši program bodo napisali.

Drugo funkcijo, smo letos pisali ničkolikokrat - z želvami, s potniki... Včasih smo uporabljali ife, včasih slovarje, morda smo omenili rešitev s kompleksnimi števili. Tokrat naredimo nekaj sorazmerno izvirnega.

def korak(x, y, smer): return (x + {"U": 0, "D": 0, "L": -1, "R": 1}[smer], y + {"U": -1, "D": 1, "L": 0, "R": 0}[smer])

Potovanje je zdaj preprosto: z zanko while preganjamo figuro okrog, dokler ne pade čez rob plošče ali pa se polje ponovi. Obiskana polja bomo hranili v seznamu, ki ga moramo vrniti. Manjše težave nam povzroča le to, da je v seznamu tudi zadnje obiskano polje. Tega se rešimo tako, da namesto (x, y) not in pot preverjamo (x, y) not in pot[:-1]. Potovanje se torej konča, ko trenutno polje najdemo v seznamu vseh polj, razen zadnjega dodanega (ki je seveda trenutno).

Kdor se ni spomnil tega trika, lahko uporabi tudi enega, ki smo ga spoznali na predavanjih: ali pot vsebuje same unikatne elemente, preverimo tako, da spremenimo seznam v množico in pogledamo, ali sta enako dolga, len(pot) == len(set(pot)).

def potuj(x, y, smer, plosca): pot = [(x, y)] while 0 <= x < len(plosca[0]) and 0 <= y < len(plosca) and (x, y) not in pot[:-1]: smer = spremeni_smer(smer, plosca[y][x]) x, y = korak(x, y, smer) pot.append((x, y)) return pot

Knjižnica

Odločiti se moramo, kako bomo shranjevali knjige. Zaradi metode vrni je najbolj priročen slovar, saj nam tako ne bo potrebno po seznamu iskati knjige z danim naslovom.

Razred je potem preprost: konstruktor pripravi množico, izposodi doda knjigo v slovar, vrni jo pobriše, izposojeno vrne množico ključev. Za računanje zamudnine gremo prek vrednosti v slovarju in za vsako zamujeno knjigo k zamudnini prištejemo število dni zamude.

class Knjizica: def __init__(self): self.knjige = {} def izposodi(self, knjiga, dan): self.knjige[knjiga] = dan def vrni(self, knjiga): del self.knjige[knjiga] def izposojeno(self): return set(self.knjige) def zamudnina(self, danes): zamudnina = 0 for dan_izposoje in self.knjige.values(): if danes - dan_izposoje > 21: zamudnina += danes - dan_izposoje - 21 return zamudnina

Zadnjo metodo bi lahko napisali tudi s sum in generatorjem, vendar s tem ni bi nič posebnega pridobili.