PALMA junior
Úloha o elektronických voľbách

Autorské riešenie
[stiahni py]

• Počet riešiteľov: 6 / 6 = 100 %

• Úspešnosť riešenia: 4,75 / 6 = 80 %

Pri riešení tejto úlohy sa môžeme inšpirovať postupom, aký by sme použili pri ručnom sčítavaní hlasov. Zrejme by sme vyberali hlasovacie lístky po jednom z urny. Pri každom by sme zistili, akému kandidátovi hlas patrí.

• Ak by to bol prvý hlas pre kandidáta, poznačili by sme si jeho meno na papier a pripísali k nemu prvý hlas.

• Ak by to nebol prvý hlas pre kandidáta, našli by sme jeho meno na papieri a počet hlasov by sme zvýšili o 1.

Ak sme už započítali všetky hlasovacie lístky, potrebujeme zistiť, či niektorý z kandidátov získal viac hlasov ako každý z ostatných kandidátov. Prehľadáme všetky počty hlasov a nájdeme ten najvyšší. Nakoniec zistíme, koľko kandidátov dostalo tento najvyšší počet hlasov. Ak je to len jeden, máme víťaza. Ak je takýchto kandidátov viac, víťaza niet.

Jedno z riešení môže vyzerať nasledovne:

#Python
def vitaz_volieb_1(hlasy):
    kandidati = []
    pocty_hlasov = []
    for kandidat in hlasy:
        if kandidat in kandidati:
            pozicia = kandidati.index(kandidat)
            pocty_hlasov[pozicia] = pocty_hlasov[pozicia] + 1
        else:
            kandidati.append(kandidat)
            pocty_hlasov.append(1)

    najviac_hlasov = max(pocty_hlasov)

    if pocty_hlasov.count(najviac_hlasov) == 1:
        pozicia = pocty_hlasov.index(najviac_hlasov)
        vitaz = kandidati[pozicia]
        return vitaz
    return ''

Pri ručnom sčítavaní by sme dvojicu: (meno kandidáta, počet hlasov) registrovali tak, že by sme tieto dve hodnoty napísali vedľa seba. Vo funkcii vyššie sme to vyriešili tak, že mená kandidátov si ukladáme do zoznamu kandidati a počty hlasov do zoznamu pocty_hlasov. Hodnoty patriace k sebe sú v zoznamoch uložené na rovnakých pozíciách.

Po započítaní všetkých hlasov nájdeme maximum z hlasov a zistíme, koľkokrát sa maximum v zozname nachádza. Podľa toho vieme, či voľby majú víťaza (jeden výskyt) alebo nie (viac výskytov).

V tomto riešení trochu nešikovne udržiavame dva zoznamy a vzťahy medzi hodnotami v nich. Navyše, pre každý hlas zisťujeme, či už ho máme poznačený a ak áno, tak na akom mieste. Pre takéto prípady v Pythone existuje dátová štruktúra slovník. Slovník udržiava dvojice. V našom prípade dvojice meno_kandidata:pocet_hlasov. Slovník navyše dokáže veľmi rýchlo zistiť, či meno kandidáta už obsahuje alebo nie. Riešenie využitím slovníka môže vyzerať nasledovne:

#Python
def vitaz_volieb_2(listky):
    kandidati_hlasy = {}
    for kandidat in listky:
        kandidati_hlasy[kandidat] = kandidati_hlasy.get(kandidat, 0) + 1

    pocty_hlasov = list(kandidati_hlasy.values())
    najviac_hlasov = max(pocty_hlasov)

    if pocty_hlasov.count(najviac_hlasov) == 1:
        kandidati = list(kandidati_hlasy.keys())
        pozicia = pocty_hlasov.index(najviac_hlasov)
        vitaz = kandidati[pozicia]
        return vitaz
    return ''

Slovník kandidati_hlasy uchováva mená kandidátov a k nim zodpovedajúce počty hlasov. Mená kandidátov označujeme ako kľúče (keys) a počty ich hlasov ako hodnoty (values). Pre každý hlasovací lístok požiadame slovník, aby nám vrátil počet hlasov, ktoré sme pre aktuálneho kandidáta už započítali alebo 0, ak sme zatiaľ hlas pre kandidáta nenašli. Túto hodnotu zvýšime o 1 a vložíme do slovníka.

Po „naplnení“ slovníka (t.j. započítaní všetkých hlasov) musíme zistiť, aké je maximum z hlasov a koľkokrát sa medzi hlasmi nachádza. Ak je maximum len jedno, tak zistíme, ktorému kandidátovi patrí. Aby sme s kľúčmi a hodnotami mohli pracovať ako so zoznamom (napr. nájsť pozíciu prvku, počet výskytov prvku), pretypujeme tieto časti slovníka na zoznamy.

Slovník nám uľahčil prácu so započítavaním hlasov. Trochu "nešikovne" sme však hľadali výsledné maximum a počet jeho výskytov a museli sme preto časti slovníka pretypovať na zoznamy. Zamyslime sa, či by sme nevedeli maximum a víťaza zisťovať priebežne už počas toho, ako započítavame hlasy.

Pamätajme si najvyšší počet hlasov, aký sme počas započítavania dosiahli a kandidátov, ktorí ho dosiahli. Implementácia tohto postupu môže vyzerať takto:

#Python
def vitaz_volieb_3(listky):
    kandidati_hlasy = {}
    maximum = 0
    kandidati_maximum = []
    for kandidat in listky:
        kandidati_hlasy[kandidat] = kandidati_hlasy.get(kandidat, 0) + 1
        if kandidati_hlasy[kandidat] > maximum:
            kandidati_maximum.clear()
            kandidati_maximum.append(kandidat)
            maximum = kandidati_hlasy[kandidat]
        elif kandidati_hlasy[kandidat] == maximum:
            kandidati_maximum.append(kandidat)
    if len(kandidati_maximum) == 1:
        return kandidati_maximum[0]
    return ''

V premennej maximum si uchovávame doteraz najvyšší počet hlasov. V zozname kandidati_maximum si uchovávame mená kandidátov, ktorí dosiahli aktuálne maximum hlasov.

Postupne prechádzame hlasmi kandidátov, hlas započítame a porovnáme nový počet hlasov aktuálneho kandidáta s doterajším maximom.

• Ak je nový počet hlasov aktuálneho kandidáta väčší ako doterajšie maximum, zapamätáme si meno kandidáta, ktorý ho dosiahol a zároveň sme našli nové maximum. V tomto momente je takýto kandidát len jeden, takže zoznam kandidátov s maximom hlasov vyčistíme a vložíme doň aktuálne meno kandidáta.

• Ak je nový počet hlasov aktuálneho kandidáta rovný doterajšiemu maximu, pridáme meno kandidáta k menám kandidátov, ktorí tiež dosiahli rovnaký počet hlasov.

Nakoniec potrebujeme zistiť, koľko kandidátov sa nachádza v zozname kandidati_maximum. a či voľby majú víťaza alebo nie.

Ukážme si ešte jedno riešenie. Problém nájsť najčastejšie sa vyskytujúcu hodnotu pomerne často riešime aj v matematike, konkrétne v štatistike. Najčastejšia hodnota v súbore dát sa označuje ako modus a je jedným zo znakov, ktoré charakterizujú súbor dát. Časť riešenia nám ponúka modul statistics a funkcia multimode. Funkcia multimode vráti zoznam hodnôt, ktoré sa v zadanom zozname vyskytujú najčastejšie. Výsledná funkcia môže vyzerať nasledovne:

#Python
import statistics


def vitaz_volieb_4(listky):
    vitazi = statistics.multimode(listky)
    if len(vitazi) == 1:
        return vitazi[0]
    return ''

Nenechajme sa "oklamať" krátkosťou kódu. Časť roboty už spravil niekto za nás. Podobný postup, ako sme si uviedli v predchádzajúcich verziách funkcie vitaz_volieb vyššie, je schovaný aj za funkciou multimode. 

Vaše zaujímavé riešenia a najčastejšie chyby

Väčšina z vás vyriešila úlohu správne. Problémy ste mali s efektívnosťou riešenie. Opakovane ste prehľadávali zoznamy, zisťovali či nejaká hodnota v zozname je, prípadne na akom mieste. Niektorí dokonca usporiadali zoznamy. Šikovnejšou cestou sa vydali tímy mangomongosh a oliverseman a v riešení využili slovník.