====== 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í úkol =====
==== Lehká varianta ====
* Úkolem je napsat program **fill_easy.py** (úloha HW08), který nalezne uspořádání kamenů tak, aby zcela vyplnily matici o rozměrech MxN
* Kameny jsou složeny ze čtverečků (buněk) - jedná se o tzv. [[ https://en.wikipedia.org/wiki/Polyomino | polyomina ]]
* Vstupem programu je:
* jméno souboru jako první argument příkazové řádky (''sys.argv[1]'')
* vstupní soubor obsahuje:
* první řádek: celé číslo udávající počet řádků vyplňované matice (M)
* druhý řádek: celé číslo udávající počet sloupců vyplňované matice (N)
* každý další řádek obsahuje celá čísla oddělená mezerou ve formátu:
* ''barva r1 c1 r2 c2 ... rn cn''
* kde barva označuje barvu kamene
* ''r_i c_i'' je i-tá buňka kamene (řádek, sloupec)
* Výstupem programu je na std. výstupu:
* Matice o rozměrech MxN, kde její prvky obsahují čísla kamenů, které jsou na odpovídající pozici uloženy
* matice je vypsána v tzv. pythonovském formátu, použijte standardní funkci ''print()''
* pokud existuje více řešení, vypište libovolné z nich
* Nebo řetěžec ''NOSOLUTION'', pokud vstupní kameny nelze poskládat tak, aby zcela matici vyplnily
* Správné řešení (pokud existuje) je takové, že jsou použity všechny kameny, každý zcela leží uvnitř matice a žadné políčko matice není prázdné
* Povolené operace s kameny: posun nahoru/dolu/vlevo/vpravo
* Je zakázáno kameny rotova nebo zrcadlit.
* Je zaručeno, že vstupní soubor obsahuje alespoň tři řádky (tj. M, N a jeden kamen).
* Je zaručeno, že každý kamen je složen z alespoň jednoho čtverečku
* Barva kamene je vždy větší než 0
* Barvy kamenů nemusí být číslovány vzestupně (viz příklady)
* Výpis matice proveďte takto:
m = [ [ 1,1,1], [2,2,2] ] #priklad matice 2x3, kde na 1. radku lezi kamen '1' a na 2. radku kamen s barvou '2'
print(m) #takto vypiste reseni
* Brute bude testovat na maticích 5x5 .. 7x7 s 5..10 kameny, dále na obdélníkových maticích (např. 5x9, 10x3 apod) a příklady, kde řešení neexistuje. V každé skupině bude provedeno 15-20 testů. Timeout na výpočet programů v každé skupině je 100s (tj. cca 5s na vyřešení jednoho příkladu).
Pro načtení vstupních dat můžete využít tento program:
def readStones(filename):
stones = [] #vystup funkce - seznam nactenych kamenu
f = open(filename,"r")
numRows = int(f.readline().strip()) #precti 1. radek ze souboru
numCols = int(f.readline().strip()) #precti 2. radek ze souboru
for line in f:
numbers = list(map(int, line.strip().split())) #precti vsechna cisla na dalsich radcich
color = numbers[0] #prvni z nich je barva kamene
coords = numbers[1:] #zbyle jsou souradnice r1 c1 ... rn cn
cells = [] #prevedeme [r1,c1 ... rn,cn] na pole cells = [[r1,c1], ... [rn,cn]]
for i in range(len(coords)//2):
cells.append( [ coords[2*i+0], coords[2*i+1] ] )
stones.append( [ color, cells ] )
f.close()
return numRows, numCols, stones;
M,N, stones = readStones("kameny.txt")
#n-ty kamen je stones[n]
#jeho barva je stones[n][0], jeho bunky jsou stones[n][1]
#vypis pozic n-teho kamene:
n = 0 #napriklad chceme 0.kamen
for cellindex in range(len(stones[n][1])):
row,col = stones[n][1][cellindex]
print(row,col)
==== Příklad 1: ====
python3 fill_easy.py soubor.txt
pokud soubor.txt obsahuje:
5
5
6 0 4 0 5 -1 5 -1 4
5 4 2 4 1 4 0 3 1 3 2 3 0 2 1 2 0
2 6 4 7 4 7 3
3 -2 9 -3 9
4 7 10 8 10 8 11 9 10 6 10 5 10
1 4 14 4 13
Správné řešení je:
[[4, 5, 5, 1, 1], [4, 5, 5, 5, 3], [4, 5, 5, 5, 3], [4, 4, 2, 6, 6], [4, 2, 2, 6, 6]]
Vysvětlení: vstupní kameny vypadají takto (kameny jsou pro účel zobrazení posunuty, aby se vešly do obrázku):
|kamen s barvou 6 | kamen s barvou 5 | kamen s barvou 2 |
|{{:courses:b3b33alp:cviceni:e-13739-stone0.png?200|}} | {{:courses:b3b33alp:cviceni:e-13739-stone1.png?200|}} | {{:courses:b3b33alp:cviceni:e-13739-stone2.png?200|}} |
|kamen s barvou 3 | kamen s barvou 4 | kamen s barvou 1 |
|{{:courses:b3b33alp:cviceni:e-13739-stone3.png?200|}} | {{:courses:b3b33alp:cviceni:e-13739-stone4.png?200|}} | {{:courses:b3b33alp:cviceni:e-13739-stone5.png?200|}} |
Tyto kameny lze poskládat takto:
{{:courses:b3b33alp:cviceni:e-13739.png?200|}}
==== Příklad 2: ====
python3 fill_easy.py soubor.txt
pokud soubor.txt obsahuje:
5
5
3 -5 7 -6 7 -4 7 -5 8
6 -7 1 -6 1 -6 2 -5 1 -5 2 -5 3 -5 4
4 3 12 3 11 4 11
5 7 12 8 12
1 4 -5 3 -5 3 -6
2 0 -6 -1 -6 -1 -7 -2 -7 -2 -8 -1 -8
Správné řešení je:
NOSOLUTION
Vysvětlení: vstupní kameny vypadají takto:
|kamen s barvou 3 | kamen s barvou 6 | kamen s barvou 4 |
|{{:courses:b3b33alp:cviceni:e-74004-stone0.png?200|}} | {{:courses:b3b33alp:cviceni:e-74004-stone1.png?200|}} | {{:courses:b3b33alp:cviceni:e-74004-stone2.png?200|}} |
|kamen s barvou 5 | kamen s barvou 1 | kamen s barvou 2 |
|{{:courses:b3b33alp:cviceni:e-74004-stone3.png?200|}} | {{:courses:b3b33alp:cviceni:e-74004-stone4.png?200|}} | {{:courses:b3b33alp:cviceni:e-74004-stone5.png?200|}} |
Tyto kameny nelze posládat do matice 5x5.
==== Příklad 3: ====
python3 fill_easy.py soubor.txt
pokud soubor.txt obsahuje:
5
8
6 -1 0 -1 1 -1 -1
5 -8 10 -9 10 -9 11 -8 11 -7 10 -9 12 -7 9 -6 10 -6 11
7 -4 12 -3 12 -2 12
8 11 0 11 1 12 0 10 0 12 1 11 -1 10 1 13 1
3 10 0 10 1 10 2 11 1 11 0 10 -1
4 9 -2 9 -3 8 -3 8 -2
2 3 6 3 5 3 4 3 3 2 3
1 -9 -7 -10 -7
Správné řešení je:
[[1, 5, 5, 5, 3, 3, 3, 3], [1, 5, 5, 8, 8, 3, 3, 7], [5, 5, 8, 8, 8, 4, 4, 7], [2, 5, 5, 8, 8, 4, 4, 7], [2, 2, 2, 2, 8, 6, 6, 6]]
Vysvětlení: vstupní kameny vypadají takto:
|kamen s barvou 6 | kamen s barvou 5 | kamen s barvou 7 |
|{{:courses:b3b33alp:cviceni:e-27166-stone0.png?200|}} | {{:courses:b3b33alp:cviceni:e-27166-stone1.png?200|}} | {{:courses:b3b33alp:cviceni:e-27166-stone2.png?200|}} |
|kamen s barvou 8 | kamen s barvou 3 | kamen s barvou 4 |
|{{:courses:b3b33alp:cviceni:e-27166-stone3.png?200|}} | {{:courses:b3b33alp:cviceni:e-27166-stone4.png?200|}} | {{:courses:b3b33alp:cviceni:e-27166-stone5.png?200|}} |
|kamen s barvou 2 | kamen s barvou 1 | |
|{{:courses:b3b33alp:cviceni:e-27166-stone6.png?200|}} | {{:courses:b3b33alp:cviceni:e-27166-stone7.png?200|}} | |
Tyto kameny lze poskládat takto:
{{:courses:b3b33alp:cviceni:e-27166.png?400|}}
==== Těžká varianta ====
* Úkolem je napsat program ''fill_hard.py'' (úloha HW08), který je rozšířením lehké varianty (viz předchozí sekce)
* Vstup programu:
* jméno souboru jako první argument příkazové řádky (''sys.argv[1]'')
* formát souboru je stejný jako pro lehkou úlohu
* Výstup programu:
* Matice o rozměrech MxN, kde její prvky obsahují čísla kamenů, které jsou na odpovídající pozici uloženy
* matice je vypsána v tzv. pythonovském formátu, použijte standardní funkci print()
* Nebo řetěžec ''NOSOLUTION'', pokud vstupní kameny nelze poskládat tak, aby zcela matici vyplnily
* Úkolem je opět vyplnit vstupní matici a zcela ji pokrýt všemi vstupními kameny
* **Oproti lehké variantě je možno rotovat kameny**
* rotace buňky ''[row,col]'' okolo středu souřadnicového systému o 90 stupňů doleva je ''[-col, row]''
* Je zakázáno kameny zrcadlit.
* Pokud existuje více řešení, vypište libovolné z nich
* Váš program bude testován na čtvercových maticích, obdélníkových a na příkladech, kde neexistuje řešení. V každé skupině bude provedeno 15-20 testů. Timeout na výpočet programů v každé skupině je 100s (tj. cca 5s na vyřešení jednoho příkladu).
=== Příklad 1 ===
Vstupní soubor
5
5
1 13 0 13 1 13 -1 13 2
2 3 -2 3 -1 2 -2 2 -3 3 -3 2 -4 4 -1 2 -1 2 0 3 0 4 0 4 -2 4 -3 5 0
3 -3 10 -2 11 -1 10 -3 11 -2 10 -1 11 0 10
Vstupní kameny jsou:
| Kamen barva 2 | Kamen barva 1 | Kamen barva 3 |
|{{:courses:b3b33alp:cviceni:h-92967-stone0.png?200|}}|{{:courses:b3b33alp:cviceni:h-92967-stone1.png?200|}}|{{:courses:b3b33alp:cviceni:h-92967-stone2.png?200|}}|
Jedno z možných řešení:
[[2, 2, 2, 2, 2], [1, 2, 2, 2, 2], [1, 2, 2, 2, 2], [1, 3, 3, 3, 2], [1, 3, 3, 3, 3]]
Možná řešení:
{{:courses:b3b33alp:cviceni:h-92967-s0.png?200|}} {{:courses:b3b33alp:cviceni:h-92967-s2.png?200|}}
{{:courses:b3b33alp:cviceni:h-92967-s4.png?200|}} {{:courses:b3b33alp:cviceni:h-92967-s6.png?200|}}
=== Příklad 2 ===
Vstupní soubor
3
10
4 9 -5 9 -4 10 -5 9 -3 10 -3 10 -4 8 -5
5 -9 -4 -9 -5 -8 -5 -8 -4 -9 -6 -7 -4 -7 -5
1 10 7 10 6 11 7 11 6 12 7 12 6 9 7
3 4 -5 4 -4 4 -3
2 -9 -1 -9 0 -9 1 -10 1 -11 1 -12 1
Správné řešení:
NOSOLUTION