Zadanie skúšky z 3.7.2020


Máme trocha upravenú počítačovú hru na motívy Pet Detective: hrá sa v štvorcovej sieti, ktorá zobrazuje plánik mestečka. Na niektorých políčkach sú domčeky pre zvieratká, na niektorých iných sú zase stratené zvieratká. Úlohou záchrancu, ktorý sa pohybuje po mestečku v aute, je zozbierať všetky stratené zvieratká a odviesť ich do príslušných domčekov (pre každé zvieratko máme určený práve jeden domček). Záchranca to bude mať o to ťažšie, že pri presúvaní sa v mestečku (z políčka na políčko) môže na každé stúpiť maximálne raz. Zrejme, keď prejde cez políčko s domčekom a nemá naložené príslušné zvieratko, na toto políčko sa už nikdy viac nedostane, aj keby neskôr toto zvieratko naložil. V štvorcovej sieti môžu byť niektoré políčka nepriechodné a záchranca ich musí obchádzať.

V reči grafov riešime takýto problém: daný je neorientovaný neohodnotený graf, v ktorom sú v niektorých vrcholoch domčeky (označujeme ich veľkými písmenami od 'A' po 'Z') a v niektorých vrcholoch sú zvieratká (označujeme ich malými písmenami od 'a' po 'z'). Úlohou je nájsť čo najkratšiu trasu (od nejakého štartového vrcholu), ktorý prejde cez všetky vrcholy so zvieratkami a domčekmi, ale v správnom poradí: cez domček prejde len vtedy, keď už predtým prešiel cez vrchol so zvieratkom. Cez žiaden vrchol neprejde viackrát.

Celý graf (štvorcová sieť s mestečkom) je popísaný v textovom súbore takto:

  • každý riadok súboru popisuje jeden riadok štvorcovej siete (zrejme všetky riadky siete majú rovnakú dĺžku);

  • každý znak v riadku reprezentuje jedno políčko siete, teda jeden vrchol grafu;

  • malé písmena (od 'a' po 'z') reprezentujú zvieratká;

  • veľké písmena (od 'A' po 'Z') reprezentujú domčeky;

  • znaky '#' reprezentujú nepriechodné políčka (nie sú to vrcholy grafu);

  • znaky '.' reprezentujú voľné políčka;

  • pre každý domček v ploche existuje jediné zvieratko s príslušným písmenom (pre domček 'A' zvieratko 'a', pre domček 'B' zvieratko 'b', …) a platí to aj naopak: pre každé zvieratko existuje jediný príslušný domček.

Napríklad súbor:

zH.h
..Z.
...K
k...

popisuje graf so 16 vrcholmi, v ktorých sú popísané tri domčeky a tri zvieratká. Graf neobsahuje žiadne nepriechodné políčka.

Riešenie zapíš do triedy Zachrana s týmito metódami:

class Zachrana:
    def __init__(self, meno_suboru):
        ...

    def zvierata(self):
        return set()

    def domceky(self):
        return set()

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

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

kde metódy:

  • __init__(meno_suboru): prečíta súbor a vytvorí z neho graf pomocou ľubovoľnej reprezentácie (stačí aj ako dvojrozmerná tabuľka znakov);

  • zvierata(): vráti množinu písmen všetkých zvieratiek v ploche;

  • domceky(): vráti množinu písmen všetkých domčekov v ploche;

  • susedne(riadok, stlpec): vráti zoznam pozícií (dvojíc (riadok, stĺpec)) susediacich vrcholov;

  • start(riadok, stlpec): pomocou backtrackingu nájde najkratšiu trasu, ktorá prejde cez všetky vrcholy so zvieratkami aj s domčekmi, pritom v tejto trase bude vrchol so zvieratkom ešte pred príslušným vrcholom domčeka; ak riešenie neexistuje, metóda vráti prázdny zoznam; môžeš počítať s tým, že záchranca (pozícia (riadok, stĺpec)) vždy začína na prázdnom políčku.

Uvedom si, že počas behu backtrackingu nemá zmysel pokračovať vo vytváraní trasy, ak sa už našla kratšia, ako momentálna dĺžka cesty.

Môžeš si dodefinovať aj ďalšie pomocné metódy. Ak chceš definovať nejaké ďalšie pomocné triedy, zapíš ich ako vnorené do triedy Zachrana.

Program môžeš testovať, napríklad takto:

if __name__ == '__main__':
    z = Zachrana('subor1.txt')
    print('zvierata =', z.zvierata())
    print('domceky =', z.domceky())
    for r, s  in (0, 2), (2, 1), (3, 0):
        print(f'susedne pre ({r}, {s}) =', z.susedne(r, s))
    for r, s  in (3, 1), (1, 3), (2, 2), (1, 1):
        print(f'riesenie pre ({r}, {s}) =', z.start(r, s))

a pre vyššie uvedený textový súbor by mal vypísať (možno s pozmenenými poradiami):

zvierata = {'h', 'k', 'z'}
domceky = {'K', 'H', 'Z'}
susedne pre (0, 2) = [(1, 2), (0, 1), (0, 3)]
susedne pre (2, 1) = [(1, 1), (3, 1), (2, 0), (2, 2)]
susedne pre (3, 0) = [(2, 0), (3, 1)]
riesenie pre (3, 1) = [(3, 1), (3, 0), (2, 0), (2, 1), (2, 2), (2, 3), (1, 3),
                       (0, 3), (0, 2), (0, 1), (0, 0), (1, 0), (1, 1), (1, 2)]
riesenie pre (1, 3) = [(1, 3), (0, 3), (0, 2), (0, 1), (0, 0), (1, 0), (2, 0),
                       (3, 0), (3, 1), (2, 1), (1, 1), (1, 2), (2, 2), (2, 3)]
riesenie pre (2, 2) = [(2, 2), (2, 1), (2, 0), (3, 0), (3, 1), (3, 2), (3, 3),
                       (2, 3), (1, 3), (0, 3), (0, 2), (0, 1), (0, 0), (1, 0),
                       (1, 1), (1, 2)]
riesenie pre (1, 1) = []

Z úlohového servera L.I.S.T. si stiahni kostru programu skuska.py. Pozri si testovacie dáta v súboroch 'subor1.txt', 'subor2.txt', 'subor3.txt', …, ktoré bude používať testovač. Aby si mohol spúšťať skúškové testy, program ulož do súboru skuska.py. Riešenie (bez dátových súborov) odovzdaj na úlohový server https://list.fmph.uniba.sk/. Celkovo môžeš získať 60 bodov.

Praktická časť končí o 16:30.