Nim

Testi

testi-nim.py

Naloga

Ker smo se ravno učili o funkcijah, boš moral (ali morala, če si v manjšini) napisati kup funkcij. Na koncu bodo vodile - čeprav ne po najkrajši poti - v program, ki bo znal (dobro) igrati igro Nim.

Nim se začne tako, da v nekaj vrstic postavimo nekaj kovancev, na primer tako:

1 (4)  * * * *
2 (7)  * * * * * * *
3 (5)  * * * * *
4 (6)  * * * * * *

Igralca izmenično jemljeta kovance. Ko je igralec na potezi, lahko iz poljubne vrstice (vendar le ene) vzame poljubno število kovancev. Zmaga igralec, ki vzame zadnji kovanec. Če prvi igralec vzame, recimo, tri kovance iz druge vrstice, dobimo

1 (4)  * * * *
2 (4)  * * * *
3 (5)  * * * * *
4 (6)  * * * * * *

Obvezna naloga

Napiši torej naslednje funkcije:

najvecja_potenca(n) vrne največjo potenco števila 2, ki je manjša ali enaka podanemu števila n. Klic najvecja_potenca(22) vrne 16, saj bi bilo 32 že preveč. Klic najvecja_potenca(32) pa vrne 32. Število n je pozitivno realno število. Število naračunaj sam; uporaba modula math ali česa podobnega v tej funkciji je prepovedana.

Precej študentov je - po zaslugi nekoga, ki misli, da jim pomaga, če se gre "tutorja" in jim pošilja svoje rešitve - oddalo takšno funkcijo (oziroma kakšno manjšo variacijo le-te):

def najvecja_potenca(n):
    najvecja = 0
    for i in range(0, n + 1):
        x = 2 ** i
        if x <= n:
            najvecja = x
        else:
            break
    return najvecja

Pa pokomentirajmo to reč. Začnimo s for, ki pošlje i (kasneje potem računamo 2 ** i) od 0 do n + 1. Zgornja meja je sicer prevelika, a ideja je prav v tem, da bo 2 ** n gotovo že večje od n, torej bo zanka zagotovo tekla "dovolj časa". Da se bo ustavila v ustreznem trenutku, pa bo itak poskrbel break.

Sam bi to raje napisal z while, ne for: for uporabim, ko grem prek kake reči (seznama, terke, slovarja, datoteke...) ali pa, kadar štejem in vem, do kod moram prešteti. K tej nalogi pa se mi veliko bolj poda kratek in jasen while 2 ** i <= n. Resda pa moramo potem v zanki pisati i += 1. Če bi kdo zaradi tega raje uporabil for, lahko uporabi count(), ki je podoben range, vendar šteje do neskončno. Funkcijo count dobimo v modulu itertools.

Zakaj se je avtorju te množično oddane rešitve zdelo posebej potrebno poudariti, naj range teče od 0, pa ne vem. range(n + 1) bi namreč naredil natančno isto kot range(0, n + 1).

Naslednje, kar je tu nepotrebno, je najvecja. Ko zanko prekinemo z break, je najvecja ravno enaka prejšnjemu x, ta pa je pol manjši od trenutnega. Se pravi, najvecja je isto kot x // 2.

Sploh pa ni potrebe, da bi zanko prekinjali z break, če ji sledi le return. Namesto break-a napišemo return, pa je.

To rešitev lahko torej spremenimo v

def najvecja_potenca(n):
    for i in range(n + 1):
        x = 2 ** i
        if x > n:
            return x // 2

ali

def najvecja_potenca(n):
    for i in range(n + 1):
        if 2 ** i > n:
            return 2 ** (i - 1)

ali

from itertools import count

def najvecja_potenca(n):
    for i in count():
        if 2 ** i > n:
            return 2 ** (i - 1)

Različica z while pa je, recimo

def najvecja_potenca(n):
    i = 0
    while 2 ** i <= n:
        i += 1
    return 2 ** (i - 1)

Toliko o "tutorski" rešitvi. Sam bi nalogo raje rešil brez potenciranja, z množenjem:

def najvecja_potenca(n):
    r = 1
    while r <= n:
        r *= 2
    return r // 2

• razbij(n) vrne seznam potenc števila 2, ki se seštejejo v podano število n; vsaka potenca lahko nastopa le enkrat. Klic razbij(22) vrne [16, 4, 2]. Števila naj bodo urejena v padajočem vrstnem redu. Nalogo reši tako, da s prejšnjo funkcijo poiščeš največjo potenco ter jo dodaš v seznam in jo odšteješ od števila n. To ponavljaš, dokler ne dobiš 0. Morda za začetek razmisli, kako bi to nalogo rešil ročno, potem pa jo sprogramiraj na enak način. (Če te naloga (upravičeno) spominja na pretvarjanje v dvojiški zapis, naj te to ne moti. Tudi s tem, kako neučinkovito je takšno pretvarjanje, se ne ukvarjaj.)

Funkcija bo vrnila seznam, torej moramo najprej narediti seznam. Prazen seznam, vendar ga, prosim, ne poimenujmo prazen_seznam. Naj bo, recimo razbitje. Nato ponavljamo tole vajo: poiščemo največjo potenco, jo dodamo v seznam in odštejemo od podanega števila. To ponavljamo, dokler ne ostane 0.

def razbij(n):
    razbitje = []
    while n:
        p = najvecja_potenca(n)
        razbitje.append(p)
        n -= p
    return razbitje

• vsebuje(s, x) vrne True, če seznam s vsebuje elemnt x in False, če ga ne. Nekaj podobnega smo že delali na vajah, samo da bo zdaj, s funkcijami, lažje.

Funkcijo smo pisali le zato, ker na predavanjih pred to domačo nalogo še nismo spoznali operatorja in. Ker bi nam prišel prav pri naslednji funkciji, smo si ga tule sami sprogramirali.

Nalogo lahko rešimo tako, kot smo reševali prve naloge v zvezi s seznami.

def vsebuje(s, x):
    for e in s:
        if e == x:
            return True
    return False

Če je kdo namesto tega napisal

def vsebuje(s, x):
    return x in s

se ne bomo pritoževali. Tisti, ki so oddali "tutorjevo" rešitev

def vsebuje(s, x):
    if x in s:
        return True
    else:
        return False

pa onesrečili profesorja - tudi zato, ker ima izraz x in s že vrednost True ali False, kar je natančno tisto, kar želimo vrniti.

• razlika(s, t) prejme dva seznama in vrne nov seznam, ki vsebuje elemente, ki se pojavijo v enem od podanih seznamov, ne pa v obeh. Klic razlika([16, 4, 2], [4, 1]) vrne [16, 2, 1] (v tem ali poljubnem drugem vrstnem redu), saj so to števila, ki se pojavijo le v prvem ali v drugem seznamu. Vsak element seznama s (ali t) se v tem seznamu pojavi le enkrat. Pri reševanju se ti morda (a ne nujno) splača uporabiti funkcijo, ki si jo sprogramiral prejle.

Ne bomo je uporabili. Raje bomo uporabili kar in, ki dela isto in je jedrnatejši. "Tutor" se je odločil nalogo rešiti tako:

def razlika(s,t):
    r = []
    for e in s:
        if not e in t:
            r.append(e)
    for f in t:
        if not f in s:
            r.append(f)
    return r

S to rešitvijo ni nič narobe, pripomnil bi le, da ni potrebe, da v zankah uporabljamo različni spremenljivki - v gornjem primeru e in f. Obe bi lahko bili e. Vsi, ki jim je pomagal anonimni dobrohotnež, so to funkcijo napisali z dvema spremenljivkama, le da so ju preimenovali v x in y ali m in n ali kaj podobnega.

Seveda pa gre krajše. Če dvakrat ponovimo isto, lahko to spravimo v zanko. Imeli bomo še dva seznama, recimo jima m in n. Najprej bo m isto kot s in n isto kot t, nato pa obratno. Ostanek je enak kot prej.

def razlika(s, t):
    r = []
    for m, n in ((s, t), (t, s)):
        for e in m:
            if e not in n:
                r.append(e)
    return r

Če se komu zdi škoda kopirati sezname zgolj zato, da bi bil program malenkost krajši: v resnici se ne kopirajo. Kaj se v resnici dogaja, bomo izvedeli na enem od prihodnjih predavanjih.

Ponavljanju se še lepše izognemo, če gremo prek obeh seznamov kar z isto zanko, potem pa preverimo, ali je element v enem seznamu in ne v drugem ali pa obratno.

def razlika(s, t):
    u = []
    for e in s + t:
        if (e in s and e not in t) or (e in t and e not in s):
            u.append(e)
    return u

Oklepaji tule niso potrebni, dodali smo jih le zaradi preglednosti.

Pogoj lahko napišemo tudi precej lepše: e mora biti v enem in ne v drugem ali obratno. Se pravi, to, ali je e v s mora biti različno od tega, ali je v e v t.

def razlika(s, t):
    u = []
    for e in s + t:
        if (e in s) != (e in t):
            u.append(e)
    return u

Tu pride prav, če vemo, da je e in s enak True ali False in da lahko tudi te True-je in False primerjamo med sabo.

Potem se spomnimo, da pravzaprav kompliciramo: če e ni v enem, je gotovo v drugem, saj sicer ne bi naleteli nanj. Pogoj bi lahko bil tudi e not in s or e not in t ali (po de Morganu) not (e in s and e in t). V obeh ne sme biti, pa je.

Čisto simpatična rešitev je tudi

def razlika(s, t):
    r = s[:]
    for e in t:
        if e in r:
            r.remove(e)
        else:
            r.append(e)
    return r

V r pripravimo kopijo enega od seznamov. To je pomembno: če bi napisali le r = s, bi bila r in s en in isti seznam in ko bi spreminjali r, bi se spremenil tudi s. Seznama s pa funkcija ne sme spreminjati, saj je ni nihče pooblastil za to.

Nato gremo prek drugega seznama. Če v njem vidimo kaj, kar je bilo že v prvem, to pobrišemo, če vidimo kaj, česar še ni, pa dodamo. Tole deluje le ob predpostavki, da se lahko vsak element pojavi le enkrat. Če bi se lahko večkrat, pa naloga tako ali tako ne bi bila jasno določena. Zato si tu torej privoščimo uporabiti remove, pred katerim vas sicer redno svarim.

Ker bomo vsak čas spoznali izpeljane sezname, povejmo še, kako bi nalogo rešili z njimi:

def razlika(s, t):
    return [e for e in s + t if (e in s) != (e in t)]

Nobena od teh rešitev ni posebej učinkovita: če bi bili seznami dolgi, bi bile te funkcije počasne. Takšnih stvari zato navadno ne počnemo s seznami temveč z množicami, ki pa jih še na poznamo.

• razbij_seznam(s) prejme seznam števil in vrne seznam seznamov njihovih razbitij. Klic razbij([22, 5, 13]) vrne [[16, 4, 2], [4, 1], [8, 4, 1]]. To ne bi smelo biti težko: pripravimo nov seznam, nato za vsak element seznama s izračunamo razbitje in ga dodamo v ta, novi seznam, ki ga potem na koncu vrnemo.

Tu ni kaj pametovati: naredimo nov seznam in vanj zlagamo razbita števila.

def razbij_seznam(s):
    razbit = []
    for e in s:
        razbit.append(razbij(e))
    return razbit

Ko bomo spoznali izpeljane sezname, bomo namesto tega napisali kar

def razbij_seznam(s):
    return [razbij(e) for e in s]

Pythonovski staromodneži pa napišejo

def razbij_seznam(s):
    return list(map(razbij, s))

To nima veliko smisla, če bi bili testi (oz. uporaba funkcije) malo drugačna, pa bi nalogo res lahko rešili precej jedrnateje, z

def razbij_seznam(s):
    return map(razbij, s)

• vsota(s) izračuna vsoto števil v podanem seznamu. To seveda že poznamo s predavanj, vendar vseeno sprogramiraj še enkrat. Sam(a). Zato, ker ti bo pomagala razmišljati pri naslednji funkciji, ki bo skoraj enaka funkciji vsota! (Čeprav seveda vemo, kako se to dela, povejmo, ker nam bo pomagalo pri naslednji funkciji. Vzamemo število 0. K 0 prištejemo prvi element; dobimo, seveda, prvi element. Nato k temu prištejemo drugi element. K tej vsoti prištejemo tretjega. K temu prištejemo četrtega...)

To nalogo ste morali rešiti kot ogrevanje za naslednjo. Takšne stvari namreč že dolgo znamo. Tudi brezzvezna navodila na koncu opisa naloge so služila predvsem temu, da bi pri branju naslednje funkcije odkrili, da je to eno in isto.

Rešitev je, seveda

def vsota(s):
    v = 0
    for e in s:
        v += e
    return v

• zdruzi_sezname(s) prejme seznam seznamov (takšen, kot ga vrača funkcija razbij_seznam) in vrne vse elemente, ki se pojavijo lihokrat. To naredi s trikom. Pripravimo prazen seznam. Izračunamo razliko tega seznama in prvega seznama (zato smo si pripravili funkcijo razlika); rezultat bo seveda prvi seznam. Nato izračuna razliko te "razlike" in drugega seznama. Nato razliko tega, kar je pravkar naračunal, in tretjega seznama. Izračuna razliko tega, kar je pravkar naračunal, in četrtega seznama. Izračuna razliko tega, kar je pravkar naračunal, in petega seznama ... in tako naprej, dokler je treba. Še enkrat: ta funkcija bo zelo podobna funkciji vsota, le da tu ne seštevamo.

Naloga je enaka prejšnji, le da ne seštevamo števil temveč sezname. V začetku imamo namesto 0 prazen seznam, []. V zanki panamesto v += e pišemo v = razlika(v, s).

def zdruzi_sezname(ss):
    v = []
    for s in ss:
        v = razlika(v, s)
    return v

Poleg tega napiši funkcijo

• poteza_racunalnik(s), ki prejme seznam, v katerem je zapisano, koliko kovancev je v posamezni vrstici. Funkcija vrne naključno (a legalno!) potezo, ki jo bo naredil računalnik. Naključna pomeni naključna, ne vedno ista. Potezo vrne v obliki dveh števil; prva je številka vrstice (pri tem ima prva vrstica številko 0, ne 1!), druga pa število kovancev, ki jih želi odstraniti iz te vrstice. Pri tem si lahko pomagaš s funkcijo randint(a, b), ki vrne naključno število med a in vključno b; da jo lahko uporabiš, moraš na začetku programa napisati from random import *. Spomni se tudi, da dolžino seznama s dobiš z len(s).

Izberemo vrstico in če ni prazna, vrnemo številko te vrstice in naključno število kovancev v njej. Če je pa ... ponavljamo, dokler ne naletimo na takšno, ki ni prazna.

def poteza_racunalnik(s):
    while True:
        vrstica = randint(0, len(s) - 1)
        if s[vrstica]:
            return vrstica, randint(1, s[vrstica])

Na dnu naloge je program, ki ga lahko dodaš na konec svojega programa, pa boš lahko igral to igro proti računalniku.

Zadnja funkcija očitno nima nobene zveze z onimi prej. To je zato, ker račualnik igra neumno. Funkcije od prej ti pridejo prav, če hočeš narediti program, ki bo (skoraj) vedno premagal človeka. To pa je dodatna naloga.

Dodatna naloga

Dopolni funkcijo poteza_racunalnik(s), tako da vrne optimalno potezo, kadar le-ta obstaja. Kadar ne, vrne poljubno možno potezo, tako kot prej.

Kakšna je optimalna poteza? Takšna, po kateri je njegov nasprotnik v izgubljeni poziciji. Izgubljena pozicija je pozicija, za katero velja naslednje: če razbijemo vsa števila v sezname (kot to dela funkcijo razbij_seznam) in potem združimo te sezname (zdruzi_seznam) dobimo prazen seznam.

Nasvet za pisanje funkcije (namerno ne povsem jasen - kar potrudi se!). Najprej moraš ugotoviti trenutno pozicijo: razbij vse v sezname in jih združi. Če dobiš prazen seznam, je računalnik v izguljeni poziciji (če nasprotnik ne bo naredil kakšne napake). Sicer pa je potrebno odstraniti to, kar je v združenem seznamu. Zdaj pojdi čez vse vrstice. Za vsako izračunaš razlika med to vrstico in tem, kar bi bilo potrebno odstraniti. razlika ti pove, koliko kovancev bi moralo ostati v tej vrstici. Če ta vrstica dejansko vsebuje vsaj toliko kovancev, je to optimalna poteza.

Gornjega odstavka morda ne razumeš, ker ni napisan dovolj jasno. Tudi prav. Pogooglaj in odkrij, kakšna je zmagovalna strategija za Nim. Vendar ne oddajaj programov, ki jih najdeš na spletu, temveč funkcijo, ki uporablja, kar si sprogramiral prej.

def poteza_racunalnik(s):
    vsote = razbij_seznam(s)
    odstraniti = zdruzi_sezname(vsote)

    if not odstraniti:  # Računalnik je izgubljen -> naključna poteza
        while True:
            vrstica = randint(0, len(s) - 1)
            if s[vrstica]:
                return vrstica, randint(1, s[vrstica])

    for vrstica, (kovancev, cleni) in enumerate(zip(s, vsote)):
        ostane = vsota(razlika(cleni, odstraniti))
        if ostane < kovancev:
            return vrstica, kovancev - ostane

V prvih dveh vrsticah ugotovimo, koliko kovancev (točneje, katere potence 2) je potrebno odstraniti, da bo računalnik v zmagovalni poziciji. Če je seznam prazen, je v zmagovalni poziciji nasprotnik in računalnik bo naredil naključno potezo; kako to stori, smo videli v rešitvi zadnje funkcije iz obveznega dela.

Sicer pa gremo prek vseh vrstic. Potrebovali bomo številko vrstice ,število kovancev v njej in "razbito" število kovancev. Slednja dva dobimo z zip(s, vsote), številko vrstice pa pripnemo zraven z enumerate. Tako dobimo čudni for. Preverimo, koliko kovancev bo ostalo v vrstici po tem, ko jih odvzamemo toliko, kolikor naj bi jih odvzeli. Če vrstica vsebuje toliko kovancev, jih bomo odstranili - vrnemo torej številko te vrstice in število kovancev. Sicer pa iščemo naprej.

Igra

Ko si napisal funkcijo poteza_racunalnik, dodaj na konec svojega program še tole, pa boš lahko igral proti računalniku. (Tole bi znal napisati tudi sam, razen izpisa, ki je malo stlačen. Vendar to ni del naloge, ker bi bilo tole malo težje avtomatsko testirati.)

def izpis(s):
    print("".join(f"{i + 1} ({e}) {' *' * e}\n" for i, e in enumerate(s)))

def poteza_clovek(s):
    while True:
        vrstica = int(input("Vrstica: ")) - 1
        kovancev = int(input("Kovancev: "))
        if vrstica < len(s) and 0 < kovancev <= s[vrstica]:
            return vrstica, kovancev
        print("Ne moreš.")

def igra(s):
    izpis(s)
    while True:
        for kdo, vprasaj in (("Računalnik", poteza_racunalnik), ("Človek", poteza_clovek)):
            vrstica, kovancev = vprasaj(s)
            s[vrstica] -= kovancev
            print(kdo, "vzame", kovancev, "iz", vrstica + 1)
            print()
            izpis(s)
            if vsota(s) == 0:
                print(kdo, "je zmagal")
                return

# Če nočeš igrati, temveč poganjati teste,
# postavi znak na začetek spodnjih dveh vrstic
from random import randint
igra([randint(3, 10) for _ in range(4)])