Testi

testi-barvanje.py

Ogrevanje

Šahovnica ima 64 polj. Stolpci so označeni s črkami A, B, C ..., H; vrstice so označene s številkami 1, 2, 3, ... 8. Oznake polj so torej, A5, C3 in podobno. Polja so navadno črna in bela. Tule pa predpostavimo, da imamo belo šahovnico. Pobarvamo jo tako, da na polja lepimo nalepke različnih barv. Če jih, na primer, lepimo takole:

[("A3", "zelena"), ("B5", "modra"), ("G2", "rumena")]

bo šahovnica pobarvana takole:

{"A3": "zelena", "B5": "modra", "G2": "rumena"}

Če pa bi jih, recimo, lepili tako:

[("A3", "zelena"), ("B5", "modra"), ("A3", "rumena")]

bi bila šahovnica pobarvana tako:

{"A3": "rumena", "B5": "modra"}

Polje A3 je rumeno, ker je rumena nalepka prekrila modro.

  • Napiši funkcijo barvanje(barve), ki kot argument dobi seznam parov (koordinata, barva), in kot rezultat vrne barve polj v obliki slovarja, katerega ključi so koordinate in vrednosti barve - kot kaže gornji primer.

  • Napiši funkcijo barvanje_eno(barve), ki je podobna gornji, vendar ne lepi nalepk na polja, ki so že polepljena. To pomeni, da mora barvanje_eno([("A3", "zelena"), ("B5", "modra"), ("A3", "rumena")]) vrniti {"A3": "zelena", "B5": "modra"} in ne {"A3": "rumena", "B5": "modra"}.

Rešitev

Tako kot smo morali v funkcijah, ki naj bi vračale nek (nov) seznam, najprej narediti nov seznam, bomo v tej, ki mora vračati slovar, najprej naredili slovar; sahovnica = {}. Nato se sprehodimo čez seznam parov (for polje, barva in barve:) in za vsako polje zabeležimo njegovo barvo, sahovnica[polje] = barva. Tako dobimo

def barvanje(barve):
    sahovnica = {}
    for polje, barva in barve:
        sahovnica[polje] = barva
    return sahovnica

Kasnejša barva bo prekrila zgodnejšo preprosto zato, ker bomo istemu polju priredili novo vrednost. Če tega nočemo, je pač ne priredimo, kadar je polje že pobarvano: v funkcijo vstavimo še en if polje not in sahovnica.

def barvanje_eno(barve):
    sahovnica = {}
    for polje, barva in barve:
        if polje not in sahovnica:
            sahovnica[polje] = barva
    return sahovnica

Obvezne naloge

Recimo, da imamo takole polepljeno šahovnico:

sahovnica = {
    "A3": "rumena", "A6": "rumena", "H2": "rumena", "G7": "rumena",
    "C2": "zelena", "C3": "zelena",
    "H6": "modra"
}

  • Napiši funkcijo prestej_barvo(sahovnica, barva), ki kot argument dobi slovar, kakršen je gornji, in barvo, kot rezultat pa vrne število polj te barve. Tako mora, recimo prestej_barvo(sahovnica, "rumena") v gornjem primeru vrniti 4, saj imamo štiri rumena polja.

  • Napiši funkcijo pobarvanih_polj(sahovnica), ki vrne število pobarvanih polj.

  • Napiši funkcijo nepobarvanih_polj(sahovnica), ki vrne število nepobarvanih polj.

  • Napiši funkcijo polja_po_barvi(sahovnica, barva), ki prejme šahovnico in barvo, kot rezultat pa vrne koordinate polj s to barvo. Tako mora pri gornji šahovnici klic polja_po_barvi(sahovnica, "modra") vrniti množico {"C2", "C3"}. Klic polj_po_barvi(sahovnica, "rjava") mora v gornjem primeru vrniti prazno množico.

Rešitev

V prvi nalogi lahko gremo, recimo, čez vse vrednosti v šahovnici (sahovnica.values()) in štejemo, kolikokrat naletimo na iskano barvo.

def prestej_barvo(sahovnica, barva):
    stevec = 0
    for barva1 in sahovnica.values():
        if barva1 == barva:
            stevec += 1
    return stevec

Lahko pa bi spremenili vrednosti v slovarju v seznam (list(sahovnica.values())) in prepustili štetje seznamovi metodi count().

def prestej_barvo(sahovnica, barva):
    return list(sahovnica.values()).count(barva)

Če bi imeli že napisano funkcijo polja_po_barvi, bi si lahko pomagali z njo in sestavili množico vseh polj te barve ter vrnili velikost te množice.

def prestej_barvo(sahovnica, barva):
    return len(polja_po_barvi(sahovnica, barva))

Če pa bi v okviru dodatne naloge že sprogramirali prestej_barve, bi lahko prešteli kar vse barve in vrnili število polj te barve.

def prestej_barvo(sahovnica, barva):
    return prestej_barve(sahovnica)[barva]

Ups, ne, to ne deluje, če določena barva ne obstaja. Takole bo boljše: če barve ni, vrnimo 0.

def prestej_barvo(sahovnica, barva):
    return prestej_barve(sahovnica).get(barva, 0)

Število pobarvanih polj je preprosto velikost slovarja. Število nepobarvanih pa je 64 - toliko.

def pobarvanih_polj(sahovnica):
    return len(sahovnica)

def nepobarvanih_polj(sahovnica):
    return 64 - len(sahovnica)

Ob tej nalogi ste bili fascinantno kreativni. Tipična rešitev je bila

def pobarvanih_polj(sahovnica):
    pobarvanih = 0
    for polje, barva in sahovnica.items():
        pobarvanih += 1
    return pobarvanih

Bilo pa je tudi veliko še bolj zapletenih.

Končno, za polja po barvi si pripravimo prazno množico (te_barve = set()). Gremo čez šahovnico (for polje, barva1 in sahovnica.items()) in ko naletimo na polje iskane barva (if barva == barva1), dodamo koordinate v to množico (te_barva.add(polje)).

def polja_po_barvi(sahovnica, barva):
    te_barve = set()
    for polje, barva1 in sahovnica.items():
        if barva == barva1:
            te_barve.add(polje)
    return te_barve

Dodatna naloga

  • Napiši funkcijo prestej_barve(sahovnica), ki vrne slovar, katerega ključi so barve, vrednosti pa število polj te barve. Pri gornji šahovnici mora funkcija vrniti slovar {"rumena": 4, "zelena": 2, "modra": 1}.

  • Napiši funkcijo polja_po_barvah(sahovnica), ki vrne podoben slovar, le da so elementi množice s koordinatami polj te barve. V gornjem primeru bi morala funkcija vrniti slovar

    {"rumena": {"A3", "A6", "H2", "G7"}, "zelena": {"C2", "C3"}, "modra": {"H6"}}

Rešitev

Za dodatno nalogo mi prideta prav dve stvari, ki sem ju hvalil na predavanjih. Obe sta iz modula collections in se imenujeta Counter in defaultdict.

Za preštej barve uporabim Counter. Spustim ga čez vrednosti (sahovnica.values()), pa bo preštel, kar je treba.

def prestej_barve(sahovnica):
    return collections.Counter(sahovnica.values())

Za množice polj določene barve pa bom imel slovar po_barvah, katerega ključi bodo barve in vrednosti množice koordinat polj. Grem čez vsa polja in barve (for polje, barva in sahovnica.items()) in v slovar pod ključ barva dodam polje (po_barvah[barva].add(polje)). Pri tem predpostavljam, da po_barvah[barva] že vsebuje množico. Pri barvah, ki jih vidim prvič, to ni res. Da mi ne bi bilo tega primera obravnavati posebej (if barva not in po_barvah: po_barvah[barva] = set()), po_barvah ne bo običajen slovar temveč slovar s privzetimi vrednostmi (po_barvah = collections.defaultdict(set)).

def polja_po_barvah(sahovnica):
    po_barvah = collections.defaultdict(set)
    for polje, barva in sahovnica.items():
        po_barvah[barva].add(polje)
    return po_barvah

Hitrejša rešitev

Vsaj eden izmed vaših kolegov, ki lahko ostane anonimen, je napisal prav Metodične rešitve. Kar je tule spodaj naj berejo le pogumni: tole je narejeno toliko dobro, kot znam jaz, na enem mestu celo malo boljše in na enem morda malenkost nerodnejše.

import itertools

def barvanje(barve):
    return dict(barve)

def barvanje_eno(barve):
    return dict(reversed(barve))

def prestej_barvo(sahovnica, barva):
    return list(sahovnica.values()).count(barva)

def pobarvanih_polj(sahovnica):
    return len(sahovnica)

def nepobarvanih_polj(sahovnica):
    return 64 - pobarvanih_polj(sahovnica)

def polja_po_barvi(sahovnica, barva):
    return polja_po_barvah(sahovnica).get(barva, set())

def pari_po_barvah(sahovnica):
    return itertools.groupby(sorted(sahovnica.items(), key=lambda par: par[1]), key=lambda par: par[1])

def prestej_barve(sahovnica):
    return {barva: len(list(polja)) for barva, polja in pari_po_barvah(sahovnica)}

def polja_po_barvah(sahovnica):
    return {barva: set(map(lambda par: par[0], polja)) for barva, polja in pari_po_barvah(sahovnica)}

V barvanje je le pretvoril seznam parov v množico. Da, dict zna tudi to. V barvanje_eno se je spomnil preprostega trika, ki tudi meni ni prišel na misel: isto kot barvanje, le seznam barv obrne. Super ideja.

Naslednje tri funkcije so takšne, kot v "uradni" rešitvi. polja_po_barvi uporablja polja_po_barvah, le z uporabo get popazi, da v primeru, da določene barve ni, vrne prazno množico.

Ostanek uporablja hujšo eksotiko. Pomožna funkcija pari_po_barvah pogrupira polja po barvah in zadnji dve funkciji uporabita te skupine.

Super. Dve stvari bi se dalo napisati malenkost preprosteje. Namesto lambda x: x[1] lahko uporabimo funkcijo itemgetter(1), ki jo dobimo v modulu operator.

from operator import itemgetter
def pari_po_barvah(sahovnica):
    return itertools.groupby(sorted(sahovnica.items(), key=itemgetter(1)), key=itemgetter(1))

V polja_po_barvah pa lahko uporabimo izpeljane množice (set comprehension).

def polja_po_barvah(sahovnica):
    return {barva: {par[0] for par in polja} for barva, polja in pari_po_barvah(sahovnica)}
Zadnja sprememba: torek, 23. marec 2021, 20.18