Testi

testi-zupanske-volitve.py

Obvezna naloga

Da bi imeli vsi županske kandidatke enake možnosti, so pripravili glasovnice z različnimi vrstnimi redi. Tako lahko nekdo dobi seznam kandidatk["Anna", "Berta", "Cilka"] in nekdo drug ["Cilka", "Anna", "Berta"]. Če na prvi glasovnici obkrožimo Cilko, takšno glasovnico opišemo z [False, False, True]. Na drugi glasovnici pa je nekdo obkrožil Cilka in Berta (zaradi česar je glasovnica sicer neveljavna), kar predstavimo z [True, False, True].

• Napiši funkcijo glasov(obkrozeno), ki kot argument dobi seznam, ki pove, kaj je obkroženo in kaj ne, ter vrne število obkroženih kandidatk. Klic glasov([True, True, False, True]) vrne 3.

Različica 1: preštejemo.

def glasov(obkrozeno):
    obkrozenih = 0
    for krozec in obkrozeno:
        if krozec:
            obkrozenih += 1
    return obkrozenih

Različica 2: seštejemo. Če vemo, da je (v Pythonu in večini drugih jezikov) False isto kot 0 in True isto kot 1, naloga sprašuje po vsoti seznama.

def glasov(obkrozeno):
    return sum(obkrozeno)

Različica 3: znamo Python in povemo, da je glasov isto kot sum. Namesto, da bi pisali funkcijo, samo priredimo ime.

glasov = sum

• Napiši funkcijo voljeni(obkrozeno, imena), ki prejme seznam obkroženih (kot v prejšnji nalogi) in seznam imen na glasovnici, ter vrne kandidatko, za katero je glasoval glasovalec. Če je obkroženih več imen ali pa nobeno, naj funkcija vrne None, saj glasovnica ni veljavna.

Če je na glasovnici obkroženo le eno ime, gremo čez pare iz obkrozeno in imena ter vrnemo ime, ki je obkroženo.

def voljeni(obkrozeno, imena):
    if glasov(obkrozeno) == 1:
        for krozec, ime in zip(obkrozeno, imena):
            if krozec:
                return ime

Malo drugačen razmislek: vrniti moramo ime, ki se nahaja na tistem mestu v imena, na katerem se v obkrozeno nahaja True.

def voljeni(obkrozeno, imena):
    if glasov(obkrozeno) == 1:
        return imena[obkrozeno.index(True)]

Svaril sem pred uporabo metode index, ker da vedno vrne indeks prvega elementa z iskano vrednostjo (kar morda ni točno tisto, kar hočemo) in ker je počasna, saj mora preiskati seznam, medtem ko bi z malo spretnosti indeks pridobili na kak drug način. Za ta primer svarili ne veljata. Vemo, da je True le eden - to smo preverili v prejšnji vrstici - tako da index vrne vrednost enega in edinega True-ja. Poleg tega pa ni "počasen" oziroma ga ne moremo prav nič pospešiti, saj ne vemo, kje v obkrozeno se nahaja True. V resnici je druga funkcija bistveno hitrejša od prve, saj je Pythonova metoda indeks napisana v jeziku C, ki je pri takšnih rečeh 30-krat ali pa celo 100-krat hitrejši od Pythona.

• Napiši funkcijo najvecji(d), ki kot argument prejme slovar d, poišče največjo vrednost in kot rezultat vrne par, ki vsebuje pripadajoči ključ in to vrednost. Klic najvecji({"a": 5, "b": 9, "c": 8, "d": 4}) vrne ("b", 9). Vrednosti so lahko tudi negativne!

To spominja na iskanje največjega elementa seznama, le da primerjamo eno reč, poleg nje pa vrnemo še eno drugo. To smo počeli že parkrat.

Tule gremo čez pare (ključ, vrednost) v slovarju d (for k, v in d.items()). Primerjamo vrednosti (v > naj_v), zapomnimo pa si ključ in vrednost (naj_k, naj_v = k, v).

Ker se v slovarju pojavljajo tudi negativne vrednosti, bomo začetno vrednost naj_k in naj_v nastavili na None. Na ta način se lahko pogoj v zanki glasi "če nismo videli še nobene vrednosti ali pa je trenutna večja od največje doslej", to je if naj_v == None or v > naj_v.

To poskrbi tudi za primer, ko je slovar prazen. V tem primeru se zanka nikoli ne izvede, naj_k in naj_v ostaneta None, in funkcija vrne (None, None) - tako kot mora.

def najvecji(d):
    naj_k = naj_v = None
    for k, v in d.items():
        if naj_v == None or v > naj_v:
            naj_k, naj_v = k, v
    return naj_k, naj_v

• Napiši funkcijo pristej(s, t), ki "prišteje" slovar t k slovarju s. Če imamo s = {"a": 5, "b": 6, "d": 4} in t = {"b": 3, "c": 8}, klic pristej(s, t) spremeni s v {"a": 5, "b": 9, "d": 4, "c": 8}. Funkcija ne vrača ničesar.

Gremo čez slovar t (for k in t). Za vsak ključ k preverimo, ali se nahaja v s (if k in s). Če se ne, prepišemo pripadajočo vrednost iz t v s (s[k] = t[k]). Če se, pa vrednosti v slovarju s prištejemo tisto iz t (s[k] += t[k]).

def pristej(s, t):
    for k in t:
        if k not in s:
            s[k] = t[k]
        else:
            s[k] += t[k]

To je stvar okusa, vendar: kadar potrebujem ključe in vrednosti, grem raje čez items. Takole:

def pristej(s, t):
    for k, v in t.items():
        if k not in s:
            s[k] = v
        else:
            s[k] += v

Vendar prav v tem primeru nisem prepričan, da je to bolj elegantno. Pač pa postane bolj elegantno, ko se domislimo, da imajo slovarji metodo get.

def pristej(s, t):
    for k, v in t.items():
        s[k] = s.get(k, 0) + v

V s[k] zapišemo tisto, kar je bilo tam prej, pa še v prištejemo zraven. Če v slovarju s ni ključa k, pa mora v prišteti k ničli.

• Napiši funkcijo zmagovalec(glasovnice), ki prejme seznam glasovnic, na primer,

  [([False, True, True], ["Berrta", "Ana", "Cilka"]),
  ([False, True, True], ["Berrta", "Ana", "Cilka"]),
  ([False, False, True], ["Ana", "Cilka", "Berrta"]),
  ([False, True, False], ["Ana", "Berrta", "Cilka"]),
  ([False, True, False], ["Berrta", "Ana", "Cilka"])
  ]
  

  Vrniti mora ime kandidatke z največ glasovi in delež glasov zanjo na veljavnih glasovnicah. V gornjem primeru sta prvi dve glasovnici neveljavni. Zmagovalec je Berrta, ki je dobila dva glasova od treh, zato funkcija vrne ("Berrta", 2 / 3).

Pripravimo si slovar, v katerega bomo šteli glasove (glasovi = defaultdict(int)). Uporabili bomo defaultdict(int), zato da bomo glasove za nove kandidate preprosto prištevali, ne da bi jih morali prej vstavljati v slovar; primere si lahko ogledate na predavanjih.

Nato gremo čez glasovnice (for obkrozeno, imena in glasovnice). Za vsako pogledamo, kdo je obkrožen (obkrozen = voljeni(obkrozeno, imena)) in če je glasovnica veljavna (if obkrozen != None), k obkroženemu kandidatu prištejemo en glas (glasovi[obkrozen] += 1). Nato uporabimo funkcijo najvecji, da dobimo ime kandidata z največ glasovi in število glasov, ki jih je dobil.

Za konec moramo izvedeti še število veljavnih glasovnic, da bomo lahko vrnili delež dobljenih glasov. Ta je enak vsoti glasov, ki so jih dobili vsi kandidati skupaj; sešteti moramo vrednosti slovarja glasovi (sum(glasovi.values()))

def zmagovalec(glasovnice):
    glasovi = defaultdict(int)
    for obkrozeno, imena in glasovnice:
        obkrozen = voljeni(obkrozeno, imena)
        if obkrozen != None:
            glasovi[obkrozen] += 1
    zmago, glasov = najvecji(glasovi)
    return zmago, glasov / sum(glasovi.values())

• Napiši funkcijo voljeni_vec(obkrozeno, imena), ki prejme enake podatke kot voljeni, vendar obravnava vse glasovnice kot veljavne, število glasov pa razdeli med vse obkrožene kandidatke. Funkcija vrne slovar, katerega ključi so imena obkroženih kandidatk, vrednost pa 1 deljeno s številom obkroženih kandidatk. Če pokličemo vabljeni_vec([True, False, True, True], ["Ana", "Berta", "Cilka", "Dani"]), funkcija vrne {"Ana": 1 / 3, "Cilka": 1 / 3, "Dani": 1 / 3}.

Določiti moramo delež glasu, ki ga dobi vsak obkroženi. Ta je enak 1 deljeno s število obkroženih, 1 / glasov(obkrozeno). Popaziti moramo še na glasovnice, na katerih ni obkrožen nihče. Tedaj bomo namesto s številom obkroženih delili z 1. Tako bo vsak od obkroženih dobil 1 glas, vendar ni obkroženih nihče, torej - komu mar. Se pravi, delez = 1 / (glasov(obkrozeno) or 1).

Zdaj pa pripravimo nov slovar, gremo prek glasovnice in vsakemu od obkroženih imen damo njegov delež glasu.

def voljeni_vec(obkrozeno, imena):
    delez = 1 / (glasov(obkrozeno) or 1)
    glasovi = {}
    for krozec, ime in zip(obkrozeno, imena):
        if krozec:
            glasovi[ime] = delez
    return glasovi

Dodatna naloga

Kandidatke seveda obljubijo to in ono. Recimo, da Ana obljubi cesto, šolo in kolesarko stezo. Nekdo si želi cesto, kolesarsko stezo, izboljšan javni prevoz in zastonj sladoled. Pokrivanje je 2 (cesta in steza), vseh stvari, ki so tu v igri, pa je 5 (cesta, šola, steza, prevoz, sladoled). Zato bomo rekli, da je ujemanje med Aninimi obljubami in temi željami 2 / 5, to je, 0.4.

• Napiši funkcijo ujemanje(obljube, zelje), ki izračuna ujemanje, kot ga opisujemo v gornjem odstavku. Pri tem sta obljube in zelje seznama nizov, na primer ["cesta", "šola", "steza"].

Izračunati moramo dva seznama: skupne bo vseboval vse skupne elemente seznamov obljube in zelje (po domače: presek), oboje pa vse, ki se pojavijo na enem ali drugem ali obeh (po domače: unija).

def ujemanje(obljube, zelje):
    skupne = []
    oboje = obljube[:]
    for zelja in zelje:
        if zelja in obljube:
            skupne.append(zelja)
        else:
            oboje.append(zelja)
    return len(skupne) / (len(oboje) or 1)

Seznam skupne bo v začetku prazen, v oboje pa skopiramo vse elemente seznama obljube. Nato gremo prek želja. Če je želja med obljubami, jo dodamo v presek. V uniji je tako ali tako že. Če želje ni med obljubami, pa je ne bomo dodali v presek, temveč manjka v uniji.

Na koncu vrnemo razmerje med dolžinama seznamov, s tem da k len(oboje) pritaknemo še or 1, tako da bomo v primeru, da je unija prazna, delili z 1. V slednjem primeru bo rezultat tako ali tako 0, saj je takrat, ko je unija prazna, presek prazen še toliko bolj.

• Napiši funkcijo naj_kandidata(kandidati, zelje). Ta prejme seznam parov (ime kandidata, obljube), na primer

  [("Ana", ["cesta", "šola", "steza"]),
  ("Berta", ["šola", "sladoled"]),
  ("Cilka", []),
  ("Dani", ["sladoled", "steza", "cesta", "šola"])
  ]
  

  in seznam želja, na primer ["cesta", "šola"]. Funkcija vrne imeni kandidatov, ki se najbolj ujemata z željami - najprej prvega in nato drugega. Da ne bo prezapleteno, smete predpostaviti, da ne bo izenačenih mest.

Tale je pa malo daljša.

def naj_kandidata(kandidati, zelje):
    ime1 = ujem1 = ime2 = ujem2 = None
    for ime, obljube in kandidati:
        ujem = ujemanje(obljube, zelje)
        if ujem1 == None or ujem > ujem1:
            ime2, ujem2 = ime1, ujem1
            ime1, ujem1 = ime, ujem
        elif ujem2 == None or ujem > ujem2:
            ime2, ujem2 = ime, ujem
    return ime1, ime2

Funkcija bo potrebovala imeni najboljših kandidatov doslej (ime1 in ime2) ter ujemanje njihovih obljub z našimi željami (ujem1 in ujem2). V začetku postavimo vse to na None.

V zanki gremo prek kandidatov (ime) in njihovih obljub (obljube). Za vsakega izračunamo ujemanje (ujem). Če je to prvi kandidat na seznamu (ujem1 == None) ali pa je boljši od najboljšega doslej, potisnemo trenutnega vodilnega na drugo mesto (ime2, ujem2 = ime1, ujem1) in si zapomnimo trenutno ime in ujemanje kot najboljše doslej (ime1, ujem1 = ime, ujem). Sicer pa je trenutni kandidat morda boljši od drugega najboljšega (ali pa drugi najboljši še ne obstaja); v tem primeru si ga zapomnimo kot drugega najboljšega.

Ko je to končano, vrnemo imeni najboljših kandidatov.