====== Cvičení 11: Objekty, halda, asociativní pole ======
==== 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.
==== Genealogie (Objekty dokončení) ====
* 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 objektů: 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'' značí že osoba ''name1'' je rodičem osoby ''name2''. ''sex1'' a ''sex2'' označují pohlaví těchto osob (buď F nebo M)
* záznam pro partnery: ''M name1 name2 sex1 sex2'' značí že osoby ''name1'' a ''name2'' jsou partneři, ''sex1'' a ''sex2'' jsou opět F nebo 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
{{courses:b3b33alp:cviceni:family.png?800|}}
===== Prémie navíc: zobrazení přes dot format =====
Uložení načtených dat do '[[ https://en.wikipedia.org/wiki/DOT_(graph_description_language) | Dot ]]' souboru, který lze pak vykreslit do png nástrojem **dot** z balíku nástrojů [[http://www.graphviz.org/|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];
...
}
==== Binární halda ====
[[https://en.wikipedia.org/wiki/Binary_heap | Binární halda ]] je binární stromová datová struktura. Je tvořena uzly, které mají max. dva potomky (levý a pravý potomek) (odtud přídavné jméno binární), pričemž potomek je opět uzel. Její důležitou vlastností je, že:
* hodnota každého uzlu je **rovna nebo menší** než hodnoty jejich potomků.
* Pokud je tato vlastnost splněna tak platí, že prvek v tzv. kořenu stromu obsahuje **nejmenší** prvek mezi všemi prvky.
* **V tomto cvičení budeme předpokládat tuto variantu.**
* Takové haldě se někdy říká min-halda.
Binární haldu lze samozřejmě realizovat i s opačnou vlastností:
* hodnota každého uzlu je **rovna nebo větší** než hodnoty jejich potomků.
* Pokud je tato vlastnost splněna tak platí, že prvek v tzv. kořenu stromu obsahuje **největší** prvek mezi všemi prvky.
* Takové haldě se říká max-halda.
Použití binární haldy:
* Pro realizaci prioritní fronty, v důsledku toho např. pro hledání cest v grafech, mapách, plánování pohybu robotů
{{courses:b3b33alp:cviceni:heap.png?400|}}
=== Binární halda: vyjmutí nejmenšího prvku ===
Předpokládejme, že máme existující binární haldu. Při vyjmutí prvky stačí vzít prvek v kořeni stromu, neboť ten již z definice obsahuje nejmenší hodnotu mezi všemi uzly.
Po odebrání prvku je ale nutné zbylé prvky přeskupit a určit nový kořen haldy. Postup je:
* Vyjmout prvek z kořene haldy ( prvek s nejmenší hodnotou )
* Vzít poslední prvek v poslední úrovni a přesunout na pozici kořene.
* Nyní je třeba nahrat prvky v haldě tak, aby byla splněna vlastnost min-haldy. Jelikož budeme začínat od kořene a procházet strom směrem dolu, říká se tomuto postupu tzv. bubble-down.
==Bubble-down:==
* Předpokládejme, že jsme v uzlu $U$.
* Porovnáme hodnotu $U$, $U$.left a $U$.right. Pokud je splěna vlastnost min-haldy (tj. hodnota $U$ je menší nebo rovna hodnotám jejích potomků), končíme.
* Pokud ne, vybereme toho potomka, který je menší než $U$. Vyměníme hodnotu $U$ s tímto potomek.
* Pokračujeme bubble-down z tohoto potomka.
* Algoritmus končí, pokud už jsme narazili na uzel bez potomka.
=== Binární halda: vložení prvku ===
Předpokládejme, že máme existující binární haldu. Vložení prvku se provede takto:
===Bubble-up===
* Vložíme prvek na poslední nejpravější místo v poslední úrovni.
* Porovnáme hodnotu tohoto prvku s jeho rodičem. Pokud je splněna vlastnost haldy (tj. u min-haldy: hodnota prvku je větší nebo rovna hodnotě jeho rodiče), pak končíme.
* Pokud ne, vyměníme hodnotu prvku za hodnotu rodiče a opakujeme tento postup od změněného rodiče.
Tento algoritmus se nazývá bubble-up, jelikož při něm procházíme haldu ze spodní úrovně nahoru.
==== Realizace binární haldy na poli ====
Nejjednodušší realizací binární haldy je implementaci na poli. Použijeme jednoduchý trik:
* Nechť uzel má v poli index $i$.
* Jeho levý potomek má v poli index $2i+1$.
* Jeho pravý potomek má v poli index $2i+2$.
{{courses:b3b33alp:cviceni:heap1.png?200|}}
* Jaký je index rodiče, pokud má potomek index v poli $i$?
=== Implementace haldy z přednášky ===
# Implementace haldy
#
# http://interactivepython.org/runestone/static/pythonds/Trees/BinaryHeapImplementation.html
# Jan Kybic, 2016
class MinHeap:
""" binarni halda __init__ konstruktor """
def __init__(self):
self.heap = [] # indexujeme od nuly
def bubble_up(self,i):
""" probubla prvek i nahoru, zajisti splneni podminek haldy """
while i>0:
j=(i-1)//2 # index rodice
if self.heap[i] >= self.heap[j]:
break
self.heap[j],self.heap[i]=self.heap[i],self.heap[j]
i = j
def insert(self,k):
""" vloz prvek do haldy """
self.heap+=[k]
self.bubble_up(len(self.heap)-1)
def peek(self):
""" vrati nejmensi prvek """
return self.heap[0]
def size(self):
""" vrati pocet prvku v halde """
return len(self.heap)
def is_empty(self):
""" je halda prazdna? """
return self.size()==0
def bubble_down(self,i):
""" probublej prvek dolu """
n=self.size()
while 2*i+1 < n:
j=2*i+1 # zjisti index mensiho syna
if j+1 < n and self.heap[j] > self.heap[j+1]:
j+=1
if self.heap[i]>self.heap[j]:
self.heap[i],self.heap[j]=self.heap[j],self.heap[i]
i=j
def pop(self):
""" odebere nejmensi prvek a uprav haldu """
element=self.heap[0]
self.heap[0]=self.heap[-1]
self.heap.pop() # smaz posledni prvek
self.bubble_down(0)
return element
==== Implementace funkce delete ===
Implementujte metody pro odebrání prvku na pozici i z binární haldy:
* Metodu pojmenujte ''delete(i)''
* metoda dále smaže tento prvek z haldy
* ošetřete tuto metodu tak, aby ji bylo možné volat i na prázdnou haldu, případně pokud je i větší než velikost haldy
Pomocí této funkce smažte z haldy vytvořené z pole všechna sudá čísla (Nejdříve haldu vytvořte se všemi čísly a pak smažte všechna sudá čísla z haldy):
pole=[10,21,7,11,31,6,1,-11,31,42,-12,80,25,-7,-12,9,14]
==== Karty v haldě ====
* Upravte implementaci haldy tak, aby byla realizována min-halda s kartami ve formátu cvičení 7 příklad 6.
* Vytvořte haldu z následujících karet:
cards = [[0, 'Q'], [2, '6'], [1, 'K'],
[1, '8'], [2, '10'], [2, '4'],
[3, '4'], [0, '4'], [1, '3'],
[2, '5'], [0, 'K'], [3, 'A'],
[1, 'J'], [0, '3'], [0, '9']]
* V cvičení 8 jsme pro porovnání karet využívali funkci index a dvojího porovnání (nejdříve barvu a pak hodnotu). Nyní definujte pořadí pomocí asociativního pole a operací sčítání a násobení.
==== Asociativní pole a římská čísla ====
* Využijte následující asociativní pole k převodu římského čísla na dekadické číslo:
conv={'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}
* Převeďte na číslo např. MCMXCIX
===== Domácí úkol =====
==== Lehká varianta: Babylonská věž (zjednodušená) ====
**Babylonská věž (hlavolam):** hlavolam obsahující celkem 35 kuliček o 6 různých barvách (5 barev má 6 kuliček, 1 barva má pouze 5), které jsou uspořádány v 6x6 poli. Cílem hlavolamu je srovnat kuličky tak, aby každý sloupec obsahoval pouze kuličky jedné barvy a nebo prázdné místo.
* Chybějící kulička umožňuje přesun sousední kuličky na prázdné místo.
* Věž je cyklická v horizontálním směru. To znamená, že lze rotovat celým řádkem. To umožňuje posunutí vlevo či vpravo všech kuliček v jednom řádku.
{{courses:b3b33alp:domaci_ulohy:stavovy_prostor:babylonska_vez.jpg?200|}}
**Babylonská věž (v ALP):**
* Stejný problém, avšak ne pro věž o rozměrech 6x6, ale menší a také nečtvercové.
* Reprezentována 2D maticí.
* Kuličky jedné barvy mají stejný odstín. Není třeba je ve sloupci třídit dle odstínu jako tomu je u některých verzí Babylonské věže.
**Úkol:** Napište program ''babylon.py'', který najde řešení zmenšené Babylónské věže v **nejmenším počtu kroků**.
**Vstup:**
* Babylonská věž reprezentována 2D maticí o rozměrech ''M x N'', které reprezentují:
* ''M'': počet kuliček jedné barvy,
* ''N'': počet barev.
* Hodnoty v matici reprezentují barvy kuliček na dané pozici takto:
* ''0'': prázdné místo,
* ''1, 2, ..., N'': barva kuličky.
* Matice bude programu předána v argumentu programu, využijte tedy ''sys.argv[1]''.
* Příklad věže 3x3 (tedy 3 barvy, každá po 3 kuličkách, krom barvy ''3'', která má kuličky pouze 2):
1 2 3
1 2 0
2 1 3
**Povolené akce:**
* Pro zjednodušení v ALP je v každém stavu věže (neboli uspořádání kuliček) možné využít pouze těchto 4 akcí:
- **Rotace řádku vpravo**: posun všech kuliček ''n''-tého řádku o 1 doprava.
* Značení: ''r n 1'' (rotace řádku s indexem ''n'' o 1 vpravo)
- **Rotace řádku vlevo**: posun všech kuliček ''n''-tého řádku o 1 doleva.
* Značení: ''r n -1'' (rotace řádku s indexem ''n'' o 1 vlevo)
- **Přesun kuličky nahoru do prázdného místa**.
* Značení: ''m -1'' (posun kuličky pod prázdným místem nahoru)
* Pozor: lze aplikovat pouze pokud prázdné místo není ve spodní řadě
- **Přesun kuličky dolů do prázdného místa**.
* Značení: ''m 1'' (posun kuličky nad prázdným místem dolů)
* Pozor: lze aplikovat pouze pokud prázdné místo není v horní řadě
* Využitím jedné z těchto 4 akcí se věž dostane do nového stavu.
* **Příklad** pro věž:
1 2 3
1 2 0
2 1 3
* ''r 1 1'' vyvolá stav
1 2 3
0 1 2
2 1 3
* ''r 2 -1'' vyvolá stav
1 2 3
1 2 0
1 3 2
* ''m -1'' vyvolá stav
1 2 3
1 2 3
2 1 0
* ''m 1'' vyvolá stav
1 2 0
1 2 3
2 1 3
* **Pozor:** žádné další akce (např.: rotace řádku o 2 či více) nelze v ALP řešení využít.
**Výstup:**
* Nejkratší možná sekvence akcí, které převedou vstupní věž do stavu, ve kterém bude každý sloupec obsahovat pouze jednu barvu a nebo mezeru.
* Předpokládaný formát: string obsahující sekvenci akcí 1-4 oddělených čárkou.
* Příklad řešení pro naši věž výše: ''m -1,r 1 1,m 1,r 2 -1,m -1,r 1 -1'' převede věž do validního konečného stavu
1 2 3
1 2 3
1 2 0
**Poznámky:**
* Pokud existuje vícero řešení, vypište jedno z nich.
* Tip: využijte známých algoritmů pro prohledávání stavového prostoru.
* Tip: akce uložené v poli lze převést na výstupní string pomocí
sequence = ['m -1', 'r 1 1', 'm 1', 'r 2 -1', 'm -1', 'r 1 -1']
output = ','.join(sequence)
>>> output
m -1,r 1 1,m 1,r 2 -1,m -1,r 1 -1
**Příklady:**
**1. Příklad**
Pro věž
1 1
2 0
existují čtyři různá řešení o nejmenším počtu kroků 2. Tato řešení jsou:
- m 1,r 0 1
které vede na stav
0 1
2 1
- m 1,r 0 -1
které vede na stav
0 1
2 1
- m 1,r 1 1
které vede na stav
1 0
1 2
- m 1,r 1 -1
které vede na stav
1 0
1 2
Výstupem ''babylon.py'' tedy bude jedno ze čtyř nalezených řešení, například tedy
m 1,r 0 1
**2. Příklad**
Pro věž
3 0 1
2 1 2
existují čtyři různá řešení o nejmenším počtu kroků 3. Tato řešení jsou:
- r 0 1,m -1,r 0 1
které vede na stav
2 1 3
2 1 0
- r 0 1,m -1,r 1 -1
které vede na stav
1 3 2
1 0 2
- r 1 -1,m -1,r 0 1
které vede na stav
1 3 2
1 0 2
- r 1 -1,m -1,r 1 -1
které vede na stav
3 2 1
0 2 1
Výstupem ''babylon.py'' tedy bude jedno ze čtyř nalezených řešení, například tedy
r 0 1,m -1,r 0 1
**3. Příklad**
Pro věž
1 3 3
1 1 2
0 2 2
existuje pouze jedno řešení o nejmenším počtu kroků 7. Toto řešení je:
- r 0 -1,m 1,m 1,r 0 -1,m -1,m -1,r 2 1
které vede na stav
3 1 2
3 1 2
0 1 2
Výstupem ''babylon.py'' tedy
r 0 -1,m 1,m 1,r 0 -1,m -1,m -1,r 2 1
Všechna další možná řešení jsou již délky 8 a více, a tudíž nesprávná.
==== Těžká varianta: Nurikabe ====
**Nurikabe** je japonský logický rébus s poněkud složitějšími pravidly a náročnými řešeními.
Pro každou prázdnou buňku na vstupní desce musíte rozhodnout, zda reprezentuje ostrov a nebo vodu.
U rozhodování se musíte řídit podmínkami pro to, jak má vypadat řešení problému:
- Všechny buňky vody jsou propojeny (tzv. musí tvořit jednu komponentu souvislosti).
- Buňky každého ostrova jsou propojeny.
- Dva ostrovy nejsou propojeny (uvažujeme 4-okolí).
- Každý ostrov má stejný počet buňek jako je zadáno (včetně první zadané buňky).
- Neexistuje blok buněk o velikosti 2x2, který je vyplněný vodou.
Doporučujeme si rébus vyzkoušet zde: ''https://www.logicgamesonline.com/nurikabe/''.
**Úkol:** Napište program ''nurikabe.py'', který najde řešení zadaného problému.
**Vstup:**
* 2D matice o rozměrech ''M x N'', reprezentujíci problém.
* Hodnoty v matici reprezentují:
* ''-1'': prázdno (je nutno kompletně nahradit),
* ''0'': voda (doplňujete vy, na vstupu se nevyskytuje),
* ''1, 2, ...'': ostrov, kde hodnota určuje velikost příslušného ostrova ve finální konfiguraci. Tuto hodnotu nelze v matici posunout (tj. ostrovy neplují). Na vstupu se vyskytuje pouze jedna buňka ostrova, zbytek je nutno doplnit.
* Matice bude programu předána v argumentu programu, využijte tedy ''sys.argv[1]''.
* Příklad problému 3x3, který obsahuje 2 ostrovy, oba o očekávané velikosti 3:
-1 -1 -1
3 -1 3
-1 -1 -1
**Výstup:**
* Řešení zadaného problému vytištěné na standardní výstup. Pro náš příklad výše je očekávaný výstup Vašeho programu:
3 0 3
3 0 3
3 0 3
* Všimněte si, že v řešení:
* jsou nahrazeny všechna prázdná místa za vodu nebo ostrov,
* všechna voda ''0'' propojena,
* neexistuje vodní 2x2 blok a
* oba ostrovy mají velikost 3.
* Tip: 2D matici lze vypsat do očekávaného tvaru například touto funkcí:
def printMat(mat)
print('\n'.join([' '.join([str(i) for i in row]) for row in mat ]))
**Poznámky:**
* Tvary ostrovů nejsou předem známy.
* Existuje pouze jedno unikátní řešení.
* Můžete předpokládat, že každý zadaný problém má řešení.
* Tip: využijte známých algoritmů pro prohledávání stavového prostoru.
* Tip2: Naprogramujte [[https://www.logicgamesonline.com/nurikabe/tutorial.html|pravidla]], která Vám umožní vyřešit velké množství políček přímo, u zbytku vyzkoušejte obě možnosti (řeka, ostrov) z nichž jedna vede k řešení.
**Bodování:**
* BRUTE obsahuje test 4 náročností. Za vyřešení nejjednodušší varianty dostanete 1.5b a za další varianty (střední, těžká, velmi těžká) pak lze nasbírat zbytek do 3b (0.7b, 0.6b, 0.2b).
**Příklady:**
**1. Příklad**
Problém
-1 2 -1
-1 -1 -1
-1 -1 -1
má jednoznačné řešení
0 2 0
0 2 0
0 0 0
**2. Příklad**
Problém
-1 -1 -1 1
-1 -1 -1 -1
-1 -1 2 -1
4 -1 -1 -1
má jednoznačné řešení
4 0 0 1
4 0 2 0
4 0 2 0
4 0 0 0
**3. Příklad**
Problém
-1 2 -1 -1 -1
-1 -1 -1 1 -1
-1 -1 -1 -1 -1
-1 2 -1 -1 -1
-1 -1 -1 6 -1
má řešení
2 2 0 0 0
0 0 0 1 0
0 2 0 0 6
0 2 0 6 6
0 0 6 6 6
**3. Příklad (těžký)**
Problém
-1 -1 -1 -1 2 -1 2 -1
5 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
1 -1 -1 -1 3 -1 2 -1
-1 3 -1 -1 -1 1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 3
-1 -1 -1 -1 -1 4 -1 -1
má řešení
5 0 0 0 2 0 2 2
5 5 5 0 2 0 0 0
0 0 5 0 0 0 2 0
1 0 0 3 3 0 2 0
0 3 0 3 0 1 0 0
0 3 0 0 0 0 0 3
0 3 0 4 4 4 0 3
0 0 0 0 0 4 0 3