18. Polymorfizmus, typ množina


Ešte raz zopakujme, aké sú najdôležitejšie vlastnosti objektového programovania:

  • zapuzdrenie (encapsulation)

  • dedičnosť (inheritance)

  • polymorfizmus (polymorphism)

V dnešnej prednáške sa sústredíme na poslednú vlastnosť polymorfizmus.

Vráťme sa k príkladu zo 16. prednášky, v ktorom korytnačka kreslila domček:

import turtle

class MojaTurtle(turtle.Turtle):
    def domcek(self, dlzka):
        for uhol in 90, 90, 90, 30, 120, -60:
            self.fd(dlzka)       # fd z triedy Turtle
            self.rt(uhol)        # rt z triedy Turtle

t = MojaTurtle()
t.domcek(100)
_images/18_1.png

V metóde domcek() sme predpokladali, že pri kreslení domčeka inštancia t triedy MojaTurtle použije zdedenú metódu fd() (z triedy Turtle) a tiež zdedenú metódu rt() z triedy Turtle.

Do triedy MojaTurtle sme ešte pridali vlastnú verziu metódy fd(), ktorá prekryla (override) kreslenie obyčajných čiar na kreslenie cikcakových čiar:

import turtle

class MojaTurtle(turtle.Turtle):
    def domcek(self, dlzka):
        for uhol in 90, 90, 90, 30, 120, -60:
            self.fd(dlzka)       # fd z triedy MojaTurtle
            self.rt(uhol)        # rt z triedy Turtle

    def fd(self, dlzka):
        while dlzka >= 5:
            self.lt(60)
            super().fd(5)        # fd z triedy Turtle
            self.rt(120)
            super().fd(5)        # fd z triedy Turtle
            self.lt(60)
            dlzka -= 5
        super().fd(dlzka)        # fd z triedy Turtle

t = MojaTurtle()
t.domcek(100)

Vidíme, že kreslenie domčeka teraz už nepoužíva obyčajné fd() z triedy Turtle, ale využíva našu zmenenú metódu fd() a kreslí cikcakové čiary:

_images/18_2.png

Lenže kreslenie cikcakového domčeka môžeme prepísať do takýchto dvoch definícií tried:

import turtle

class MojaTurtle(turtle.Turtle):
    def domcek(self, dlzka):
        for uhol in 90, 90, 90, 30, 120, -60:
            self.fd(dlzka)       # fd z triedy ??? Turtle
            self.rt(uhol)        # rt z triedy Turtle

class MojaTurtle1(MojaTurtle):
    def fd(self, dlzka):
        while dlzka >= 5:
            self.lt(60)
            super().fd(5)        # fd z triedy Turtle
            self.rt(120)
            super().fd(5)        # fd z triedy Turtle
            self.lt(60)
            dlzka -= 5
        super().fd(dlzka)        # fd z triedy Turtle

t = MojaTurtle1()
t.domcek(100)

Z triedy MojaTurtle sme odvodili novú triedu MojaTurtle1. Táto nová trieda teda zdedila od svojej základnej triedy MojaTurtle všetko (aj domcek()) okrem metódy fd(), ktorú prekryla (override) svojou vlastnou verziou tejto metódy.

Takže teraz:

  • inštancia triedy MojaTurtle pomocou metódy domcek() nakreslí domček zo 6 obyčajných úsečiek

  • inštancia triedy MojaTurtle1 pomocou metódy fd() kreslí cikcakové čiary

  • táto inštancia triedy MojaTurtle1 bude takýmito cikcakovými čiarami kresliť aj domček (volaním metódy domcek())

Ako je to možné? Veď predsa v metóde domcek(), keď sme ju definovali, sme jasne zapísali, že kreslenie čiar fd() sa bude robiť tak, ako bolo definované v základnej triede Turtle. Nikde sme tu nijako nezaznačovali (ani nás to vtedy nenapadlo), že tento fd() niekto v budúcnosti možno nahradí svojou vlastnou verziou metódy (napríklad cikcak). Tak práve tomuto mechanizmu sa hovorí polymorfizmus a označuje:

  • keď Python vykonáva nejakú metódu (napríklad domcek()), tak sa toto vykonávanie prispôsobí (adaptuje) tej inštancii, ktorá túto metódu zavolala

  • vždy sa použijú aktuálne verzie metód objektu, pre ktorý sa niečo vykonáva

  • funguje to aj spätne, teda vo všetkých zdedených metódach: ak sa v nich nachádza volanie niečoho, čo sme práve prekryli svojou novou verziou, tak sa to naozaj uplatní

Uvedomte si, čo by sa stalo, keby tu nefungoval polymorfizmus:

  • metóda domcek() by vždy kreslila úplne rovnaký domček z rovných čiar bez ohľadu na to, kto túto metódu zavolal (kto bol self)

  • keby sme potrebovali domček z cikcakových čiar aj pre objekt typu MojaTurtle1, museli by sme túto metódu skopírovať aj do tejto triedy, hoci dedičnosť nám hovorí, že by sme to nemali robiť

Pridajme k týmto dvom triedam aj MojaTurtle2, pomocou ktorej korytnačka po každej kreslenej čiare prešla trikrát:

import turtle
import random

class MojaTurtle(turtle.Turtle):
    def domcek(self, dlzka):
        for uhol in 90, 90, 90, 30, 120, -60:
            self.fd(dlzka)       # fd z triedy ???Turtle
            self.rt(uhol)        # rt z triedy Turtle

class MojaTurtle1(MojaTurtle):
    def fd(self, dlzka):
        while dlzka >= 5:
            self.lt(60)
            super().fd(5)        # fd z triedy Turtle
            self.rt(120)
            super().fd(5)        # fd z triedy Turtle
            self.lt(60)
            dlzka -= 5
        super().fd(dlzka)        # fd z triedy Turtle

class MojaTurtle2(MojaTurtle):
    def fd(self, dlzka):
        super().fd(dlzka)        # fd z triedy Turtle
        self.rt(180 - random.randint(-3, 3))
        super().fd(dlzka)        # fd z triedy Turtle
        self.rt(180 - random.randint(-3, 3))
        super().fd(dlzka)        # fd z triedy Turtle

Ďalej vytvoríme 100-prvkový zoznam korytnačiek, pričom pre každú z nich sa náhodne rozhodneme, aký typ vyberieme:

turtle.delay(0)
zoz = []
moja = (MojaTurtle, MojaTurtle1, MojaTurtle2)
for i in range(100):
    t = random.choice(moja)()   # všimnite si zátvorky na konci
    t.ht()
    t.speed(0)
    t.pu()
    t.setpos(random.randint(-300, 250), random.randint(-250, 250))
    t.pd()
    zoz.append(t)

for t in zoz:
    t.domcek(50)

Vytvorili sme tu zoznam korytnačiek troch rôznych typov. Každá z korytnačiek dokáže nakresliť domcek() ale každá to robí po svojom. Keďže tento zoznam obsahuje inštancie rôznych typov, niekedy hovoríme, že je to tzv. polymorfný zoznam (prípadne polymorfné pole).

V Pythone ale nie je problém so zoznamami, resp. poľami, ktorých prvky sú rôznych typov. Toto ale nie je bežné v iných programovacích jazykoch (Pascal, C++, …), kde väčšinou určujeme nejaký jeden konkrétny typ ako typ všetkých prvkov poľa (napríklad pole celých čísel, pole reťazcov, …). Aj v týchto jazykoch sa dá vytvárať polymorfné pole, ale už to nebude také jednoduché ako v Pythone.

Toto ale nie sú jediné významy polymorfizmu - tento pojem sa objavuje na mnohých miestach aj v situáciách, s ktorými sme sa zoznámili dávnejšie a už sme sa zmierili s takýmto správaním Pythonu. Pripomeňme si triedu Cas z 15. prednášky:

class Cas:

    def __init__(self, hodiny=0, minuty=0, sekundy=0):
        self.sek = abs(3600*hodiny + 60*minuty + sekundy)

    def __str__(self):
        return f'{self.sek // 3600}:{self.sek // 60 % 60:02}:{self.sek % 60:02}'

    def sucet(self, iny):
        return Cas(sekundy=self.sek + iny.sek)

    def rozdiel(self, iny):
        return Cas(sekundy=self.sek - iny.sek)

    def vacsi(self, iny):
        return self.sek > iny.sek

    def rovny(self, iny):
        return self.sek == iny.sek

Tu vidíme použitie aj magickej metódy __str__():

>>> c1 = Cas(10, 22, 30)
>>> c1.__str__()
'10:22:30'
>>> c2 = Cas(4, 55, 18)
>>> str(c2)
'4:55:18'
>>> print('sucet =', c1.sucet(c2))
sucet = 15:17:48

Už vieme, že c1.__str__() priamo zavolá metódu __str__(), teda vráti reťazcovú reprezentáciu hodnoty čas. Volanie str(c2) tiež zavolá __str__(), ale neurobí sa to priamo, ale cez nejaký „magický“ mechanizmus:

  • štandardná funkcia str() má za úlohu ľubovoľnú Pythonovskú hodnotu (napríklad číslo, zoznam, n-ticu, …) vyjadriť ako znakový reťazec

  • keďže túto štandardnú funkciu naprogramovali vo firme „Python“ pred veľa rokmi, nemohli vtedy myslieť aj na to, že v roku 2019 niekto zadefinuje vlastný typ Cas a bude ho potrebovať pomocou str(c2) previesť na znakový reťazec

  • preto má táto štandardná funkcia v sebe skrytý mechanizmus, pomocou ktorého veľmi jednoducho zistí reťazcovú reprezentáciu ľubovoľného typu: namiesto toho aby sama vyrábala znakový reťazec, zavolá metódu __str__() danej hodnoty; pritom každá trieda má vždy zadefinovanú náhradnú verziu tejto metódy, ktorá (keď ju neprekryjeme vlastnou metódou) vypisuje známe '<__main__.Cas object at 0x035B92D0>'

Štandardná funkcia print(), ktorá má za úlohu vypísať všetky svoje parametre, najprv všetky neznakové parametre prevedie na znakové reťazce: pomocou štandardnej funkcie str() z nich vyrobí reťazce a tieto vypíše.

Takže aj prevod hodnoty typu Cas na znakový reťazec pomocou štandardnej funkcie str() funguje vďaka polymorfizmu: aj táto funkcia sa prispôsobí (adaptuje) k zadanému typu a snaží sa z neho získať reťazec volaním jeho metódy __str__().


Operátorový polymorfizmus

Už máme skúsenosti s tým, že napríklad operácia + funguje nielen s číslami ale aj s reťazcami a zoznamami:

>>> 12 + 34
46
>>> 'Pyt' + 'hon'
Python
>>> [1, 2] + [3, 4, 5]
[1, 2, 3, 4, 5]
>>> 12 + '34'
...
TypeError: unsupported operand type(s) for +: 'int' and 'str'

Hovoríme tomu operátorový polymorfizmus, lebo táto operácia funguje rôzne pre rôzne typy. Python sa v tomto prípade nemusí pre každú dvojicu typov rozhodovať, či ich súčet je realizovateľný alebo je to chyba TypeError. Jednoducho prvému operandu oznámi, aby pripočítal druhý operand, t.j. zavolá nejakú jeho metódu a pošle mu druhý operand. Tou metódou je samozrejme magická metóda __add__() a preto pri vyhodnocovaní súčtu Python vlastne volá magickú metódu:

>>> 12 + 34
46
>>> (12).__add__(34)   # 12 tu musí byť v zátvorkách
46
>>> 'Pyt' + 'hon'
Python
>>> 'Pyt'.__add__('hon')
Python
>>> (12).__add__('34')
NotImplemented

Tiež si uvedomte, že a.__add__(b) pre a napríklad celé číslo je to isté ako int.__add__(a, b). Práve táto metóda je zodpovedná za to, či a ako sa dá k celému číslu pripočítať hodnota nejakého iného typu.

Teraz už vieme, že keď v Pythone zapíšeme a + b, v skutočnosti sa volá metóda a.__add__(b) a preto aj pre našu triedu Cas stačí dodefinovať túto metódu, teda vlastne stačí len premenovať sucet() na __add__(). Vyskúšajme:

class Cas:

    ...

    def __add__(self, iny):
        return Cas(sekundy=self.sek+iny.sek)

    ...

c1 = Cas(10, 22, 30)
c2 = Cas(4, 55, 18)
print('sucet =', c1 + c2)

a vidíme, že to naozaj funguje. Zrejme na rovnakom princípe fungujú nielen všetky aritmetické operácie ale aj relačné operátory:

aritmetické operácie

metóda

operácia

x.__add__(y)

x + y

x.__sub__(y)

x - y

x.__mul__(y)

x * y

x.__truediv__(y)

x / y

x.__floordiv__(y)

x // y

x.__mod__(y)

x % y

x.__pow__(y)

x ** y

x.__neg__()

- x

Tomuto sa hovorí preťažovenie operátorov (operator overloading): existujúca operácia dostáva pre našu triedu nový význam, t.j. prekryli sme štandardné správanie Pythonu, keď niektoré operácie pre neznáme operandy hlásia chybu. Stretnete sa s tým aj v iných programovacích jazykoch.

relačné operácie

metóda

relácia

x.__eq__(y)

x == y

x.__ne__(y)

x != y

x.__lt__(y)

x < y

x.__le__(y)

x <= y

x.__gt__(y)

x > y

x.__ge__(y)

x >= y

Teraz môžeme vylepšiť kompletnú triedu Cas:

class Cas:

    def __init__(self, hodiny=0, minuty=0, sekundy=0):
        self.sek = abs(3600*hodiny + 60*minuty + sekundy)

    def __str__(self):
        return f'{self.sek // 3600}:{self.sek // 60 % 60:02}:{self.sek % 60:02}'

    def __add__(self, iny):
        return Cas(sekundy=self.sek+iny.sek)

    def __sub__(self, iny):
        return Cas(sekundy=self.sek-iny.sek)

    def __gt__(self, iny):
        return self.sek > iny.sek

    def __eq__(self, iny):
        return self.sek == iny.sek

Vďaka tomuto môžeme časy nielen sčitovať ale aj odčitovať a porovnávať relačnými operátormi.

Pozrime si ešte takúto funkciu:

def sucet(a, b):
   return a + b

Zrejme táto funkcia bude dávať správne výsledky pre rôzne typy parametrov, môžeme im hovoriť polymorfné parametre a niekedy sa stretnete aj s pojmom parametrický polymorfizmus.

Trieda Zlomok

Na 14. cvičeniach ste riešili aj úlohu, v ktorej ste definovali triedu Zlomok aj s metódami str() a float(). My toto riešenie trochu vylepšíme:

class Zlomok:
    def __init__(self, citatel=0, menovatel=1):
        self.cit = citatel
        self.men = menovatel

    def __str__(self):
        return f'{self.cit}/{self.men}'

    def __int__(self):
        return self.cit // self.men

    def __float__(self):
        return self.cit / self.men

a jednoduchý test:

>>> z1 = Zlomok(3, 8)
>>> z2 = Zlomok(2, 4)
>>> print('desatinne cislo z', z1, 'je', float(z1))
desatinne cislo z 3/8 je 0.375
>>> print('cela cast', z2, 'je', int(z2))
cela cast 2/4 je 0

Magické metódy __int__() a __float__() slúžia na to, aby sme objekt typu Zlomok mohli poslať do konvertovacích funkcií int() a float().

Tento dátový typ by mohol byť naozaj užitočný, keby obsahoval aj nejaké operácie. S týmto už máme nejaké skúsenosti z definovania triedy Cas. Tiež by bolo veľmi vhodné, keby sa v tejto triede zlomok automaticky upravil na základný tvar. Túto úpravu budeme robiť v inicializácii __init__(): z matematiky na základnej škole vieme, že na to potrebujeme zistiť najväčší spoločný deliteľ. Použijeme známy Euklidov algoritmus:

def nsd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

Ak budeme túto funkciu potrebovať len v metóde __init__(), nemusíme ju definovať ako globálnu funkciu, ale ju prenesieme do tela inicializačnej funkcie, čím z nej urobíme lokálnu funkciu (vidí ju len samotná metóda __init__()). Všimnite si, že sme sem doplnili niekoľko zatiaľ neznámych magických metód:

class Zlomok:

    def __init__(self, citatel=0, menovatel=1):

        def nsd(a, b):
            while b != 0:
                a, b = b, a % b
            return a

        if menovatel == 0:
            menovatel = 1
        delitel = nsd(citatel, menovatel)
        self.cit = citatel // delitel
        self.men = menovatel // delitel

    def __str__(self):
        return f'{self.cit}/{self.men}'

    __repr__ = __str__

    def __add__(self, iny):
        if isinstance(iny, int):
            c, m = iny, 1
        else:
            c, m = iny.cit, iny.men
        return Zlomok(self.cit*m + self.men*c, self.men*m)

    __radd__ = __add__

    def __sub__(self, iny):
        if isinstance(iny, int):
            c, m = iny, 1
        else:
            c, m = iny.cit, iny.men
        return Zlomok(self.cit*m - self.men*c, self.men*m)

    def __rsub__(self, iny):
        if isinstance(iny, int):
            c, m = iny, 1
        else:
            c, m = iny.cit, iny.men
        return Zlomok(self.men*c - self.cit*m, self.men*m)

    def __mul__(self, iny):
        if isinstance(iny, int):
            c, m = iny, 1
        else:
            c, m = iny.cit, iny.men
        return Zlomok(self.cit * c, self.men*m)

    __rmul__ = __mul__

    def __abs__(self):
        return Zlomok(abs(self.cit), self.men)

    def __int__(self):
        return self.cit // self.men

    def __float__(self):
        return self.cit / self.men

    def __lt__(self, iny):
        return self.cit*iny.men < self.men*iny.cit

    def __eq__(self, iny):
        return self.men==iny.men and self.cit==iny.cit

Niekoľko noviniek v tomto kóde:

  • atribút __repr__ je tu definovaný pomocou priradenia __repr__ = __str__ a znamená:

    • aj __repr__ bude metódou triedy Zlomok a týmto sme ju definovali ako identickú k __str__ (triedny atribút __repr__ obsahuje rovnakú referenciu ako __str__, teda obsahuje rovnakú definíciu metódy)

    • magická metóda __repr__ špecifikuje, čo sa bude vypisovať, ak inštanciu zadáme priamo v shelli alebo sa objaví pri vypisovaní prvkov zoznamu, napríklad:

      >>> z = Zlomok(1, 3)
      >>> z
      1/3
      >>> zoznam = [Zlomok(1, 5), Zlomok(2, 5), Zlomok(3, 5), Zlomok(4, 5)]
      >>> zoznam
      [1/5, 2/5, 3/5, 4/5]
      
  • magická metóda __radd__ (jej definícia je identická s __add__) je potrebná v situáciách, keď chceme sčitovať celé číslo so zlomkom:

    • samotná __add__ zvláda sčítať len zlomok s číslom (súčet Zlomok(1, 3) + 1 označuje volanie Zlomok(1, 3).__add__(1))

    • sčitovanie čísla so zlomkom 1 + Zlomok(1, 3) označuje (1).__add__(Zlomok(1, 3)), čo by znamenalo, že metóda __add__ triedy int by mala vedieť sčitovať aj zlomky (je nemožné predefinovať štandardnú metódu int.__add__() aby fungovala s nejakým divným typom)

    • preto pri sčitovaní 1 + Zlomok(1, 3), keď Python zistí, že nefunguje (1).__add__(Zlomok(1, 3)), vyskúša vymeniť operandy operácie a namiesto __add__() zavolať __radd__()

  • podobne je definovaná aj metóda __rmul__, pričom odčitovanie __rsub__ nemôže byť identická funkcia s metódou __sub__, preto je zadefinovaná zvlášť

  • pridali sme magickú metódu __abs__(), vďaka ktorej bude fungovať aj štandardná funkcia abs(zlomok)

Uvedomte si, že všetky nami definované metódy triedy Zlomok (okrem __init__()) sú pravé funkcie a preto aj náš nový typ Zlomok môžeme považovať za nemeniteľný (immutable).

Vďaka relačným operátorom __lt__() a __eq__() a schopnosti sčitovať zlomky s číslami bude fungovať aj takáto ukážka:

>>> zoznam = []
>>> for m in range(2, 8):
        for c in range(1, m):
            zoznam.append(Zlomok(c, m))

>>> zoznam
[1/2, 1/3, 2/3, 1/4, 1/2, 3/4, 1/5, 2/5, 3/5, 4/5, 1/6, 1/3,
 1/2, 2/3, 5/6, 1/7, 2/7, 3/7, 4/7, 5/7, 6/7]
>>> min(zoznam)
1/7
>>> max(zoznam)
6/7
>>> sum(zoznam)
21/2
>>> sorted(zoznam)
[1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 1/3, 2/5, 3/7, 1/2, 1/2, 1/2,
 4/7, 3/5, 2/3, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7]

Typ množina

Na 14. cvičeniach (10. úloha) ste riešili aj príklad s triedou Zoznam, pomocou ktorej sa uchovávali nejaké texty v zozname. Tu je možné riešenie:

class Zoznam:
    def __init__(self):
        self.zoznam = []

    def __str__(self):
        p = []
        for prvok in self.zoznam:
            p.append(str(prvok))
        return ', '.join(p)

    def pridaj(self, prvok):
        if prvok not in self.zoznam:
            self.zoznam.append(prvok)

    def vyhod(self, prvok):
        if prvok in self.zoznam:
            self.zoznam.remove(prvok)

    def je_v_zozname(self, prvok):
        return prvok in self.zoznam

    def pocet(self):
        return len(self.zoznam)

Jednoduchý test:

z = Zoznam()
z.pridaj('behat')
z.pridaj('upratat')
z.pridaj('ucit sa')
if z.je_v_zozname('behat'):
    print('musis behat')
else:
    print('nebehaj')
z.pridaj('upratat')
print('zoznam =', z)
z.vyhod('spievat')
print('pocet prvkov v zozname =', z.pocet())
musis behat
zoznam = behat, upratat, ucit sa
pocet prvkov v zozname = 3

V Pythone je zaužívané použiť operáciu in vtedy, keď potrebujeme zistiť, či sa v nejakej postupnosti hodnôt nachádza nejaká konkrétna hodnota, napríklad:

>>> 3 in [1, 2, 3, 4, 5]
True
>>> 'x' in 'Python'
False

Zrejme by bolo prirodzené, keby sme aj našu metódu je_v_zozname() vedeli prerobiť na pythonovský štýl (pythonic). Aj na toto existuje magická metóda __contains__() a predchádzajúce dva príklady sú vlastne krajšími zápismi (tzv. syntactic sugar) pre:

>>> [1, 2, 3, 4, 5].__contains__(3)
True
>>> 'Python'.__contains__('x')
False

Podobne aj štandardná funkcia len(), ktorá vie zistiť počet prvkov zoznamu alebo dĺžku reťazca (počet znakov v reťazci), využíva polymorfizmus, teda v skutočnosti, aby zistila počet prvkov nejakej štruktúry, sa jej na to opýta pomocou magickej metódy __len__(). Preto nasledovné trojice príkazov robia to isté:

>>> len([1, 2, 3, 4, 5])
5
>>> [1, 2, 3, 4, 5].__len__()
5
>>> list.__len__([1, 2, 3, 4, 5])
5

>>> len('Python')
6
>>> 'Python'.__len__()
6
>>> str.__len__('Python')
6

Upravme aj našu triedu Zoznam, pričom premenujeme aj metódy pridaj() a vyhod() na anglické ekvivalenty:

class Zoznam:
    def __init__(self):
        self.zoznam = []

    def __str__(self):
        p = []
        for prvok in self.zoznam:
            p.append(str(prvok))
        return ', '.join(p)

    def __contains__(self, prvok):
        return prvok in self.zoznam

    def __len__(self):
        return len(self.zoznam)

    def add(self, prvok):
        if prvok not in self.zoznam:
            self.zoznam.append(prvok)

    def discard(self, prvok):
        if prvok in self.zoznam:
            self.zoznam.remove(prvok)

Otestujeme rovnako ako predtým:

z = Zoznam()
z.add('behat')
z.add('upratat')
z.add('ucit sa')
if 'behat' in z:
    print('musis behat')
else:
    print('nebehaj')
z.add('upratat')
print('zoznam =', z)
z.discard('spievat')
print('pocet prvkov v zozname =', len(z))
musis behat
zoznam = behat, upratat, ucit sa
pocet prvkov v zozname = 3

Uvedomte si, že do takéhoto zoznamu nemusíme vkladať len znakové reťazce, ale rovnako by fungoval aj pre ľubovoľné iné typy hodnôt. Tento typ je vlastne jednoduchá realizácia matematickej množiny hodnôt: každý prvok sa tu môže nachádzať maximálne raz.


Štandardný typ množina - set

Python má medzi štandardnými typmi aj typ množina, ktorý má v Pythone meno set. Podobne ako aj iné typy str, list a tuple aj tento množinový typ je postupnosťou hodnôt, ktorú môžeme prechádzať for-cyklom alebo ju poslať ako parameter pri konštruovaní iného typu. Napríklad:

>>> mnozina = {'behat', 'ucit sa', 'upratat'}
>>> mnozina
{'upratat', 'behat', 'ucit sa'}
>>> zoznam = list(mnozina)
>>> zoznam
['upratat', 'behat', 'ucit sa']
>>> ntica = tuple(mnozina)
>>> ntica
('upratat', 'behat', 'ucit sa')
>>> for prvok in mnozina:
        print(prvok, end=', ')

'upratat', 'behat', 'ucit sa',

Podobne ako vieme skonštruovať zoznam pomocou generátora postupnosti range(), vieme to urobiť aj s množinami:

>>> list(range(7))
[0, 1, 2, 3, 4, 5, 6]
>>> set(range(7))
{0, 1, 2, 3, 4, 5, 6}

alebo vytvorenie zoznamu a množiny zo znakového reťazca:

>>> list('mama ma emu')
['m', 'a', 'm', 'a', ' ', 'm', 'a', ' ', 'e', 'm', 'u']
>>> set('mama ma emu')
{' ', 'm', 'u', 'a', 'e'}

Štandardný Pythonovský typ set má kompletnú sadu množinových operácií a veľa užitočných metód. Pre prvky množiny ale platí, že to nemôžu byť ľubovoľné hodnoty, ale musia to byť nemenné typy (immutable), napríklad čísla, reťazce, n-tice.

Predchádzajúci príklad, v ktorom sme definovali triedu Zoznam vieme prepísať l s použitím pythonovských množín, napríklad takto:

z = set()                  # prázdna pythonovská množina
z.add('behat')
z.add('upratat')
z.add('ucit sa')
if 'behat' in z:
    print('musis behat')
else:
    print('nebehaj')
z.add('upratat')
print('zoznam =', z)
z.discard('spievat')
print('pocet prvkov v zozname =', len(z))
musis behat
zoznam = {behat, upratat, ucit sa}
pocet prvkov v zozname = 3

Operácie a metódy s množinami

Štandardný typ množina (set) je meniteľný (mutable) a z toho vyplývajú všetky dôsledky podobne ako pre pythonovské zoznamy (list).

V ďalších tabuľkách predpokladáme, že M, M1 a M2 sú nejaké množiny:

množinové operácie

popis

M1 | M2

zjednotenie dvoch množín

M1 & M2

prienik dvoch množín

M1 - M2

rozdiel dvoch množín

M1 ^ M2

vylučovacie zjednotenie dvoch množín

M1 == M2

dve množiny majú rovnaké prvky

M1 is M2

dve množiny sú identické štruktúry v pamäti (je to tá istá hodnota)

M1 < M2

M1 je podmnožinou M2 (funguje aj pre zvyšné relačné operátory)

prvok in M

zistí, či prvok patrí do množiny

prvok not in M

zistí, či prvok nepatrí do množiny

for prvok in M: ...

cyklus, ktorý prechádza cez všetky prvky množiny

štandardné funkcie

popis

len(M)

počet prvkov

min(M)

minimálny prvok (ale všetky prvky sa musia dať navzájom porovnávať)

max(M)

maximálny prvok (ale všetky prvky sa musia dať navzájom porovnávať)

list(M)

vráti neusporiadaný zoznam prvkov z množiny

sorted(M)

vráti usporiadaný zoznam (ale všetky prvky sa musia dať navzájom porovnávať)

niektoré metódy

popis

M.add(prvok)

pridá prvok do množiny (ak už v množine bol, neurobí nič)

M.remove(prvok)

vyhodí daný prvok z množiny (ak neexistuje, vyhlási chybu)

M.discard(prvok)

vyhodí daný prvok z množiny (ak neexistuje, neurobí nič)

M.pop()

vyhodí nejaký neurčený prvok z množiny a vráti jeho hodnotu (ak je množina prázdna, vyhlási chybu)

M.clear()

vyčistí množinu

Všetky tieto metódy sú mutable, teda zmenia obsah premennej a ak je na ňu viac referencií, ovplyvní to všetky.

Metód, ktoré pracujú s množinami, je oveľa viac.

Vytvorenie množiny

niektoré metódy

popis

M = set()

vytvorí prázdnu množinu

M = {hodnota, hodnota, ...}

vytvorí neprázdnu množinu so zadanými prvkami

M = set(zoznam)

so zadaného zoznamu vytvorí množinu

M = set(M1)

vytvorí kópiu množiny M1

Uvedomte si, že niektoré situácie vieme riešiť rôznymi spôsobmi, napríklad

  • pridať prvok do množiny mnoz:

    mnoz.add(prvok)           # mutable
    

    alebo:

    mnoz = mnoz | {prvok}     # immutable
    

    čo je to isté ako:

    mnoz |= {prvok}           # mutable
    
  • vyhodiť jeden prvok z množiny mnoz:

    mnoz.discard(prvok)       # mutable
    

    alebo:

    mnoz = mnoz - {prvok}     # immutable
    

    čo je to isté ako:

    mnoz -= {prvok}           # mutable
    

    ak máme istotu, že prvok je v množine (inak to spadne na chybe):

    mnoz.remove(prvok)        # mutable
    
  • zistí, či je množina mnoz prázdna:

    mnoz == set()
    

    alebo:

    len(mnoz) == 0
    

    alebo veľmi nečitateľne:

    not mnoz
    

Príklady s množinami

Napíšme funkciu, ktorá vráti počet rôznych samohlások v danom slove:

def pocet_samohlasok(slovo):
    return len(set(slovo) & set('aeiouy'))

Bez použitia množiny by sme ju zapísali asi takto:

def pocet_samohlasok(slovo):
    vysl = 0
    for znak in 'aeiouy':
        if znak in slovo:
            vysl += 1
    return vysl

Ďalšia funkcia skonštruuje množinu s takouto vlastnosťou:

  • 1 patrí do množiny

  • ak do množiny patrí nejaké i, tak tam patrí aj 2*i+1 aj 3*i+1

Funkcia vytvorí všetky prvky množiny ktoré nie sú väčšie ako zadané n:

def urob(n):
    m = {1}
    for i in range(n//2):
        if i in m:
            if 2*i + 1 <= n:
                m.add(2*i + 1)
            if 3*i + 1 <= n:
                m.add(3*i + 1)
    return m

Ďalšia funkcia je rekurzívna a zisťuje, či nejaké dané i je prvkom množiny z predchádzajúceho príkladu (bez toho, aby sme museli túto množinu najprv skonštruovať):

def test(i):
    if i == 0:
        return False
    if i == 1:
        return True
    if i%2 == 1 and test(i//2):
        return True
    if i%3 == 1 and test(i//3):
        return True
    return False

To isté sa dá zapísať trochu úspornejšie (a výrazne menej čitateľne):

def test(i):
    if i <= 1:
        return i == 1
    return i%2 == 1 and test(i//2) or i%3 == 1 and test(i//3)

Pomocou funkcie test() vieme zapísať aj funkciu urob():

def urob(n):
    m = set()
    for i in range(n+1):
        if test(i):
            m.add(i)
    return m

Ďalšia funkcia skonštruuje množinu prvočísel pomocou algoritmu Eratostenovo sito:

  • zoberieme zoznam všetkých celých čísel od 2 po nejaké zadané n

  • prvé číslo v zozname 2 je prvočíslo, zo zoznamu odstránime všetky jeho násobky

  • druhé číslo v tomto novom zozname 3 je tiež prvočíslo, zo zoznamu odstránime všetky jeho násobky

  • aj tretie číslo v tomto novom zozname 5 je prvočíslo, zo zoznamu odstránime všetky jeho násobky

  • takto to budeme opakovať, kým neprejdeme celý zoznam čísel

Zapíšme to ako funkciu:

def eratostenovo_sito(n):
    mnozina = set(range(2, n+1))
    for i in range(n):
        if i in mnozina:
            mnozina -= set(range(i+i, n+1, i))
    return mnozina
>>> eratostenovo_sito(100)
{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
 73, 79, 83, 89, 97}

Python nezaručuje, že prvky v množine sú v rastúcej postupnosti. Preto niekedy množinu prevedieme na usporiadaný zoznam, napríklad:

>>> m1 = {1,5,10,30,100,1000}
>>> m2 = {2,6,11,31,101,1001}
>>> m1 | m2
{1, 2, 100, 5, 101, 6, 1000, 1001, 10, 11, 30, 31}
>>> sorted(m1 | m2)
[1, 2, 5, 6, 10, 11, 30, 31, 100, 101, 1000, 1001]

Cvičenia

L.I.S.T.


Polymorfné korytnačky

  1. Na prednáške sa definovali tri triedy MojaTurtle, MojaTurtle1, MojaTurtle2, pričom MojaTurtle1 a MojaTurtle2 boli odvodené z MojaTurtle. Pomocou nich sa v ploche vygenerovalo 100 náhodných korytnačiek a tie všetky nakreslili domček. Pozmeň tento program tak, že sa vytvorí iba 10 inštancií týchto tried, všetky budú pravideľne rozostavené na jednej priamke, pričom sa budú pravideľne striedať ich typy: najľavejšia bude MojaTurtle1, vedľa nej MojaTurtle2, ďalšia MojaTurtle, atď. Potom každá z nich nakreslí svoj domček náhodnej veľkosti z intervalu <30, 50>.


  1. Pozmeň definíciu triedy MojaTurtle1 tak, aby namiesto metódy fd prekryla metódu rt: táto metóda bude korytnačku stále otáčať vpravo, ale s náhodnou chybou z intervalu <-5, 5> stupňou. Podobne oprav aj MojaTurtle2, v ktorej v metóde fd namiesto troch náhodných čiar sa nakreslí iba jedna čiara, ale s náhodnou chybou z intervalu <-5, 5>. Teraz vyskúšaj test z úlohy (1), v ktorom sa vytvorilo 10 inštancií a tie nakreslili domčeky náhodnej veľkosti.

    Zisti, čo sa zmení s inštanciami triedy MojaTurtle2, ak budú odvodené z MojaTurtle1 (namiesto MojaTurtle).


Polymorfizmus

  1. Aritmetické operácie sú vnútorne realizované cez volania magických metód, napríklad x-2 ako x.__sub__(2). Prepíš tento výraz tak, aby sa všetky operácie nahradili volaniami metód:

    (x * 7 - 8 ) / 4 ** 2
    

    Skontroluj zápis na správnosť dosadením, napríklad:

    >>> x = 5
    >>> (x * 7 - 8 ) / 4 ** 2
    1.6875
    

    Prepíš nasledovný výraz tak, aby v ňom neboli volania magických metód:

    >>> (6).__sub__((5).__mul__(4)).__add__((3).__pow__(2))
    -5
    

    Po vyhodnotení by si mal dostať rovnaký výsledok.


  1. Triedu Cas z prednášky doplň tak, aby operácie sčitovania a odčitovania fungovali aj s celými číslami (pripočítava, resp. odpočítava sekundy), ale aj s n-ticami (prvým prvkom sú hodiny, druhým minúty a tretím sekundy). Napríklad:

    >>> c = Cas(8, 10, 34)
    >>> c
    8:10:34
    >>> c + 640
    8:21:14
    >>> c + (1, 55)
    10:05:34
    >>> c - 100
    8:08:54
    

    Ak IDLE nevypisuje hodnoty časov, asi ti chýba magická metóda __repr__.


  1. Pomocou modulu time a funkcie vieme zistiť momentálny čas v počítači. Napríklad:

    >>> import time
    >>> time.localtime()
    time.struct_time(tm_year=2017, tm_mon=11, tm_mday=22, tm_hour=8, tm_min=26, tm_sec=12,
    tm_wday=1, tm_yday=327, tm_isdst=0)
    >>> time.localtime()[3:6]
    (8, 26, 24)
    

    Napíš funkciu teraz(), ktorá vráti inštanciu triedy Cas s momentálnym časom. Napríklad:

    >>> c = teraz()
    >>> type(c)
    <class '__main__.Cas'>
    >>> c
    8:34:07
    >>> teraz()
    8:35:22
    

  1. Vytvor zoznam rôznych časov (napríklad ich generuj náhodným generátorom). Otestuj, či funguje triedenie pomocou štandardnej funkcie sorted(). Napríklad:

    >>> zoznam = [Cas(20, 15), Cas(7), ...]
    >>> zoznam1 = sorted(zoznam)
    >>> zoznam1
    [... usporiadaný zoznam časov ...]
    

    Funkcia sorted() by mala fungovať pre ľubovoľnú postupnosť prvkov, ktoré sa navzájom dajú porovnávať reláciou menší <.


Množiny - set

  1. Napíš funkciu neparne(n), ktorá vráti množinu všetkých nepárnych čísel menších ako n. Napríklad:

    >>> m = neparne(20)
    >>> type(m)
    <class 'set'>
    >>> m
    {1, 3, ... }
    

  1. Napíš funkciu samohlasky(veta), ktorá vráti množinu samohlások v danej vete. Napríklad:

    >>> samohlasky('mama ma emu')
    {'e', 'u', 'a'}
    >>> samohlasky('strc prst skrz krk')
    set()
    

  1. Napíš funkciu slova(meno_suboru), ktorá z textového súboru vytvorí množinu slov (slová sú navzájom oddelené medzerami). Funkcia túto množinu vráti ako svoj výsledok. Napríklad:

    >>> mn = slova('text1.txt')
    >>> mn
    {...}
    

    Vyskúšaj, napríklad na súbore:

    Many years ago there was an Emperor who was so excessively fond of
    new clothes that he spent all his money in dress He did not trouble
    himself in the least about his soldiers nor did he care to go either to
    the theatre or the chase except for the opportunities then afforded him
    for displaying his new clothes He had a different suit for each hour of
    the day; and as of any other king or emperor one is accustomed to say
    he is sitting in council it was always said of him The Emperor is
    sitting in his wardrobe
    

    alebo:

    Ján Botto
    Žltá ľalija
    
    Stojí stojí mohyla
    Na mohyle zlá chvíľa
    na mohyle tŕnie chrastie
    a v tom tŕní chrastí rastie
    rastie kvety rozvíja
    jedna žltá ľalija
     ľalija smutno vzdychá
    Hlávku moju tŕnie pichá
    a nožičky oheň páli
    pomôžte mi v mojom žiali
    

  1. Napíš funkciu vyrob(od, do), ktorá vytvorí (a vráti) množinu celých čísel z intervalu <od, do>, ktoré nie sú deliteľné 7 a zvyšok po delení 5 je 2 alebo 3. Napríklad:

    >>> a = vyrob(3, 20)
    >>> a
    {3, 8, 12, 13, 17, 18}
    

    Vytvorenie množiny vo funkcii zapíš najprv pomocou for-cyklu:

    def vyrob(od, do):
        vysl = set()
        for ...
            if ...
                ...
        return vysl
    

    Potom zapíš túto funkciu tak, aby obsahovala len jeden riadok (teda výraz s množinovými operáciami):

    def vyrob(od, do):
        return ...
    

    Pomôcka: výsledkom je množína všetkých celých čísel menších ako od+1, od ktorej odpočítaš množinu čísel do od+1, ktoré sú deliteľné 7 a potom ešte urobíš prienik s množinami čísel do od+1, ktoré po delení 5 dávajú zvyšok 2, resp. 3.


  1. Napíš funkciu bez(mnoz, k), ktorá z danej množiny mnoz vyhodí všetky prvky, ktoré sú deliteľné číslom k. Funkcia nič nevracia ani nevypisuje. Napríklad:

    >>> m = {1, 2, 3, 4, '5', 6}
    >>> bez(m, 3)
    >>> m
    {1, 2, 4, '5'}
    >>> m1 = set(range(0, 100, 5))
    >>> bez(m1, 10)
    >>> m1
    {65, 35, 5, 75, 45, 15, 85, 55, 25, 95}
    

  1. Napíš funkciu viac(zoznam), ktorá vráti množinu tých prvkov zoznamu zoznam, ktoré sa v ňom vyskytujú viac ako raz. Napríklad:

    >>> p = ['prvy', 2, (3, 4), 'dva', 3, 4, 'prvy', 3]
    >>> v = viac(p)
    >>> v
    {3, 'prvy'}
    

  1. Napíš funkciu len_cisla(mnozina), ktorá z danej množiny vyrobí novú, ale len z tých prvkov, ktoré sú čísla (int alebo float). Napríklad:

    >>> a = {'1', 2.2, (3, 4), 5}
    >>> b = len_cisla(a)
    >>> b
    {2.2, 5}
    

  1. Napíš funkciu vsetky(a, b, c, d), ktorá vráti zoznam všetkých dvojprvkových množín z prvkov a, b, c, d. Môžeš predpokladať, že všetky hodnoty parametrov sú navzájom rôzne. Napríklad:

    >>> vsetky(1, 2, 3, 4)
    [{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}]
    

  1. Vylepši funkciu z predchádzajúceho príkladu vsetky(postupnost), tak aby generovala všetky dvojprvkové množiny z prvkov zadanej postupnosti (zoznam, reťazec, množina, range(), …). Daj pozor, ak sa nejaké hodnoty v postupnosti opakujú. Napríklad:

    >>> vsetky('java')
    [{'j', 'v'}, {'a', 'v'}, {'j', 'a'}]
    >>> vsetky(range(5))
    [{0, 1}, {0, 2}, {0, 3}, {0, 4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}]
    >>> vsetky((3, 1, 'x', 4, 1, 2))
    [{1, 2}, {1, 'x'}, {1, 3}, {1, 4}, {2, 'x'}, {2, 3}, {2, 4}, {3, 'x'}, {'x', 4}, {3, 4}]
    

  1. Napíš funkciu kartez_sucin(m1, m2), ktorá vráti karteziánsky súčin množín, t.j. množinu všetkých usporiadaných dvojíc (tuple), ktorých prvá zložka je z množiny m1 a druhá zložka z množiny m2. Napríklad:

    >>> k = kartez_sucin({1, 2, 3, 4}, {'a', 'b', 'c'})
    >>> type(k)
    <class 'set'>
    >>> k
    {(3, 'c'), (3, 'b'), (2, 'a'), (4, 'a'), (4, 'c'), (4, 'b'), (1, 'b'),
     (1, 'c'), (1, 'a'), (3, 'a'), (2, 'c'), (2, 'b')}
    

    Uvedom si, že výsledná množina môže obsahovať tieto dvojice v ľubovoľnom inom poradí.


8. Domáce zadanie

L.I.S.T.


Iste si sa už stretol s logickou hrou Sudoku: úlohou hráča je zaplniť voľné políčka štvorcovej siete 9x9 (dvojrozmerná tabuľka) číslami od 1 do 9, tak aby boli splnené podmienky:

  • v každom riadku tabuľky bolo každé číslo práve raz

  • v každom stĺpci tabuľky bolo každé číslo práve raz

  • v každom vyznačenom štvorci 3x3 tabuľky bolo každé číslo práve raz

Zadanie hry môže vyzerať, napríklad takto:

_images/18_3.png

Tvoj program sa bude snažiť riešiť túto hru veľmi zjednodušeným spôsobom: postupne prejde všetky voľné políčka a pre každé z nich zistí množinu kandidátov, t.j. všetkých takých čísel, ktoré by sme na toto políčko mohli položiť a nevznikla by kolízia z už položenými číslami v riadku, v stĺpci a ani vo príslušnom štvorci 3x3. Zrejme, ak je niektorá z týchto množín prázdna, táto hra už nemá riešenie a netreba sa ju ďalej snažiť riešiť. Ak na niektorom voľnom políčku je táto množina jednoprvková, znamená to, že práve toto číslo je jediné, ktoré sem môžeme (musíme) zapísať. Ak toto urobíme so všetkými jednoprvkovými množinami, trochu sa priblížime k celkovému riešeniu tohto Sudoku. Riešenie pre vás teda bude znamenať toto:

  1. všetky voľné políčka nahraď množinami kandidátov

  2. ak je niektorá z množín prázdna, úloha nemá riešenie, bude treba skončiť

  3. ak tam nie je žiadna množina (nie je tam voľné políčko), úloha je zrejme vyriešená a bude treba skončiť

  4. ak majú všetky množiny viac ako 1 prvok, bude treba skončiť, lebo tento algoritmus už viac robiť nevie

  5. ak je tam niekoľko jednoprvkových množín, všetky sa nahradia týmto svojim jediným prvkom, všetky ostatné množiny sa nahradia znakom '.'

  6. ďalej sa pokračuje v 1. kroku

Napíš pythonovský modul, ktorý bude obsahovať jedinú triedu Sudoku a žiadne iné globálne premenné:

class Sudoku:
    def __init__(self, meno_suboru):
        self.tab = []
        ...

    def __str__(self):
        ...

    def urob(self):
        ...

    def nahrad(self):
        ...

    def ries(self):
        ...

    def pocet_nezaplnenych(self):
        ...

Metódy majú fungovať takto:

  • inicializácia __init__(meno_suboru) prečíta textový súbor s počiatočným zaplnením čísel, voľné políčka sú vyznačené znakmi '.'

    • súbor obsahuje 9 riadkov, v každom je 9 číslic alebo bodiek oddelených medzerou

    • inicializácia zaplní dvojrozmernú tabuľku self.tab (prvkami musia byť celé čísla int a znaky '.')

  • metóda __str__() vyrobí reťazcovú reprezentáciu hracej plochy: reťazec bude obsahovať 9 riadkov v každom po 9 hodnôt (čísel alebo bodiek) v rovnakom formáte, ako bol zadaný vstupný súbor

  • metóda urob() všetky voľné políčka (v tabuľke sú tam '.') nahradí množinami kandidátov, t.j. čísel, ktoré by sa na tejto pozícii mohli nachádzať

    • funkcia vráti -1, ak sa medzi týmito množinami objavila prázdna množina, inak funkcia vráti celkový počet jednoprvkových množín

  • metóda nahrad() všetky políčka s jednoprvkovými množinami sa nahradia priamo hodnotou v tejto množine, ostatné políčka s množinami sa nahradia znakom '.'

  • metóda ries() bude postupne volať metódy urob() a nahrad(), kým bude metóda urob() vracať číslo väčšie ako 0 (zrejme bude vykonávať hore uvedený cyklus)

    • funkcia vráti -1, ak táto hra nemá riešenie (metóda urob() vrátila -1)

    • funkcia vráti počet voľných políčok (zrejme 0 označuje, že úloha je vyriešená)

    • po skončení metódy ries() by dvojrozmerná tabuľka self.tab mala obsahovať len čísla a znaky '.'

  • metóda pocet_nezaplnenych() vráti momentálny počet voľných políčok

Napríklad pre vstupný súbor 'subor1.txt':

. . . . . 9 . . .
. . 7 . 8 6 . . .
6 . . 3 . . . . .
. 4 . . . 7 . . 8
. . . . . . . 3 2
. . 3 6 . 5 1 . .
. 6 . 7 . . . 8 .
3 . 2 . . . 4 9 .
. 5 4 8 . . . . 3

Tento test nám bude postupne vypisovať:

>>> s = Sudoku('subor1.txt')
>>> print(s)
. . . . . 9 . . .
. . 7 . 8 6 . . .
6 . . 3 . . . . .
. 4 . . . 7 . . 8
. . . . . . . 3 2
. . 3 6 . 5 1 . .
. 6 . 7 . . . 8 .
3 . 2 . . . 4 9 .
. 5 4 8 . . . . 3
>>> s.pocet_nezaplnenych()
55
>>> s.urob()
1
>>> for r in s.tab:
        print(r)

[{1, 2, 4, 5, 8}, {1, 2, 3, 8}, {1, 5, 8}, {1, 2, 4, 5}, {1, 2, 4, 5, 7}, 9, {2, 3, 5, 6, 7, 8}, {1, 2, 4, 5, 6, 7}, {1, 4, 5, 6, 7}]
[{1, 2, 4, 5, 9}, {1, 2, 3, 9}, 7, {1, 2, 4, 5}, 8, 6, {2, 3, 5, 9}, {1, 2, 4, 5}, {1, 4, 5, 9}]
[6, {1, 2, 8, 9}, {1, 5, 8, 9}, 3, {1, 2, 4, 5, 7}, {1, 2, 4}, {2, 5, 7, 8, 9}, {1, 2, 4, 5, 7}, {1, 4, 5, 7, 9}]
[{1, 2, 5, 9}, 4, {1, 5, 6, 9}, {1, 2, 9}, {1, 2, 3, 9}, 7, {5, 6, 9}, {5, 6}, 8]
[{1, 5, 7, 8, 9}, {1, 7, 8, 9}, {1, 5, 6, 8, 9}, {1, 4, 9}, {1, 4, 9}, {1, 4, 8}, {5, 6, 7, 9}, 3, 2]
[{2, 7, 8, 9}, {2, 7, 8, 9}, 3, 6, {2, 4, 9}, 5, 1, {4, 7}, {4, 7, 9}]
[{1, 9}, 6, {1, 9}, 7, {1, 2, 3, 4, 5, 9}, {1, 2, 3, 4}, {2, 5}, 8, {1, 5}]
[3, {1, 7, 8}, 2, {1, 5}, {1, 5, 6}, {1}, 4, 9, {1, 5, 6, 7}]
[{1, 7, 9}, 5, 4, 8, {1, 2, 6, 9}, {1, 2}, {2, 6, 7}, {1, 2, 6, 7}, 3]
>>> s.nahrad()
>>> for r in s.tab:
        print(r)

['.', '.', '.', '.', '.', 9, '.', '.', '.']
['.', '.', 7, '.', 8, 6, '.', '.', '.']
[6, '.', '.', 3, '.', '.', '.', '.', '.']
['.', 4, '.', '.', '.', 7, '.', '.', 8]
['.', '.', '.', '.', '.', '.', '.', 3, 2]
['.', '.', 3, 6, '.', 5, 1, '.', '.']
['.', 6, '.', 7, '.', '.', '.', 8, '.']
[3, '.', 2, '.', '.', 1, 4, 9, '.']
['.', 5, 4, 8, '.', '.', '.', '.', 3]
>>> s.ries()
28
>>> print(s)
. . . . . 9 . . .
. . 7 . 8 6 . . .
6 . . 3 . 4 . . .
2 4 1 9 3 7 5 6 8
. . . 4 1 8 . 3 2
. . 3 6 2 5 1 . .
1 6 9 7 4 3 2 8 5
3 8 2 5 6 1 4 9 7
7 5 4 8 9 2 6 1 3

Tvoj odovzdaný program s menom riesenie.py musí začínať tromi riadkami komentárov:

# 8. zadanie: sudoku
# autor: Janko Hraško
# datum: 1.12.2019

Projekt riesenie.py odovzdávaj na úlohový server https://list.fmph.uniba.sk/ najneskôr do 23:00 13. decembra, kde ho môžeš nechať otestovať. Testovač bude spúšťať tvoje riešenie s rôznymi vstupmi. Odovzdať projekt aj ho testovať môžeš ľubovoľný počet krát. Môžeš zaň získať 10 bodov.