Rešitve s komentarji

Rešitve v enem kosu

Da si ustvarimo vtis o tem, koliko programiranja so zahtevale izpitne naloge, je tule rešitev celotnega izpita v obliki, kakršno smo pričakovali. Komentarji in nekoliko drugačne različice rešitev sledijo spodaj.

def stevilo_sosedov(s): res = [] for i in range(len(s) - 1): res.append(s[i - 1] + s[i + 1]) res.append(s[0] + s[-2]) return res def trki(xs): d = {} for x in xs: k = skrij(x) if k in d: return d[k], x d[k] = x from itertools import permutations def preveri_zaporedje(s): for i in range(len(s) - 1): if not set(str(s[i])) & set(str(s[i + 1])): return False return True def postar(naslovi): for s in permutations(naslovi): if preveri_zaporedje(s): return True return False def sester_pod(ime, rodovnik): otroci = rodovnik[ime] sester = len([otrok for otrok in otroci if otrok.split()[0][-1] == "a"]) if sester and sester == len(otroci): sester -= 1 return sester def najvec_sester(ime, rodovnik): return max([sester_pod(ime, rodovnik)] + [najvec_sester(otrok, rodovnik) for otrok in rodovnik[ime]]) from collections import defaultdict class Blagajna: def __init__(self): self.vsebina = defaultdict(int) def dodaj(self, bankovec): self.vsebina[bankovec] += 1 def vzemi(self, bankovec): if not bankovec in self.vsebina: return False self.vsebina[bankovec] -= 1 if not self.vsebina[bankovec]: del self.vsebina[bankovec] return True def bilanca(self): return sum(bankovec * kosov for bankovec, kosov in self.vsebina)

Komentarji rešitev

Sosedi

Gornja rešitev je najbolj preprosta. Naredimo nov seznam gremo od začetka do (skoraj) konca seznama in v vsakem koraku v novi seznam dodamo vsoto prejšnjega in naslednjega elementa.

def stevilo_sosedov(s): res = [] for i in range(len(s) - 1): res.append(s[i - 1] + s[i + 1]) res.append(s[0] + s[-2]) return res

Popaziti je potrebno le na robove. Ko je i enak 0, s tem ni težav, saj z s[-1] dobimo ravno zadnji element. Ko bi bil i na koncu seznama, pa bi z s[i + 1] dobili napako. In tega nočemo. ;) Zato smo pustili i le do len(s) - 1 in zadnji element dodali šele na koncu.

Druga rešitev je uporaba modula, s katerim se i + 1, ko je enak dolžini seznama, spremeni v 0.

def stevilo_sosedov(xs): ys = [] for i in range(len(xs)): ys.append(xs[i - 1] + xs[(i + 1) % len(xs)]) return ys

Manj potrpežljivi rešijo nalogo takole:

def stevilo_sosedov(s): return [s[i - 1] + s[i + 1] for i in range(len(s) - 1)] + [s[0] + s[-2]]

ali takole

def stevilo_sosedov(s): return [s[i - 1] + s[(i + 1) % len(s)] for i in range(len(s) - 1)]

Trki

Naloga preverja, ali znamo uporabiti slovar. Vsako skrito besedo, ki jo naračunamo, vtaknemo v slovar - skrita beseda je ključ, vrednost pa beseda, iz katere jo dobimo. Vsakič, ko pridelamo novo skrito besedo, preverimo, ali smo jo že videli (ključi) in vrnemo besedo, iz katere je nastala (vrednost, ki pripada temu ključu).

def trki(xs): d = {} for x in xs: k = skrij(x) if k in d: return d[k], x d[k] = x

Slaba rešitev je takšna:

def trki(xs): for beseda1 in xs: for beseda2 in xs: if beseda1 != beseda2 and skrij(beseda1) == skrij(beseda2): return beseda1, beseda2

Za 10000 besed mora bo ta funkcija 200000000-krat poklicala funkcijo skrij. Tudi če jo izboljšamo tako, da drugo besedo išče le med besedami, ki so na seznamu pred prvo, tako da bo vsak par pogledala le enkrat,

def trki(xs): for i, beseda1 in enumerate(xs): for beseda2 in xs[:i]: if skrij(beseda1) == skrij(beseda2): return beseda1, beseda2

nismo pridobili veliko, saj je program le dvakrat hitrejši - namesto dvesto milijonkrat bo funkcij skrij klical sto milijonkrat (točneje, 99990000-krat). Program, ki uporabi slovar, jo kliče desettisočkrat. Seveda pa zato porabi več pomnilnika.

Program, ki bi znal iskati tovrstne trke - pri določenih vrstah funkcije skrij, bi zelo zanimal NSA - pa še marsikoga drugega. Morda pa ga že imajo?

Poštar iz Hamiltona

Najprej preverjanje zaporedja. I-ti element mora imeti vsaj eno skupno števko z elementom i + 1. Ali je tako, preverimo tako, da element spremenimo v niz (to je, niz števk), tega pa v množico. Izračunati je potrebno presek teh dveh množic, set(str(s[i])) & set(str(s[i + 1])). Če je prazen, ni skupne števke. Reč preverimo za vse i do predzadnjega (ki ga primerjamo z zadnjim).

def preveri_zaporedje(s): for i in range(len(s) - 1): if not set(str(s[i])) & set(str(s[i + 1])): return False return True

Malenkost bolj Pythonovska rešitev uporabi zip.

def preveri_zaporedje(s): for x, y in zip(s, s[1:]): if not set(str(x)) & set(str(y)): return False return True

Zdaj le preskusimo vse možne permutacije in vrnemo True čim naletimo na kakšno pravilno.

from itertools import permutations def postar(naslovi): for s in permutations(naslovi): if preveri_zaporedje(s): return True return False

Poštar je iz Hamiltona, ker išče Hamiltonovo pot po grafu, katerega točke so hiše, dve hiši pa sta povezani, če imata skupno števko. Problem je NP-poln, kar, kot boste izvedeli v drugem letniku, za njegovo reševanje nimamo (bistveno) boljši postopkov kot je ta, ki ste ga ubrali v domači nalogi.

Največ sester

Najprej funkcija, ki pove, koliko sester ima najbolj osestreni potomec podane osebe. Prešteti moramo, koliko hčera ima oseba. Če ima toliko hčera, kolikor ima otrok, ima vsaka od njih toliko sester, kolikor je otrok - 1, saj ni sestra sama sebi. Če pa je med otroki tudi kak sin, ima toliko sester, kolikor je žensk. Z drugimi besedami,

def sester_pod(ime, rodovnik): otroci = rodovnik[ime] sester = len([otrok for otrok in otroci if otrok.split()[0][-1] == "a"]) if sester and sester == len(otroci): sester -= 1 return sester

Odtod gre po znanem vzorcu: najprej pogledamo, koliko sester ima najbolj osestreni otrok podane osebe, nato povprašamo otroke po najbolj osestrenih ljudeh iz njihovih rodbin in vrnemo maksimum vsega skupaj.

def najvec_sester(ime, rodovnik): najvec = sester_pod(ime, rodovnik) for otrok in rodovnik[ime]: sester = najvec_sester(otrok, rodovnik) if sester > najvec: najvec = sester return najvec

Ali, krajše

def najvec_sester(ime, rodovnik): return max([sester_pod(ime, rodovnik)] + [najvec_sester(otrok, rodovnik) for otrok in rodovnik[ime]])

Tule pa je še druga, elegantna rešitev, ki uporablja eno samo funkcijo.

def najvec_sester(ime, rodovnik): xs = [0] hcerk = 0 for otrok in rodovnik[ime]: xs.append(najvec_sester(otrok, rodovnik)) if otrok.split()[0][-1] == 'a': hcerk += 1 return max(xs + [hcerk - (len(rodovnik[ime]) == hcerk)])

Blagajna

O blagajni pa ni kaj prida povedati. Potrebovala bo slovar, v katerem shranjuje, kakšne bankovce ima. Najbolj prikladen je defaultdict, seveda pa bi šlo tudi z običajnim slovarjem. Vse, kar ostane (če znamo pisati metode, seveda), je preprosto delo s slovarji.