Pisma sv. Miklavžu

Testi

Testi: testi-pisma-sv-miklavzu.zip

V poddirektoriju trenutnega direktorija se nahaja direktorij pisma, v katerem so otroška pisma Miklavžu. (Torej: svoj program boste pisali v nekem direktoriju, na primer, da bo v datoteki c:\programiranje1\naloga7\resitev.py. Pisma so v poddirektoriju c:\programiranje1\naloga7\pisma, tako da je v njem, recimo c:\prorgamiranje1\naloga7\pisma\ana.txt.) Ime datoteke je vedno sestavljeno iz imena otroka, ki mu sledi .txt. Moja datoteka, recimo, bi bila janez.txt.

V datotekah ni drugega kot seznam stvari (po ena v vsaki vrstici), ki si jih je otrok zaželel. (Otroci so se odločili, da letos ne bodo obremenjevali sv. Miklavža s spiskom obljub, za katere je jasno, da se jih ne bodo držali.) Vsebina datoteke dani.txt je, recimo,

glavnik orglice zvezek

Ogrevalno-obvezni del

Napišite naslednje funkcije:

• preberi_datoteko(ime) prejme ime otroka (npr. "dani") in vrne množico stvari, ki si jih otrok želi. Za to mora prebrati ustrezno datoteko v poddirektoriju "pisma".

  >>> preberi_datoteko("dani") {'orglice', 'zvezek', 'glavnik'}

  Rešitev

  V času, ko je bila naloga zastavljena, bi jo rešili tako:

  def preberi_datoteko(ime): stvari = set() for stvar in open("pisma/{}.txt".format(ime)): stvari.add(stvar.strip("\n")) return stvari

  V času, ko jo je bilo potrebno oddati, pa bi jo že znali pogledati drugače: naloga mora vrniti množico, ki vsebuje vrstice datoteke, ki ji odluščimo \n.

  def preberi_datoteko(ime): return {stvar.strip("\n") for stvar in open("pisma/{}.txt".format(ime))}

  Za najtežjo stvar tule se je, sodeč po mailih obupanih študentov, izkazalo ime datoteke. Če ima trenutni direktorij poddirektorija "pisma" in je znotraj njega datoteka "ana.txt", je potrebno odpreti datoteko "pisma/ana.txt".

  Kadar je datoteka takšna, da je urejena po vrsticah, se jo splača brati z zanko for. Uporabimo lahko read() in jo potem razdelimo po vrsticah s split("\n"), ali pa jo preberemo z readlines()... Tule bi šlo, navadno pa je bolj praktična zanka for, tako kot v gornji rešitvi.

  Kot smo videli na predavanjih, se vsaka vrstica konča z znakom za konec vrstice, "\n". Znebimo se ga s strip("\n").

• pisci() ne dobi nobenih argumentov, vrne pa množico z imeni vseh otrok, ki so napisali pisma Miklavžu.

  >>> imena = pisci() >>> imena {'cilka', 'ema', 'ana', 'dani', 'berta'}

  Rešitev

  Spet, pred predavanji o izpeljanih seznamih, slovarjih in množicah bi se morali s to nalogo mučiti takole: sestavi prazno množico, pojdi prek imen datotek in za vsako ime dodaj v ono množico osnovni del imena, brez končnice (os.path.splitext(ime)[0])).

  def pisci(): imena = set() for ime in os.listdir("pisma"): imena.add(os.path.splitext(ime)[0]) return imena

  Po zadnjem predavanju tole rešimo z enim zamahom.

  def pisci(): return {os.path.splitext(ime)[0] for ime in os.listdir("pisma")}

• zelje(imena) prejme množico imen otrok in vrne slovar, katerega ključi so imena, vrednosti pa množice stvari, ki si jih je zaželel dotični otrok.

  >>> spiski = zelje(imena) >>> spiski {'ana': {'sanke', 'pero', 'zvezek'}, 'cilka': {'notni zvezek', 'lok za violino'}, 'ema': {'copati', 'glavnik'}, 'berta': {'copati', 'zvezek'}, 'dani': {'zvezek', 'orglice', 'glavnik'}}

  Rešitev

  Naredimo prazen slovar. Gremo prek ime in za vsako ime dodamo v slovar nov element: ključ je ime, vrednost pa spisek želja, kakor ga vrne preberi_datoteko(ime).

  def zelje(imena): spiski = {} for ime in imena: spiski[ime] = preberi_datoteko(ime) return spiski

  Gre krajše? Seveda. Samo "opisati" moramo, kar hočemo vrniti: slovar, katerega ključi so imena in vrednosti spiski želja.

  def zelje(imena): return {ime: preberi_datoteko(ime) for ime in imena}

• prestej_stvari(spiski) prejme spiske v obliki, v kateri jih vrača prejšnja funkcija, in vrne slovar, katerega ključi so imena stvari, ki so si jih zaželeli ti otroci, vrednosti pa so število teh stvari. Če so si trije otroci zaželeli zvezek, bo pod ključem zvezek shranjena vrednost 3.

  >>> stvari = prestej_stvari(spiski) {'zvezek': 3, 'glavnik': 2, 'copati': 2, 'pero': 1, 'notni zvezek': 1, 'sanke': 1, 'lok za violino': 1, 'orglice': 1}

  Namesto slovarja je dovoljeno uporabiti tudi kaj, kar je v sorodu z njim in se obnaša enako kot slovar.

  Rešitev

  Naloga več kot očitno namiguje, da je smiselno uporabiti defaultdict ali, če ste nekoliko spretnejši, Counter.

  import collections def prestej_stvari(spiski): zaloge = collections.defaultdict(int) for seznam in spiski.values(): for stvar in seznam: zaloge[stvar] += 1 return zaloge

  Najprej naredimo slovar zaloge s privzeto vrednostjo int (se pravi 0). Nato gremo prek spiska. Spisek je slovar, vendar nas njegovi ključi (imena otrok) ne zanimajo; šli bomo prek spisek.values(). Te vrednosti so množice daril, ki si jih želi posamezni otrok. Gremo prek vsake stvari v vsakem od teh seznamov in prištevamo količino vsake stvari.

  Pa krajše? Tule se malo zaplete. Vsako reč se da napisati v eni vrstici; obstajajo celo jeziki, kjer se drugače sploh ne da programirati. V Pythonu lepo teče vzorec, kjer sestavljamo seznam, slovar ali množico nekih stvari, ki jih dobimo tako, da gremo z zanko prek nečesa. Drug vzorec, ki ga na predavanjih nismo spoznali, je "akumuliranje". No, to ni čisto res, videli smo namreč seštevanje (sum), maksimum in minimum (max, min) ter konjunkcijo in disjunkcijo (all, any). V vseh teh primerih je šla funkcija prek seznama (ali česa podobnega) in "akumulirala" vrednosti v vsoto, minimum, maksimum ali karkoli že. Obstaja pa splošnejši vzorec akumuliranja. Reče se mu "reduce", Python ga pozna, vendar navadno zahteva uporabo lambda-funkcij, o katerih se ne bomo učili, ker v Pythonu niso narejene preveč posrečeno. Nalogo pa vseeno rešímo še v tem duhu - toliko, da boste bolj zagnani videli, da gre. Komentiral pa ne bom.

  from functools import reduce from collections import Counter def prestej_stvari(spiski): return reduce(lambda x, y: x.update(y) or x, spiski.values(), Counter())

• izpisi_stvari(stvari) dobi slovar, ki ga vrača funkcija prestej_stvari in ga izpiše tako, da so stvari poravnana na levo, sledi jim toliko pik, da je skupna dolžina stvari in pik 20, sledi pa število otrok, ki si želi posamezno stvar.

  Rešitev

  Gremo torej prek vseh parov stvari in količin (for stvar, kolicina in stvari.items()) in jih izpišemo. Stvari morajo biti izpisane na 20 mest, poravnane levo, tako, da odvečen prostor zapolnijo pike (:.<20). Količine izpišemo kar tako.

  def izpisi_stvari(stvari): for stvar, kolicina in stvari.items(): print("{:.<20}{}".format(stvar, kolicina))

  Izpis v eni vrstici je nekoliko prisiljen. Gre in včasih počnemo tudi to, a prav tule je nekoliko nesmiseln.

  def izpisi_stvari(stvari): print("\n".join("{:.<20}{}".format(stvar, kolicina) for stvar, kolicina in stvari.items()))

Za ilustracijo, kratek program, ki uporablja te funkcije, bi bil lahko videti takole:

imena = pisci() spiski = zelje(imena) stvari = prestej_stvari(spiski) izpisi_stvari(stvari)

in bi izpisal

notni zvezek........1 sanke...............1 orglice.............1 glavnik.............2 lok za violino......1 copati..............2 zvezek..............3 pero................1

Rešitve vseh nalog

Da še enkrat uvidimo, zakaj je tako uporabno poznati izpeljane sezname, slovarje in množice, ponovno napišimo rešitve vseh nalog.

def zelje(imena): return {ime: preberi_datoteko(ime) for ime in imena} def zelje(imena): return {ime: preberi_datoteko(ime) for ime in imena} from functools import reduce from collections import Counter def prestej_stvari(spiski): return reduce(lambda x, y: x.update(y) or x, spiski.values(), Counter()) def izpisi_stvari(stvari): print("\n".join("{:.<20}{}".format(stvar, kolicina) for stvar, kolicina in stvari.items()))

Dodatna naloga

Kako bi določili podobnost med željami dveh otrok? Takole: pogledali, koliko enakih reči sta si zaželela. To bi delili s številom vseh reči, ki si jih je zaželel eden ali drugi. Za primer vzemimo Berto in Emo: Berta bi rada copate in zvezek. Ema bi rada copate in glavnik. Imata eno skupno željo (copate), vsega skupaj pa sta si želeli tri (različne) stvari (copate, zvezek in glavnik). Podobnost med njima je torej 1/3.

Napišite funkcijo podobnosti(imena), ki dobi seznam imen otrok in vrne tri najbolj podobne. Če si več otrok deli tretje mesto, naj izpiše tudi te. V spodnjem primeru si trije pari delijo mesta od drugega do četrtega, zato funkcija izpiše štiri pare in ne le treh.

Izpis mora biti točno takšen, kot je spodaj: imena so izpisana na deset znakov, pred in za dvopičjem je presledek, prvo ime je poravnano desno, drugo levo. Število je izpisano na dve decimalki in poravnano desno. Imeni v paru sta urejeni po abecedi ("dani : ema" in ne "ema : dani").

berta : ema 0.33 dani : ema 0.25 berta : dani 0.25 ana : berta 0.25

(Opomba: Moodle zafrkava in briše presledke pred levim imenom. Pred imenom, recimo, "dani" v drugi vrstici naj bo šest presledkov.)

Rešitev

def podobnosti(imena): spiski = zelje(imena) podobnosti = [] for ime1 in imena: for ime2 in imena: if ime1 < ime2: zelje1, zelje2 = spiski[ime1], spiski[ime2] podobnosti.append( (len(zelje1 & zelje2) / len(zelje1 | zelje2), ime1, ime2)) podobnosti.sort(reverse=True) if len(podobnosti) >= 3: tretji = podobnosti[2][0] else: tretji = podobnosti[-1][0] for podobnost, ime1, ime2 in podobnosti: if podobnost < tretji: break print("{:>10} : {:<10}{:>.2}".format(ime1, ime2, podobnost))

Gremo prek vseh imen in za vsako ime gremo ponovno prek vseh imen. Par nas zanima le, če je prvo ime po abecedi pred drugim. Na ta način se izognemo temu, da bi večkrat opazovali isti par ali celo primerjali nekoga s samim sabo. Ponavljanju parov se sicer običajno izognemo z

for i, ime1 in enumerate(imena): for ime2 in imena[:i]:

(razmislite, kaj to počne!) tule pa s tem mimogrede in brez hudih kolobocij dosežemo, da je prvo ime v paru po abecedi pred drugim, kot zahteva naloga.

Potem uporabimo, kar nudijo množice. Naloga pravi, da moramo deliti število skupnih želja s številom želja enega ali drugega. Besedilo naloge je nekoliko prikrito povedalo: deliti želimo presek z unijo.

V seznam zložimo terke (podobnost, prvo ime, drugo ime). Ta trik smo že uporabili tudi v preteklosti: pri takšnih terkah, lahko preprosto pokličemo sort(reverse=True) in seznam bo urejen, kot hočemo, torej po padajočih podobnostih.

Trikov pa še ni konec. Izpisati moramo tri najbolj podobne - če si tretje mesto deli več parov, pa jih moramo izpisati toliko več. To uženemo tako, da pogledamo, kako podoben si je tretji par. Namesto zanke prek prvih treh bomo naredili zanko prek vseh, for podobnost, ime1, ime2 in podobnosti:, vendar jo bomo ustavili, čim naletimo na prvega, katerega podobnost je manjša kot podobnost med tretjim parom.

Če bi imeli opravka le z dvema otrokoma, bi imeli le en par (že pri treh otrocih imamo tri). Da funkcija ne bi v tem primeru crknila, si takrat namesto podobnosti tretjega, zapomnimo podobnost zadnjega para (ki je sicer hkrati tudi prvi).