====== 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ů).