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