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