====== 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?
<code python>
# 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
</code>

Nyní spusťte následující kód a opět si na konci vypište jednotlivá pole. 
<code python>
# 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)

a[1][2] = -1
c[2][1] = -3
</code>

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. <code python>
import copy

d = copy.deepcopy(b)
</code>

==== Ú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:
<code python>
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]
   ]
</code>

  * Vygenerování prázdného pole
<code python>[[0]*len(a[0]) for i in a]</code>
  * Využití funkce modulo (%) Vám pomůže implementovat uzavřený svět
  * Pro lepší zobrazení udělejte po každém kroku pausu 
<code python>import time
time.sleep(0.5)</code>
  * Také můžete vylepšit zobrazení tak, že místo 1 budete tisknout X a místo 0 mezeru 
<code python>''.join('X' if i!=0 else ' ' for i in x))</code>


==== Ú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:
<code python>
m=[[12,-7,3, 26],
   [4 ,5,-6, -5],
   [-7 ,8,9, 21]]
</code>
  * Zkuste program spustit znova s použítím modulu fraction (from fractions import Fraction) a přemapováním matice na typ Fraction 
<code python>
mm = [list(map(Fraction, v)) for v in m]
</code>
  * a po výpočtu výsledek transformovat opět na reálná čísla
<code python>
result = [list(map(float, v)) for v in mm]
</code>



===== domácí práce =====

==== Lehká varianta ====
  * Napište a odevzdejte program **tic_tac_toe.py**, který načte hrací pole piškvorek určí vítězného hráče
  * **Vstup**
    * Přes příkazovou řádku bude programu předána cesta k souboru s hracím polem (použijte ''sys.argv[1]'')
    * Soubor obsahuje znaky ''.'', ''x'' a ''o'' které značí postupně prázdné pole, křížek (malé písmeno x) a kolečko (malé písmeno o).
    * Znaky na řádce jsou oddělené mezerou, jiné znaky se v souborech nevyskytují. Pole ale nemusí nutně být čtvercové
    * Příklad vstupního souboru <code>
. o . x x .
. o o o . .
o o . o . .
x o x x o .
. . o x . x
. . . . x .
</code>
  * **Výstup**
    * ''x'' pokud hráč s křížky má 5 znaků v řadě
    * ''o'' pokud hráč s kolečky má 5 znaků v řadě
    * ''None'' pokud žádný z hráčů nemá 5 svých znaků v řadě  (jako u příkladu výše)
  * 

=== Příklady ===
Vstup:
<code>
. . . x x . . .
x . . x . o . .
. . x o o x . o
. o o o o o x .
. o o . . x x .
</code>
Výstup: ''o''

Vstup:
<code>
. . o o x . . .
. . x x x . x .
. . . o x x . .
x x o . x o . .
. o o x o . . .
. . x o . . . .
</code>
Výstup: ''x''

Vstup:
<code>
. o x x . . . .
o o x x . . . .
. o x o x . . .
. . x . . x . .
. . . x x x . .
</code>
Výstup: ''None''

==== 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čet 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.
  * <fc #ff0000>Timeout na výpočet je: 50 sekund.</fc>

=== 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


Testovací matice {{courses:b3b33alp:matice.tgz|matice.tgz}}