====== Cvičení 5: 2D pole ======

===== náplň cvičení =====





==== Úkol 1-2 Opakování ====
  * Nedokončený příklad z minulého cvičení


==== Dvourozměrné pole ====
  * Načtení matice - dvourozměrného pole - ze souboru kombinuje načítání vektoru z minulého cvičení
<code python>
pole=[]
f=open('pole.txt','r')
for line in f:
    pole.append(list(map(int, line.split())))
</code>

==== Matice ====
  * 2D pole se hodí např. pro reprezentaci matic

==== Úkol 3 Výpis matice ====
  * Napište funkci ''printMatrix'', která vypíše matici zadanou 2D polem
  * Prvky budou odděleny mezerou a každý řádek bude vypsán na nový řádek
  * Kromě prvků matice nebude vypsán žádný jiný znak

==== Úkol 4 Násobení vektoru a  matice ====
  * Napište funkci ''multiVecMat(v,m)'', která vypočte součin vektoru $v$ a matice $m$. 
  * Pokud nesouhlasí rozměry matice a vektoru, pak funkce vrací ''None''.
  * Vypočtete výsledek násobení $v \cdot m$:
<code python>
m=[[0,0,1],[0,1,0],[1,0,0]]
v=[2, 4, 6]
</code>




===== Domácí příprava =====

Implementujte následující úlohy:

   * Funkce, která v matici najde všechny záporné hodnoty, vraťte seznam jejich indexů
   * Funkce pro násobení dvou matic
   * Funkce pro výpočet determinantu matice
   * Funkce pro výpočet [[ https://en.wikipedia.org/wiki/Trace_(linear_algebra) | stopy ]] matice 
===== Domácí úkol =====

==== Lehká varianta ====

   * Napište program, který hledá nejlepší překryv dvou matic.
   * **Vstup:**
     * Jména dvou soborů zadaná na příkazové řádce.
     * Každý soubor obsahuje 2D matici **reálných** čísel. Matice je uložena po řádcích, čísla jsou oddělena mezerou
     * První soubor obsahuje 'velkou' matici $I$ o rozměru $M \times N$, druhý soubor obsahuje 'malou' matici $W$ o rozměnu $a \times b$, $a<M,b<N$. Malá matice má vždy lichý počet řádků a lichý počet sloupců.
   * **Výstup:**
     * Index řádku $r$ a sloupce $s$ matice $I$, kde je rozdíl matic nejmenší. Indexy začínají nulou ($0 < r < M-1$ a $0 < s < N-1$).
     * Indexy jsou vypsány na standardní výstup a jsou odděleny mezerou.
   * Výpočet rozdílu matic:
     * Nechť $I(i,j)$ je prvek matice $I$ na řádku $i$ a sloupci $j$ (obdobně, W(i,j) je prvek v matici $W$).
     * Podobnost matice $I$ a matice $W$ na souřadnici $i,j$ je: $D(i,j) = \sum_{r=-a/2}^{a/2} \sum_{s=-b/2}^{b/2} |I(i+r,j+s)-W(r+a/2,s+b/2)|$, kde '/' značí celočíselné dělení.
     * Výstupem programu je taková souřadnice $(i,j)$, kde $D(i,j)$ nabývá minima.
     * Při výpočtu podobnosti uvažujte pouze takové souřadnice, ve kterých se matice $W$ celá vejde do matice $I$.
   * Soubor odevzdejte do BRUTE, úloha HW05, soubor **bestmatch.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 výpočtu podobnosti matic:
{{:courses:b3b33alp:cviceni:matrix.eps.png?400|}}

   * Podobnost na pozici $D(1,1)= |2-1| + |4-2| + |2-3| + |6-4| + |0-5| + |1-6| + |2-7|+|8-8| + |2-9| = 28$ {{:courses:b3b33alp:cviceni:matrix2.eps.png?200|}}
   * Podobnost na pozici $D(2,3)=|1-1|+|9-2|+|0-3|+|2-4|+|1-5|+|0-6|+|4-7| + |2-8| + |1-9| = 39$ 
{{:courses:b3b33alp:cviceni:matrix3.eps.png?200|}}


Příklady:

<code>
python3 bestMatch.py velka.txt mala.txt
</code>

Testovat můžete na jednoduchých příkladech, kde se matice $W$ celá nachází v matici $A$ (a minimální hodnota metriky je 0), například

'<fc #ff0000>velka.txt</fc>'
<code>
1 2 1 2 3 8
1 2 1 2 3 8
1 2 4 5 6 8
1 2 7 8 9 8
</code>
'<fc #ff0000>mala.txt</fc>'
<code>
1 2 3
4 5 6
7 8 9
</code>

Výsledek je souřadnice číslice ''5'', tj. <code>
2 3
</code>

Pokud soubory '<fc #ff0000>velka.txt</fc>' a '<fc #ff0000>mala.txt</fc>' obsahují:

'<fc #ff0000>velka.txt</fc>'
<code>
0.658824 0.603922 0.639216 0.462745 0.376471 0.380392 0.345098
0.607843 0.545098 0.572549 0.521569 0.376471 0.345098 0.333333
0.576471 0.47451 0.501961 0.490196 0.384314 0.286275 0.333333
0.52549 0.529412 0.443137 0.384314 0.423529 0.247059 0.286275
</code>

'<fc #ff0000>mala.txt</fc>'
<code>
0.576471 0.47451 0.501961
0.52549 0.529412 0.443137
0.52549 0.541176 0.419608
</code>

Výsledek:
<code>
2 1
</code>


----
'<fc #ff0000>velka.txt</fc>'
<code>
0.709804 0.698039 0.666667 0.670588 0.627451 0.635294 0.686275 0.639216 0.596078 0.737255 0.772549 0.745098 0.623529 0.52549 0.541176 0.419608
0.756863 0.74902 0.737255 0.745098 0.745098 0.658824 0.639216 0.701961 0.733333 0.682353 0.67451 0.635294 0.698039 0.607843 0.427451 0.392157
0.733333 0.694118 0.717647 0.729412 0.729412 0.764706 0.756863 0.705882 0.705882 0.721569 0.701961 0.678431 0.647059 0.603922 0.462745 0.4
0.705882 0.701961 0.690196 0.611765 0.6 0.596078 0.588235 0.615686 0.584314 0.6 0.537255 0.576471 0.588235 0.619608 0.588235 0.482353
0.705882 0.54902 0.494118 0.462745 0.45098 0.443137 0.454902 0.505882 0.513726 0.47451 0.415686 0.443137 0.427451 0.482353 0.509804 0.458824
0.509804 0.403922 0.45098 0.517647 0.533333 0.533333 0.486275 0.47451 0.556863 0.623529 0.521569 0.447059 0.384314 0.329412 0.333333 0.337255
</code>

'<fc #ff0000>mala.txt</fc>'
<code>
0.509804 0.403922 0.45098
0.411765 0.470588 0.458824
0.419608 0.407843 0.447059
</code>

Výsledek je:
<code>
4 11
</code>

Praktická motivace: hledáním nejlepšího překryvu matice lze (velmi zjednodušeně) hledat např. obrázek v obrázku. Data pro domácí úlohu jsou generována z tohoto obrázku: 

{{:courses:b3b33alp:cviceni:dogsmall.png?200|}}

==== Těžká varianta ====

  * Napište program **chess.py**, který načte soubor zadaný na příkazové řádce (''argv[1]''). Tento soubor kóduje stav šachovnice po tahu bílého. Program zkontroluje, zda bílý dává černému mat, šach, nebo garde. 
  * **Vstup**
    * Stav šachovnice je zaznamenán čísly reprezentující jednotlivé figury podle následující tabulky (bíle figury mají kladnou hodnotu, černé zápornou):

^ figura  ^ bílý ^ černý ^
| král | 1  | -1 |
| dáma | 2  | -2 |
| věž | 3  | -3 |
| střelec | 4  | -4 |
| jezdec | 5  | -5 |
| pěšec | 6  | -6 |
| volné pole | 0  | 0 |

  * **Výstup (standardní výstup)**
    *  Výstupem Vašeho programu je hláška:
      * MAT - pokud černý dostal mat
      * SACH - pokud černý dostal šach a nenastala výše popsaná situace
      * GARDE - pokud je ohrožena černého dáma a nenastala žádná z výše popsaných situací
      * NO - pokud nenastala žádná výše popsaná situace. 
  * Soubor (viz. příklad {{courses:b3b33alp:cviceni:sachovnice.txt|sachovnice.txt}}) obsahuje dvourozměrné pole, ve kterém jsou výše definované hodnoty 
  * Program v souboru **chess.py** odevzdejte pomocí odevzdávacího systému (úloha HW05).
  * Pokud Váš program nebude umět detekovat mat, pak získáte pouze 1 bod.

----

Vstup obsah souboru, zdaného jako vstupní argument: 
<code>
-3  0 -4 -2  0 -1 -5 -3
-6 -6 -6  0  0  0 -6 -6
 0  0 -5  4  0  0  0  0
 0  0  0 -6  0  0  0  2
 0  0  0  6  0  0  0  0
 0  0  5  0  0  0  0  0
 6  6  6  0  0  0  6  6
 3  0  0  0  0  3  1  0
</code>

Výstup:
<code>
MAT
</code>