Izpit je bil sestavljen takole:

1. Najprej lihi: delo s seznami; spreminjanje seznama, podanega kot argument (imenski prostori...)
2. Binarno: rekurzija
3. Dopisovalci: delo s slovarji in množicami, malo telovadbe s pogoji in zankami
4. Zaporniki: seznami, množice, telovadba z zankami
5. Blok: objektno programiranje, seznami, zanke

Najprej lihi

Najprej dolgočasna rešitev. Pripravimo dva seznama, enega za lihe, drugega za sode. Gremo čez podani seznam in mečemo liha števila v enega, soda v drugega. Nato zamenjamo vsebino podanega seznama z vsoto prvega in drugega.

def najprej_lihi(s): lihi = [] sodi = [] for e in s: if e % 2 == 0: sodi.append(e) else: lihi.append(e) s[:] = lihi + sodi

Da se ne bo kdo pritoževal, da je naloga dolgočasna in, predvsem, neduhovita, se znebimo if-a. Oba seznama mimogrede postavimo v nov seznam in append-ajmo bodisi v enega bodisi v drugega.

def najprej_lihi(s): lihi = [] sodi = [] for e in s: [sodi, lihi][e % 2].append(e) s[:] = lihi + sodi

Zdaj je [sodi, lihi][e % 2] isto kot sodi, če je e % 2 enako 0, in isto kot lihi, če je e % 2 enako 1.

Namesto da bi sodi in lihi vsakič znova tlačili v seznam (ki smo ga naredili le zato, da smo se znebili if-a), lahko kar ves čas delamo s skupnim seznamom.

def najprej_lihi(s): sodilihi = [[], []] for e in s: sodilihi[e % 2].append(e) s[:] = sodilihi[1] + sodilihi[0]

Zdaj pa lepše rešitve. Če poznamo izpeljane sezname, brez težav sestavimo seznam lihih in seznam sodih števil ter ju seštejemo. V enem zamahu.

def najprej_lihi(s): s[:] = [x for x in s if x % 2 == 1] + [x for x in s if x % 2 == 0]

Zmagovalno rešitev pa je prispeval asistent Možina. Seznam s preprosto uredimo po ostanku po deljenju z 2.

def najprej_lihi(s): s.sort(key=lambda x: x % 2, reverse=True)

Ali, enako lepo,

def najprej_lihi(s): s.sort(key=lambda x: 1 - x % 2)

Zakaj ne bi naloge rešili še rekurzivno?

def izberi(s, o): if not s: return [] elif s[0] % 2 == o: return [s[0]] + izberi(s[1:], o) else: return izberi(s[1:], o) def najprej_lihi(s): s[:] = izberi(s, 1) + izberi(s, 0)

Funkcija najprej_lihi bo težko rekurzivna, saj ne vrača ničesar, temveč spreminja vrednosti argumentov. Tudi takšne funkcije so lahko in pogosto so rekurzivne, ampak tule ... nekako ni prikladno. Pač pa pokiče rekurzivno funkcijo izberi, ki ji podamo seznam in z drugim argumentom, o, povemo, ali hočemo tiste, pri katerih je ostanek po daljenju z 2 lih ali sod.

Funkcija izberi kar kliče po tem, da jo zapišemo krajše.

def izberi(s, o): return s and ([s[0]] * (s[0] % 2 == o) + izberi(s[1:], o)) def najprej_lihi(s): s[:] = izberi(s, 1) + izberi(s, 0)

Binarno

Če je število enako 0 ali 1, vrnemo to število, pretvorjeno v niz. Sicer pa število delimo z 2 in ga spremenimo v dvojiško, na konec pa pripnemo zadnjo števko - dobimo jo kot ostanek po deljenju števila z 2.

def binarno(n): if n <= 1: return str(n) return binarno(n // 2) + str(n % 2)

Kdor rad svinja, naredi tako.

def binarno(n): return (n > 1 and binarno(n // 2) or "") + str(n % 2)

Dopisovalci

Tole je vaja iz dela s slovarji in množicami.

def dopis(src, dst, relacije): relacije[src].add(dst) def najzgovornejsi(relacije): def deg(k): return len(relacije[k]) return max(relacije, key=deg) def vse_osebe(relacije): vsi = set(relacije) for dst in relacije.values(): vsi |= dst return vsi def neznanci(src, relacije): return vse_osebe(relacije) - relacije[src] - {src}

Čim razumemo, kaj naj bi bilo v slovarju (in če smo že kdaj uporabljali slovarje s privzetimi vrednostmi), je dopis trivialna: le dopisovalca doda.

Najzgovornejši ponavlja niškolikokrat izvedeni dril: iskanje največjega elementa. Gornja rešitev je še nekako v dosegu tega, kar smo počeli pri Programiranju 1 (čeprav uporabe argumenta key pri funkciji max res nismo posebej kazali. Kdor ne zna tako, pa je še vedn lahko naredil tako, kot smo sto in enkrat naredili na predavanjih, vajah in v domačih nalogah. Recimo tako:

def najzgovornejsi(relacije): naj = None for kdo, komu in relacije.items(): if naj is None or len(komu) > len(relacije[naj]): naj = kdo return naj

Funkcija vse_osebe le zloži v isto množico vse ključe in vse vrednosti. Ključe lahko dobi kar s set(relacije), za množice se mora sprehoditi prek vrednosti.

Neznanci pa so vsi, razen tistih, ki jim je dotični pisal in dotičnega samega.

V praksi bi resen programer te funkcije napisal takole:

def dopis(src, dst, relacije): relacije[src].add(dst) def najzgovornejsi(relacije): return max(relacije, key=lambda k: len(relacije[k])) from functools import reduce def vse_osebe(relacije): return reduce(set.union, relacije.values(), set(relacije)) def neznanci(src, relacije): return vse_osebe(relacije) - relacije[src] - {src} def najzgovornejsi(relacije): return max(relacije, key=lambda k: len(relacije[k]))

Sogovorniki

Naloga sogovorniki je vaja iz uporabe seznamov in množic (ter malo zank in pogojev). Poleg tega je, upam, pokazala, da se splača slediti objavljenim rešitvam domačih nalog. Je namreč silno funkciji ni_sosednjih, ki jo je bilo potrebno narediti pri domači nalogi Pike (tam je predstavljala sicer delček naloge za oceno 10 - vendar le preprostejši delček). Kdor je bral rešitve domačih nalog in se je spomnil na to nalogo, je lahko rešitev praktično prepisal, le da tam preverjamo, ali obstajajo sosedi z isto številko (no, v našem primeru s skupnim jezikom), tule pa ne preverjamo obstoja temveč štejemo.

Kako ugotovimo, ali dva soseda govorita kak skupni jezik, pa je namignila naloga: presek množic jezikov mora biti neprazen.

def sogovorniki(s): ista = 0 for v in s: for i, j in zip(v, v[1:]): if set(i) & set(j): ista += 1 for v1, v2 in zip(s, s[1:]): for i, j in zip(v1, v2): if set(i) & set(j): ista += 1 return ista

Če vemo, da je True isto kot 1 in False isto kot 0; če vemo, da se logičnim vrednostim reče bool; če vemo, da objekte tipa str, int, float, list, Potnik dobimo tako, da pokličemo funkcije (tipe, konstruktorje - imenujte jih kakor jih hočete) str, int, float, list, Potnik, se rešitev še nekoliko poenostavi.

def sogovorniki(s): ista = 0 for v in s: for i, j in zip(v, v[1:]): ista += bool(set(i) & set(j)) for v1, v2 in zip(s, s[1:]): for i, j in zip(v1, v2): ista += bool(set(i) & set(j)) return ista

To vodi v rešitev, ki le prešteje, kar je treba.

def sogovorniki(s): return sum(bool(set(i) & set(j)) for v in s for i, j in zip(v, v[1:])) + \ sum(bool(set(i) & set(j)) for v1, v2 in zip(s, s[1:]) for i, j in zip(v1, v2))

Ali pa sestavimo vse komunicirajoče pare in jih preštejemo.

def sogovorniki(s): return len([(i, j) for v in s for i, j in zip(v, v[1:]) if set(i) & set(j)] + [(i, j) for v1, v2 in zip(s, s[1:]) for i, j in zip(v1, v2) if set(i) & set(j)])

Blok

Ko se enkrat odločimo, kaj bomo shranjevali v razredu Blok, so vse metode le začetniške vaje iz seznamov. Metoda stanovalec bo morala vračati imena stanovalcev v določenem nadstropju, torej bo očitno potrebno shranjevati imena ljudi po nadstropjih. Nadstropja so oštevilčena od 0 naprej, torej bo primeren kar navaden seznam.

class Blok: def __init__(self, nadstropij): self.stanovalci = [None] * nadstropij def vseli(self, nadstropje, ime): if self.stanovalci[nadstropje] is not None: return False self.stanovalci[nadstropje] = ime return True def izseli(self, nadstropje): self.stanovalci[nadstropje] = None def kamorkoli(self, ime): for i in range(len(self.stanovalci) - 1, -1, -1): if self.stanovalci[i] is None: self.stanovalci[i] = ime return True return False def stanovalec(self, nadstropje): return self.stanovalci[nadstropje]

Vse skupaj

Celotna rešitev izpita, kot bi jo pričakovali od poprečnega študenta, ki se ni pretirano poglobil v izpeljane sezname in podobne trike, zna pa solidno programirati, je takšna.

# 1 def najprej_lihi(s): lihi = [] sodi = [] for e in s: if e % 2 == 0: sodi.append(e) else: lihi.append(e) s[:] = lihi + sodi # 2 def binarno(n): if n <= 1: return str(n) return binarno(n // 2) + str(n % 2) # 3 def dopis(src, dst, relacije): relacije[src].add(dst) def najzgovornejsi(relacije): naj = None for kdo, komu in relacije.items(): if naj is None or len(komu) > len(relacije[naj]): naj = kdo return naj def vse_osebe(relacije): vsi = set(relacije) for dst in relacije.values(): vsi |= dst return vsi def neznanci(src, relacije): return vse_osebe(relacije) - relacije[src] - {src} # 4 def sogovorniki(s): ista = 0 for v in s: for i, j in zip(v, v[1:]): if set(i) & set(j): ista += 1 for v1, v2 in zip(s, s[1:]): for i, j in zip(v1, v2): if set(i) & set(j): ista += 1 return ista # 5 class Blok: def __init__(self, nadstropij): self.stanovalci = [None] * nadstropij def vseli(self, nadstropje, ime): if self.stanovalci[nadstropje] is not None: return False self.stanovalci[nadstropje] = ime return True def izseli(self, nadstropje): self.stanovalci[nadstropje] = None def kamorkoli(self, ime): for i in range(len(self.stanovalci) - 1, -1, -1): if self.stanovalci[i] is None: self.stanovalci[i] = ime return True return False def stanovalec(self, nadstropje): return self.stanovalci[nadstropje]