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í
a='b\'c#d' #e
i="j\"k'l#m" #n
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
floatnumber ::= pointfloat | exponentfloat
pointfloat ::= [intpart] fraction | intpart "."
exponentfloat ::= (intpart | pointfloat) exponent
intpart ::= digit+
fraction ::= "." digit+
exponent ::= ("e" | "E") ["+" | "-"] digit+
digit ::= "0"..."9"
Ú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
()cc
()ee
[]gggg
[]bbddfff
Ú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:
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
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
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
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
Uložení načtených dat do ' Dot ' souboru, který lze pak vykreslit do png nástrojem dot z balíku nástrojů 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:
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
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
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:
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)