====== Cvičení 6, Pole, matice ======
==== Opakování ====
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
Nyní 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)
==== Úkol 1 Life ====
* Hru [[https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life|Life]] navrhl v roce 1970 matematik John Horton Conway.
* 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
* Budeme uvažovat 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]
* Využití funkce modulo (%) Vám pomůže implementovat uzavřený svět
* Pro lepší zobrazení udělejte po každém kroku pausu
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))
==== Úkol 2 Prohození řádků matice ====
* Napište program, který načte matici a následně permutaci, která definuje prohození řádků zadané matice. Na výstup program vytiskne matici s řádky prohozenými podle zadané permutace.
==== Úkol 3 Gaussova eliminační metoda ====
* Gaussova eliminační metoda je způsob řešení soustavy lineárních rovnic, případně hledání inverzní matice, nebo i počítání determinantu
=== Úkol 3a Nalezení největšího prvku ve sloupci ===
* Napište funkci **maximum(m,i)**, která pro zadanou matici **m** a číslo **i** najde číslo řádku v rozsahu **range(i,len(m))** takové, že prvek **m[max][i]** má největší absolutní hodnotu (funkce abs je v pythonu vestavěná standardně)
=== Úkol 3b Prohození řádku ===
* Napište funkci **set(m,i)**, která zavolá funkci **maximum(m,i)** a pokud je návratová hodnota rozdílná od **i**, prohodí řádek **i** a **maximum(m,i)**
=== Úkol 3c Úprava řádku ===
* Napište funkci **do_line(m,i)**, která zavolá funkci **set(m,i)** a pokud:
* **m[i][i]** se nerovná 0 pak:
* celý řádek **i** matice **m** vydělí hodnotou **m[i][i]**
* pro všechny ostatní řádky **r** matice **m** odečte od řádku **r** hodnotu **m[r][i]** násobek řádku **i**
* vrátí hodnotu True
* jinak vrátí False
=== Úkol 3d Gausova eliminace ===
* Napište funkci **Gauss_elim(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** rovna False, pak přeruší cyklus a vrací False
* Pokud byly všechny návratové hodnoty True, pak vrátí funkce True
=== Příklad ===
* Spusťte funkci Gauss_elim pro matici:
m=[[12,-7,3, 26],
[4 ,5,-6, -5],
[-7 ,8,9, 21]]
* Zkuste program spustit znova s použítím modulu fraction (from fractions import Fraction) a přemapováním matice na typ Fraction
mm = [list(map(Fraction, v)) for v in m]
* a po výpočtu výsledek transformovat opět na reálná čísla
result = [list(map(float, v)) for v in mm]
===== Domácí úkol =====
==== Lehká varianta ====
* Napište program, který řeší trojsměrku (lehčí variantu osmisměrky). Slova ve trojsměrce jsou zapsána pouze zleva doprava, shora dolů a diagonálně zleva shora doprava dolů.
* **Vstup:**
* Jména dvou souborů zadaná na příkazové řádce.
* První soubor obsahuje 2D matici **písmen**
* Druhý soubor obsahuje slova, která jsou v trojsměrce obsažena.
* **Výstup:**
* Písmena, která zbudou po vynechání všech písmen vyskytujících se v zadaných slovech (pozor slova se mohou křížit, je důležité nalezené slovo z matice nemazat)
* Písmena tiskněte zleva doprava odshora dolů.
* Soubor odevzdejte do BRUTE, úloha HW06, soubor **wordsearch.py**
* Předpokládejte, že
* Program je volán se jmény existujících souborů
* Soubory jsou neprázdné a vždy obsahují správně zadané matice
* V případě, že existuje více řešení, vypište libovolné z nich
Příklad spuštění programu:
python3 wordsearch.py osmismerka.txt slova.txt
Testovat můžete na následujícím příkladu:
'osmismerka.txt'
lnobrblalo
medvaozmfo
ovtzasbest
nznekosilo
iaajnnaoly
kludkkkzvi
ooauulaaia
'slova.txt'
nevzalo
nekosilo
bassova
letenka
vzejdu
boson
robili
zely
meioza
brblalo
moniko
asbest
kosil
saka
zadu
Výsledek Vašeho programu bude:
odfoukali
==== 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).