Cvičení 10, Stavový prostor a objekty

• 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

• 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

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

• 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

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

• 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

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];
...
}

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

• Napište program rotate2.py pro úlohu HW09, který vyřeší hlavolam dvou 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

• Cílová poloha hlavolamu je tato:

1 0 0 0 0 0
1 1 0 1 1 1

• 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ů)

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)

• Napište program rotate3.py pro úlohu HW09, který vyřeší hlavolam tří 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

• 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ů)

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)