Cvičení 10, Stavový prostor a objekty

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

• 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

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

Vstup programu je:

4 1 2 3 5 0 0

Výstupem programu bude řádka:

06 10 21 32 63

tah 06 tah 10 tah 21 tah 32 tah 63

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

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

• 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
  • 1 - dílek je otočen vrškem doprava
  • 2 - dílek je vrškem dolů
  • 3 - dílek je otočen vrškem vlevo
• 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

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