Parčkanje 2: Opravljivka

Testi

testi-opravljivka.py

Naloga

Vaška opravljivka je napisala takšno poročilo:

Na vratih sta se prva pojavila Ana in Peter, menda "slučajno". Peter se je sicer več vrtel okrog Nives. Kasneje sta Ana in Peter skupaj sedela na klopci, vendar je bil zraven tudi Benjamin. Benjamin in Ana sta skupaj pila čaj. Peter in Tina sta tudi pila čaj. Peter in Ana pravzaprav tisti večer sploh nista bila več skupaj. Nives in Peter pa. Ja, Nives in Peter. Tina je bila kasneje ob ribniku takrat kot Benjamin, le na drugi strani. Sicer pa je Tina prejšnji teden rekla Nives, da ima Benjamin lep čop. Benjamin definitivno nima lepega čopa. Tone ga ima. Ampak Tone hodi z Nives. Kura. Ana in Tone bi bila za skupaj. Ne pa Tone in Nives.

Ogrevalna naloga

Napišite funkcijo poisci_imena(stavek), ki kot argument prejme niz stavek in kot rezultat vrne seznam vseh besed v stavku, ki se začnejo z veliko začetnico. Če se beseda konča z vejico, naj jo odbije. Če, na primer, pokličemo poisci_imena('Na vratih sta se prva pojavila Ana in Peter, menda "slučajno".'), mora vrniti seznam ["Na", "Ana", "Peter"].

Rešitev

Sestaviti seznam imen pomeni: pripraviti prazen seznam, se zapeljati prek vseh besed v nizu (na besede ga razbijemo s split in vsako besedo, ki se začne z veliko črko, dodati v ta seznam. Mimogrede se znebimo še morebitne vejice tako, da jo zamenjamo s praznim nizom.

def poisci_imena(stavek): imena = [] for beseda in stavek.split(): if beseda.istitle(): beseda = beseda.replace(",", "") imena.append(beseda) return imena

Vejice se lahko namesto z replace znebimo tudi z

if beseda.endswith(","): beseda = beseda[:-1]

Stvar okusa.

Študenti so imeli pri reševanju obilo problemov s tem, da so odkrivali, ali je določena beseda ime (torej, se začne z veliko črko ali ne). V gornji funkciji smo to uredili z istitle. Nauk: branje dokumentacije se splača.

Za zagrebene še profi varianta funkcije:

def poisci_imena(stavek): return [beseda.replace(",", "") for beseda in stavek.split() if beseda.istitle()]

Obvezna naloga

Napišite funkcijo poisci_pare(besedilo), ki prejme besedilo, kakršno je gornje, in naredi naslednje: besedilo razbije na stavke. Predpostavite lahko, da so stavki ločeni s pikami. Nato za vsak stavek ugotovi, katera imena se pojavljajo v njem in izloči pare, ki se pojavljajo v njih. Če se v stavku pojavita le dve imeni, je to par; primer takega stavka je "Peter se je sicer več vrtel okrog Nives." Če se v stavku pojavijo tri imena, predpostavimo, da je prvo ime v resnici samo velika začetnica, par pa sta drugi dve imeni; v stavku "Na vratih sta se prva pojavila Ana in Peter, menda "slučajno" sta par Ana in Peter. Če je v stavku več ali manj imen, potem v njem ni nobenega para.

Funkcija naj vrne seznam vseh parov, ki se pojavljajo v stavkih v besedilu. Poleg tega naj bo vsak par urejen po abecedi. Za gornje besedilo mora torej vrniti seznam

[['Ana', 'Peter'], ['Nives', 'Peter'], ['Ana', 'Benjamin'], ['Peter', 'Tina'], ['Ana', 'Peter'], ['Nives', 'Peter'], ['Nives', 'Peter'], ['Benjamin', 'Tina'], ['Nives', 'Tone'], ['Ana', 'Tone'], ['Nives', 'Tone']]

Poleg tega napišite funkcijo prestej_pare(besedilo), ki vrne seznam terk. Prvi element terke je število pojavitev para, drugi element pa par, predstavljen s seznamom. Za gornje besedilo mora funkcija vrniti

[(2, ['Ana', 'Peter']), (3, ['Nives', 'Peter']), (1, ['Ana', 'Benjamin']), (1, ['Peter', 'Tina']), (1, ['Benjamin', 'Tina']), (2, ['Nives', 'Tone']), (1, ['Ana', 'Tone'])]

Rešitev

Ista finta. Prazen seznam. Z zanko gremo prek besedila razbitega na stavke (tako kot smo šli prej prek stavka razbitega na besede). Za vsak stavek pokličemo prejšnjo funkcijo. Če vrne nekaj s tremi elementi, dodamo v seznam zadnja dva. Če vrne dva elementa, ju dodamo, kot sta.

Ne smemo pozabiti na urejanje: naloga hoče, da so pari urejeni. To dosežemo tako, da pokličemo sorted, ki smo jo tudi že večkrat videli.

def poisci_pare(besedilo): pari = [] for stavek in besedilo.split("."): imena = poisci_imena(stavek) if len(imena) == 3: pari.append(sorted(imena[1:])) elif len(imena) == 2: pari.append(sorted(imena)) return pari

Za štetje parov naredimo, recimo, takole: sestavimo prazen seznam (stevci), v katerega bomo zlagali, kar hoče naloga in ki ga bomo na koncu vrnili. Poleg tega si naredimo seznam (steto) parov, ki smo jih že dodali v, uh, oni, prvi, seznam.

Zdaj počnemo tole: pokličemo prejšnjo funkcijo, da dobimo pare. Za vsak par pogledamo, ali ga še ni med pari, ki so že šteti. Če je tako, da dodamo v steto, da ga ne bomo več preštevali, poleg tega pa ga dodamo v stevci, skupaj s številom pojavitev tega para (par) v seznamu pari.

def prestej_pare(besedilo): stevci = [] steto = [] pari = poisci_pare(besedilo) for par in pari: if not par in steto: steto.append(par) stevci.append((pari.count(par), par)) return stevci

Gotovo je kdo poskusil, kar smo se učili na predavanjih po tem, ko ste dobili to nalogo. Tudi to je poučno - ker ne deluje.

pari = poisci_pare(besedilo) stevci = collections.Counter(pari)

Če poskusimo kaj takšnega, Python zajavka TypeError: unhashable type: 'list'. O "unhashable type" bomo brali, kadar bomo poskušali kot ključ v slovarju uporabiti nekaj, kar nespremenljivo, v tem primeru seznam (list). Če res hočemo uporabiti Counter, predalamo ves seznam seznamov v seznam terk. Vendar potem stvar izgubi svojo lepoto. Saj ni, da se ne bi dalo, ni pa prav lepo.

Dodatna naloga

Zdaj pa spet plesni pari. ;) Najprej poparite tisti osebi, ki se največkrat pojavljata skupaj v besedilu (to bi bila Nives in Peter. Nato vzamete naslednji par po pogostosti pojavitev... To bi bila Ana in Peter, vendar to ne gre, saj je Peter že zaseden. Zato ta par izpustite in pogledate naslednjega, torej Nives in Tone. Tudi to ne gre, saj je zasedena Nives. Nato vzamete naslednji par... Ena od možnih rešitev za gornje besedilo je torej

[['Nives', 'Peter'], ['Benjamin', 'Tina'], ['Ana', 'Tone']]

Napisati morate torej funkcijo razporedi(besedilo), ki sestavi plesne pare tako, da uredi potencialne pare po številu skupnih pojavitev v stavkih. Nato sestavi seznam parov tako, da jemlje pare po vrstnem redu, vendar sproti beleži, katere osebe so že zasedene in pare, v katerih je (vsaj) ena od oseb že zasedena, izpusti.

Rešitev

Pokličemo prejšnjo funkcijo. Nato pare uredimo padajoče. Zdaj pa pripravimo dva seznama: koncni bo tisto, kar bomo vračali (torej pari), oddani pa bo seznam že oddanih plesalcev.

Zanko naženemo prek terk (število_pojavitev, par). Ker števila pojavitev v resnici ne potrebujemo, dotično spremenljivko imenujemo kar _. Za vsak par preverimo, ali da ni njegov prvi ali drugi plesalec že med oddanimi (if par[0] not in oddani and par[1] not in oddani). Če ni, k seznamu oddanih pripnemo še ta seznam, k seznamu parov pa dodamo ta par.

def razporedi(besedilo): pari = prestej_pare(besedilo) pari.sort(reverse=True) oddani = [] koncni = [] for _, par in pari: if par[0] not in oddani and par[1] not in oddani: oddani += par koncni.append(par) return koncni

Bodite pozorni na tole lepoto: oddani += par bo k oddani dodal dva elementa, namreč oba elementa iz seznama par. koncni.append(par) pa v koncni doda eno samo reč, namreč seznam, ki ga podamo kot argument -- par.