Warning
This page is located in archive.

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

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];
...
}

Binární halda

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ů

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

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

Babylonská věž (v ALP):

  • Stejný problém, avšak ne pro věž o rozměrech 6×6, 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 3×3 (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í:
    1. 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)
    2. 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)
    3. 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ě
    4. 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:

  1. m 1,r 0 1
    které vede na stav
    0 1
    2 1
  2. m 1,r 0 -1
    které vede na stav
    0 1
    2 1
  3. m 1,r 1 1
    které vede na stav
    1 0
    1 2
  4. 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:

  1. r 0 1,m -1,r 0 1
    které vede na stav
    2 1 3
    2 1 0
  2. r 0 1,m -1,r 1 -1
    které vede na stav
    1 3 2
    1 0 2
  3. r 1 -1,m -1,r 0 1
    které vede na stav
    1 3 2
    1 0 2
  4. 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:

  1. 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:

  1. Všechny buňky vody jsou propojeny (tzv. musí tvořit jednu komponentu souvislosti).
  2. Buňky každého ostrova jsou propojeny.
  3. Dva ostrovy nejsou propojeny (uvažujeme 4-okolí).
  4. Každý ostrov má stejný počet buňek jako je zadáno (včetně první zadané buňky).
  5. Neexistuje blok buněk o velikosti 2×2, 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 3×3, 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í 2×2 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 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

courses/b3b33alp/cviceni/t11.txt · Last modified: 2023/12/10 21:04 by petrapa6