Testi

Naloga

Tokratna naloga bo variacija na igro Minolovec. Imamo kvadratno mrežo polj. Na nekaterih poljih so mine. Kje so, pove množica koordinat min. Na primer, množica

mine = {(3, 0), (1, 1), (6, 1), (1, 2), (2, 2), (6, 3)}`

opiše polje

...X....
.X....X.
.XX.....
......X.

Pike predstavljajo prosta polja, X so mine. (Slika je narisana tako, da je prva koordinata x, ki narašča z leve proti desni, druga pa y, ki narašča po vrsticah navzdol.)

Za oceno 6

Funkcije se lahko med sabo poljubno kličejo. Lahko jih programirate v poljubnem vrstnem redu. Funkcija, ki je na spisku prej, sme klicati funkcijo, ki je kasneje -- če vam to slučajno pride prav.

Število sosedov

Napiši funkcijo sosedov(x, y, mine), ki pove, na koliko sosedov polja s koordinatami (x, y) je postavljena mina. Klic sosedov(2, 1, mine) v gornjem primeru vrne 4, saj je polje obkroženo s štirimi minami. Klic sosedov(3, 0) vrne 0, saj nobeno od sosednjih polj nima mine; mina je seveda prav na polju (3, 0), vendar ta ne šteje.

Rešitev

Če dobimo x in y, moramo preskusiti polja, pri katerih je koordinata x enaka x - 1, x in x + 1, in enako v navpični smeri. Pri tem pa moramo preskočiti polje (x, y).

def sosedov(x, y, mine):
    n = 0
    for x0 in (x - 1, x, x + 1):
        for y0 in (y - 1, y, y + 1):
            if (x0, y0) in mine and (x0 != x or y0 != y):
                n += 1
    return n

Zanki lahko naredimo tudi z range:

    for x0 in range(x - 1, x + 2):
        for y0 in range(y - 1, y + 2):

Ali pa spustimo zanki čez razlike.

def sosedov(x, y, mine):
    n = 0
    for dx in (-1, 0, 1):
        for dy in (-1, 0, 1):
            if (x + dx, y + dy) in mine and (dx or dy):
                n += 1
    return n

Da spravimo stvar v eno vrstico, se spomnimo, da je True isto kot 1 in False isto kot 0. Pa najprej spremenimo kar tole funkcijo.

def sosedov(x, y, mine):
    n = 0
    for dx in (-1, 0, 1):
        for dy in (-1, 0, 1):
            n += (dx or dy) and (x + dx, y + dy) in mine
    return n

Samo pogoj iz if-a smo prepisali v n += .... Poleg tega smo ga preobrnili; rezultat izraza (x + dx, y + dy) in mine and (dx or dy) bi lahko bila tudi vrednost dx ali dy, ne True ali False. Potem pa že vemo, kaj seštevamo.

def sosedov(x, y, mine):
    return sum((dx or dy) and (x + dx, y + dy) in mine
               for dx in (-1, 0, 1) for dy in (-1, 0, 1))

Tale rešitev je nekoliko, emm... elegantna. Manj elegantna je

def sosedov(x, y, mine):
    return sum(1
               for dx in (-1, 0, 1) for dy in (-1, 0, 1)
               if (dx or dy) and (x + dx, y + dy) in mine)

ki sestavi seznam enic (po eno enico za vsako mino v soseščini) in jih sešteje, ali pa

def sosedov(x, y, mine):
    return len([None
                for dx in (-1, 0, 1) for dy in (-1, 0, 1)
                if (dx or dy) and (x + dx, y + dy) in mine])

ki sestavi seznam None-ov in vrne njegovo dolžino.

Frajerska rešitev - z idejo, ki bo prišla prav še kasneje - pa sestavi množico koordinat vseh sosednjih polj, {(x + dx, y + dy) for dx in (-1, 0, 1) for dy in (-1, 0, 1) if dx or dy}. Število min v soseščini je enako velikosti preseka koordinat min in koordinat sosednjih polj

def sosedov(x, y, mine):
    return len(mine & {(x + dx, y + dy) for dx in (-1, 0, 1) for dy in (-1, 0, 1) if dx or dy})

Največ sosedov

Napiši funkcijo najvec_sosedov(mine, s, v), ki vrne koordinati polja, ki je obkroženo z največ minami. Pri tem sta s in v širini in višina polja. Za gornji primer bi klic najvec_sosedov(mine, 8, 4) vrnil polje (2, 1).

Rešitev

Najprej klasična varianta - funkcija, ob kateri bi morali zdaj že zehati.

def najvec_sosedov(mine, s, v):
    naj = -1
    for x in range(s):
        for y in range(v):
            n = sosedov(x, y, mine)
            if n > naj:
                naj = n
                naj_x, naj_y = x, y
    return naj_x, naj_y

Tule velja pripomniti, da je mnoge zafrkavala tale napaka.

    x, y = najvec_sosedov(mine2, s2, v2)
ValueError: not enough values to unpack (expected 2, got 0)

To je bilo res masovno, zgodilo pa se je avtorjem takšen funkcije:

def najvec_sosedov(mine, s, v):
    naj = 0
    naj_koord = ()
    for x in range(s):
        for y in range(v):
            n = sosedov(x, y, mine)
            if n > naj:
                naj = n
                naj_koord = x, y
    return naj_koord

Za kaj gre, kako je potrebno prebrati to napako? Zgodi se v vrstici x, y = najvec_sosedov(mine2, s2, v2). Tega niste napisali vi, to je v testih. Napaka pa pravi ValueError: not enough values to unpack (expected 2, got 0). Pravi, da poskušamo razpakirati neko terko, in sicer v dve vrednosti. No, natančno to ta vrstica počne: rezultat funkcije shrani v x in y. In namesto dveh vrednosti dobi 0 vrednosti - prazno terko.

Potem pogledamo še, v katerem testu se to zgodi: v tistem, v katerem ni min. Ker smo v začetku te različice funkcije nastavili naj na 0, iščemo polje, ki ima več kot 0 min v soseščini. Takega polja ni, funkcija nikoli ne pride v vrstico naj_koord = x, y in naj_koord ostane tak, kot je bil v začetku, se pravi prazna terka ().

Zdaj pa kreativnejše rešitve.

Lahko bi si pomagali s funkcijo po_sosedih, ki jo bomo sicer sprogramirali malo spodaj. Naloga celo eksplicitno pravi, da to lahko počnemo. Ampak tole ne dela, iz dveh razlogov.

def najvec_sosedov(mine, s, v):
    p = po_sosedih(mine, s, v)
    naj = max(p)
    return p[naj]

Ideja je čisto OK: poiščemo največji ključ. Dobimo ga kar z max(p), kjer je p tisti slovar, ki ga vrača po_sosedih. Ko gre max(p) z zanko for čez p, dobiva ravno ključe tega slovarja - ker gre zanka čez slovar pač čez njegove ključe. Ko imamo največji ključ, vrnemo pripadajočo vrednost.

Problem je v tem, da slovar vsebuje vse ključe od 0 do 8, torej bo največji ključ vedno 8. Sestavimo seznam tistih ključev, katerih pripadajoče vrednosti so neprazne množice: [k for k, v in p.items() if v]. Tu p.items() vrne vse pare ključev in vrednosti. Z zanko for gremo čez njih. V seznam dodamo vse ključe k, pri čemer mora biti v resničen, se pravi neprazen. (Če bo komu lažje: to je isto kot [k for k, v in p.items() if v != set()].) Zanima nas največji element tega seznama.

def najvec_sosedov(mine, s, v):
    p = po_sosedih(mine, s, v)
    naj = max([k for k, v in p.items() if v])
    return p[naj]

To še vedno ne deluje. Napaka, ki jo dobimo, je

    self.assertEqual(najvec_sosedov(mine1, s1, v1), (2, 1))
AssertionError: {(2, 1)} != (2, 1)

Funkcija bi morala vrniti terko (2, 1), vrne pa množico, ki vsebuje to terko, {(1, 2)}. Seveda. Vrednosti slovarja so množice koordinat. To bo preprosto rešiti: pač vrnemo enega od elementov te množice. Dobimo ga s pop.

To očitno vodi v rešitev v eni vrstici: samo oba p zamenjamo s po_sosedih(mine, s, v), pa vse skupaj zbašemo v eno samo vrstico.

def najvec_sosedov(mine, s, v):
    return po_sosedih(mine, s, v)[max(k for k, v in po_sosedih(mine, s, v).items() if v)].pop()

Ni pa posebej lepo, saj dvakrat kliče po_sosedih.

Lepša strategija je tale. Zgoraj smo pridelali seznam ključev, katerih pripadajoče vrednosti so neprazne množice. Pa pustimo v tem seznamu tudi vrednosti! Torej [(k, v) for k, v in po_sosedih(mine, s, v).items() if k]. Zdaj poiščemo maksimum tega. Ko Python primerja terke, jih najprej primerja po prvi vrednosti. max([(k, v) for k, v in po_sosedih(mine, s, v).items() if k]) (ali max((k, v) for k, v in po_sosedih(mine, s, v).items() if k) - ni nam potrebno sestaviti seznama, temveč lahko vrednosti kar generiramo), bo tista terka, ki ima največji ključ, zraven pa bo ohranjena tudi pripadajoča vrednost. Vzeti moramo element z indeksom 1 (to bo vrednost, množica koordinat) in iz te množice, tako kot zgoraj, s pop izvleči enega od elementov.

def najvec_sosedov(mine, s, v):
    return max((k, v) for k, v in po_sosedih(mine, s, v).items() if kdo)[1].pop()

Veliko elegantneje pa je, če si ne pomagamo z najvec_sosedov temveč gremo čez vsa polja in sestavljamo trojke (število sosedo, x, y). Potem preprosto poiščemo maksimum tega in vrnemo le x in y.

def najvec_sosedov(mine, s, v):
    return max((sosedov(x, y, mine), x, y) for x in range(s) for y in range(v))[1:]

Še boljše: ker nam je podarjena funkcija vsa_polja(s, v), ki izgleda takole

def vsa_polja(s, v):
    return ((x, y) for x in range(s) for y in range(v))

lahko zanki zamenjamo z eno samo:

def najvec_sosedov(mine, s, v):
    return max((sosedov(x, y, mine), x, y) for x, y in vsa_polja(s, v))[1:]

Dlakocepec bi se pritožil, da ta funkcija vrača seznam namesto terke. Prav, rezultat lahko mimogrede pretvorimo še v terko. A teste preživi tudi brez tega.

Brez sosedov

Napiši funkcijo brez_sosedov(mine, s, v), ki vrne množico vseh polj, ki nimajo na sosednjih poljih nobene mine. (Dovoljeno pa je, da mina stoji prav na tem polju). V gornjem primeru klic brez_sosedov(mine, 8, 4) vrne {(3, 0), (4, 2), (6, 1), (6, 3), (4, 3)}

Rešitev

Tule lahko vrnemo preprosto

def brez_sosedov(mine, s, v):
    return po_sosedih(mine, s, v)[0]

Ali pa sestavimo množico vseh polj brez sosedov.

def brez_sosedov(mine, s, v):
    return {(x, y) for x, y in vsa_polja(s, v) if not sosedov(x, y, mine)}

kar je, seveda, bližnjica za

def brez_sosedov(mine, s, v):
    brez = set()
    for x in range(s):
        for y in range(v):
            if not sosedov(x, y, mine):
                brez.add((x, y))
    return brez

Namesto dveh zank, kot ju imamo tule, lahko v vseh funkcijah uporabljamo vsa_polja, takole:

def brez_sosedov(mine, s, v):
    brez = set()
    for x, y in vsa_polja(s, v):
        if not sosedov(x, y, mine):
            brez.add((x, y))
    return brez

Generatorji (tisto, kar se skriva za funkcijo vsa_polja) so zakon. Škoda le, da jih pri Programiranju 1 ne obdelamo podrobneje, saj bi bilo to za mnoge pretežko.

Po sosedih

Napiši funkcijo po_sosedih(mine, s, v), ki vrne slovar, katerega ključi so števila od 0 do 8, pripadajoče vrednosti pa so množice koordinat polj, ki vsebujejo toliko min. V gornjem primeru bi klic po_sosedih(mine, 8, 4) vrnil slovar

{0: {(3, 0), (4, 2), (6, 1), (6, 3), (4, 3)},
 1: {(7, 3), (3, 2), (0, 0), (7, 0), (3, 3), (7, 1),
    (4, 0), (6, 0), (5, 0), (5, 3), (5, 1), (1, 0),
    (4, 1), (0, 3)},
 2: {(0, 1), (1, 2), (1, 3), (0, 2), (3, 1), (2, 0),
    (6, 2), (2, 3), (2, 2), (5, 2), (1, 1), (7, 2)},
 3: set(),
 4: {(2, 1)},
 5: set(),
 6: set(),
 7: set(),
 8: set()}

Rešitev

Navidez dobra ideja je

from collections import defaultdict

def po_sosedih(mine, s, v):
    po = defaultdict(set)
    for x, y in vsa_polja(s, v):
        po[sosedov(x, y, mine)].add((x, y))
    return po

Vendar sem nalogo otežil s tem, da sem zahteval, naj ima slovar vse ključe od 0 do 8, tudi če je pripadajoča vrednost prazna množica. defaultdict nam tu zato ne pomaga, saj bomo morali prazne množice tako ali tako dodati.

Druga navidez dobra ideja je

def po_sosedih(mine, s, v):
    po = dict.fromkeys(range(9), set())
    for x, y in vsa_polja(s, v):
        po[sosedov(x, y, mine)].add((x, y))
    return po

Tu dict.fromkeys(range(9), set()) naredi slovar, katerega ključi so števila od 0 do 8 (range(9)), pripadajoče vrednosti pa prazna množica. Torej {0: set(), 1: set(), 2: set(), 3: set(), 4: set(), 5: set(), 6: set(), 7: set(), 8: set()}.

Da, takšen slovar naredi. To že. Ampak vse te prazne množice so ena in ista prazna množica, kot smo spoznali na naslednjih predavanjih. Da naredimo slovar z različnimi praznimi množicami, potrebujemo

po = {}
for i in range(9):
    po[i] = set()

ali, krajše,

po = {i: set() for i in range(9)}

Cela rešitev je tedaj

def po_sosedih(mine, s, v):
    po = {i: set() for i in range(9)}
    for x, y in vsa_polja(s, v):
        po[sosedov(x, y, mine)].add((x, y))
    return po

To nas direktno pripelje v eno samo vrstico: namesto, da bi bile vrednosti prazne množice, naj bodo množice koordinat vseh polj z i sosedi.

def po_sosedih(mine, s, v):
    return {i: {(x, y) for x, y in vsa_polja(s, v) if sosedov(x, y, mine) == i} for i in range(9)}

S to funkcijo s tem imeli lovci na oceno 9 kar nekaj problemov. Vendar so bili koristni. Prejšnje funkcije v eni vrstici so bile dokaj rutinske, ta pa zahteva, da znamo pomisliti malo drugače. Kdor zna napisati tole, ta res razume, kako delujejo izpeljani seznami, slovarji in množice.

Za oceno 7

Zdaj pa hodimo po minskem polju. Pot opišemo z zaporedjem točk, na primer

pot = [(0, 0), (0, 3), (4, 3), (4, 2), (7, 2), (7, 3)]

Vsak premik je v vodoravni ali navpični smeri. Če gremo po gornji poti, gremo v resnici po poljih navzdol -- (0, 0), (0, 1), (0, 2), (0, 3); nato zavijemo desno in gremo prek (1, 3), (2, 3), (3, 3), (4, 3); odtod za eno polje gor na (4, 2) in potem desno na (5, 2), (6, 2), (7, 2), na koncu pa dol na (7, 3).

Dolžina poti

Napiši funkcijo dolzina_poti(pot), ki prejme pot in vrne njeno dolžino. V gornjem primeru vrne 12 (to je, 3 + 4 + 1 + 3 + 1).

Rešitev

Tule se ne bomo ukvarjali z range in tako naprej, temveč kar takoj napisali tako, kot se piše: zaporedne pare dobimo z zip(pot, pot[1:]). Ker pot vsebuje pare (terke), bodo zip(pot, pot[1:]) pari parov (terke terk). Na srečo zna Python razpakirati tudi to.

def dolzina_poti(pot):
    v = 0
    for (x0, y0), (x1, y1) in zip(pot, pot[1:]):
        v += abs(x0 - x1) + abs(y0 - y1)
    return v

Na vsakem odseku se spremeni bodisi koordinata x bodisi koordinata y. Vendar ni nobene potrebe, da bi pisali

        if x0 != x1:
            v += abs(y0 - y1)
        else:
            v += abs(x0 - x1)

kot so mnogi brez dvoma počeli. V izrazu abs(x0 - x1) + abs(y0 - y1) bo en člen vedno enak 0. A kaj za to!

Funkcija je čisto običajno seštevanje, torej je pretvorba v eno vrstico trivialna.

def dolzina_poti(pot):
    return sum(abs(x0 - x1) + abs(y0 - y1) for (x0, y0), (x1, y1) in zip(pot, pot[1:]))

Varen premik

Napiši funkcijo varen_premik(x0, y0, x1, y1, mine), ki pove, ali je s polja (x0, y0) varno iti (po poljih, kot smo opisali zgoraj) do polja (x1, y1). Kje so mine, pove argument mine. Če je varno, vrne True, če je na katerem od vmesnih polj mina, pa False. Upoštevaš lahko, da bo vedno veljalo bodisi x0 == x1 ali y0 == y1, saj so vsi premiki vodoravni ali navpični.

Rešitev

Ta vam je pa dala vetra! Veliko študentov je simuliralo premike, v slogu

if x0 == x1:
    for y in range(y0, y1 + 1):
        if (x0, y) in mine:
            return False

in tako naprej. Nekateri so odkrili, da lahko gredo čez mine in za vsako preverijo, ali je v intervalu.

if x0 == x1:
    for x, y in mine:
        if x == x0 and y in range(y0, y1 + 1)

Potem se zaplete še to, da je y0 lahko večji od y1... Funkcija se z vsakim posebnim primerom daljša in daljša.

S tako dolgimi rešitvami se ne bomo ukvarjali. Prvo, kar moramo uvideti, je, da range ni potreben. Če imamo, recimo, mino na (5, 2) in gremo z (5, 0) na (5, 8), bomo očitno stopili na mino: koordinata x je enaka 5, minina koordinata y pa je med koordinatama poti, po kateri gremo. Koordinate y je med koordinatama poti, če je večja ali enaka manjši od njiju, in hkrati manjša ali enaka večji. Tako dobimo

def varen_premik(x0, y0, x1, y1, mine):
    for x, y in mine:
        if x0 == x1 == x and min(y0, y1) <= y <= max(y0, y1) or \
                y0 == y1 == y and min(x0, x1) <= x <= max(x0, x1):
            return False
    return True

Če hočemo do spraviti v eno vrstico, uporabimo any (bomo kje stopili na mino) in ga zanikamo.

def varen_premik(x0, y0, x1, y1, mine):
    return not any(x0 == x1 == x and min(y0, y1) <= y <= max(y0, y1) or
                y0 == y1 == y and min(x0, x1) <= x <= max(x0, x1)
                for x, y in mine)

Nato pa opazimo, da bo takrat, ko velja x0 == x1 == x veljalo tudi x0 <= x <= x1. Pa imamo preprostejši pogoj:

def varen_premik(x0, y0, x1, y1, mine):
    return not any(min(x0, x1) <= x <= max(x0, x1) and min(y0, y1) <= y <= max(y0, y1)
                   for x, y in mine)

Če nam gresta na živce min in max se ju znebimo takole. Izračunamo, koliko je (x0 - x) * (x1 - x). Če je x manjši od obeh, sta oba faktorja pozitivna in produkt bo pozitiven. Če je x večji od obeh, sta ob faktorja negativna in produkt bo spet pozitiven. Negativen bo le, kadar je eden od faktorjev večji, drugi pa manjši od 0 - tedaj je x med x0 in x1. Kadar je produk enak 0, pa je eden od faktorjev enak 0, torej je mina točno na začetku ali koncu poti. Pa imamo:

def varen_premik(x0, y0, x1, y1, mine):
    return not any((x0 - x) * (x1 - x) <= 0 and (y0 - y) * (y1 - y) <= 0
                for x, y in mine)

Uporabimo de Morganovo pravilo: not any zamenjamo all, obrnemo neenakosti in zamenjamo and z or.

def varen_premik(x0, y0, x1, y1, mine):
    return all((x0 - x) * (x1 - x) > 0 or (y0 - y) * (y1 - y) > 0
                for x, y in mine)

Tisti, ki so malo manj, a vseeno še vedno kar zvidi, pa izračunajo presek množice koordinat min z množico koordinat na poti.

def varen_premik(x0, y0, x1, y1, mine):
    return not mine & {(x, y)
                       for x in range(min(x0, x1), max(x0, x1) + 1)
                       for y in range(min(y0, y1), max(y0, y1) + 1)}

Varna pot

Napiši funkcijo varna_pot(pot, mine), ki prejme celotno pot in pove, ali jo je varno prehoditi.

Rešitev

Pri merjenju dolžine poti smo se naučili priti do koordinat premikov

for (x0, y0), (x1, y1) in zip(pot, pot[1:]):

Skoraj delujoča rešitev je

def varna_pot(pot, mine):
    for (x0, y0), (x1, y1) in zip(pot, pot[1:]):
        if not varen_premik(x0, y0, x1, y1, mine):
            return False
    return True

Vendar ne deluje na kamnu masovne spotike - na testu, kjer je bila pot dolga eno samo točko.

    self.assertFalse(varna_pot([(1, 1)], mine1))
AssertionError: True is not false

Pot je tu [(1, 1)]. Začne in konča se na (1, 1) in smola hoče, da je ravno tam tudi mina. Tedaj je zip(pot, pot[1:]) isto kot zip([(1, 1)], []): ta zip ne vrne ničesar. Če ima seznam le en element, potem zaporednih parov ni.

To lahko rešimo tako, da pot dolžine 1 obravnavamo ločeno. Na začetek funkcije dodamo

if len(pot) == 1:
    return (pot[0], pot[1]) not in mine

Veliko lepši trik pa je tale: podvojimo prvo koordinato.

def varna_pot(pot, mine):
    for (x0, y0), (x1, y1) in zip([pot[0]] + pot, pot):
        if not varen_premik(x0, y0, x1, y1, mine):
            return False
    return True

Z zip([pot[0]] + pot, pot) bomo na začetku namesto prvega pravega premika dobili eno ponovitev prve koordinate -- x0 in x1 bosta enaka, y0 in y1 pa tudi. To nič ne škodi: če je tam mina, je mina, in če je ni, je ni. Tako ukrotimo pot dolžine 1. Žal pa to ne dela pri poti dolžine 0, prazni poti.

Tu pa se spomnimo trika, ki smo ga spoznali pri prejšnji domači nalogi. Če bi radi prvi element nekega seznama, a smo, kadar je seznam prazen, zadovoljni, če namesto prvega elementa dobimo prazen seznam, zahtevamo prvi 1 elementov.

def varna_pot(pot, mine):
    for (x0, y0), (x1, y1) in zip(pot[:1] + pot, pot):
        if not varen_premik(x0, y0, x1, y1, mine):
            return False
    return True

Ta rešitev se spet očitno pretvori v rešitev v eni vrstici. Varni morajo biti pač vsi premiki.

def varna_pot(pot, mine):
    return all(varen_premik(x0, y0, x1, y1, mine)
               for (x0, y0), (x1, y1) in zip(pot[:1] + pot, pot))

Za oceno 8

Napiši funkcijo polje_v_mine(polje), ki prejme niz s sliko polja, in vrne koordinate min ter širino in višino polja. Niz vsebuje vse vrstice, ločene s presledki; vsaka vrstica je sestavljena iz pik in X-ov.

Klic polje_v_mine("...X.... .X....X. .XX..... ......X.") mora vrniti ({(3, 0), (1, 1), (6, 1), (1, 2), (2, 2), (6, 3)}, 8, 4). (Ta niz opisuje natančno polje, kakršnega smo imeli v prvem primeru. V testih je niz razpisan v več vrstic, tako da ga boste lažje brali, vendar so posamezne vrstice še vedno ločene s presledki.)

(Mimogrede: prav to funkcijo sem si moral sam napisati, da sem lažje sestavljal teste. In če sem jo moral pisati jaz, ne vidim nobenega razloga, da ne bi s tem gnjavil še vas. :)

Rešitev

Tule zablesti enumerate. Pripravimo si prazno množico. Minsko polje razbijemo v vrstice. Nato gremo z for y, vrstica in enumerate(vrstice): čez te vrstice: y bo številka vrstice, vrstica bo vrstica.

Znotraj vrstice ponovimo vajo: napišemo for x, mina in enumerate(vrstica):, pa bo x koordinata x, mina pa bo črka, bodisi "X" bodisi ".". Če je prvo, v množico min dodamo koordinate tega polja.

def polje_v_mine(polje):
    mine = set()
    vrstice = polje.split()
    for y, vrstica in enumerate(vrstice):
        for x, mina in enumerate(vrstica):
            if mina == "X":
                mine.add((x, y))
    return mine, len(vrstica), len(vrstice)

Med vprašanji, ki so jih pošiljali študenti, sem pogosto videval

def polje_v_mine(polje):
    mine = set()
    vrstice = polje.split()
    for vrstica in vrstice:
        y = vrstice.index(vrstica)
        ... in tako naprej

To ne more delovati: če je več vrstic enakih, bo vrstice.index(vrstica) vrnil indeks prve med njimi. vrstica je pač nek niz, recimo ...X.. in klic vrstice.index(vrstica) je v tem primeru isto kot vrstice.index("...X.."). Seznam ne more narediti drugega, kot vrniti prvi takšen niz, saj ne ve, kje smo ga dobili.

Te naloge ni bilo potrebno reševati v eni vrstici. Ne zato, ker se ne bi dalo, temveč, ker je grdo. Recimo tako:

def polje_v_mine(polje):
    return ({(x % ((polje + ' ').find(' ') + 1), x // ((polje + ' ').find(' ') + 1))
            for x, y in enumerate(polje) if y == 'X'},
            (polje + ' ').find(' '),
            (len(polje) + 1) // ((polje + ' ').find(' ') + 1))

Brez komentarja.

Za oceno 9

Vse funkcije za oceno 6 in 7 morajo biti napisane v eni vrstici.

Tule je še nekaj uporabnih trikov, ki jih na predavanjih nisem omenil.

>>> [(x, y) for x in range(3) for y in range(4)]
[(0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (1, 1), (1, 2), (1, 3), (2, 0), (2, 1), (2, 2), (2, 3)]

Še boljše: tule je funkcija, ki vam jo pustim skopirati in uporabiti:

def vsa_polja(s, v):
    return ((x, y) for x in range(s) for y in range(v))

Preverite, kaj izpiše:

for x, y in vsa_polja(3, 4):
    print(x, y)

Uporabite, če želite.

Tole pa je eno hecno razpakiranje:

for (x0, y0), (x1, y1) in zip(pot, pot[1:])

Ker pot vsebuje pare koordinate, bo zip(pot, pot[1:]) vrnil pare parov. In razpakiramo jih, kot vidite zgoraj.

Rešitev

To je že za nami. :)

Za oceno 10

Naloge za oceno 10 niso tako težke, vendar se je pri njih zelo lahko zaplezati. Razmislite, kako se jih lotiti čimbolj sistematično. V moji rešitvi je vsaka od teh dveh funkcij dolga po 15 vrstic; vi se morda ne boste spomnili istih trikov, gotovo pa ga lomite, če bosta dolgi 100 vrstic.

Preberi pot

Napiši funkcijo preberi_pot(ukazi), ki dobi niz ukazi v obliki
```
DESNO
DESNO
3
LEVO
4
LEVO
1
DESNO
3
DESNO
1
```
pri čemer DESNO pomeni obrat za 90 stopinj na desno in LEVO obrat za 90 stopinj na levo (glede na trenutno smer), številka pa pomeni, da naredimo podano število korakov v tej smeri. Premikanje vedno začnemo na točki (0, 0), začetna smer je vedno gor (tako da bi y padal). Funkcija mora vrniti prehojeno pot.

Če funkciji podamo gornji niz, mora vrniti pot [(0, 0), (0, 3), (4, 3), (4, 2), (7, 2), (7, 3)].

Rešitev

Ker gre za nalogo za oceno 10, naj bo tale elegantna rešitev kar nova uganka. Razmisli, kako deluje!

def preberi_pot(ukazi):
    x = y = smer = 0
    pot = [(x, y)]
    for ukaz in ukazi.splitlines():
        if ukaz == "LEVO":
            smer = (smer + 3) % 4
        elif ukaz == "DESNO":
            smer = (smer + 1) % 4
        else:
            razdalja = int(ukaz)
            x += (smer % 2) * (2 - smer) * razdalja
            y += (1 - smer % 2) * (smer - 1) * razdalja
            pot.append((x, y))
    return pot

Zapiši pot

Napiši funkcijo zapisi_pot(ukazi), ki naredi ravno obratno.

Isto pot je mogoče opisati z različnimi ukazi. Vaša funkcija lahko vrne poljubno zaporedje ukazov, ki da pravo pot. Testi v resnici izgledajo takole:
```
pot = [(0, 0), (0, 3), (4, 3), (4, 2), (7, 2), (7, 3)]
self.assertEqual(preberi_pot(zapisi_pot(pot)), pot)
```
Test torej prepiše pot v ukaze, potem pa te ukaz nazaj v pot; po tem moramo dobiti isto.

Rešitev, ki sem jo sestavil jaz, za gornjo pot vrne naslednje ukaze:
```
DESNO
DESNO
3
DESNO
DESNO
DESNO
4
DESNO
DESNO
DESNO
1
DESNO
3
DESNO
1
```
(Kot vidite, nikoli ne zavijam levo, temveč grem raje trikrat desno. Tako mi je bilo pač bolj praktično.)

Rešitev

Spet: kar sam ugani, kako to deluje.

def sign(x):
    return int(x / max(1, abs(x)))

def zapisi_pot(pot):
    if not pot:
        return ""
    ukazi = []
    smer = 0
    x, y = pot[0]
    for nx, ny in pot[1:]:
        dx, dy = nx - x, ny - y
        nsmer = sign(dx) + max(sign(dy), 0) * 2
        dsmer = (nsmer - smer) % 4
        ukazi += ["DESNO"] * dsmer + [str(abs(dx + dy))]
        x, y, smer = nx, ny, nsmer
    return "\n".join(ukazi)

Testi

Testi že vsebujejo začetke definicij vseh funkcij. Namesto kode funkcija pa je večvrstični niz z dokumentacijo funkcije. Ta je napisana po določenem standardu. Te nize lahko pobrišete in napišete definicije funkcij. Lahko pa jih tudi pustite. Če jih pustite, bo PyCharm pameten: če na imenu funkcije (tam, kjer jo definirate ali pa tam, kjer jo kličete) pritisnete F1, boste dobili dokumentacijo.

Še več. Tole je eden od načinov, da Pythonu poveste, kakšnega tipa so argumenti funkcije. Python s tem nikoli ne teži: če hočeš poklicati funkcijo z napačnimi argumenti, ti to dovoli. Liberalec pač. Pač pa bo PyCharm namignil, da tole ne bo dobro.

Pozor: ne dopisujte novih funkcij nad te funkcije. Če boste na začetek datoteke napisali novo funkcijo, spodaj pa pustili mojo (ki ne dela ničesar), bo obveljala moja.

Na začetku testov so narisana polja, ki se uporabljajo v testih. Nekatere slike se kasneje ponovijo, da so bolj pri roki.

마지막 수정됨: 수요일, 24 3월 2021, 3:53 PM

Course Activities

Recent Courses

Testi

Naloga

Za oceno 6

Število sosedov

Rešitev

Največ sosedov

Rešitev

Brez sosedov

Rešitev

Po sosedih

Rešitev

Za oceno 7

Dolžina poti

Rešitev

Varen premik

Rešitev

Varna pot

Rešitev

Za oceno 8

Rešitev

Za oceno 9

Rešitev

Za oceno 10

Preberi pot

Rešitev

Zapiši pot

Rešitev

Testi