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

Prémie navíc: zobrazení přes dot format

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:

  • Napište program rotate2.py pro úlohu HW09, který vyřeší hlavolam dvou kruhů:

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

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

 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)

courses/b3b33alp/cviceni/t10.txt · Last modified: 2021/11/21 15:29 by stepan