====== Cvičení 10, Stavový prostor a objekty ======
===== náplň cvičení =====
==== Úloha 1 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 2: 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];
...
}
==== Úloha 3 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 4 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
===== 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 **shift.py** pro úlohu HW09, který vyřeší přesouvací hlavolam:
* Hlavolam obsahuje 7 míst pro 5 kamenů, označených 1,2,3,4,5.
* Místa označená kamenem 0 jsou prázdná a na jejich místo lze přešunout libovolný sousední kamen po zobrazených čarách
* Příklad počáteční pozice je na tomto obrázku (místa jsou očíslována od 0,...,6, zelené kameny mají čísla 1,2,3,4,5 a kameny s čísly 0 jsou volné pozice) {{:courses:b3b33alp:cviceni:shift-s0.png?200|}}
* Cílová poloha hlavolamu je ta, že na pozici 0 je kamen 1, na pozici 1 kamen 2, na pozici 2 kamen 3, na pozici 3 kamen 4 a na pozici 4 kamen 5, pozice 5,6 jsou volné - viz obrázek {{:courses:b3b33alp:cviceni:shift-s5.png?200|}}
* Kameny se mohou přesouvat pouze na volné pole, po nakreslených čarách, tedy:
* z pozice 0 na pozici 1, nebo pozici 6
* z pozice 1 na pozici 0, 2, nebo 5
* z pozice 2 na pozici 1, nebo 3
* z pozice 3 na pozici 2, 4, nebo 6
* z pozice 4 na pozici 3, nebo 5
* z pozice 5 na pozici 1, nebo 4
* z pozice 6 na pozici 0, nebo 3
* Zápis přesunu kamene z pozice 0 na pozici 6 se zapíše jako dvouciferné číslo 06
* Vstup programu je jedna řádka ze standarního vstupu definující konfigurace hlavolamu zadanou jako pole 7 čísel oddělených mezerou
* každé číslo určuje jaký kámen je na dané pozici, případně 0 označuje prázdnou pozici.
* Výstup programu je na standardní výstup a obsahuje jednu řádku, na které je vytištěna nejkratší posloupnost přesunů, která složí daný hlavolam:
* řádek obsahuje dvojice cifer oddělené mezerou
* každá dvojice cifer označuje z které pozice a na kterou pozici se přesunul kamen
* pokud existuje více možností, vyberte libovolnou z těch nejkratších
=== Příklad ===
Vstup programu je:
4 1 2 3 5 0 0
Výstupem programu bude řádka:
06 10 21 32 63
protože je to nejkratší posloupnost tahů, která složí daný hlavolam.
{{:courses:b3b33alp:cviceni:shift-s0.png?200|}}
tah 06
{{:courses:b3b33alp:cviceni:shift-s1.png?200|}}
tah 10
{{:courses:b3b33alp:cviceni:shift-s2.png?200|}}
tah 21
{{:courses:b3b33alp:cviceni:shift-s3.png?200|}}
tah 32
{{:courses:b3b33alp:cviceni:shift-s4.png?200|}}
tah 63
{{:courses:b3b33alp:cviceni:shift-s5.png?200|}}
==== Těžká varianta:====
Napište program **rotate.py** pro úlohu HW09, který zjistí, jak složit následující hlavolam:
* hlavolam je obrázek, který je rozdělený na 9 částí - viz obrázek
{{:courses:b3b33alp:cviceni:python-obr-final.png?200|}}
* pokud si zvolíte jeden dílek, pak se rotuje zvolený dílek a jeho sousední dílky.
* rotace dílku znamená, že zvolený dílek se otočí na své pozici o 90 stupňů ve směru hodinových ručiček.
{{:courses:b3b33alp:cviceni:python-obr-rotace.png?200|}}
* na obrázku je rotace spojená s dílkem 0 - posměru hodinových ručiček se rotují dílky 0,1,3.
* stav hlavolamu budeme značit čísly:
* 0 - dílek je ve správné poloze {{:courses:b3b33alp:cviceni:python-dil-0.png?40|}}
* 1 - dílek je otočen vrškem doprava {{:courses:b3b33alp:cviceni:python-dil-1.png?40|}}
* 2 - dílek je vrškem dolů {{:courses:b3b33alp:cviceni:python-dil-2.png?40|}}
* 3 - dílek je otočen vrškem vlevo {{:courses:b3b33alp:cviceni:python-dil-3.png?40|}}
* tah umožňuje rotovat dílky pouze po směru hodinových ručiček
* rotace dílku:
* 0 - znamená otočit dílky 0,1,3
* 1 - znamená otočit dílky 0,1,2,4
* 2 - znamená otočit dílky 1,2,5
* 3 - znamená otočit dílky 0,3,4,6
* 4 - znamená otočit dílky 1,3,4,5,7
* 5 - znamená otočit dílky 2,4,5,8
* 6 - znamená otočit dílky 3,6,7
* 7 - znamená otočit dílky 4,6,7,8
* 8 - znamená otočit dílky 5,7,8
Protože operace tahu jsou komutativní (nezáleží na pořadí provedených rotací), tak bude program hledat jenom počet rotací spojených s jednotlivými pozicemi.
Bude nás zajímat jen nejkratší řešení, tedy řešení s nejmenším počtem provedených rotací.
Vstup programu bude ze standardního vstupu:
* jedna řádka obsahující 9 čísel 0,..,3, které značí počáteční stav hlavolamu. Poloha jednotlivých dílků je zadána podle obráku výše.
Výstup programu bude na standardní výstup:
* jedna řádka obsahující 9 čísel, které určují kolikrát je nutné provést rotace spojené s kterým dílkem, abychom dostali složený hlavolam, tedy všechny dílky byly v pozici 0
=== Příklad ===
Vstup programu je stav obrázku, který má horní prostřední díl otočen dolů:
0 2 0 0 0 0 0 0 0
Výstupem programu bude řádka (kontrolu si zkuste sami, řádka značí, že se bude 2x rotovat podle prostředního dílku a 2x rotovat podle všech dílků spodní řady):
0 0 0 0 2 0 2 2 2
Vstup programu je stav obrázku, který má jen levý horní roh otočen doprava, ostatní dílky jsou správně:
1 0 0 0 0 0 0 0 0
Výstupem programu bude řádka:
3 0 3 0 2 1 3 1 2