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