====== Cvičení 11: Objekty, Halda, Asociativní pole, Stromy ======
===== náplň cvičení =====
==== Quick test 1 ====
==== Objekty ====
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
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())
==== 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í 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
==== Úkol 1: 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]
==== Úkol 2: Karty v haldě ====
* Upravte implementaci haldy tak, aby byla realizována min-halda s kartami ve formátu cvičení 8 příklad 1.
* Vytvořte hladu 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í.
==== Úkol 3: 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
===== 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];
...
}
===== Domácí úkol =====
==== Lehká varianta:====
* Napište program **adam7.py**, který podle algoritmu [[ https://en.wikipedia.org/wiki/Adam7_algorithm | adam7 ]] vykreslí černobílý obrázek přenášený po síti (kódování Adam7 je využito ve formátu obrázků [[ https://en.wikipedia.org/wiki/Portable_Network_Graphics | png ]] ).
* Program čte ze standardního vstupu dvě řádky:
* první řádka obsahuje dvě čísla oddělená mezerou, počet sloupců a počet řádků obrázku
* všechny rozměry obrázků budou dělitelné 8
* druhá řádka obsahuje pole čísel s hodnotou 0 nebo 1 oddělené mezerou
* zaslaná data mohou být neúplná data o informaci o barvě obrázku
* data jsou od začátku uspořádaná podle algoritmu Adam7
* pokud je dat méně než je rozměr obrázku (sloupce*řádky) tak je potřeba doplnit informaci o barvě pixelů podle:
* 1) barvy nejbližšího definovaného pixelu vlevo
* 2) pokud na řádce není žádný definovaný pixel pak podle barvy nejbližšího definovaného nebo doplněného pixelu nad zkoumaným pixelem
* Výstup - program vytiskne mezeru pro číslo 0 nebo znak '*' pro číslo 1 pro každý pixel obrázku, vždy jednu řádku obrázku na jeden řádek standardního výstupu bez mezer mezi tištěnými znaky.
* Váš program **adam7.py** odevzdejte do odevzdávacího systému jako **HW10.**
== Příklad ==
Vstup (1/16 dat)
24 24
0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 0 0 0 0
má výstup:
****
****
****
****
**** ****
**** ****
**** ****
**** ****
**** ****
**** ****
**** ****
**** ****
****
****
****
****
Vstup (1/8 dat):
24 24
0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 0 0 0 0 1 0 0 1 0 0 1 1 0 0 0 0 1 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0
má výstup:
** **
** **
** **
** **
** ** **
** ** **
** ** **
** ** **
** ** **
** ** **
** ** **
** ** **
** ****
** ****
** ****
** ****
** **
** **
** **
** **
** **
** **
** **
** **
Vstup (1/4 dat):
24 24
0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 0 0 0 0 1 0 0 1 0 0 1 1 0 0 0 0 1 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0
má výstup:
** **
** **
** ** ** **
** ** ** **
** ** **
** ** **
** ** **
** ** **
** ** **
** ** **
**
**
** ****
** ****
**** **
**** **
** **
** **
** **** **
** **** **
** **
** **
** **
** **
Vstup (1/2 dat):
24 24
0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 0 0 0 0 1 0 0 1 0 0 1 1 0 0 0 0 1 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 1 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 1 1 0 0 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0
má výstup:
* * * * *
* * * * *
* * * * * *
* * * * * *
* * * * * * *
* * * * * * *
* ** ** *
* ** ** *
** * * **
** * * **
* *
* *
*** ***
*** ***
** * * **
** * * **
* * * * *
* * * * *
** **** * *
** **** * *
* * * * * *
* * * * * *
* * * *
* * * *
Vstup (cela data):
24 24
0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 0 0 0 0 1 0 0 1 0 0 1 1 0 0 0 0 1 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 1 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 1 1 0 0 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 1 0 1 0 0 0 1 0 0 0 0 1 1 0 0 0 1 0 0 0 1 0 0 1 1 1 1 0 0 1 0 0 0 1 0 0 0 1 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0 1 1 1 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 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0
má výstup:
* * * * *
* * * * *
* * * * * *
* * * * * * **
* * * * * * *
* * **** * *
* ** ** *
** * * * * *
** * * **
* * * **
* *
*** * *
*** ***
* * *
** * * **
** * **
* * * * *
* ** ** *
** **** * *
* * * * * *
* * * * * *
* * * *
* * * *
* * * *
Vstup (1/4 data):
24 8
0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
má výstup:
**
**
******
******
******
******
**
**
Vstup (1/2 data):
24 8
0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 1 1 1 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 1 1 1 0 1 1 0 0 0 0 0 1 1 1 0 0 1 1 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 1 1 1
má výstup:
** * * *
** * * *
***** * * *
***** * * *
***** * * *
***** * * *
** * * *
** * * *
Vstup (cela data):
24 8
0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 1 1 1 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 1 1 1 0 1 1 0 0 0 0 0 1 1 1 0 0 1 1 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 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 0 0 0
má výstup:
** * * *
**** * * *
***** * * *
************************
***** * * *
**** * * *
** * * *
==== Těžká varianta:====
Úkolem je implementovat kompresi obrázku pomocí [[ https://cs.wikipedia.org/wiki/LZ77 | algoritmu LZ77]].
* Program **lz77.py** buď kóduje, nebo dekóduje v závislosti na zadaném obsahu vstupu
* Kódování:
* Vstupní data obsahují pouze znaky ' ' a '*' a čtou se ze standardního vstupu - pro načítání použijte smyčku for line in sys.stdin:
* Nejdříve vstupní data překódujete do [[https://cs.wikipedia.org/wiki/Nibble | Nibble]] (půl bajt), každý nibble je reprezentován jedním hexadecimálním znakem (tj. čísla od '0' do '9' a písmena od 'A' do 'F')
* Algoritmus lz77 bude pracovat nad celým obrázkem, začne s prázdným bufferem.
* Velikost bufferu pro najití opakující se sekvence bude 16 hexadecimálních znaků, maximální délka opakující se sekvence bude 5. Základní jednotka pro vyhledávání opakujících se sekvencí je nibble, jedna hexadecimální hodnota.
* Výstup je bitový řetězec vytištěný v hexadecimálním formátu
* Pokud v bufferu nebude nalezena sekvence, pak se na výstup:
* zapíše bit s hodnotou 0
* a 4 bity daného hexadecimálního znaku (v pořadí od MSB k LSB)
* Pokud v bufferu bude nalezena sekvence o délce více než jeden znak, pak se zakóduje následujícím způsobem:
* zapíše se bit s hodnotu 1
* a zapíší se 4 bity kódující (//offset//) od začátku bufferu (v pořadí od MSB k LSB)
* a zapíší se 2 bity kódující délku sekvence zmenšenou o 2 (//length-2//) (v pořadí MSB, LSB)
* pokud je sekvencí o stejné délce více, vybere se ta s nejmenším offsetem
* Obrázek se na hexadecimální hodnoty převádí tak, že [[https://cs.wikipedia.org/wiki/Nejv%C3%BDznamn%C4%9Bj%C5%A1%C3%AD_bit|MSB (most significant bit)]] je vlevo a [[https://cs.wikipedia.org/wiki/Nejm%C3%A9n%C4%9B_v%C3%BDznamn%C3%BD_bit|LSB (least significant bit)]] je vpravo.
* Počet sloupců obrázku je vždy dělitelný 4
* Příklad převodu řetězce na hexa hodnoty probíhá následovně:
84218421
** * *
C 5
* Výstupní bitový řetězec se převádí na hexadecimální hodnoty obdobně jako obrázek, tedy MSB je vlevo (dříve v řetězci) a LSB je vpravo (později v řetězci).
* Pokud není délka řetězce dělitelná 4, doplní se na konec bitového řetězce 0. Tedy ''11011'' je haxadecimálně ''D8''
* Příklad převodu řetězce ''11000101'' na hexadecimální řetězec 'C5'
84218421
11000101
C 5
* Příklad:
Vstupní obrázek šachovnice o velikosti 12x8 bitů:
** ** **
** ** **
** ** **
** ** **
** ** **
** ** **
** ** **
** ** **
se v prvním kroku zakóduje do hexadecimálních hodnot:
333333CCCCCC333333CCCCCC
Tyto hexadecimální hodnoty se začnou převádět do bitového řetězce podle vyhledávání opakujících se částí v předchozích datech (první pole je buffer posledních maximálně 16 znaků, které již byly zpracovány, druhé pole je aktuálně zpracovávané znaky, jejich prefix hledáme v prvním poli, za bity je výsledek zpracování jednoho znaku, nebo prefixu):
[] [3, 3, 3, 3, 3] - bity 0 0011
[3] [3, 3, 3, 3, 3] - bity 0 0011
[3, 3] [3, 3, 3, 3, 12] - bity 1 0000 00 (offset 0 délka 2 - upravená na 0)
[3, 3, 3, 3] [3, 3, 12, 12, 12] - bity 1 0000 00 (offset 0 délka 2 - upravená na 0)
[3, 3, 3, 3, 3, 3] [12, 12, 12, 12, 12] - bity 0 1100
[3, 3, 3, 3, 3, 3, 12] [12, 12, 12, 12, 12] - bity 0 1100
[3, 3, 3, 3, 3, 3, 12, 12] [12, 12, 12, 12, 3] - bity 1 0110 00 (offset 6 délka 2 - upravená na 0)
[3, 3, 3, 3, 3, 3, 12, 12, 12, 12] [12, 12, 3, 3, 3] - bity 1 0110 00 (offset 6 délka 2 - upravená na 0)
[3, 3, 3, 3, 3, 3, 12, 12, 12, 12, 12, 12] [3, 3, 3, 3, 3] - bity 1 0000 11 (offset 0 délka 5 - upravená na 3)
[3, 3, 3, 3, 3, 12, 12, 12, 12, 12, 12, 3, 3, 3, 3, 3] [3, 12, 12, 12, 12] - bity 1 0100 11 (offset 4 délka 5 - upravená na 3)
[12, 12, 12, 12, 12, 12, 3, 3, 3, 3, 3, 3, 12, 12, 12, 12] [12, 12] - bity 1 0000 00 (offset 0 délka 2 - upravená na 0)
Tento bitový řetězec se převede na hexadecimální symboly jako:
18E040632C58874E00
* Dekódování
* Dekódování probíhá, pokud první řádka vstupu obsahuje pouze hexadecimální znaky (znaky nejsou oddělené mezerou) a druhá řádka obsahuje počet sloupců zakódovaného obrázku
* Celý obrázek je zakódován v jedné řádce vstupu, druhá řádka obsahuje informaci nutnou pro vykreslení obrázku
* Hexadecimální řetězec si rozdělíte na bitový řetězec podle algoritmu kódování a dekódujete, tedy převedete na originální hexadecimální řetězec a ten zobrazíte pomocí znaků ' ' a '*'
* Bitový řetězec začnete zpracovávat a pokud je zpracovávaný bit roven:
* 0 přenesete následující 4 bity do výstupu
* 1 načtete 4 bity posunutí a 2 bity délky, délku zvětšíte o 2 a na výstup si zkopírujete tolik nibble kolik je délka z offset již zpracovaných hexa hodnot
*
=== Příklad ===
* K otestování správné činnosti můžete zkusit rozbalit následující řetězec, který jsme získali kompresí úvodního obrázku:
18E040632C58874E00
12
* Příklad spuštění dekomprese a získání obrázku krysy od Banksyho {{courses:b3b33alp:cviceni:banksy.png?140|}} (odkaz na {{courses:b3b33alp:cviceni:banksy.txt|banksy.txt}}):
python3 lz77.py