====== Cvičení 8: Fronta, zásobník ====== ===== opakování ===== ==== Ú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. ===== náplň cvičení ===== ==== Úloha 2 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 3 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? ==== Úloha 4 Fronta ==== * Přeměňte řešení úlohy 3 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. ===== Domácí úkol ===== ==== Lehká varianta ==== * Úkolem je nalézt v mapě světlé a tmavé cesty, které vedou zleva doprava a shora dolů. * Program odevzdávejte do HW08 jako **paths.py** * Příklad mapy: {{:courses:b3b33alp:cviceni:hw08-12214.png?300|}} * **Vstup programu:** jméno souboru jako první argument příkazové řádky. * Soubor obsahuje 2D matici zapsanou po řádcích, prvky v každém řádku jsou odděleny mezerou (počet řádků se nemusí rovnat počtu sloupců). * Prvky matice jsou řetězce o čtyřech znacích, které reprezentují jednotlivé dílky mapy. * Dílky jsou reprezentovány řetezcem složeným z písmen 'l' (light) a 'd' (dark) podle toho, kde se nachází světlé (tmavé) cesty. Dílek bez cest (prázdný) je označen 'none'. * Pořadí písmen je: west-north-east-south. Index písmene ve jménu dílku jsou: {{:courses:b3b33alp:cviceni:2022trx-nums.png?100|}} * např. výše uvedený dílek má jméno "ldld": light na pozici 0 (west), dark na pozici 1 (north), light na pozici 2 (east) a dark na pozici 3 (south). * Bludiště je tvořeno těmito dílky: | {{:courses:b3b33alp:cviceni:2022trx-tileAa.png?100|}} | {{:courses:b3b33alp:cviceni:2022trx-tileAb.png?100|}} | {{:courses:b3b33alp:cviceni:2022trx-tileBa.png?100|}} | {{:courses:b3b33alp:cviceni:2022trx-tileBb.png?100|}} | {{:courses:b3b33alp:cviceni:2022trx-tileBc.png?100|}} | {{:courses:b3b33alp:cviceni:2022trx-tileBd.png?100|}} | {{:courses:b3b33alp:cviceni:2022trx-empty.png?100|}} | | **ldld** | **dldl** | **ddll** | **lddl** | **lldd** | **dlld** | **none** | * Příklad vstupního souboru: lddl dldl dldl ddll lldd dldl dldl dlld ddll lldd dlld lddl dldl ddll lddl dlld * Tomuto souboru odpovidá {{:courses:b3b33alp:cviceni:hw08-12214.png?300|}} * **Výstupem programu** je čtveřice celých čísel oddělených mezerou na standardní výstup: * **První číslo:** počet dílků, které tvoří nejdelší __světlou__ cestu, která vede __zleva doprava__ * **Druhé číslo:** počet dílků, které tvoří nejdelší __tmavou__ cestu, která vede __zleva doprava__ * **Třetí číslo:** počet dílků, které tvoří nejdelší __světlou__ cestu, která vede __shora dolů__ * **Čtvrté číslo:** počet dílků, které tvoří nejdelší __tmavou__ cestu, která vede __shora dolů__ * Pokud taková cesta neexistuje, vypište '-1'. * Cesta je posloupnost dílků tak, že uvažovaná barva na sebe plynule navazuje. * Cesta pro danou barvu začíná (končí) v levé (pravé straně) pokud dílek touto barvou do uvedené strany směruje. Obdobně pro cesty shora dolů. Viz obrázek: {{:courses:b3b33alp:cviceni:2022trx-cestye1.png?200|}} V tomto případě: existuje tmavá cesta zleva doprava (mezi body a-b), světlá cesta zleva doprava (a'-b'). Tmavá cesta mezi body c-d zleva doprava nevede, nebo v bodě c neprotíná levou stranu desky. Pro načtení vstupního souboru můžete použít tuto funkci, která vrací 2D pole, každá buňka pak obsahuje jméno dílku (indexujeme [radek][sloupec]). def loadBoard(filename): b = [] f = open(filename,"r") for line in f: b.append( line.strip().split() ) f.close() return b * Brute bude testovat na různých mapách, nejmenší mapa 4x4, největší 25x25. * Časový limit: 2s na 100 příkladů. === Příklady === * {{ :courses:b3b33alp:cviceni:hw08examples.zip | Balíček s testovacími daty (lehká i tězká varianta) }} * Příklad 1 Vstup: ddll lddl dldl ddll lldd dlld lddl dlld lldd dldl dldl ddll lddl dlld ldld ldld lldd dlld lldd dlld lddl ddll lddl ddll ldld ldld lddl dldl dldl dlld lldd ddll lddl dlld lldd dlld lddl ddll lldd dlld lddl ddll lddl dldl dlld ldld ldld lldd dlld Výstup: -1 21 24 -1 {{:courses:b3b33alp:cviceni:2022trx-case-13527.png?400|}} Komentář: žádná světlá cesta nevedle zleva doprava (-1), tmavá cesta zleva doprava vede přes 21 dílků (z pozice 4,0 do pozice 2,6), délka světlé cesty shora dolů je 24 dílků, a žádná tmavá cesta nevede shora dolů (-1). * Příklad 2 Vstup: lddl none lldd dlld lddl none lddl dlld lldd dlld lddl ddll lddl dlld lldd Výstup: 6 6 -1 -1 {{:courses:b3b33alp:cviceni:2022trx-case-15307.png?200|}} ==== Těžká varianta ==== * Uvažujme stejná vstupní data jako v lehké variantě. * Úkolem je napsat program, který v mapě hledá světlé a tmavé cykly. * Program odevzdávejte do Bruta jako **cycles.py** * **Vstup programu:** jméno souboru jako první argument příkazové řádky * Interpretace vstupních dat je stejná jako v lehké variantě HW08. * **Výstup programu:** čtveřice celých čísel oddělených mezerou s významem: * **První číslo:** počet světlých cyklů (nebo 0 pokud žádný takový neexistuje) * **Druhé číslo:** počet tmavých cyklů (nebo 0 pokud žádný takový neexistuje) * **Třetí číslo:** délka nejdelšího světlého cyklu (nebo 0 pokud žádný takový neexistuje) * **Čtvrté číslo:** délka nejdelšího tmavého cyklu (nebo 0 pokud žádný takový neexistuje) * Cyklem se rozumí uzavřená cesta pro vybranou barvu, tato cesta musí celá ležet uvnitř mapy. * Délka cesty je počet buňek, které tuto cestu tvoří. * Brute bude testovat na různých mapách, nejmenší mapa 4x4, největší 25x25. * Časový limit: 2s na 100 příkladů. === Příklady === * {{ :courses:b3b33alp:cviceni:hw08examples.zip | Balíček s testovacími daty (lehká i tězká varianta) }} * Příklad 1 Vstup: dlld lldd dlld ldld ddll lddl ddll lddl lldd dldl dlld lldd lddl none ldld lddl Výstup: 1 1 4 4 {{:courses:b3b33alp:cviceni:2022trx-hard-10584.png?400|}} Komentář: mapa obsahuje jeden světlý cyklus a jeden tmavý cyklus, jejich délka je v obou případech 4 dílky. * Příklad 2 Vstup: ddll lddl ddll lddl dlld lldd dlld lldd ddll lddl ddll none dlld none dldl ddll Výstup: 2 1 4 4 {{:courses:b3b33alp:cviceni:2022trx-hard-10823.png?400|}} Komentář: mapa obsahuje dva světlé cykly (délka nejdelšího je 4) a jeden tmavý cyklus délky 4. * Příklad 3 Vstup: lldd ddll ldld lddl ddll ldld ldld lddl dldl ddll lldd dlld lddl ddll dldl dldl dldl ddll lddl dldl dldl dldl dlld lldd dlld lldd dlld lldd lldd ddll lddl ddll lddl ddll ldld lddl dlld lldd dlld lldd dlld ldld lldd ddll ldld lddl ddll ldld ldld Výstup: 4 2 10 4 {{:courses:b3b33alp:cviceni:2022trx-hard-14943.png?400|}} Komentář: mapa obsahuje 4 světlé a 2 tmavé cykly. Délka nejdelšího světlého cyklu je 10, délka nejdelšího tmavého cyklu je 4. * Příklad 4 Vstup: ddll lldd dlld lddl lldd ddll lddl dlld lddl dlld lldd ddll dlld lddl ddll lldd Výstup: 1 1 4 12 {{:courses:b3b33alp:cviceni:2022trx-hard-16914.png?400|}} * Příklad 5 Vstup: lldd ddll lddl dldl dlld lldd dldl ldld lldd dldl dldl ddll lddl dlld lddl ddll lldd dlld lldd dlld ldld dldl dlld ldld lddl ddll ldld lddl dldl ddll lddl dldl dlld lddl dldl dldl dlld lldd dlld lddl dlld lldd dlld lddl ddll ldld lldd ddll lddl Výstup: 2 0 8 0 {{:courses:b3b33alp:cviceni:2022trx-hard-11754.png?400|}} Komentář: mapa obsahuje pouze 2 světlé cykly (délka nejdelšího je 8 políček). Mapa neobsahuje žádný tmavý cyklus.