Cvičení 8: Fronta, zásobník

• 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.

Uvažujme 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']]

• 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**

• 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?

• Ú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. 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 5×5 .. 7×7 s 5..10 kameny, dále na obdélníkových maticích (např. 5×9, 10×3 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)

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
kamen s barvou 3	kamen s barvou 4	kamen s barvou 1

Tyto kameny lze poskládat takto:

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
kamen s barvou 5	kamen s barvou 1	kamen s barvou 2

Tyto kameny nelze posládat do matice 5×5.

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
kamen s barvou 8	kamen s barvou 3	kamen s barvou 4
kamen s barvou 2	kamen s barvou 1

Tyto kameny lze poskládat takto:

• Ú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).

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

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í:

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