Igra
Testi
Testi: testi-igra.zip
Naloga
S to nalogo se bomo spomnili Josipa Jurčiča, ki bi bil rojen ravno na današnji dan, če bi bil rojen 28. novembra in ne 4. marca.
Imamo pravokotno igralno ploščo poljubne velikosti. Na vsakem polju je označeno, kam se moramo premakniti z nje. Smer je podana s črko S, J, V ali Z (sever, jug, vzhod, zahod), sledi pa ji število (eno ali večmestno), ki označuje razdaljo. Tako, recimo, J12 pomeni premik za 12 polj na jug.
Ploščo opišemo s seznamom seznamov. Prva plošča s spodnjih slik je opisana tako:
plosca1 = [["J2", "Z1", "J1"],
["V2", "V1", "S2"],
["S1", "Z1", "S1"]]
Ker je vsebina plosca1[1][0] enaka "V2", se s tega polja premaknemo dve polji
proti vzhodu, torej na plosca1[1][2], na katerem imamo "S2", kar pomeni, da
gremo za dve polji proti severu (ob čemer pademo prek zgornjega roba!).
V testih za ocene od 7 naprej so uporabljene naslednje tri plošče (in še dve preprostejši):
Ogrevanje
Napiši naslednje funkcije.
visina(plosca)vrne višino plošče.sirina(plosca)vrne širino plošče.polj(plosca)vrne število polj na plošči-na_plosci(plosca, x, y)vrneTrue, če se koordinati nahajata znotraj plošče inFalse, če se ne.preberi(plosca, x, y)prejme opis plošče in koordinati polja ter vrne par (terko) s smerjo in dolžino. Tako mora, na primer,preberi(plosca1, 0, 1)vrniti("V", 2).
Rešitev
Vse to je bilo samo toliko, da se navadite na ploščo. Nič resnega.
def visina(plosca):
return len(plosca)
def sirina(plosca):
return len(plosca[0])
def polj(plosca):
return visina(plosca) * sirina(plosca)
def na_plosci(plosca, x, y):
return 0 <= x < sirina(plosca) and 0 <= y < visina(plosca)
def preberi(plosca, x, y):
vsebina = plosca[y][x]
return vsebina[0], int(vsebina[1:])
V funkciji na_plosci naj tisti, ki so navajeni kakega drugega jezika,
ne spregledajo, da smemo pisati kar 0 <= x < sirina(plosca) in ne
0 <= x and x < sirina(plosca) (ali celo 0 <= x && x < sirina(plosca)).
Za oceno 6
Igro igramo tako, da postavimo figuro na določeno polje in jo nato premikamo, skladno z navodili na poljih.
premakni(plosca, x, y)prejme enake argumente kotpreberi, vendar vrne novi koordinati.premakni(plosca1, 0, 1)mora vrniti(1, 2).Namig: morda ti bo pomagal slovar, katerega ključi so črke, vrednosti pa pripadajoče spremembe koordinat x in y,
premiki = {"S": (0, -1), "J": (1, 0), "V": (-1, 0), "Z": (1, 0)}. Ni pa nujno; narediš lahko tudi drugače.dolzina_poti(plosca, x, y)prejme začetne koordinate in vrne dolžino poti, ki jo naredi figura, preden pade ven iz plosca. Predpostaviš lahko, da se bo to vedno zgodilo.Namig: v zanki, ki teče, dokler je figura na plošči, izvajaj in štej poteze. To je vse.
Rešitev
def premakni(plosca, x, y):
smer, r = preberi(plosca, x, y)
dx, dy = {"S": (0, -r), "J": (0, r), "V": (r, 0), "Z": (-r, 0)}[smer]
return x + dx, y + dy
def dolzina_poti(plosca, x, y):
dolzina = 0
while na_plosci(plosca, x, y):
x, y = premakni(plosca, x, y)
dolzina += 1
return dolzina
V premakni lahko uporabimo celo nekoliko boljši trik, kot ga je predlagala
naloga: zapišemo si premik, za r in ne samo za eno enoto (ki bi ga potem
morali še množiti z r).
V dolzina_poti pa le kličemo premakni, dokler smo na_plosci. V klicu
premakni ne smemo pozabiti, da funkcija ne spreminja vrednosti argumentov
x in y (tega niti ne more storiti), temveč vrne novi vrednosti za x in
y, zato moramo pisati x, y = premakni(plosca, x, y) in ne samo
x, y = premakni(plosca, x, y).
Za oceno 7
pot(plosca, x, y)podobno kot prejšnja funkcija, le da vrne seznam ali generator polj (kar je še lažje), ki jih figura obišče. Seznam naj ne vsebuje polja, ki je že izven plošče.
Rešitev
To je čisto podobno kot dolzina_poti, le da namesto prištevanja
dolzina += 1 shranjujemo prehojene koordinate v seznam p, tako da
kličemo p.append((x, y)).
def pot(plosca, x, y):
p = []
while na_plosci(plosca, x, y):
p.append((x, y))
x, y = premakni(plosca, x, y)
return p
Z generatorji je, kot običajno, še preprosteje:
def pot(plosca, x, y):
while na_plosci(plosca, x, y):
yield x, y
x, y = premakni(plosca, x, y)
Za oceno 8
ciklicno(plosca, x, y)vrneTrue, če polje vodi v cikel - torej, če igralec, ki bi začel na tem polju, nikoli ne bi stopil s plošče, inFalse, če ne. Pazi: polje lahko vodi v cikel, ne da bi sodelovalo v ciklu: vsa tri polja plošče[["V2", "V1", "Z1"]]vodijo v cikel, čeprav v samem ciklu sodelujeta le desni polji.Namig: razmisli, kakšna je najdaljša možna pot brez cikla.
ciklicna(plosca)vrne množico vseh polj (polje je opisano s koordinatami), ki vodijo v cikle.vrnljivo(plosca, x, y)vrneTrue, če bi se igralec, ki začne na tem polju, kdaj vrnil na to polje, inFalse, če ne.vrnljiva(plosca)vrne množico vseh polj, ki so "vrnljiva"varno(plosca, x, y)vrneTrue, če polje ne vodi (v enem koraku) ven iz plošče inFalse, če po potezi, na tem polju ostanemo na plošči.varna(plosca)vrne množico vseh polj, ki so varna.
V razmislek: morda se ti splača napisati funkcijo izberi(plosca, lastnost),
ki vrne množico koordinat vseh polj, ki imajo podano lastnost. Pri tem je
lastnost funkcija, ki prejme ploščo in koordinati in vrne True ali False.
Na ta način boš v funkcijah ciklicna, vrnljiva in varna le poklical
izberi s primernimi argumenti. Če ne znaš rešiti na ta način, pa nič hudega;
boš pa na malo daljšega.
Rešitev
Ali je polje ciklično, preverimo tako da naredimo toliko potez, kolikor polj ima plošča. Če smo po tem še vedno na plošči, se je eno polje gotovo ponovilo. In če se je ponovilo eno polje ... se bo ponavljalo vse.
Hodimo torej po plošči in če pademo z nje, vrnemo False. Če se to ne zgodi
in smo po polj(plosca) potezah še vedno na njej, pa vrnemo True, saj je
polje ciklično.
def ciklicno(plosca, x, y):
for _ in range(polj(plosca)):
if not na_plosci(plosca, x, y):
return False
x, y = premakni(plosca, x, y)
return True
Množico cikličnih polj bomo sestavili kot izpeljano množico vseh koordinat
(x, y) for x in range(sirina(plosca)) for y in range(visina(plosca)), ki so
ciklične (if ciklicno(x, y)).
def ciklicna(plosca):
return {(x, y) for x in range(sirina(plosca)) for y in range(visina(plosca))
if ciklicno(x, y)}
Ali je polje "vrnljivo" preverjamo s podobnim trikom kot, ali je ciklično.
Koordinati prepišemo v dve novi spremenljivki, x, y = x0, y0. Nato naredimo
polj(plosca) korakov. Če pri tem pademo s plošče, prekinemo zanko in vrnemo
False. Če smo prišli do začetnega polja, vrnemo True. Ko se zanka konča,
pa smo lahko prepričani, da smo se zaciklali, vendar se pri tem ne vračamo na
začetno polje; torej ni vrnljivo in lahko vrnemo False.
Funkcija vrniljiva je takšna kot ciklicna, le drugo funkcijo kliče.
def vrnljivo(plosca, x0, y0):
x, y = x0, y0
for _ in range(polj(plosca)):
x, y = premakni(plosca, x, y)
if not na_plosci(plosca, x, y):
break
if (x, y) == (x0, y0):
return True
return False
def vrnljiva(plosca):
return {(x, y) for x in range(sirina(plosca)) for y in range(visina(plosca))
if vrnljivo(x, y)}
Funkciji varno in varna sta preprosti.
def varno(plosca, x, y):
x, y = premakni(plosca, x, y)
return na_plosci(plosca, x, y)
def varna(plosca):
return {(x, y) for x in range(sirina(plosca)) for y in range(visina(plosca))
if varno(x, y)}
Funkcije ciklicna, vrnljiva in varna so si zelo podobne: vse sestavijo
množico vseh polj, ki imajo določeno lastnost; pri tem lastnost preverja
določena funkcija (ciklicno, vrnljivo in varno). Torej lahko napišemo
splošnejšo funkcijo za sestavljanje množic polj z določeno lastnostjo; vse
tri funkcije potem le kličejo to funkcijo.
def izberi(plosca, lastnost):
return {(x, y) for x in range(sirina(plosca)) for y in range(visina(plosca))
if lastnost(plosca, x, y)}
def ciklicna(plosca):
return izberi(plosca, ciklicno)
def vrnljiva(plosca):
return izberi(plosca, vrnljivo)
def varna(plosca):
return izberi(plosca, varno)
Za oceno 9
dolzina_cikla(plosca, x, y)vrne dolžino cikla, v katerem se vrti figura, če začne na polju(x, y). Upoštevaj, da polje(x, y)ne sodeluje nujno v ciklu, temveč morda le vodi vanj. Če polje ne vodi v cikel, temveč pripelje pot prek roba plošče, naj funkcija vrneNone.Namig: figuro premikaj toliko časa, da se bo gotovo znašla v ciklu. Nato jo premikaj še toliko časa, da boš izmeril dolžino cikla.
veckratnik_ciklov(plosca)vrne najmanjši skupni večkratnik dolžin ciklov. Če ciklov ni, naj vrne 1.
Rešitev
Dalo bi se elegantneje, vendar ne bomo komplicirali: funkcijo dolzina_cikla
bomo napisali tako, da bomo najprej naredili polj(plosca) korakov. Če pri
tem pademo s plošče, vrnemo None, kot ahtevajo navodila.
Po toliko korakih pa smo lahko prepričani, da smo že znotraj cikla. Zdaj moramo le še izmeriti, po koliko korakih bomo stali na istem polju, kot stojimo sedaj.
Namesto da bi uporabili zanko while in šteli sami, tako kot smo prej,
bomo uporabili zanko for, ki pa jo prekinemo z returnom.
def dolzina_cikla(plosca, x, y):
for _ in range(polj(plosca)):
x, y = premakni(plosca, x, y)
if not na_plosci(plosca, x, y):
return None
x0, y0 = x, y
for dolzina in range(polj(plosca)):
x, y = premakni(plosca, x, y)
if (x0, y0) == (x, y):
return dolzina + 1
Če vam je trik s for všeč, si vsekakor oglejte funkcijo itertools.count.
Za drugi del te naloge bomo najprej napisali funkcijo, ki izračuna največji skupni delitelj in z njo najmanjši skupni večkratnik.
def gcd(a, b):
while b != 0:
a, b = b, a % b
return a
def lcm(a, b):
return a * b // gcd(a, b)
Zdaj gremo prek vseh polj in računamo najmanjši skupni večkratnik - vseh tistih, ki so ciklična.
def veckratnik_ciklov(plosca):
veckratnik = 1
for x in range(sirina(plosca)):
for y in range(visina(plosca)):
cikel = dolzina_cikla(plosca, x, y)
if cikel is not None:
veckratnik = lcm(veckratnik, cikel)
return veckratnik
Če koga zanima, ali se da to napisati krajše, naj pogleda functools.reduce.
Za oceno 10
igra(plosca, zacetki)prejme ploščo in seznam koordinat začetnih polj igralcev. Igralci nato izmenično delajo poteze, začenši s prvim v seznamu. Igralec je izločen, če pade iz igralne plošče ali če na polje, na katerem stoji, pride drug igralec. Zmaga igralec, ki zadnji ostane na plošči. Funkcijaigraizvede igro in pove zaporedno številko zmagovalca.Predpostaviš lahko, da se igra vedno konča.
Rešitev
Tole ni posebna umetnost, le lepo previdno moraš izločati igralce.
def igra(plosca, pozicije):
igralcev = len(pozicije)
zadnji = 0
while igralcev > 1:
for igralec, (x, y) in enumerate(pozicije):
if x is None:
continue
x, y = premakni(plosca, x, y)
if not na_plosci(plosca, x, y):
pozicije[igralec] = None, None
igralcev -= 1
zadnji = igralec
continue
drugi = pozicije.find((x, y))
if drugi > 0:
pozicije[drugi] = None, None
igralcev -= 1
zadnji = igralec
return zadnji
Za oceno 11
igra(plosca, zacetki): kot pri prejšnji nalogi, vendar tako, da ne predpostaviš, da se igra vedno konča. To se lahko zgodi, če se dva ali več tekmovalcev podi v krogu ali krogih, ne da bi se kdaj srečali. Funkcija naj namesto indeksa zmagovalca (kot pri nalogi za oceno 10) vrne množico indeksov vseh, ki ostanejo večno na plošči.Namig: razmisli, po koliko potezah smo lahko prepričani, da se je igra zaciklala.
Rešitev
Tule ni potrebno dodati dosti drugega kot razmisliti, po koliko potezah so se gotovo vsi zaciklali. In, glej no, po toliko potezah, kolikor je najmanjši skupni večkratnik dolžin vseh ciklov. :)
def igra(plosca, pozicije):
igralcev = len(pozicije)
for i in range(polj(plosca) + veckratnik_ciklov(plosca)):
for igralec, (x, y) in enumerate(pozicije):
if x is None:
continue
x, y = premakni(plosca, x, y)
if not na_plosci(plosca, x, y):
pozicije[igralec] = None, None
igralcev -= 1
continue
elif (x, y) in pozicije:
pozicije[pozicije.index((x, y))] = None, None
igralcev -= 1
pozicije[igralec] = x, y
if igralcev == 1:
break
if igralcev == 1:
break
return {i for i, (x, y) in enumerate(pozicije) if x is not None}