====== Cvičení 5: 2D pole ======
==== Dvojrozměrné pole ====
* Ukázka "pole polí":
x = [[0, 1], ['a', True], [1, 1.0, 2, 4]]
>>> len(x)
3
>>> len(x[0])
2
>>> x[1][1]
True
>>> type(x)
>>> type(x[0])
* Vytvoření nulové matice o rozměrech 2x3:
x = []
for i in range(2):
x.append([0] * 3)
>>> print(x)
[[0, 0, 0], [0, 0, 0]]
==== 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
==== Stopa matice ====
* Napište funkci pro výpočet [[ https://en.wikipedia.org/wiki/Trace_(linear_algebra) | stopy ]] matice
==== Násobení vektoru a matice ====
* Napište funkci ''multiVecMat(v,m)'', která vypočte součin vektoru $v \in \mathbb{R}^{N}$ a matice $m \in \mathbb{R}^{N \times N}$.
* Pokud nesouhlasí rozměry matice a vektoru, pak funkce vrací ''None''.
* Vypočtete výsledek násobení $m \cdot v$:
m=[[0,0,1],[0,1,0],[1,0,0]]
v=[2, 4, 6]
==== Načtení 2D pole ze souboru ====
* Načtení matice uložené v souboru. Na každém řádku v souboru je uložen jeden řádek matice. Čísla jsou oddělena mezerou.
* Vstupní soubor (matice.txt)
1 2 3
4 0 5
7 -1 2
* Soubor matice.txt musí být "viditelný" pro váš skript (pokud ne, je třeba zadat absolutní cestu k souboru).
pole=[]
f=open('matice.txt','rt')
for line in f:
pole.append(list(map(int, line.split())))
f.close()
print(pole)
* Program vypíše
[[1,2,3],[4,0,5],[7,-1,2]]
==== Načtení zakódovaného obrázku ze souboru ====
* Stáhněte si soubor {{ :courses:b3b33alp:cviceni:encoded.txt |encoded.txt}}, jenž obsahuje zakódovaný obrázek. Každý řádek obsahuje různý počet dvojic **znak+číslo** (např. ''#2'') oddělených mezerou. Pro zobrazení obrázku se musí tyto dvojice prvně dekódovat.
* Pročtete si a porozumějte tomutou kódu a poté ho spusťte.
## | ------------------ Functions definition ------------------ |
# [You should understand this function]
# Function loading given file
def loadFile(filename):
mat = [] # create empty list
f = open(filename, 'rt') # open file with name 'filename' in 'read' and 'text' modes
for line in f: # iterate all lines in the file
# parse single line from file:
# 1) strip: remove spaces and new line characters from beginning and end of the line
# 2) split: split line by spaces, returns list
# 3) map: maps each element to string
# 4) list: convert output of map to list of strings
lst = list(map(str, line.strip().split(' ')))
mat.append(lst) # append list to our 'mat' variable
f.close()
return mat
# [You don't need to understand this function]
# Function decoding our file
def decode(mat):
mat_decoded = [] # create empty output list
for lst in mat: # for each list in 'mat' (list of lists)
decoded = '' # initialize the decoded string to empty value
for s in lst: # for each encoded value in list 'lst'
char = s.rstrip('0123456789') # cut the numbered part of our string out, example: #2 -> #
num = s[len(char):] # retrieve the cut part, example: 2
if char == 's': # space is encoded as 's'
char = ' ' # replace 's' by space character
decoded = decoded + int(num) * char # decode and store into 'decoded' variable
mat_decoded.append(decoded) # append single decoded line into our output list
return mat_decoded # return output list
## | -------------- Python starts processing here ------------- |
encoded = loadFile('encoded.txt') # load the encoded file
decoded = decode(encoded) # decode the encoded file
for line in decoded: # print our decoded file
print(line)
===== Témata k procvičení =====
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
===== Domácí úkol =====
==== Lehká varianta ====
* Napište program **dama_tah.py**, který načte matici celých čísel ze souboru, jehož jméno je zadáno jako první argument programu sys.argv[1] a zjistí, zda existuje bílý kamen, který může skočit přes nějaký černý kámen. Pokud takový kámen existuje, pak vypíše tah bílého v šachových souřadnicích.
* ** Vstup:**
* První argument programu obsahuje jméno souboru.
* Soubor obsahuje matici $ 8 \times 8 $ - celých čísel s tímto významem:
* 0 - volné pole
* 1 - bílý kámen
* 2 - bílá dáma
* 3 - černý kámen
* 4 - černá dáma
* Pole na šachovnici odpovídají tomu, že první řádek matice představuje řadu 8, druhý řádek reprezentuje řadu 7, ... , poslední řádek v souboru reprezentuje řádek 1. Sloupce jsou označeny písmeny a,...,g.
* ** Úkol:**
* Bílý je na tahu a program najde kamen, který může skočit.
* Na šachovnici je v této úloze vždy jen jeden kamen, který může skočit.
* V tomto programu lehké varianty uvažujte pouze pohyb bílého kamene, šachovnice nebudou obsahovat bílou dámu. Tah odpovídá pravidlům České dámy ([[https://cs.wikipedia.org/wiki/D%C3%A1ma_(deskov%C3%A1_hra)|Dáma (desková hra)]])
* Bílý kámen se pohybuje pouze "nahoru", tedy pouze směrem k vyšším číslům řad.
* Kameny se pohybují po úhlopříčkách na sousední volné pole.
* Kamen může skočit, pokud je sousední pole obsazené cizím kamenem nebo dámou a následující pole za obsazeným polem je volné, pak kamen může skočit na volné pole a cizí kamen je z šachovnice odstraněn.
{{courses:b3b33alp:cviceni:2023_sachovnice.png?150|}}
* Pokud kamen po skoku může ještě jednou skočit, pak lze tento skok také provést a opakovat skok, dokud je možné skákat.
{{courses:b3b33alp:cviceni:2023_sachovnice_vice_skok.png?150|}}
* **Výstup:**
* Program vytiskne na jeden řádek souřadnice kamenu, který skočil a všechna místa, kam skočil (míst je víc pro vícenásobný skok)
* Příklad pro výše uvedené šachovnice bude výstup programu:
* ''a1 c3''
* ''a1 c3 a5''
* Program v souboru **dama_tah.py** odevzdejte pomocí odevzdávacího systému (úloha HW05).
* Můžete předpokládat, že všechny matice jsou zadány korektně, tedy všechny řádky mají stejný počet prvků.
* Pokud se vstupní soubor jmenuje ''dama.txt'', Váš program můžete spustit příkazem ''python3 dama_tah.py dama.txt''.
* Soubor s šachovnicí můžete otevřít takto:
import sys
sachovnice = open(sys.argv[1], "rt")
=== Příklad ===
* Soubor dama.txt obsahuje:
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 0 0
0 3 0 0 0 0 0 0
1 0 0 0 0 0 0 0
Výstup:
a1 c3
Vysvětlení: Šachovnice obsahuje pouze dva kameny, jeden bílý, jeden černý. Bílý skočí černý kámen skokem z pole ''a1'' na pole ''c3''.
* Soubor dama.txt:
0 0 0 0 0 0 0 3
0 0 0 0 0 0 4 0
0 0 0 0 0 1 0 0
1 0 3 0 3 0 4 0
0 3 0 0 0 0 0 0
1 0 0 0 4 0 0 0
0 3 0 3 0 0 0 1
1 0 1 0 0 0 0 0
Výstup:
a1 c3
Vysvětlení: Šachovnice obsahuje pouze mnoho kamenů, ale kromě kamenu na poli ''a1''. Například kamen z pole ''a3'' nemá za černým kamenem na poli ''b4'' volné pole ''c5'', bílý kamen z pole ''h2'' nemá černý kámen na poli ''g3'', bílý kamen z pole ''f6'' by mohl skákat pouze zpět a to není v České dámě dovoleno.
* Soubor dama.txt:
0 0 0 0 0 0 0 3
0 0 0 0 0 0 4 0
0 3 0 0 0 1 0 0
0 0 3 0 3 0 4 0
0 3 0 0 0 0 0 0
1 0 0 0 4 0 0 0
0 3 0 3 0 0 0 1
1 0 1 0 0 0 0 0
Výstup:
a1 c3 a5 c7
Vysvětlení: Kamenu z pole ''a1'' skočí nejdříve na pole ''c3'', dále pokračuje skokem na poli ''a5'' a ještě může pokračovat skokem na pole ''c7''.
==== Těžká varianta ====
* Nejdříve si přečtěte zadání lehké úlohy.
* Napište program **dama_max.py**, který načte matici celých čísel ze souboru, jehož jméno je zadáno jako první argument programu sys.argv[1] a najde kamen (obyčejný kamen, nebo dámu) která může provést nejdelší skok. Délku skoku určuje nejdříve počet kamenů černého, které při skoku zajme. V přípedě, že dva různé skoky zajmou stejný počet černých kamenů pak o délce skoku záleží na počtu políček, které kamen při braní urazí.
* Pokud existují skoky se stejnou délkou, vytiskněte libovolný z nich.
* ** Vstup:**
* První argument programu obsahuje jméno souboru.
* Soubor obsahuje matici $ 8 \times 8 $ - celých čísel s tímto významem:
* 0 - volné pole
* 1 - bílý kámen
* 2 - bílá dáma
* 3 - černý kámen
* 4 - černá dáma
* Pole na šachovnici odpovídají tomu, že první řádek matice představuje řadu 8, druhý řádek reprezentuje řadu 7, ... , poslední řádek v souboru reprezentuje řádek 1. Sloupce jsou označeny písmeny a,...,g.
* ** Úkol:**
* Bílý je na tahu a program najde kamen, který provede nejdelší skok.
* Uvažujte všechna pravidla České dámy ([[https://cs.wikipedia.org/wiki/D%C3%A1ma_(deskov%C3%A1_hra)|Dáma (desková hra)]])
* Oproti lehké variantě přidáme pohyb dámy. Dáma se pohybuje úhlopříčně libovolným směrem.
* Dáma může skočit, pokud jsoou na diagonále volná pole a hned za nimi sousední pole obsazené cizím kamenem nebo dámou a následující pole za obsazeným polem je volné, pak dáma může skočit na libovolné volné pole za cizím kamen.
* Cizí kamen (nebo kameny) se odstraní, až když tah dámy skončí. Cizí kamen lze přeskočit při jednom tahu pouze jednou.
* Jak bylo uvedeno výše, délka skoku závisí nejvíce na počtu braných kamenů, v případě shody v počtu braných kamenů rozhoduje počet polí, která dáma, nebo kamen musel překonat (i když to vede k nevýhodné situaci pro bílého).
* V následujících obrázcích jsou černě značeny nejdelší skoky, modře skoky kratší:
{{courses:b3b33alp:cviceni:2023_dama_vice_skok1.png?150 |}} {{courses:b3b33alp:cviceni:2023_dama_vice_skok2.png?150|}}
* **Výstup:**
* Program vytiskne na jeden řádek souřadnice kamenu, který skočil a všechna místa, kam skočil (míst je víc pro vícenásobný skok)
* Program v souboru **dama_max.py** odevzdejte pomocí odevzdávacího systému (úloha HW05).
* Můžete předpokládat, že všechny matice jsou zadány korektně, tedy všechny řádky mají stejný počet prvků a obsahují pouze celá čísla od 0 do 4.
=== Příklad ===
* Soubor dama.txt obsahuje:
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 3 0 0 0 0
0 0 0 0 0 0 0 0
0 3 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 3 0 2 0 0 0 0
0 0 1 0 0 0 0 0
Výstup:
c1 a3 c5 e7
Vysvětlení: Skok bílého kamene je delší než skok bílé dámy.
* Soubor dama.txt:
0 0 0 0 0 2 0 0
0 0 3 0 3 0 4 0
0 0 0 0 0 0 0 0
0 0 3 0 0 0 3 0
0 0 0 0 0 0 0 0
0 0 0 0 3 0 3 0
0 0 0 3 0 0 0 0
1 0 1 0 0 0 2 0
Výstup:
g1 d4 b6 d8 f6 h4 e1 c3 h8
Velmi dlouhý skok dámy.
* Soubor dama.txt:
0 0 0 0 0 4 0 0
0 0 3 0 0 0 3 0
0 2 0 0 0 0 0 0
0 0 0 0 3 0 0 0
0 0 0 0 0 0 0 0
0 0 3 0 0 0 3 0
0 1 0 0 0 0 0 1
0 0 0 0 0 0 0 0
Výstup:
buď
b2 d4 f6 h8
nebo
h2 f4 d6 b8
Dva stejně dlouhé tahy, Váš program vytiskne buď první nebo druhý tah.