Kojn

Testi

testi-kojn.py

Naloga

Šahovski konj je žival, ki živi na šahovnici in se premika v obliki črke L. O njegovi pomembnosti priča tudi to, da mu je posvečen poseben članek na Wikipediji. Posvečena mu je tudi ta naloga.

Pri vsaki nalogi, razen pri nalogi za oceno 10, morate obvezno uporabiti funkcijo, ki ste jo napisali pri prejšnji nalogi!

Pri rešitvah smete uporabljati funkciji, ki smo ju napisali na predavanjih:

def polje_v_koord(polje): return ord(polje[0]) - 64, int(polje[1]) def koord_v_polje(x, y): return chr(x + 64) + str(y)

Za ogrevanje

Napišite funkcijo legalne_koord(x, y), ki prejme koordinati polja (x je stolpec, y vrstica) in vrne True, če so koordinate pravilne (ob koordinati sta med, vključno, 1 in 8), in False, če niso.

>>> legalne_koord(4, 5) True >>> legalne_koord(0, 6) False >>> legalne_koord(-5, 10) False >>> legalne_koord(6, 9) False

Za oceno 6

Napišite funkcijo moznosti(polje), ki kot argument dobi polje (v šahovskih koordinatah, npr. "B4") in kot rezultat vrne seznam polj, na katera lahko s tega polja skoči konj. Polja naj bodo urejena po abecedi. (Namig: sicer lahko uporabite tudi funkcijo sort, vendar se ji poskusite izogniti: raje sestavite seznam tako, da bo urejen.)

>>> moznosti("B4") ['A2', 'A6', 'C2', 'C6', 'D3', 'D5'] >>> moznosti("A1") ['B3', 'C2'] >>> moznosti("D5") ['B4', 'B6', 'C3', 'C7', 'E3', 'E7', 'F4', 'F6']

Za oceno 7

Napišite funkcijo legalna(polje1, polje2), ki za par polj pove, ali konj lahko skoči iz enega polja na drugo.

>>> legalna("A1", "B3") True >>> legalna("F3", "D4") True >>> legalna("B2", "D4") False

Za oceno 8

Napišite funkcijo legalna_pot(pot), ki kot argument dobi pot konja (seznam s poljubnim številom zaporednih polj, po katerih je skakal konj) in vrne True, če je pot pravilna in False, če ni. Predpostaviti smete, da vsebuje seznam vsaj eno polje.

>>> legalna_pot(["F3", "E1", "G2", "H4", "F5"]) True >>> legalna_pot(["F3", "E1", "G3", "H5"]) False >>> legalna_pot(["B4"]) True

Za oceno 9

Napišite funkcijo obhod(pot), ki za podano pot pove, ali vsebuje obhod konja prek vseh polj šahovnice. Konj se mora gibati pravilno in mora obiskati vsako polje natančno enkrat. Izjema je samo zadnje polje, ki mora biti enako prvemu.

>>> obhod(["A2", "B4", "D3"]) False

Več primerov je v testih.

Za oceno 10

Napišite funkcijo razdalje(), ki vrne število potez, ki ga konj potrebuje, od zgornjega levega polja do ostalih polj šahovnice. Funkcija mora vrniti takšen niz:

03232345 34123434 21432345 32323434 23234345 34343454 43434545 54545456

Niz torej predstavlja šahovnico in vsako številka na posameznem polju pove, koliko (najmanj) potez potrebuje konj do posameznega polja.

Niz razbijete v vrstice tako, da na konec vsake vrstice dodate "\n".

>>> print("a\nb\nc") a b c

Funkcija mora seveda izračuati niz; če ga bo kdo shranil in izpisal, bomo to razumeli kot (blažji) poskus goljufije. Naloge se lahko lotite tako, da najprej premislite, kako bi jo rešili ročno. Vzemite list karirastega papirja, narišite šahovnico in v zgornji levi kvadratek ničlo. Nato v vsa polja, v katera lahko pridete s tega polja, napišete enico. Nato na vsa polja, kjer ste pravkar napisali enico, napišete ...

Ocene 5-9

# Ocena 5 def legalne_koord(x, y): return 0 < x < 9 and 0 < y < 9 # Ocena 6 def moznosti(polje): m = [] x, y = polje_v_koord(polje) for dx, dy in ((-2, -1), (-2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2), (2, -1), (2, 1)): x1, y1 = x + dx, y + dy if legalne_koord(x1, y1): m.append(koord_v_polje(x1, y1)) return m # Ocena 7 def legalna(polje1, polje2): return polje2 in moznosti(polje1) # Ocena 8 def legalna_pot(pot): for i in range(len(pot)-1): if not legalna(pot[i], pot[i+1]): return False return True # Ocena 9 def obhod(pot): if len(pot) != 65 or not legalna_pot(pot) or pot[0] != pot[-1]: return False for i, polje in enumerate(pot[:-1]): if polje in pot[:i]: return False return True

Rešitve so komajda vredne komentarja. Bistvo naloge ni bilo programiranje zank in pogojev (to naj bi po enem mesecu že nekako znali), temveč spretno klicanje funkcij, ki smo jih že napisali.

Pri nalogi za oceno 5 ste morali znati elegantno zapisati pogoj. Seveda ga je bilo, kot vedno, možno tudi brez potrebe zaplesti.

Rešitev za oceno 6 je bilo mogoče skrajšati z nekaj zvitosti: pripravimo si seznam premikov konja in ga prištejemo k trenutnemu polju, a obdržimo le tiste premike, ki dajo legalno polje. Katero polje je legalno, pa preverimo s funkcijo, ki smo jo napisali za oceno 5.

Daljša različica bi lahko šla takole:

kandidati = [(x-2, y-1), (x-2, y+1), (x-1, y-2), (x-1, y+2), (x+1, y-2), (x+1, y+2), (x+2, y-1), (x+2, y+1)] m = [] for polje in kandidati: if legalno_polje(polje): m.append(polje)

Rešitev za oceno 7 ne bi mogla biti lažja, kot je: skok s polje1 na polje2 je legalen, če je polje2 na seznamu polj, na katera je mogoče priti s polja polje1.

Za oceno 8 se je potrebno sprehoditi čez seznam polj in dati funkciji s prejšnje naloge preveriti vsak zaporedni par.

Za nalogo 9 mora biti pot legalna (kar preverimo s funkcijo iz naloge 8), dolga 65 polj, prvo polje mora biti enako zadnjemu, poleg tega pa se nobeno polje ne sme ponoviti - preveriti je potrebno, da se i-to polje ne pojavlja na seznamu prvih i-1 polj.

Za oceno 10

Tole ni najhitrejša, temveč le najbolj razumljiva rešitev. Pokazali bomo tudi precej boljšo.

# Ocena 10, počasnejša različica def razdalje(): sahovnica = [] for i in range(8): sahovnica.append([-1] * 8) sahovnica[0][0] = 0 obiskanih = 1 skok = 1 while obiskanih < 64: for x in range(1, 8): for y in range(1, 8): if sahovnica[x-1][y-1] == skok-1: for kam in moznosti(koord_v_polje(x, y)): xn, yn = polje_v_koord(kam) if sahovnica[xn-1][yn-1] < 0: sahovnica[xn-1][yn-1] = skok obiskanih += 1 skok += 1 s = "" for vrstica in sahovnica: for skokov in vrstica: s += str(skokov) s += "\n" return s

Najprej sestavimo seznam osmih seznamov, ki vsebujejo po osem številk -1; -1 bo pomenila, da razdalja do tega polja še ni bila izračunana.

Za zgornje levo polje nastavimo, da ga dosežemo v 0 korakih in si zapomnimo, da poznamo razdaljo do enega samega polja (obiskanih=1). V naslednjem koraku bomo označili polja, do katerih potrebujemo en skok (skok=1). Dokler ne obiščemo vseh 64 polj, ponavljamo naslednje: preletimo vso šahovnico. Če naletimo na polje, do katerega smo prišli v 0 skokih, zabeležimo, da se do njega pride v enem skoku in povečamo število obiskanih polj. Ko tako pridemo čez vso šahovnico, gremo čeznjo ponovno: iščemo vsa polja, do katerih smo prišli v enem skoku in zabeležimo, da do njih pridemo v dveh skokih ... in tako naprej.

Bistveno boljše je tole:

# Ocena 10, hitrejša različica def razdalje(): sahovnica = [[-1] * 8 for i in range(8)] sahovnica[0][0] = 0 kandidati = ["A8"] while kandidati: polje = kandidati.pop(0) x, y = polje_v_koord(polje) skokov = sahovnica[x-1][8-y] for naprej in moznosti(polje): x, y = polje_v_koord(naprej) if sahovnica[x-1][8-y] == -1: sahovnica[x-1][8-y] = skokov+1 kandidati.append(naprej) s = "" for vrstica in sahovnica: for skokov in vrstica: s += str(skokov) s += "\n" return s

Seznam kandidati bo vseboval vsa polja, do katerih smo prišli, nismo pa še preiskali poti z njih. Na začetku označimo, da je pod do A8 (sahovnica[0][0]) dolga 0 skokov in damo A8 na seznam kandidatov. Nato ponavljamo zanko, dokler seznam kandidatov ni prazen. S kandidati.pop(0) poberemo prvega kandidata in pogledamo, koliko skokov je potrebnih do njega. Preverimo vsa polja, do katerih je možnost skočiti s "kandidata": če na teh poljih še nismo bili, si zapomnimo, da je pot do njih dolga en skok več kot do "kandidata" in dodamo to polje med kandidate.

Resne rešitve

Funkcije, ki smo jih napisali tule, so relativno dolge. Če bi šlo zares, bi jih sprogramirali takole.

# Ocena 5 def legalne_koord(x, y): return 0 < x < 9 and 0 < y < 9 # Ocena 6 def moznosti(polje): x, y = polje_v_koord(polje) return [koord_v_polje(x+dx, y+dy) for dx, dy in ((-2, -1), (-2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2), (2, -1), (2, 1)) if legalne_koord(x+dx, y+dy)] # Ocena 7 def legalna(polje1, polje2): return polje2 in moznosti(polje1) # Ocena 8 def legalna_pot(pot): return all(legalna(polje1, polje2) for polje1, polje2 in zip(pot, pot[1:])) # Ocena 9 def obhod(pot): return len(pot) == 65 and len(set(pot)) == 64 and pot[0] == pot[-1] and legalna_pot(pot)

Pri rešitvi za oceno 10 nam je v nadlego, da funkcija moznosti dela z nerodnimi šahovskimi koordinatami. V praksi bi se jim izogibali; tule bomo, da bomo funkcija krajša, uporabili rešitev s slovarji, ki časovno ni ravno optimalna, je pa lepa.

# Ocena 10 def razdalje(): sahovnica = {} kandidati = [("A8", 0)] while kandidati: polje, skokov = kandidati.pop(0) if polje not in sahovnica: sahovnica[polje] = skokov kandidati += [(polje2, skokov+1) for polje2 in moznosti(polje)] return "\n".join("".join(str(sahovnica[i+j]) for i in "ABCDEFGH") for j in "87654321")