Opravljivke

Bistvo domače naloge je bilo delo s slovarji in množicami. Če veste, kaj je bistvo slovarjev (to, da lahko preverim, ali obstaja določen ključ in da lahko hitro dobim vrednost, ki pripada ključu) ter če veste, kaj se da delati z množicami (računati unije, preseke, razlike...) so bile naloge lahke. Kdor v slovarjih in množicah vidi samo nekoliko drugačne sezname, je naloge vseeno lahko rešil, vendar se je z njimi nekoliko (ali veliko) več mučil. In to, da mora funkcija vračati takšen in takšen slovar, mu ni bilo v pomoč, temveč v napoto.

V nalogi se bomo ukvarjali z nekakšnimi mrežami. Za začetek si lahko predstavljamo, da gre za opravljivke, ki vsako novico sporočijo natančno eni osebi; Ana, na primer, vse izčveka Cilki, Berta prav tako pripoveduje Cilki, Dani Emi, Ema Fanči in Greta Fanči. Cilka in Fanči začuda vse obdržita zase.

Takšno mrežo bomo predstavili s slovarjem

čveke = {"Ana": "Cilka", "Berta": "Cilka", "Dani": "Ema", "Ema": "Fanci", "Greta": "Fanci"}

Naredimo lahko tudi bolj zapletene mreže, na primer spodnji sistem cevi. V eno od cevi vržemo kroglico, zanima pa nas, kje prileti ven. Kroglico lahko vstavimo tudi na kateremkoli križišču ali celo na koncu (vstavimo jo na "o" in prileti iz "o").

Slovar zanjo je takšen:

cevi = {"a": "b", "b": "o", "c": "o", "d": "x", "e": "q", "g": "k", "h": "o", "i": "q", "j": "F", "l": "w", "m": "B", "n": "z", "p": "f", "q": "b", "r": "t", "s": "f", "t": "k", "u": "s", "v": "t", "x": "g", "y": "g", "z": "m", "A": "r", "C": "y", "D": "p", "E": "l", "F": "m", "w": "B"}

Ogrevanje: Od kod kam

Napišite funkcijo kam(cevi, cev). Prvi argument je slovar s sistemom, kot sta, recimo, gornja, drugi pa začetna cev. Če pokličemo, denimo, kam(čveke, "Dani") mora vrniti "Fanči" in če pokličemo kam(cevi, "r") mora vrniti "k".

Gre za osnovno nalogo iz slovarjev: potrebno je preveriti, ali slovar vsebuje določen ključ in priti do vrednosti pri tem ključu. Nekateri ste se ubijali s tem, da ste pisali zanko for prek cevi.items() in s tem počeli ravno tisto, čemur se z uporabo slovarjev izognemo: slovarje imamo prav zato, da lahko na preprost način pridemo do tistega, kar je shranjeno pod določenim ključem.

Sam postopek, ki ste ga morali sprogramirati, je takšen. Dokler podana cev kam vodi (kar vemo po tem, da se pojavi med ključi v slovarju, kar preverimo s cev in cevi), gremo v to cev (cev = cevi[cev]). Ko je konec, vrnemo cev, kjer smo se ustavili (return cev).

def kam(cevi, cev): while cev in cevi: cev = cevi[cev] return cev

Kot sem napisal tudi na forumu, so si nekateri zapletli življenje z metodo get, takole

def kam(cevi, cev): while cevi.get(cev) != None: cev = cevi.get(cev) return cev

Metodo get uporabim takrat, predvsem takrat in skoraj samo takrat, kadar želim dodati še privzeto vrednost. V gornjem kontekstu pa je le nerodna.

Nekateri (pravzaprav večina) ste uvedli "trenutno" cev:

def kam(cevi, cev): trenutna = cev while trenutna in cevi: trenutna = cevi[trenutna] return trenutna

Ni narobe. Potrebno pa tudi ne.

Ocena 6: Koliko kam

Napišite funkcijo koliko_kam(cevi, zacetne), ki dobi slovar s sistemom in seznam začetnih pozicij ter vrne slovar, ki pove, kolikokrat smo končali na določenem mestu. Če pokličemo, recimo koliko_kam(čveke, ["Ana", "Ana", "Greta", "Berta", "Cilka"]), mora vrniti {"Cilka": 4, "Fanci": 1}.

Tole je klasična naloga iz slovarjev: preštevanje. Seveda je zelo koristilo, če ste se spomnili na defaultdict. Mislim, da sem vsaj vsakemu, ki je pisal po nasvet, svetoval, naj ga uporabi.

Še en razlog, zakaj sem vam dal to nalogo, je, da se učite uporabiti funkcije, ki jih že imate. Tisti, ki v tej funkciji niso klicali funkcije kam, ki so jo napisali v prejšnji nalogi, so morali tule ponoviti vse iz prejšnje naloge, zato je bila funkcija bolj zapletena, kot bi lahko bila. In z njo ste se bolj mučili. Preprosta rešitev je torej:

def koliko_kam(cevi, zacetne): koliko = defaultdict(int) for cev in zacetne: koliko[kam(cevi, cev)] += 1 return koliko

Grem prek vseh podanih cevi, za vsako ugotovim, kam vodi in pri tej, slednji cevi, povečam števec za 1.

Malenkost daljša varianta je

def koliko_kam(cevi, zacetne): koliko = defaultdict(int) for cev in zacetne: kam_vodi = kam(cevi, cev) koliko[kam_vodi] += 1 return koliko

Če se niste spomnili na default_dict, ste morali narediti nekaj takšnega:

def koliko_kam(cevi, zacetne): koliko = {} for cev in zacetne: kam_vodi = kam(cevi, cev) if kam_vodi not in koliko: koliko[kam_vodi] = 1 else: koliko[kam_vodi] += 1 return koliko

Ocena 7: Najpogostejša

Napišite funkcijo najpogostejsa(cevi, zacetne), ki deluje podobno kot prejšnja, le da vrne najpogostejši izhod. Če pokličemo najpogostejsa(čveke, ["Ana", "Ana", "Greta", "Berta", "Cilka"]), mora vrniti "Fanci".

Domače naloge so en dolgčas. Tudi tole ste že videli: poiskati ključ, ki pripada največji vrednosti. Če je niste videli v točno tej obliki, ste jo pa v kakšni drugi: opazovati moramo velikost nečesa, vrniti pa nekaj, na kar se ta velikost nanaše.

Vzorec ste videli že večkrat. Tule je ena od izvedenk.

def najpogostejsa(cevi, zacetne): naj = None kolikam = koliko_kam(cevi, zacetne) for katera, koliko in kolikam.items(): if naj is None or koliko > kolikam[naj]: naj = katera return naj

V začetku postavi naj na None, kar mi bo povedalo, da nisem pogledal še nobene cevi. Potem izračunam, koliko jih gre kam (pri čemer seveda uporabim prejšnjo funkcijo). Nato grem čez vse pare končnih cevi in njihovih števcev. V pogoju poglejmo najprej drugi del, koliko > kolikam[naj]: če je v "to" končno cev (katera) prišlo več krogel kot v tisto, v katero jih je prišlo največ, si zapomnim, da jih je prišlo največ v to (naj = katera). To bi bilo lepo in prav, samo za prvo cev ne deluje. Na kaj naj postavim naj v začetku? Ena možnost je torej narediti, kot smo naredili: v začetku ga postavimo na None in potem še preden preverimo ali je koliko > kolikam[naj], preverimo, ali je naj slučajno None. Če je, potem si seveda zapomnimo to cev kat najpopularnejšo, saj je pač prva doslej.

Mimogrede, nisem napisal naj == None temveč naj is None. Kakšna je razlika, smo se učili takrat, ko smo risali škatlice. V tem primeru je v bistvu ni. Po nekih pravilih lepega vedenja v Pythonu pa je zaželeno, da takrat, kadar imamo samo en objekt določene vrste (takšni so, recimo, None, False in True - vsi Trueji, recimo, niso samo enaki Trueji temveč celo isti Trueji) uporabljamo is in ne ==. Samo toliko, da veste in da vas ne bo začudilo, ko me boste videli početi to reč. Če boste sami uporabljali ==, ni nič narobe.

Ocena 8: Vir in ponor

Napišite funkciji zacetne(cevi) in koncne(cevi). Prva naj vrne množico vseh cevi, ki nimajo vhodov, druga vse, ki so na koncu. Tako mora zacetne(čveke) vrniti {"Ana", "Berta", "Dani", "Greta"}, koncne(čveke) pa {"Cilka", "Fanči"}.

Tale je pa najpreprostejša - če vemo, da so začetne cevi vse tiste, ki se pojavljajo med ključi, ne pa tudi med vrednostmi, končne pa tiste, ki se med vrednostmi in ne med ključi. (Razmislite, pa boste videli, da je tako. Poleg tega sem to, se mi zdi, povedal na predavanjih. ;)

Takšne reči se lepo pove z množicami. Ergo,

def zacetne(cevi): return set(cevi.keys()) - set(cevi.values()) def koncne(cevi): return set(cevi.values()) - set(cevi.keys())

Osebno mi je sicer všečnejše brez nepotrebnega keys().

def zacetne(cevi): return set(cevi) - set(cevi.values()) def koncne(cevi): return set(cevi.values()) - set(cevi)

Ta naloga je bila v bistvu naloga, ki je preverjala, ali se spomnite, kaj vse se da narediti z množicami. Tisti, ki se ne, ste si sami krivi, če ste se ubijali s kakšnimi groznimi zankami.

Ocena 9: Viri

Napišite funkcijo viri(cevi), ki vrne slovar, katerega ključi so končne cevi, vrednosti pa množice vseh točk, ki vodijo v to cev. V primeru opravljivk nas bosta ključa tisti dve, ki držita jezik za zobmi, pripadajoči vrednosti pa množici tistih, ki jih zalagata (posredno ali neposredno) z informacijami. Torej, viri(čveke) mora vrniti {"Cilka": {"Ana", "Berta", "Cilka"}, "Fanci": {"Dani", "Ema", "Fanci", "Greta"}}.

V tej nalogi ste morali kombinirati množice in slovarje. Spet vam je lahko zelo pomagal defualtdict.

Kar moramo narediti, je preprosto, le v pravo smer moramo razmišljati. Nekateri ste začeli s končnimi cevmi in razmišljali, na kakšne načine je mogoče priti do njih. Za to smer je potrebno obračati slovar in se iti rekurzijo (ne čisto nujno, ampak drugi načini so lahko še bolj zoprni).

Veliko lažje pa je v drugo smer: za vsako cev - bodisi začetno, končno ali karkoli vmes - pogledamo, kam pelje. Potem v množico, ki pripada tisti kam-pelje cevi dodamo cev, iz katere smo začeli.

def viri(cevi): v = defaultdict(set) for zacetek in cevi.keys() | cevi.values(): v[kam(cevi, zacetek)].add(zacetek) return v

Če vam ni padlo v oči, vas opozarjam na nenavadni: cevi.keys() | cevi.values(). To je videti kot unija množic - vendar cevi.keys() in cevi.values() vendar nista množici! Kaj je to, bomo izvedeli prav ta teden.

Ocena 10: Zapiši in beri

Napišite funkciji zapisi(cevi) in preberi(s). Prva dobi cevi in jih zapiše v obliki niza, takole:

Ana>Cilka Berta>Cilka Dani>Ema Ema>Fanci Greta>Fanci

Vrstni red vrstic v nizu je poljuben. Druga funkcija preberi(s) kot argument dobi prav takšen niz in kot rezultat vrne slovar.

Tole je pa bolj tehnična zadeva, saj ne gre toliko za slovarje kot za sestavljanje in razkopavanje nizov.

def zapisi(cevi): res = "" for vir, izhod in cevi.items(): res += "{}>{}\n".format(vir, izhod) return res def preberi(s): cevi = {} for pot in s.splitlines(): vir, izhod = pot.split(">") cevi[vir] = izhod return cevi
Ultime modifiche: mercoledì, 7 maggio 2014, 01:05