====== 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 ====
* Napište program **assemble.py**, který si ze souboru se jménem zadaným jako první argumentu na příkazové řádce, přečte rozměr pole a díly, kterými má to pole zaplnit
* první řádek obsahuje dvě čísla //S// //R//, kde //R// je počet řádků a //S// je počet sloupců obdélníkového pole
* dále násluduje //R// řádků, kde
* 0 - definují volná pole v matici, která se mají vyplnit zadanými dílky
* -1 - definují obsazená pole, kam dílky nesmí zasahovat
* čísla na jednom řádku jsou oddělena jednou nebo více mezerami (použijte funkci "split()" bez parametrů).
* každý další řádek obsahuje popis jednoho dílku:
* jedna řádka obsahuje souřadnice čtverečků (x y), ze kterých je sestaven celý dílek
* souřadnice jsou uvedeny za sebou bez oddělovacích čárek a závorek
* dílek může být libovolně posunut, nemusí obsahovat čtverec se souřadnicemi (0,0)
* Program v souboru **assemble.py** nalezne libovolné pokrytí volných polí matice dílky, které se použijí tak, jak jsou zadány - nesmíte je natáčet ani převracet, pouze posouvat. Námi zadané příklady mají právě jedno řešení.
* Výstupem programu je pokrytí matice dílky, kdy plocha prvního dílku (zadaný v souboru hned za maticí volného místa) je vyplněna číslem 1, plocha druhého dílku (na další řádce za prvním dílkem) číslem 2, atd.
* Notace pro popis dílků: je to seznam x y souřadnic.
* Pro T-dílek na obrázku je jeho popis: 0 0 1 0 2 0 1 1
{{:courses:b3b33alp:cviceni:blokus1.eps.png?200|}}
* Pro obsah zadan0ho souboru:
5 5
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
-1 0 0 0 0
-1 -1 0 0 0
2 2 2 1 2 0 1 0 0 0 0 1
0 0 0 1 1 1 2 1 2 0 2 2
3 0 3 1 2 1 1 1 0 1
0 0 0 1 0 2 1 1 2 1
Příklad dílku 1:
2 2 2 1 2 0 1 0 0 0 0 1
souřadnice
y
2 *
1* *
0***
012 souřadnice x
Graficky znázorněné všechny dílky
1:{{:courses:b3b33alp:cviceni:ubongo-0e.png?100|}}
2:{{:courses:b3b33alp:cviceni:ubongo-1.png?100|}}
3:{{:courses:b3b33alp:cviceni:ubongo-2e.png?100|}}
4:{{:courses:b3b33alp:cviceni:ubongo-3e.png?100|}}
program vytiskne:
4 3 3 3 3
4 4 4 2 3
4 2 2 2 1
-1 2 1 2 1
-1 -1 1 1 1
Nápověda možného řešení:
* Postupně se snažím vyplnit prázné místo, např odshora zleva
* Na první volné políčko se snažím umístit dílek tak, že toto volné pole zaplní svou nejhořejší levou částí (protože vše nad a vlevo od volného políčka je zaplněno, viz obrázek) a rekurzivně zavolám plnění se seznamem dílků, ze kterých odstraním právě použitý dílek
{{:courses:b3b33alp:fill.png?100|}}
* Pokud to nevyjde a políčko nelze žádným dílkem zaplnit tak, aby tento dílek nepřekrýval jiné dílky, nebo nepřesahoval přes okraj matice), pak se vrátím z rekurze
* Při návratu z rekurze, zkusím obsadit volné pole jiným dílkem
* Pro správné fungování rekurze buď vytvořím nové pole s nově vloženým dílkem, nebo při návratu z rekurze musím odstranit z matice starý dílek
* Pokud již nemám dílky a celá matice je obsazená - mám řešení a mohu skončit
==== Těžká varianta ====
* Napište program **three.py**, který převede výraz z [[https://cs.wikipedia.org/wiki/Infixov%C3%A1_notace|infixového zápisu]] (standarní zápis výrazů, jak jste zvyklí ze školy) do reprezentace [[https://en.wikipedia.org/wiki/Three-address_code|tří-adresného módu]]. Tento tří-adresový kód je využíván překladačem, jako mezistupeň mezi programem a strojovým jazykem.
**Vstup:**
* Výraz je zadán na jedné řádce standardního vstupu
* Vstupní výraz může obsahovat pouze celá kladná celá čísla (záporné číslo je unární operátor - a kladné číslo), mezery, závorky (, ) a operace +,-,*,/,^. (Operace ^ je mocnina a má nejvyšší prioritu, nejnižší prioritu mají operace +,-, prostřední prioritu *,/)
* Oproti lehké variantě výraz umožňuje unární + a -, tedy je správně 2 + - 3, i 2-+-3 (POZOR unární - má ještě vyšší prioritu než mocnina)
**Výstup:**
* Při převodu musíte otestovat správnost zadaného výrazu a pokud je formát chybný, pak vytisknete ERROR
* formát výstupu:
* první trojice má číslo 1, každá další trojice o jedno větší číslo
* trojice tiskněte bez mezer, tak jak je uvedeno níže
* unární - se přeloží jako trojice, např -5 bude tXX:=0-5
* unární + se vypustí, ve výrazu je vlastně zbytečné
* výraz se vyhodnocuje zleva doprava (všechny operace i mocniny) a toto vyhodnocování určuje pořadí trojic. V příkladu níže není tedy možné nejdříve vypočítat rozdíl 1-5 a teprve potom součin 4*2
Příklad:
* Vstup
3 + 4 * 2 / ( 1 - 5 )
* převede na výstup:
t1:=4*2
t2:=1-5
t3:=t1/t2
t4:=3+t3
Příklad:
* Vstup
(1+2)*(3+4)/(5+6)
* převede na výstup:
t1:=1+2
t2:=3+4
t3:=t1*t2
t4:=5+6
t5:=t3/t4
Příklad:
* Vstup
1+2/(*4+5)
* převede na výstup:
ERROR