====== Cvičení 10, Stavový prostor a objekty ====== ===== náplň cvičení ===== ==== Úloha 1 Fronta ==== * Přeměňte řešení úlohy 3 Flood fill z cvičení 8 na frontu. * Postupnou animací zjistěte jak se změnilo vyplňování prostoru * Zjistěte, zda potřebuje více paměti zásobník, nebo fronta ==== Úloha 2 Komentáře - rozšíření ==== * Upravte program na odstraňování komentářů z přednášky tak: * aby program bral v úvahu řetězce začínající a končící znakem ' * aby správně interpretoval znaky \' a \" * aby pokud řádka končí znakem \ dovedl řetězec prodloužit přes více řádek * Program otestujte na následujících datech a='b\'c#d' #e i="j\"k'l#m" #n * Program z přednášky: def preskoc_komentare(line): # vytiskne obsah souboru 'f' s vynechanymi komentari stav=0 # počáteční stav automatu for c in line: # přečti jeden znak if stav==0: # počáteční stav if c=="#": # začátek komentáře stav=1 continue elif c=='\"': stav=2 # začátek řetězce elif stav==1: # 1="komentar" continue elif stav==2: if c=='\"': stav=0 print(c,end="") # vytiskni znak i=input() preskoc_komentare(i) # nacti radku a preskakuj ==== Úloha 3 Kontrola reálného čísla ==== * Reálné číslo v pythonu je zadána touto BNF gramatikou: floatnumber ::= pointfloat | exponentfloat pointfloat ::= [intpart] fraction | intpart "." exponentfloat ::= (intpart | pointfloat) exponent intpart ::= digit+ fraction ::= "." digit+ exponent ::= ("e" | "E") ["+" | "-"] digit+ digit ::= "0"..."9" * Vymyslete a naprogramujte stavový automat, který bude zjišťovat, zda je řetězec na řádce reálným číslem. * ==== Úloha 5 Obsahy závorek ==== * Uvažujme řetězec obsahující závorky () a []. * Napište program, který bude testovat, zda je výraz správně uzávorkován a zjistí text uvnitř závorek * Závorky mohou být do sebe vnořeny a pak text patří do poslední úrovně závorek * Program tedy text: aa[bb(cc)dd(ee)fff[gggg]]hhh * převede na výstup: ()cc ()ee []gggg []bbddfff * písmena 'aa' a 'hhh' se zahodí, nejsou uvnitř žádných závorek ==== Úloha 4 Přelévání nádob ==== Mějme tři nádoby o objemu 2, 5, 9. S nádobami můžeme provádět následující akce: * Nx - napusť plnou nádobu x, x je v rozsahu 0,1,2 * Vx - vylij celou nádobu x, x opět v rozsahu 0,1,2 * xPy - nádobu x přelij do nádoby y, x,y různé v rozsahu 0,1,2: * buď se celý objem x vejde do nádoby y * nebo se z x odlije jen takové množství, které zaplní y Napište program, který najde nejrychlejší způsob, jak získat v poslední nádobě objem 6. Nejrychlejší znamená s nejmenším počtem kroků. ==== Úkol 5: Genealogie ==== * Využijte následující třídu pro reprezentaci rodinných vztahů class Person: def __init__(self, name, sex): self.name = name self.sex = sex self.children = [] self.parents = [] # parents of this node self.partner = None # partner (=husband/wife of this node) def addChild(self, node): self.children.append(node) def addParent(self, node): self.parents.append(node) def setPartner(self, node): self.partner = node def __repr__(self): s = "Female" if self.sex == 'F' else "Male" return self.name + " " + s * Každá osoba může mít více potomků a max. jednoho partnera (manžela/manželku) * Třída by měla obsahovat: * Seznam potomků, odkaz na rodiče, a partnera * Metody pro manipulaci s těmito prvky (např. addChild, setPartner ..) * Vytvořte objekt Tree - genealogický strom, který bude obsahovat seznam všech lidí a bude umět přidávat lidi i vztahy mezi nimi. * Objekt Tree otestujte přidáním 4 objekty: dva partnery a dvě děti. * Otestujte, zda byly vytvořeny správné vazby, tj. aby objekty děti ukazovaly na rodiče a naopak. * Napište funkce pro: * nalezení všech vnuků dané osoby * nalezení všech vnuček dané osoby * nalezení všech babiček dané osoby * Rozšiřte předchozí kód o načítání ze souboru: * na každém řádku je jeden záznam * záznam pro rodiče-děti: 'P name1 name2 sex1 sex2', kde P definuje vztah osoba name1 je rodičem osoby name2 a sex1, sex2 označují pohlaví těchto osob (buď F nebo M) * záznam pro partnery: 'M name1 name2 sex1 sex2', name1 a name2 jsou partneri, sex1, sex2 je F/M Vstupní soubor family.txt: M Jana Jan F M P Jana Martin F M P Jana Robert F M P Robert Gabriel M M P Robert Oleg M M P Robert Ondrej M M P Martin Jiri M M P Martin Rudolf M M P Jan Petra M F P Jan Uxana M F P Uxana Klara F F P Uxana Jakub F M P Uxana Adam F M P Petra Alex F M P A C M M P A D M F P D K F F P C J M M P C I M F P C H M M P B E F F P B F F M P B G F F Schéma rodiny ve family.txt: * Červeně: females * Modrá hrana: partneři {{courses:b3b33alp:cviceni:family.png?800|}} ===== Prémie navíc: zobrazení přes dot format ===== Uložení načtených dat do '[[ https://en.wikipedia.org/wiki/DOT_(graph_description_language) | Dot ]]' souboru, který lze pak vykreslit do png nástrojem **dot** z balíku nástrojů [[http://www.graphviz.org/|Graphviz]]: dot -Tpng family.dot > family.png Příklad family.dot: digraph G { Jana[ color=red]; Jana->Martin [label="child"]; Jana->Robert [label="child"]; Jana->Jan[color=blue; penwidth=4]; Jan[ color=green]; Jan->Petra [label="child"]; Jan->Uxana [label="child"]; Jan->Jana[color=blue; penwidth=4]; Martin[ color=green]; Martin->Jiri [label="child"]; Martin->Rudolf [label="child"]; Martin->Jana [style=dashed]; ... } ===== Domácí práce - Hlavolamy ===== Znalosti k vyřešení následujících úloh budou postupně rozebírány na cvičeních, proto je termín odevzdání úloh až do konce semestru. Hlavolamy jsou inspirovány hrami pro Android Can you escape the 100 room I-XII, kde najdete plno podobných zajímavých hlavolamů. ==== Lehká varianta:==== * Napište program **rotate2.py** pro úlohu HW09, který vyřeší hlavolam dvou kruhů: {{ :courses:b3b33alp:cviceni:otaceni2-anim.gif?direct&400 | Příklad otáčení kruhů}} * Hlavolam obsahuje 2 kruhy které dohromady obsahují 10 kuliček. * Při otáčení jednoho kruhu se mění i dvě kuličky v druhém kruhu * Cílový stav je, když červené kuličky jsou v červených částech kruhu a zelené kuličky jsou v zelených částech kruhu * Místa na kruzích jsou označena indexy 0 .. 5. přičemž červené kuličky značíme číslem 0 a zelné kuličky číslem 1 * Počáteční stav hlavolamu je zadán dvěma řádky na standardním vstupu, kdy první řádka obsahuje seznam kuliček v červeném kruhu od indexu 0 do indexu 5 a druhá řádka obsahuje seznam kuliček v zeleném kruhu od indexu 0 do indexu 5 * Budeme Vám zadávat pouze korektní vstupy, tedy hodnota v červeném kruhu na indexu 0 se rovná hodnotě v zeleném kruhu na indexu 0, protože jde o stejnou kuličku. Stejně tak hodnoty s indexem 2 se v obou kruzích rovnají, jde o druhou sdílenou kuličku. * Příklad počáteční pozice: 1 0 1 0 0 0 1 1 1 0 1 1 je na následujícím obrázku {{:courses:b3b33alp:cviceni:otaceni2a.png?200| Výchozí pozice}} * Cílová poloha hlavolamu je tato: 1 0 0 0 0 0 1 1 0 1 1 1 v červeném kruhu jsou samé červené kuličky - 0, kromě pozice 0, v zeleném kruhu jsou samé zelené kuličky - 1, kromě pozice 2 {{:courses:b3b33alp:cviceni:otaceni2.png?200|}} * Kruhy se mohou otáčet ve směru +1 značeno písmenem 'p', nebo ve směru -1 značeno písmenem 'm' * Červený kruh má index 0, zelený kruh má index 1 * Zápis jednoho tahu začíná '(' index_kruhu ',' směr otáčení ')' * Tedy například řešení animovaného gifu ze začátku zadání je: (0,m)(1,m) * Vstup programu jsou dvě řádky ze standardního vstupu definující počáteční stav hlavolamu, každá řádka obsahuje pole 6 čísel oddělených mezerou * každé číslo určuje jaký kámen je na dané pozici, číslo 0 je červená kulička, číslo 1 zelená kulička, první řádka definuje červený kruh, druhá řádka zelený kruh. * Výstup programu je jedna řádka na standardní výstup, ve které je vytištěna nejkratší posloupnost přesunů, která složí daný hlavolam: * řádek obsahuje tahy popsané výše * pokud existuje více možností sestavení hlavolamu, vyberte libovolnou z těch nejkratších (tedy na nejmenší počet otočení kruhů) === Příklad === Vstup programu je: 1 0 1 0 0 0 1 0 1 1 1 1 Výstupem programu bude řádka: (1,p) Vstup programu je: 1 1 1 0 0 0 1 0 1 1 1 0 Výstupem programu bude řádka: (1,p)(0,m) Vstup programu je: 1 0 1 1 0 1 1 1 1 0 0 0 Výstupem programu bude řádka: (0,m)(1,p)(1,p)(0,p)(1,p)(0,p) ==== Těžká varianta:==== * Napište program **rotate3.py** pro úlohu HW09, který vyřeší hlavolam tří kruhů: {{ :courses:b3b33alp:cviceni:otaceni3.png?direct&400 | Cílový stav kruhů}} * Prostudujte si lehkou úlohu, která obsahuje obdobný hlavolam složený ze dvou kruhů * Tento hlavolam obsahuje 3 kruhy, které dohromady obsahují 12 kuliček. * Při otáčení jednoho kruhu se mění i dvě kuličky v ostatních kruzích * Cílový stav je, když červené kuličky jsou v červených částech kruhu, zelené kuličky jsou v zelených částech kruhu a modré kuličky v modrých částech kruhu * Místa na kruzích jsou označena indexy 0 .. 5. přičemž červené kuličky značíme číslem 0, zelné kuličky číslem 1 a modré klučky číslem 2. * Počáteční stav hlavolamu je zadán třema řádky na standardním vstupu, kdy první řádka obsahuje seznam kuliček v červeném kruhu od indexu 0 do indexu 5 a druhá řádka obsahuje seznam kuliček v zeleném kruhu od indexu 0 do indexu 5 a třetí řádka obsahuje seznam kuliček v modrém kruhu. * Budeme Vám zadávat pouze korektní vstupy, tedy hodnota v červeném kruhu na indexu 0 se rovná hodnotě v zeleném kruhu na indexu 0, protože jde o stejnou kuličku. Stejně tak hodnoty s indexem 2 se v červeném a zeleném kruhu rovnají, jde o druhou sdílenou kuličku. Nyní navíc hodnota v červeném kruhu s indexem 1 se rovná hodnotě modrého kruhu s indexem 1, hodnota červeného kruhu s indexem 3 se rovná hodnotě modrého kruhu s indexem 5, hodnota zeleného kruhu s indexem 1 se rovná hodntě modrého kruhu s indexem 0 a hodnota zeleného kruhu s indexem 3 se rovná hodnotě modrého kruhu s indexem 2. * Cílová poloha hlavolamu je tato: 1 2 0 0 0 0 1 1 0 2 1 1 1 2 2 2 2 0 v červeném kruhu jsou samé červené kuličky - 0, kromě pozice 0 a 1, v zeleném kruhu jsou samé zelené kuličky - 1, kromě pozice 2 a 3 a v modrém kruhu jsou samé modré kuličky 2 kromě pozice 0 a 5. Obrázek cílové pozice je v horní části zadání těžké úlohy. * Kruhy se mohou otáčet ve směru +1 značeno písmenem 'p', nebo ve směru -1 značeno písmenem 'm' * Červený kruh má index 0, zelený kruh má index 1 a modrý kruh má index 2 * Zápis jednoho tahu začíná '(' index_kruhu ',' směr otáčení ')' * Vstup programu jsou tři řádky ze standardního vstupu definující počáteční stav hlavolamu, každá řádka obsahuje pole 6 čísel oddělených mezerou * každé číslo určuje jaký kámen je na dané pozici, číslo 0 je červená kulička, číslo 1 zelená kulička, číslo 2 modrá kulička, první řádka definuje červený kruh, druhá řádka zelený kruh, třetí řádka modrý kruh * Výstup programu je jedna řádka na standardní výstup, ve které je vytištěna nejkratší posloupnost přesunů, která složí daný hlavolam: * řádek obsahuje tahy popsané výše * pokud existuje více možností sestavení hlavolamu, vyberte libovolnou z těch nejkratších (tedy na nejmenší počet otočení kruhů) === Příklad === Vstup programu je: 1 2 2 0 0 0 1 0 2 1 1 1 0 2 1 2 2 0 Výstupem programu bude řádka: (1,p) Vstup programu je: 0 1 2 1 0 0 0 1 2 1 0 2 1 1 1 2 2 1 Výstupem programu bude řádka: (0,m)(1,m)(1,m) Vstup programu je: 2 0 1 2 1 1 2 2 1 0 0 1 2 0 0 0 2 2 Výstupem programu bude řádka: (2,m)(0,p)(1,m)(0,p)(0,p)(2,m)(0,p)