====== Cvičení 10, Stavový prostor a objekty v Pythonu ======
===== náplň cvičení =====
===== Quick test 1 - data =====
{{ :courses:b3b33alp:cviceni:slovnik.txt | slovnik.txt}}
==== Ú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, kde X je v rozsahu 0,1,2
* **Vx**: vylij celou nádobu X, kde X je v rozsahu 0,1,2
* **xPy**: přelij nádobu X do nádoby Y, kde X a Y jsou různá čísla z rozsahu 0,1,2:
* pokud se celý objem z X nevejde do Y, odlije se voda z X tak, aby se Y naplnila
Napište program, který najde nejmenší počet kroků takový, že v poslední nádobě bude objem 6.
==== Úloha 2: Nejkratší cesta v grafu ====
Mějme orientovaný graf, který má uzly očíslované od 1 do N. Hrany v tomto grafu jsou zadány ve speciálním souboru, který na jedné řádce obsahuje definici jedné hrany, tedy dvě čísla:
* první číslo je číslo uzlu ze kterého vede hrana
* druhé číslo je číslo uzlu do kterého vede tato hrana
Napište program ''path.py'', který z příkazové řádky načte jméno souboru s definicí hran a číslo startovního uzlu a číslo koncového uzlu. Program vytiskne jednu z nejkratších cest ze startovního uzlu do cílového uzlu.
Program otestujte na tomto souboru:
1 2
1 9
2 3
2 6
3 4
3 8
4 6
4 1
5 4
5 8
6 8
6 9
7 4
7 5
8 7
8 3
9 5
9 1
Výsledek pro cestu z uzlu 2 do uzlu 5 je:
2 6 9 5
==== Úkol 3: Objekt komlexní číslo ====
Třídy pro komplexní čísla:
* Třída obsahuje dvě proměnné ''real'' a ''imag''
* Konstruktor (metoda ''_init_()'') nastavuje tyto proměnné defaultně na 0
* Pro přímý výpis funkcí print je vhodné definovat metodu ''_repr_'', která vrací string
* **Pozor: init a repr má v názvu dvě podtržítka!!! **
class Complex:
def __init__(self, real=0, imag=0):
self.real = real
self.imag = imag
def amplitude(self):
return (self.real*self.real + self.imag*self.imag)**(1/2)
def add(self, rhs):
self.real += rhs.real
self.imag += rhs.imag
def sub(self, rhs):
self.real -= rhs.real
self.imag -= rhs.imag
def __repr__(self):
sign = "+";
if (self.imag < 0):
sign = "-";
return str(self.real) + sign + str(abs(self.imag)) + "i"
def mul(self, rhs):
r = self.real*rhs.real - self.imag*rhs.imag;
i = self.real*rhs.imag + self.imag*rhs.real;
self.real = r
self.imag = i
if __name__=="__main__":
a = Complex()
print("a=",a)
b = Complex(1,-1)
print("b=",b)
a.add(b)
print("a=",a)
a.mul(b)
print("a=",a)
print("|a|=",a.amplitude())
print("|b|=",b.amplitude())
===== Domácí práce: Hlavolamy =====
==== Lehká varianta:====
* Máme robota, který se pohybuje na kluzišti, ale **neumí zastavit**. Dokáže se pouze odrazit jedním ze 4 povolených směrů a zastavit se buď o konec kluziště nebo o překážku.
* Kluziště má tvar obdélníka reprezentovaného maticí, ve které:
* 0 je volný prostor,
* 1 je překážka (na toto místo se robot nemůže postavit, zastaví se před překážkou),
* 2 je volné místo reprezentující počáteční polohu robotu, a
* 4 je volné místo reprezentující cíl, tj. místo kam má robot doklouzat.
* Robot se může pohybovat pouze ve čtyřech směrech -> **S**: nahoru, **V**: doprava, **J**: dolů, a **Z**: doleva.
* Napište program ''skate.py'' pro úlohu HW09, který najde pro zadanou matici nejkratší sekvenci pohybů pro robota z počáteční do cílové pozice.
{{ :courses:b3b33alp:cviceni:robot.png?direct&200 | Robot na kluzišti}}
* Program je spouštěn s jedním argumentem, kterým je název souboru v němž je uložené kluziště.
* Výstup je sekvence písmen **S**, **V**, **J**, **Z** která na nejmenší počet příkazů dovede robota z počáteční do cílové pozice
* POZOR: Robot se musí v cílové pozici zastavit, tedy zarazit o překážku nebo o konec kluziště.
=== Příklad ===
Soubor skate1.txt obsahuje tyto data:
0 0 0 0 1 0
1 0 2 0 0 0
4 1 0 0 0 0
0 0 0 0 1 0
Výstupem programu ''python3 skate.py skate1.txt'' bude řádka:
JZS
protože nekratší cestou z (1, 2) je jet na **J**ih, pak na **Z**ápad a pak na **S**ever. Cesta robotu je naznačena písmeny S, J, a Z:
0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0
1 0 J 0 0 0 1 0 J 0 0 0 1 0 J 0 0 0
4 1 J 0 0 0 4 1 J 0 0 0 2 1 J 0 0 0
0 0 2 0 1 0 2 Z Z 0 1 0 S Z Z 0 1 0
Soubor skate2.txt obsahuje tyto data:
0 0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 2 0
0 0 0 0 0 1 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 1 0 0 0 0
0 1 0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 1 0 0 4 0 0 0
0 0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1 0
0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 0 0
Výstupem programu ''python3 skate.py skate2.txt'' bude řádka:
JZJVS
Nejkratší cesta pro robota je opět označena písmeny
0 0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 2 0
0 0 0 0 0 1 0 0 0 0 0 J 0
0 1 Z Z Z Z Z Z Z Z Z J 0
0 0 J 0 0 0 0 0 0 0 0 1 0
0 0 J 0 0 0 0 0 1 0 0 0 0
0 1 J 0 0 0 0 0 0 1 0 0 0
0 0 J 0 0 0 1 0 0 4 0 0 0
0 0 J 0 1 0 0 0 0 S 0 0 0
0 0 J 0 0 0 0 0 0 S 0 1 0
0 1 J 0 0 0 0 0 0 S 0 0 0
0 0 J 1 0 0 0 0 0 S 0 0 0
0 1 J 0 0 0 0 0 0 S 0 0 0
0 0 J 1 0 0 0 0 0 S 0 0 0
0 0 J 0 0 0 1 0 0 S 0 0 0
0 0 J V V V V V V V 1 0 0
Soubor skate3.txt obsahuje tyto data:
1 0 0 0 0 0 0
1 0 0 0 0 0 0
0 0 0 0 1 0 0
0 0 0 0 0 2 0
0 0 0 4 1 0 0
0 0 0 1 0 0 0
Výstupem programu ''python3 skate.py skate3.txt'' bude řádka:
ZSVJ
Nejkratší cesta pro robota je opět označena písmeny
1 0 0 0 0 0 0
1 0 0 0 0 0 0
S V V V 1 0 0
Z Z Z Z/J Z 2 0
0 0 0 4 1 0 0
0 0 0 1 0 0 0
==== Těžká varianta:====
* Na obdélníkovém hřišti se pohybuje **šachový** kůň. Takový kůň se umí pohybovat pouze o dvě pole svisle nebo vodorovně a poté ještě o jedno pole kolmo na původní směr. Jeho cesta tedy připomíná písmeno L.
* Hřiště má tvar obdélníka a je reprezentované maticí, ve které:
* 0 je volný prostor,
* 1 je překážka (na toto místo kůň nemůže skočit),
* 2 je volné místo reprezentující počáteční polohu koně, a
* 4 je volné místo reprezentující cíl pohybu koně, tj. kam má kůň doskákat.
* Napište program ''horse.py'' pro úlohu HW09, který najde pro zadanou matici nejkratší sekvenci skoků koně z počáteční do cílové pozice:
* Program je spouštěn s jedním argumentem, kterým je název souboru definující hřiště.
* Výstup je sekvence pozic, kam kůň skočil ve formě ''číslo řádku číslo sloupce'', tedy dvě čísla oddělená mezerou.
* Levý horní roh hřiště má pozici ''0 0''.
* Pokud cesta do cíle neexistuje, pak program vypíše ''NEEXISUJE''.
=== Příklad ===
Soubor horse1.txt obsahuje tyto data:
0 0 0 0 0
0 0 1 1 0
2 0 0 0 0
1 0 1 0 0
0 1 4 0 0
0 0 0 0 0
Výstupem programu ''python3 horse.py horse1.txt'' bude řádka:
0 1 2 2 3 4 4 2
protože nekratší cesta vede přes pozice (0,1), (2,2), (3,4), (4,2). Cílová pozice se uvádí, startovní se neuvádí. Cesta koně je označena písmeny H:
0 H 0 0 0
0 0 1 1 0
2 0 H 0 0
1 0 1 0 H
0 1 4H 0 0
0 0 0 0 0
Soubor horse2.txt obsahuje tyto data:
0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0
0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0
1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 0 1 0 0 1 0 1 1 0 0 0 1 0 0 0 1 0 0 0 0
0 0 0 1 0 0 0 1 0 0 0 1 1 1 0 0 1 0 0 0 1 0 0 0 0 1 0
0 0 0 0 0 0 0 0 1 1 1 0 1 0 1 0 0 0 1 0 0 0 0 0 0 1 0
0 0 0 1 0 0 0 1 1 0 0 0 1 0 1 0 1 0 0 0 0 0 1 1 2 0 0
0 0 1 0 0 0 0 1 0 0 1 1 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 1 1 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0
0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0
0 0 4 0 1 0 1 1 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0
0 0 0 0 1 0 0 1 0 1 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0
0 0 0 0 1 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0
0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0
0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0
0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0
0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0
Výstupem programu ''python3 horse.py horse2.txt'' bude řádka:
11 22 12 20 13 18 14 16 15 14 16 12 17 10 16 8 17 6 15 5 14 3 16 2
Nejkratší cesta pro robota je opět označena písmeny
0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0
0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0
1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 0 1 0 0 1 0 1 1 0 0 0 1 0 0 0 1 0 0 0 0
0 0 0 1 0 0 0 1 0 0 0 1 1 1 0 0 1 0 0 0 1 0 0 0 0 1 0
0 0 0 0 0 0 0 0 1 1 1 0 1 0 1 0 0 0 1 0 0 0 H 0 0 1 0
0 0 0 1 0 0 0 1 1 0 0 0 1 0 1 0 1 0 0 0 H 0 1 1 2 0 0
0 0 1 0 0 0 0 1 0 0 1 1 0 1 1 0 0 0 H 0 0 0 1 0 0 0 0
0 0 0 H 0 0 0 1 1 0 1 1 1 0 0 0 H 0 0 0 0 1 0 0 0 0 0
0 0 0 0 1 H 1 0 0 0 1 0 0 0 H 0 0 1 1 0 0 0 0 0 0 1 0
0 0 4H 0 1 0 1 1 H 0 0 1 H 0 0 0 0 1 1 0 1 0 0 0 0 0 0
0 0 0 0 1 0 H 1 0 1 H 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0
0 0 0 0 1 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0
0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0
0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0
0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0
0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0
Soubor horse3.txt obsahuje tyto data:
1 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0 0 0
0 1 0 2 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0
1 0 0 0 0 0 0 4 0 0
0 0 0 1 0 0 0 0 0 0
Výstupem programu ''python3 horse.py horse3.txt'' bude řádka:
6 4 5 6 7 7
nebo
6 4 8 5 7 7
Nejkratší cesty jsou dvě a Váš program vytiskne libovolnou jednu z nich. Níže jsou označeny obě možná řešení
1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0
0 1 0 2 0 0 0 0 0 0 0 1 0 2 0 0 0 0 0 0
0 0 0 1 0 0 H 0 0 0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 H 1 0 0 0 0 0 0 0 0 H 1 0 0 0 0
1 0 0 0 0 0 0 4H 0 0 1 0 0 0 0 0 0 4H 0 0
0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 H 0 0 0 0
Soubor horse4.txt obsahuje tyto data:
0 0 0 0 0 0 0 0 1 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0 0 0 1 0
0 0 1 0 0 1 1 0 1 0 0 0 0 0 0
0 1 0 0 0 1 1 0 0 0 0 1 1 0 0
0 0 0 1 1 1 0 1 0 0 1 0 1 0 0
0 0 1 0 1 1 1 1 0 1 0 1 1 0 0
0 0 0 1 2 0 1 1 0 1 0 1 1 1 0
0 1 0 0 0 0 1 0 1 0 1 1 1 1 1
1 0 0 1 0 1 0 1 1 0 0 0 4 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 0 0
0 0 0 0 0 0 0 0 0 0 0 1 1 0 0
Výstupem programu ''python3 horse.py horse4.txt'' bude řádka:
NEEXISTUJE
V tomto prostředí neexistuje cesta ze startovní pozice do cíle.