====== Cvičení 6: Pole, matice ====== ==== Inicializace a kopírování 2D polí ==== * Projdeme si inicializaci a kopírování 1D a více-D polí. Spusťte následující kód a na konci si vytiskněte jednotlivá pole. Co pozorujeme? # Inicializace pole a = [0] * 5 # Jak správně zkopírovat pole? b = a c = a[:] d = list(a) a[3] = 3 b[0] = -5 c[4] = 4 * Spusťte následující kód a opět si na konci vypište jednotlivá pole. # Inicializace 2D pole přímo a = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] # Inicializace po řádcích f = [] for i in range(3): f.append([i] * 3) # Inicializace po řádcích ve zkráceném zápisu g = [[i] * 3 for i in range(3)] # Jak správně zkopírovat pole? b = a c = a[:] d = list(b) e = [ r[:] for r in a ] f = [ list(a[i]) for i in range(len(a))] a[0][0] = -1 b[0][1] = -2 c[0],c[1]=c[1],c[0] d[1][0] = -3 e[1][1] = -4 * Pokud chceme opravdovou kopii vícedimenzionálního pole, tvz. //deep copy//, můžeme použít modul ''copy'' a funkci ''deepcopy''. Doplňte import a kopírování do předchozí ukázky a porovnejte výsledky. import copy d = copy.deepcopy(b) ==== Life ==== * Hru [[https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life|Life]] navrhl v roce 1970 matematik John Horton Conway. * [[ https://www.youtube.com/watch?v=jvSp6VHt_Pc | Historie ]], [[https://www.youtube.com/watch?v=FWSR_7kZuYg | Coding challenge ]] * Pravidla hry jsou jednoduchá: * pokud jsou v okolí jedné buňky živé právě 3 buňky, pak v této buňce život vznikne (nebo zůstane) * pokud je buňka živá a v jejím okolí jsou právě 2 živé buňky, pak tato buňka bude žít i nadále * v ostatních případech buňka zahyne buď na osamění, nebo přemnoženost * Uvažujte osmiokolí: 8 sousedních buněk. * Uvažujte uzavřený svět, tedy sousední políčko pro první pole řádku je poslední pole řádku, sousední pole pro první řádek je poslední řádek * Napište program, který bude simulovat 40 kroků hry life pro toto počáteční pole: a = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 1, 1, 1, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 1, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 1, 1, 0, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0] ] * Vygenerování prázdného pole [[0]*len(a[0]) for i in a] * Pro lepší zobrazení udělejte po každém kroku pauzu import time time.sleep(0.5) * Také můžete vylepšit zobrazení tak, že místo 1 budete tisknout X a místo 0 mezeru ''.join('X' if i!=0 else ' ' for i in x) ==== Prohození řádků matice ==== * Napište program, který načte matici a následně permutaci, která definuje prohození řádků matice. Na výstup program vytiskne matici s řádky prohozenými podle zadané permutace. ==== Gaussova eliminační metoda ==== * Gaussova eliminační metoda je metodou řešení soustavy lineárních algebraických rovnic. GEM lze využít pro výpočet inverzní matice nebo determinantu matice. === Krok 1: Nalezení největšího prvku ve sloupci === * Napište funkci ''maximum(M, i)'', která pro zadanou matici **M** a index (číslo) **i** najde takový index řádku **j** v rozsahu ''range(i, len(M))'' jehož absolutní hodnota **M[j][i]** je maximální. Využijte vestavěnou funkci ''abs''. === Krok 2: Prohození řádku === * Napište funkci ''swap_rows(M, i)'', která prohodí řádek **i** a řádek s indexem ''j = maximum(M, i)'', pokud ''i != j''. === Krok 3: Úprava řádku === * Napište funkci ''do_line(M, i)'', která zavolá funkci ''swap_rows(M, i)'' a pokud: * ''M[i][i] != 0'': * celý řádek **i** matice **M** vydělí hodnotou **M[i][i]** * od všech řádků **r** v rozsahu ''range(i + 1, len(M))'' odečte **M[r][i]**-násobek řádku **i** * vrátí hodnotu ''True'' * jinak vrátí ''False'' === Krok 4: Gausova eliminace === * Napište funkci ''GEM(M)'', která pro všechna **i** z rozsahu ''range(len(m))'' zavolá funkci **do_line(M, i)** * Pokud je návratová hodnota funkce ''do_line()'' alespoň 1x False, metoda ''Gauss_elim()'' vrací ''False''. V opačném případě vrací ''True''. === Příklad === * Spusťte funkci ''GEM()'' pro matici: m=[[12,-7,3, 26], [4 ,5,-6, -5], [-7 ,8,9, 21]] ==== Použití modulu fraction ==== Využijte ve výpočtu úkolu 3 zlomků namísto reálných čísel. K tomu využijte Python modul **fraction** (''from fractions import Fraction'') pomocí kterého přemapujte prvky matice **M** na typ Fraction (zlomek): M_fr = [list(map(Fraction, v)) for v in M] GEM(M_fr) Výsledek GEM lze transformovat zpět na reálná čísla pomocí: result = [list(map(float, v)) for v in M_fr] ===== Domácí úkol ===== ==== Lehká varianta ==== * Napište a odevzdejte program **find_pic.py**, který: - načte vzor (matice //3x3//) ze standardního vstupu, - načte obraz (matice //NxM//) ze souboru a - najde, kde se vzor vyskytuje uvnitř obrazu. * **Vstup** * Přes příkazovou řádku bude programu předána cesta k souboru s obrazem (použijte ''sys.argv[1]'') * Soubor je matice celých kladných čísel. * Předpokládejte, že matice je zadána korektně a že každá řádka obsahuje stejný počet celých čísel. * Druhým vstupem je vzor zadaný ze standardního vstupu. * Vzor, který bude program hledat, se skládá ze tří řádek čísel. Každá řádka obsahuje tři čísla 0 nebo 1. Příklad vzoru: 1 0 1 0 1 0 1 0 1 * **Úkol** * Vzor se v obraze vyskytuje právě jednou. Nalezněte, na které pozici se vzor v obraze vyskytuje. * Vzor obsahuje pouze čísla 0 a 1: * Číslo **0** znamená, že na tomto místě se v matici může vyskytovat **libovolné číslo**. * Číslo **1** znamená, že na této pozici se vyskytuje **stejné číslo, jako na ostatních pozicích čísla 1 ve vzoru**. * Vzor se celý musí nacházet uvnitř matice, např., nelze nalézt část vzoru na pravé straně a část vzoru na levé straně obrazu. * **Výstup** * Dvě celá čísla oddělená mezerou ''c r'', kde ''c'' je číslo sloupce a ''r'' je číslo řádku **levého horního rohu vzoru v matici**. * Pozn.: Indexy řádků i sloupců začínají od 0, první řádek v souboru je řádek číslo 0. === Příklady === **Vstup:** Vzor ze standardního vstupu: 1 0 1 0 1 0 1 0 1 Obsah souboru: 1 2 1 2 3 1 1 2 3 1 1 2 3 2 1 1 1 1 1 1 **Výstup:** ''1 0'' V zadané matici lze nalézt vzor (tvar připomínající X složený z čísel 2) od řádky 0 do řádky 2 a od sloupce 1 do sloupce 3. Vzor v matici na místech 1 má 2, na místech 0 může být libovolná hodnota pro celý vzor navzájem rozdílná (v tomto případě 1 a 3). **Vstup:** Vzor ze standardního vstupu: 1 1 1 1 0 1 1 1 1 Obsah souboru: 1 4 1 2 3 3 3 1 1 4 4 4 4 3 1 2 3 4 4 4 4 1 5 1 4 4 4 1 4 4 4 3 4 4 1 1 5 3 5 1 1 1 4 4 4 4 4 4 4 **Výstup:** ''3 1'' V zadané matici lze nalézt vzor od řádky 1 do řádky 3 a od sloupce 3 do sloupce 5. Vzor v matici na místech 1 má 4, na místech 0 může být libovolná hodnota, zde je také 4. **Vstup:** Vzor ze standardního vstupu: 1 0 1 0 0 0 1 0 1 Obsah souboru: 1 4 1 2 3 3 3 1 1 4 4 4 4 3 1 2 3 4 4 4 4 1 5 1 5 4 4 1 4 4 4 3 4 4 1 1 5 3 5 1 1 1 4 4 3 4 4 4 4 **Výstup:** ''1 3'' V zadané matici lze nalézt vzor od řádky 3 do řádky 5 a od sloupce 1 do sloupce 3. Vzor v matici na místech 1 má 5, na místech 0 může být libovolná hodnota, zde hodnota 1, 3, a 4. ==== Těžká varianta ==== * Napište program **rectangle.py**, který v matici celých čísel zadané na příkazové řádce (''sys.argv[1]'') najde největší souvislou podmatici libovolného rozměru, která obsahuje pouze záporné hodnoty. Příklad volání: python3 rectangle.py matice.txt * Výstupem programu jsou souřadnice levého horního rohu a pravého dolního rohu podmatice. Na prvním řádku výstupu je levý horní roh ve formátu řádek sloupec, na druhém řádku pravý dolní roh. Řádky i sloupce se číslují od 0. * Velikost podmatice je určena jejím počtem prvků. * Snažte se, aby Váš program byl co nejefektivnější, ideálně, aby jeho časová složitost odpovídala velikosti matice. Bodové ohodnocení této úlohy bude záviset na efektivnosti (rychlosti) Vašeho algoritmu. * Pokud existuje více řešení, vypište libovolné z nich. * Nastudujte si nejrychlejší způsob nalezení maximálního obdélníku pod histogramem [[https://www.geeksforgeeks.org/largest-rectangular-area-in-a-histogram-set-1/|Část 1]] a [[https://www.geeksforgeeks.org/largest-rectangle-under-histogram/ | Část 2]] * Timeout na výpočet je: 50 sekund. Toto platí i pro velké matice, které si můžete stáhnout níže. Na nich je dobře patrný rozdíl mezi lineárním algoritmem $O(n)$, algoritmem $O(n \cdot \log(n))$ a $O(n^2)$, kde n je počet prvků matice. === Příklad === Matice {{courses:b3b33alp:rectangle.txt|matice.txt}}: 1 -9 -2 8 6 1 8 -1 -11 -7 6 4 10 12 -1 -9 -12 14 8 10 -3 -5 17 8 6 4 10 -13 -16 19 Výstup: 1 2 3 3 Obrovské testovací matice {{courses:b3b33alp:matice.tgz|matice.tgz}} (i ty je nutné spočítat do 50s pro získání plného počtu bodů).