Zadanie skúšky 28.6.2017

Labyrint je štvorcová sieť veľkosti m x n a poznáme, medzi ktorými políčkami siete sú steny, teda sa tadiaľ nebude dať prechádzať. Na niektorých políčkach sa nachádzajú mince. Úlohou je nájsť ľubovoľnú (stačí jednu) trasu zo štartového políčka, ktorá pozbiera všetky mince. Treba dať pozor, aby sa na žiadne políčko nestúpilo 2-krát.

Labyrint reprezentujte ako graf, v ktorom sú políčka labyrintu vrcholy grafu a hrany sú priechody medzi políčkami. Uvedomte si, že každý vrchol môže mať maximálne štyroch susedov (nemusí mať žiadneho).

Súbor má tvar:

  • prvý riadok obsahuje dve čísla: počet riadkov a počet stĺpcov labyrintu
  • ďalej nasledujú riadky so stenami a mincami (v ľubovoľnom poradí)
  • ak riadok obsahuje iba 2 čísla, označuje to políčko s mincou (riadok, stĺpec), riadky aj stĺpce číslujeme o 0
  • inak riadok obsahuje postupnosť aspoň dvoch políčok (riadok1, stĺpec1, riadok2, stĺpec2, …) - touto postupnosťou definuje nejaké steny v labyrinte: stena je medzi prvý a druhým políčkom, aj druhým a tretím, … atď.

Zadefinujte triedu Labyrint:

class Labyrint:
    class Vrchol:
        def __init__(self, riadok, stlpec):
            self.sus = []      # pole susedov, susedia su typu Vrchol
            self.poloha = riadok, stlpec
            self.minca = False
        def __repr__(self):
            return '<{},{}>'.format(*self.poloha)

    def __init__(self, meno_suboru):
        self.g = []           # pole vrcholov grafu – obsahuje objekty typu Vrchol
        ...

    def daj_vrchol(self, riadok, stlpec):
        return ...

    def hrana(self, riadok1, stlpec1, riadok2, stlpec2):
        return False

    def zmen_mince(self, *pole):
        ...

    def start(self, riadok, stlpec):
        return []

kde

  • vnorená definícia triedy Vrchol má už zadefinované nejaké metódy aj atribúty – tieto atribúty využite pre reprezentáciu grafu; atribút sus bude obyčajné pole (list), ktoré bude obsahovať zoznam susediacich vrcholov, teda prvkami tohto poľa budú opäť objekty typu Vrchol;
  • metóda __init__(meno_suboru): prečíta súbor a vytvorí z neho graf: atribút g bude obsahovať všetky vrcholy grafu, teda objekty typu Vrchol; pre atribút g si môžete zvoliť buď obyčajné pole vrcholov (list), alebo dvojrozmerné pole vrcholov (list of list);
  • metóda daj_vrchol(riadok, stlpec): vráti referenciu (typ Vrchol) na príslušný vrchol grafu, ktorý reprezentuje zadané políčko;
  • metóda hrana(self, riadok1, stlpec1, riadok2, stlpec2): vráti True alebo False podľa toho, či tieto dve políčka susedia a nemajú medzi sebou stenu;
  • metóda zmen_mince(*pole): parameter pole je postupnosť (list alebo tuple) dvojíc (riadok stĺpec); metóda zmení na všetkých zadaných políčkach to, či sa na nich nachádza minca: ak na políčku bola minca, odstráni ju, inak na políčko umiestni mincu;
  • metóda start(riadok, stlpec): pomocou backtrackingu hľadá správnu trasu; metóda vráti postupnosť navštívených políčok (zrejme prvé políčko v tejto postupnosti bude (riadok, stĺpec)); ak trasa, ktorá prejde cez všetky políčka s mincami sa skonštruovať nedá, metóda vráti prázdny zoznam []; testovač môže zavolať túto metódu viac krát s rôznymi štartovými políčkami.

Napr. pre takéto zadanie labyrintu:

_images/35_1.png
3 3
1 0 1 1
2 2
0 2
1 2 0 2

tento test:

if __name__ == '__main__':
    lab = Labyrint('subor1.txt')
    for param in (1, 1, 2, 1), (0, 1, 2, 0):
        print('hrana{} = {}'.format(param, lab.hrana(*param)))
    v = lab.daj_vrchol(1, 0)
    print('vrchol:', v, 'susedia:', v.sus, 'minca:', v.minca)
    v = lab.daj_vrchol(0, 2)
    print('vrchol:', v, 'susedia:', v.sus, 'minca:', v.minca)
    print(lab.start(0, 0))
    print(lab.start(0, 2))
    lab.zmen_mince((2, 2))
    print(lab.start(0, 0))

vypíše:

hrana(1, 1, 2, 1) = True
hrana(0, 1, 2, 0) = False
vrchol: <1,0> susedia: [<0,0>, <2,0>] minca: False
vrchol: <0,2> susedia: [<0,1>] minca: True
[(0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (1, 2), (1, 1), (0, 1), (0, 2)]
[(0, 2), (0, 1), (1, 1), (1, 2), (2, 2)]
[(0, 0), (0, 1), (0, 2)]

Prvé z riešení nájde túto trasu:

_images/35_2.png

Z úlohového servera L.I.S.T. si stiahnite kostru programu skuska.py. Mali by ste dodržať tieto vlastnosti programu:

  • odkontroluje, či sa vo vašom module nachádzať len jedna definícia triedy Labyrint s vnorenou triedou Vrchol (do existujúcich tried môžete pridávať vlastné atribúty a metódy)
  • bude kontrolovať štruktúru vami vytvoreného grafu (atribút g) s rôznymi textovými súbormi, ktoré si môžete stiahnuť z L.I.S.T.u

Aby ste mohli spúšťať skúškové testy, riešenie (bez ďalších súborov) odovzdajte na úlohový server https://list.fmph.uniba.sk/. Testy postupne na všetkých testovacích súboroch preverujú vlastnosti vašich algoritmov, pri prvej chybe sa testovanie s daným súborom preruší a ďalšie časti sa netestujú:

  • 50% bodov za vytvorenie grafu
  • 50% bodov za algoritmus hľadania trasy v grafe
  • pozrite si testovacie dáta v súboroch 'subor1.txt', 'subor2.txt', 'subor3.txt', …, ktoré bude používať testovač

Praktická časť končí o 11:00 a skúška ďalej pokračuje od 12:00 vyhodnotením v kancelárii m162.