====== Cvičení 8, Fronta, zásobník ====== ===== náplň cvičení ===== ==== Úkol 1 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. ==== Úkol 2: třídění karet ==== Uvažujme [[ https://en.wikipedia.org/wiki/Playing_card#/media/File:Svg-cards-2.0.svg | hrací karty ]]. * Máme karty čtyř barev, každá barva má dále karty 2,3,4,5,6,7,8,9,10,J,Q,K,A * Kartu budeme reprezentovat 1D polem, kde: * první prvek je barva karty (0,1,2,3). Tento prvek bude ''int'' * druhý prvek je typu ''string'' a je to hodnota karty, tedy např. "Q" nebo "1" * Příklad karty: ''[1,"2"], [2,"A"], [0,"K"]'' * Pořadí karet v dané barvě je toto: 2,3,4,5,6,7,8,9,10,J,Q,K,A, kde * 2 má nejmenší hodnotu * A má největší hodnotu * platí že $2<3$, $3<4$, ... Q $<$ K, J $>$ 10, atd. Napište funkci, který **vzestupně** třídí karty podle jejich barvy a podle jejich hodnoty. * na vstupu je seznam (pole) karet * funkce vrátí setříděné pole tak, že na začátku budou karty barvy 0, pak karty barvy 1,atd., přičemž v každé skupině budou karty setříděny podle jejich hodnot. * Využijte bublinkové třídění, nebo Vaše oblíbené třídění z přednášky * Příklad:

  
cards = [  [3,"A"],  [3,"Q"],  [0,"2"],  [1,"10"]  ]

výsledek pro setřídění:


[  [0, "2"],  [1, "10"],  [3, "Q"],  [3, "A"]  ]

Seřaďte toto pole:


cards = [[0, 'Q'], [2, '6'], [1, 'K'], 
         [1, '8'], [2, '10'], [2, '4'], 
         [3, '4'], [0, '4'], [1, '3'], 
         [2, '5'], [0, 'K'], [3, 'A'], 
         [1, 'J'], [0, '3'], [0, '9']]

==== Úloha 3 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**

==== Úloha 4 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žíte vstupní bod * Opakuje, dokud není zásobník prázdný: * pro každý bod (x,y) ze zásobníku, pokud je hodnota matice v tomto bodu 0 proveďte: * pokud jsou body (x-1,y),(x+1,y),(x,y-1),(x,y+1) v matici a jejich hodnota je 0, pak je vložte do zásobníku * 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? ===== domácí práce ===== ==== 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 výpíš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 teamsech. * Jak bude hodnoceno: * Vyřešení hrací desky o velikosti 3x3, počet kamenů 2 až 4 (0.25b) * Vyřešení hrací desky o velikosti 4x4, počet kamenů 3 až 5 (0.25b) * Vyřešení hrací desky o velikosti 5x5, počet kamenů 2 až 6 (0.25b) * Správná detekce hrací desky bez řešení (0.25b) === 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 }} == Souřadnicový systém == * Pozice každé buňky na hexagonálním gridu lze vyjádřit souřadnicí (p,q), kde p označuje sloupec a q řádek. * Horní levý roh má souřadnici (0,0) * Liché řádky (q=1,3..) jsou oproti sudým posunuty směrem doprava * Vzhledem k posunu buněk mezi řádky je osa 'p' nakloněna, viz obrázek: {{ :courses:b3b33alp:cviceni:hw8-pqsystem.png?400 |}} * Tento souřadnicový systém je zvolen proto, že umožňuje logické adresování buněk, je celočíselný a hlavně, podporuje rychlou operaci rotace, viz zadání těžké varianty * Pro vypracování úlohy není nutné soubor base.py používat, protože nás pouze zajímá, jak bude hrací deska obsazena, nicméně silně doporučujeme využít base.py === 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)

* Práci s hrací deskou umožňuje třída Board, která obsahuje proměnnou board typu dictionary, která představuje hrací desku * Následující program vyplní první řadu hodnotou 1


board = base.Board(size)
for p in board.board:
   if board.inBoard(p,0):
       board.board[p][0] = 1
board.saveImage("deska.png")

* metoda 'inBoard(p,q)' vrací True, pokud souřadnice (p,q) odkazuje na správnou pozici uvnitř hrací desky * před zápisem do hrací desky, např. 'board[p][q] = 3' je vždy nutné zkontrolovat, zda-li je souřadnice (p,q) validní, tedy:


#chci zapsat hodnotu 3 na souradnici p,q
if board.inBoard(p,q):
   board.board[p][q] = 3

* vždy používejte 'inBoard(p,q)' před zápisem do hrací desky, předejdete tak situaci, že budete zapisovat mimo hrací desku * Vykreslení kamenů


stones = base.loadStones("nejaky vstupni soubor")
for si in range(len(stones)):
   board = base.Board(10)  #velikost 10x10
   for i in range(len(stones[si])):
      p,q = stones[si][i]   #i-ta bunka si-teho kamene
      p += 10//3            #posuneme kamen doprosted hraci desky,
      q += 10//2            #abychom ho mohli cely vykreslit
      if board.inBoard(p,q):  #kontrola, ze i-ta bunka kamene je v hraci desce
          board.board[p][q] = 1  #zapiseme
   board.saveImage("kamen-{}.png".format(si))

* Pokud chcete projít celou hrací desku, používejte vždy tuto konstrukci:


for p in board.board:    #vsechny sloupce v hraci deske
    for q in board.board[p]:   #vsechny radky, ktere nalezi sloupci p
        print("Hodnota bunky ", p,q, " je ", board.board[p][q] )

* První for cyklus prochází validní 'p' souřadnice, druhý for cyklus prochází validní 'q' souřadnice na 'p'-tém sloupci === Doporučený postup === * Nejprve se seznamte se souřadnicovým systémem (p,q) pro hexagonální gridy * Udělejte si následující úkoly: * Vyplnit zadaný řádek hodnotou 1 * Vyplnit zadaný sloupec hodnotou 2 * Najděte buňky, které mají levého souseda mimo hrací desku. Obdobně, identifikujte buňky, které mají souseda vpravo/nahoře/dole mimo hrací desku * používejte saveImage() pro uložení do png * Práce s kameny: * vykreslete kamen na pozici (0,0) * napište metodu pro vycentrování kamene např. tak, aby jeho 'i'-tá část měla hodnotu (0,0) * vykreslete všechny možné pozice kamenu na hrací desce (uvažujte pouze translace). Pro tento úkol se hodí mít kamen vycentrovaný * Teprve až se důkladněte seznámíte s hrací deskou, začněte přemýšlet, jak vyřešit úlohu výplně hrací desky kameny 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 rozmisteni 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 base.py === * Následující program si můžete stáhnou odtud {{courses:b3b33alp:cviceni:base.py|base.py}} a zkopírovat do stejné složky, ve které píšete domácí úlohu * Nezapomeňte na 'import base' na začátku vašeho programu * Objekt Board si můžete zkopírovat i z tohoto výpisu:


b = base.Board(size)

* Načtení kamenů


stones = base.loadStones(soubor-s-kameny)

* Pro ukládání obrázků se používá knihovna [[ https://en.wikipedia.org/wiki/Python_Imaging_Library | Python Imaging Library ]] * Návod na instalaci: [[https://pillow.readthedocs.io/en/stable/installation.html ]]


import copy
import math
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
        """

        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="m")
        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}}