Cvičení 10, Stavový prostor a objekty v Pythonu

slovnik.txt

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.

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

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

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

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

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 Jih, pak na Západ a pak na Sever. 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

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

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.