====== Cvičení 8: Fronta, zásobník, objekty ====== ==== Dekódování zprávy ==== * Dekódujde zprávu ze standardního vstupu pomocí zásobníku: * Písmeno znamená push znaku na zásobník * Hvězdička znamená pop znaku ze zásobníku na výstup * Mezery se ignorují * Dekódujte následující vstup


TE*A*QYS***SEU****NI*O**

==== Flood fill ==== * Napište program, který v zadané matici nahradí souvislou oblast 0 ze zadaného bodu hodnotou 2. * Matici vezměte jako vnitřní proměnnou: m=[ [0,0,1,0,0,1,0,0,0,0], [0,0,1,0,0,1,0,0,0,0], [0,0,1,1,0,1,0,0,0,1], [0,0,1,0,0,0,1,0,1,0], [0,0,1,0,0,0,0,1,0,0], [0,0,1,1,0,1,0,0,0,0], [0,0,1,0,1,1,1,1,0,0], [0,0,1,0,0,1,0,1,1,1], [0,0,1,0,0,1,0,0,0,0], [0,0,1,0,0,1,0,0,0,0] ] * Program si načte počáteční bod ze standardního vstupu * Do zásobníku vloží vstupní bod * Opakuje, dokud není zásobník prázdný: * uloží si hodnotu (x, y) prvního prvku v zásobníku * odstraní první prvek ze zásobníku * pokud je hodnota matice v bodě (x, y) rovna 0, vloží do zásobníku: * souřadnice (x-1,y),(x+1,y),(x,y-1),(x,y+1), pokud jsou v mezích rozměrů matice * Vytiskněte výslednou matici * Program otestujte pro vstupy: 4,4 a 9,9 * Co by se stalo, pokud byste na zásobník vložili i body (x-1,y-1),(x+1,y+1),(x+1,y-1),(x-1,y+1)? * Jaká je složitost tohoto algoritmu? Uměli byste tento algoritmus zefektivnit, aby nevkládal jedno pole matice do zásobníku vícekrát? ==== Fronta ==== * Přeměňte řešení úlohy //Flood fill// změňte zásobník na frontu. * Postupnou animací zjistěte jak se změnilo vyplňování prostoru * Zjistěte, zda potřebuje více paměti zásobník, nebo fronta. Otestujte i na větším prostoru. ==== Objekt komlexní číslo ==== Třídy pro komplexní čísla: * Třída obsahuje dvě proměnné ''real'' a ''imag'' * Konstruktor (metoda ''_init_()'') nastavuje tyto proměnné defaultně na 0 * Pro přímý výpis funkcí print je vhodné definovat metodu ''_repr_'', která vrací string * **Pozor: init a repr má v názvu dvě podtržítka!!! **


class Complex:
    def __init__(self, real=0, imag=0):
        self.real = real
        self.imag = imag

    def amplitude(self):
        return (self.real*self.real + self.imag*self.imag)**(1/2)
    
    def add(self, rhs):
        self.real += rhs.real
        self.imag += rhs.imag

    def sub(self, rhs):
        self.real -= rhs.real
        self.imag -= rhs.imag

    def __repr__(self):
        sign = "+";
        if (self.imag < 0):
            sign = "-";
        return str(self.real) + sign + str(abs(self.imag)) + "i"

    def mul(self, rhs):
        r = self.real*rhs.real - self.imag*rhs.imag;
        i = self.real*rhs.imag + self.imag*rhs.real;
        self.real = r
        self.imag = i 

a = Complex()
print("a=",a)

b = Complex(1,-1)
print("b=",b)

a.add(b)
print("a=",a)

a.mul(b)
print("a=",a)

print("|a|=",a.amplitude())
print("|b|=",b.amplitude())

===== Témata k procvičení ===== ==== Inverzní permutace ==== * Pokud pole o délce $N$, obsahuje všechna čísla od $0$ do $N-1$ právě jednou, pak toto pole kóduje permutaci tak, že první prvek se zobrazí na místo, kde se v poli nachází $0$, druhý prvek na místo, kde se v poli nachází $1$, atd. * Pole ''[0, 1, 2, 3]'' kóduje identickou, tzv. jednotkovou, permutaci o čtyřech prvcích, * Pole ''[3, 2, 1, 0]'' kóduje otočení prvků v poli. * Napište program, který načte z jednoho řádku standardního vstupu vektor reprezentující permutaci a najde a vytiskne inverzní permutaci, tj. permutaci, která převede zadanou permutaci na jednotkovou. * Inverzní permutace k permutaci ''[2, 0, 1]'', je permutace ''[1, 2, 0]'', neboť první permutace zobrazí 0->2 a druhá permutace 2->0, obdobně 1->0, druhá permutace 0->1; první 2->1 a druhá 1->2. ===== Domácí úkol ===== ==== Lehká varianta ==== * Tématem úlohy je napsat program **tile_easy.py**, který vyplní hexagonální hrací desku zadanými kameny Příklad 1: vstupní kameny {{ :courses:b3b33alp:cviceni:hw8-4-5-0a.png?400 |}} Úkolem je vyplnit hrací desku o velikosti 4x4 (4-řádky, každý řádek 4 pole). Všechna řešení jsou: {{:courses:b3b33alp:cviceni:config-4-5-0b-0.png?100}} {{:courses:b3b33alp:cviceni:config-4-5-0b-1.png?100}} {{:courses:b3b33alp:cviceni:config-4-5-0b-2.png?100}} {{:courses:b3b33alp:cviceni:config-4-5-0b-3.png?100}} {{:courses:b3b33alp:cviceni:config-4-5-0b-4.png?100}} {{:courses:b3b33alp:cviceni:config-4-5-0b-5.png?100}} * **Vstup programu:** argumenty příkazové řádky * první argument: velikost hrací desky (jedno celé číslo) určující jak počet řádků tak i počet sloupců * druhý argument: jméno vstupního souboru s hracími kameny (je zaručeno, že existuje, že obsahuje alespoň jeden kamen a obsahuje správně zadané kameny) * třetí argument: jméno výstupního souboru * Program nalezne kombinaci kamenů na hrací desce tak, aby každé políčko bylo vyplněno právě jedním kamenem * **V lehké variantě domácí úlohy** je povolena pouze translace kamenů, tedy je zakázáno kameny otáčet * Je možné použít všechny kameny, ale není to nutné. Každý kamen se ale použije nejvýše jednou. * Pokud je nějaký kamen použit, musí se **celý vejít do hrací desky**, nesmí přečnívat přes hrací desku ani se nesmí překrývat s jiným kamenem * Program do výstupního souboru vypíše: * právě jedno řešení - libovolné ze všech existujících řešení * Výstup programu se zapisuje do výstupního souboru takto: * každý řádek obsahuje tři celá čísla ve tvaru 'p q i', kde (p,q) je celočíselná souřadnice na hrací desce a 'i' je index kamene, který tuto buňku obarvuje * kameny jsou číslovány od **jedničky** podle pořadí ve vstupním souboru (kamen definován na první řádce bude barvit na 1, kamen na druhá řádce obarvuje hodnotou 2 atd..) * NOSOLUTION, pokud žádné neexistuje * pokud řešení neexistuje, obsahuje soubor pouze jednu řádku s textem 'NOSOLUTION' * Program **odevzdejte jako tile_easy.py do HW08** * Timeout je nastaven dostatečně, pokud by Váš program měl problémy s časovým omezením, kontaktujte nás na fóru předmětu. * Jak bude hodnoceno: * Vyřešení hrací desky o velikosti 3x3, počet kamenů 2 až 4 (0.4b) * Vyřešení hrací desky o velikosti 4x4, počet kamenů 3 až 5 (0.4b) * Vyřešení hrací desky o velikosti 5x5, počet kamenů 2 až 6 (0.4b) * Správná detekce hrací desky bez řešení (0.3b) === Nápověda a pomocný program === * Obtížnost této úlohy spočívá jednak v tom, jak najít vhodné poskládání kamenů, které zcela pokrývá hrací desku, a také v tom, jak pracovat s hexagonálním gridem * Pro usnadnění práce na domácí úloze si stáhněte program base.py (na konci této stránky), který vám nabízí užitečné nástroje * {{ :courses:b3b33alp:cviceni:hexagonalgrid.pdf | PDF template s hexagonálním gridem }} === Ukázka programu === * Volání programu


python3 tile_easy.py 3 stones.txt solution.txt

* Stones.txt obsahuje:


2 0 
1 2 1 1 0 2 
0 0 1 0 0 1 -1 2 
2 1

* Visualizace kamenů - pozor - při vykreslovani jsou kameny posunuty směrem do stredu hraci desky. Následující obrázky tedy nevykresují absolutní souřadnice ze vstupního souboru! {{:courses:b3b33alp:cviceni:config-3-4-stones.png?400}} * Jedno z řešeních je

* Toto řešení odpovídá levému obrázku níže. * Všechna řešení jsou: {{:courses:b3b33alp:cviceni:config-3-4-2b-0.png?200}}{{:courses:b3b33alp:cviceni:config-3-4-2b-1.png?200}} {{:courses:b3b33alp:cviceni:config-3-4-2b-2.png?200}} {{:courses:b3b33alp:cviceni:config-3-4-2b-3.png?200}} === Kameny === * Kamen je tvořen jednou nebo více buňkami * Kameny jsou tedy zadány ve stejné notaci jako hexagonální grid * Na každém řádku vstupního souboru je zadán jeden kamen ve formátu 'p1 q1 p2 q2 ... pn qn', pro 'n' buněk, kde p,q jsou celá čísla * V souboru mohou být kameny stejného tvaru (ale mohou být zadány různými souřadnicemi). * Kamen1: 0 0 1 0 2 0 * Kamen2: 1 0 0 0 2 0 * Kamen3: -1 1 0 1 1 1 * Tyto kameny jsou tvarově stejné, ale pro vyplňování hrací desky je považujte za různé (každý bude obarvovat jinou barvou podle pořadí v souboru. * Pro načtení kamenů můžete využít funkci


stones = base.loadStones(filename)

* Pro výpis jednotlivých kamenů můžete použít např.


for si in range(len(stones)):
   print("Stone ", si, " has ", len(stones[si]), " cells ") 
   stoneColor = si + 1    #toto je barva kamene, kterou zapisujeme do hraci desku
   for i in range(len(stones[si])):
      p,q = stones[si][i]
      print("Cell[",i,"] of stone ",si, " is ",p,q)

Takto bude vypadat typický program pro HW08:


import base
import sys
 
#nacteni vstupnich parametru z prikazove radky do promennych size, inputFile, outputFile
size = int(sys.argv[1])
board = base.Board(size)
stones = base.loadStones(sys.argv[2])

#program hledajici rozmísteni kamenu, ktery svuj vysledek zapisuje do board.board

#vytvoreni, ci otevreni vystupniho souboru do handleru f
f=open(sys.argv[3], "w")
if reseni_exist:
  for p in board.board:
   for q in board.board[p]:
      f.write("{} {} {}\n".format(p,q,board.board[p][q]))
else:
  f.write("NOSOLUTION")
f.close()

/** Soubor {{ :courses:b3b33alp:cviceni:base.py |base.py}} může stáhnout zde. */ ==== base.py ==== Následující program si uložte do stejného adresáře jako program pro tuto úlohu. Uložte jej pod názvem base.py




import copy
import math
#import random
from PIL import Image, ImageDraw


def loadStones(filename):
    f = open(filename,"r")
    stones = []
    for line in f:
        coords = list(map(int, line.rstrip().split()))
        if len(coords) > 0:
            stones.append( [] )
            for i in range(len(coords)//2):
                x = coords[2*i]
                y = coords[2*i+1]
                stones[-1].append([ x,y ] )
    return stones;
            

class Board:
    def __init__(self, size):
        self.size = size
        self.board = {}

        #create empty board as a dictionary
        self.b2 = {}
        for p in range(-self.size,self.size):
            for q in range(-self.size, self.size):
                if self.inBoard(p,q):
                    if not p in self.board:
                        self.board[p] = {}
                    self.board[p][q] = 0

                    if not q in self.b2:
                        self.b2[q] = {}
                    self.b2[q][p] = 0

        #this is for visualization and to synchronize colors between png/js
        self._colors = {}
        self._colors[-1] = "#fdca40" #sunglow
        self._colors[0] = "#ffffff" #white
        self._colors[1] = "#947bd3" #medium purple
        self._colors[2] = "#ff0000" #red
        self._colors[3] = "#00ff00" #green
        self._colors[4] = "#0000ff" #blue
        self._colors[5] = "#566246" #ebony
        self._colors[6] = "#a7c4c2" #opan
        self._colors[7] = "#ADACB5" #silver metalic
        self._colors[8] = "#8C705F" #liver chestnut
        self._colors[9] = "#FA7921" #pumpkin
        self._colors[10] = "#566E3D" #dark olive green
        


    def inBoard(self,p,q):
        """ return True if (p,q) is valid coordinate """
        return (q>= 0) and (q < self.size) and (p >= -(q//2)) and (p < (self.size - q//2))


    def rotateRight(self,p,q):
        pp = -q
        qq = p+q
        return pp,qq

    def rotateLeft(self, p,q):
        pp = p+q
        qq = -p
        return pp, qq



    def saveImage(self, filename):
        """ draw actual board to png. Empty cells are white, -1 = red, 1 = green, other values according to
            this list 
            -1 red, 0 = white, 1 = green 
        """

        cellRadius = 25
        cellWidth = int(cellRadius*(3**0.5))
        cellHeight = 2*cellRadius

        width = cellWidth*self.size + cellRadius*3
        height = cellHeight*self.size

        img = Image.new('RGB',(width,height),"white")
        
        draw = ImageDraw.Draw(img)

        lineColor = (50,50,50)

        
        for p in self.board:
            for q in self.board[p]:
                cx = cellRadius*(math.sqrt(3)*p + math.sqrt(3)/2*q) + cellRadius
                cy = cellRadius*(0*p + 3/2*q) + cellRadius

                pts = []
                for a in [30,90,150,210,270,330]:
                    nx = cx + cellRadius * math.cos(a*math.pi/180)
                    ny = cy + cellRadius * math.sin(a*math.pi/180)
                    pts.append(nx)
                    pts.append(ny)
                color = "#ff00ff" #pink is for values out of range -1,..10
                if self.board[p][q] in self._colors:
                    color = self._colors[self.board[p][q]]
                
                draw.polygon(pts,fill=color)
                pts.append(pts[0])
                pts.append(pts[1])
                draw.line(pts,fill="black", width=1)
                draw.text([cx-3,cy-3], "{} {}".format(p,q), fill="black", anchor="mm")
        img.save(filename)

==== Těžká varianta ==== * Zadání je stejné jako pro lehkou úlohu, kromě této změny: * Hledejte kombinaci kamenů, aby úplně vyplnily hrací desku s tím, že je možné použít jak translace, tak i rotace kamenů * Je zakázáno kameny překlápět zrcadlově * V hexagonálním gridu můžeme rotovat kameny o 60 stupňů, existuje 6 rotací * Pro rotaci buňky (p,q) doleva o 60 stupňů okolo buňky (0,0) použijte funkci:


newp, newq = board.rotateLeft(p,q)

* Pro rotaci buňky (p,q) doprava o 60 stupňů okolo buňky (0,0) použijte funkci:


newp, newq = board.rotateRight(p,q)

* Opakovaným volání těchto funkcí dostanete další rotace * **Odevzdejte jako tile_hard.py do HW08** * Vstupy i výstupy jsou shodné s lehkou úlohou == Ukázka rotace == Základní pozice kamene {{:courses:b3b33alp:cviceni:hw8-stone15-rot0.png?200}} 1. rotace {{:courses:b3b33alp:cviceni:hw8-stone15-rot1.png?200}} 2. rotace {{:courses:b3b33alp:cviceni:hw8-stone15-rot2.png?200}} 3. rotace {{:courses:b3b33alp:cviceni:hw8-stone15-rot3.png?200}} 4. rotace {{:courses:b3b33alp:cviceni:hw8-stone15-rot4.png?200}} 5. rotace {{:courses:b3b33alp:cviceni:hw8-stone15-rot5.png?200}}