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):

Slike plošč

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) vrne True, če se koordinati nahajata znotraj plošče in False, č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 kot preberi, 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) vrne True, če polje vodi v cikel - torej, če igralec, ki bi začel na tem polju, nikoli ne bi stopil s plošče, in False, č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) vrne True, če bi se igralec, ki začne na tem polju, kdaj vrnil na to polje, in False, če ne.

  • vrnljiva(plosca) vrne množico vseh polj, ki so "vrnljiva"

  • varno(plosca, x, y) vrne True, če polje ne vodi (v enem koraku) ven iz plošče in False, č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 vrne None.

    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. Funkcija igra izvede 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}
Zadnja sprememba: sreda, 24. marec 2021, 15.51