Skúška 2023/2024 - Variant D - 27.6.2024


Turistická kancelária organizuje prehliadky po starom meste a maximálne sa snaží vychádzať v ústrety požiadavkám turistov. Turisti si môžu vybrať ľubovoľné pamiatky a sprievodca s nimi prejde zvolenú prehliadku, pričom kancelária si účtuje jednotný poplatok za každú navštívenú pamiatku. Majiteľ kancelárie je zvedavý, aké rôzne prehliadky sa dajú zostaviť, ak prehliadka začne aj skončí na tom istom mieste a prejde cez presne zadaný počet pamiatok.

Mapu starého mesta máme uloženú v tvare neorientovaného grafu, v ktorom vrcholy reprezentujú pamiatky a hrany sú ulice. Program pre zadaný štartový vrchol a dĺžku trasy nájde všetky cykly. Cyklom je taká cesta v grafe, ktorá začína aj končí v tom istom vrchole a pritom prechádza len cez navzájom rôzne vrcholy.

Graf je zadaný v textovom súbore, ktorý má takúto štruktúru:

  • každý riadok popisuje jeden vrchol a skladá sa z jednej alebo viacerých dvojíc celých čísel, ktoré sú uzavreté v okrúhlych zátvorkách;

  • prvá dvojica čísel označujú súradnice pamiatky na mape (bude to pre nás meno vrcholu);

  • za týmito súradnicami nasledujú súradnice ďalších pamiatok, ktoré sú spojené s danou pamiatkou ulicou;

  • graf je neorientovaný, preto, ak má pamiatka A susednú pamiatku B, tak potom aj B susedí s A – možno to bude treba do grafu doplniť.

Zadefinuj triedu:

class StareMesto:
    class Vrchol:
        def __init__(self):
            self.sus = set()

    def __init__(self, meno_suboru):
        self.g = {}
        ...

    def ulice(self):
        ...

    def vsetky(self, start, dlzka):
        ...
        return set()

kde

  • vnorená definícia triedy Vrchol má atribút sus, ktorý bude obsahovať množinu (typ set) všetkých susediacich vrcholov (teda ich mien), to znamená, že sus je množina dvojíc (tuple) celých čísel;

  • metóda __init__(meno_suboru): prečíta súbor a vytvorí z neho graf: atribút g (typu dict), v ktorom kľúčmi budú mená vrcholov (teda polohy na mape, t.j. dvojice (tuple) celých čísel), ako príslušné hodnoty budú vrcholy grafu, teda objekty typu Vrchol;

  • metóda ulice(): vráti generátor všetkých ulíc v meste, pričom každá ulica je v tvare dvojica (tuple) dvoch vrcholov (každý vrchol je opäť tuple); keďže graf je neorientovaný, každá ulica sa vo vygenerovanej postupnosti objaví len raz, buď ako (A, B) alebo (B, A);

  • metóda vsetky(start, dlzka): pomocou backtrackingu vyhľadá všetky cykly zadanej dĺžky, ktoré začínaju (a končia) v zadanom vrchole start; metóda vráti množinu (set) všetkých takýchto cyklov, každý z nich ako n-ticu (tuple) mien vrcholov (teda dvojíc čísel); ak neexistuje žiaden cyklus, ktorý by spĺňal tieto podmienky, metóda vráti prázdnu množinu; testovač zavolá túto metódu viac krát s rôznymi štartovými vrcholmi a aj dĺžkami.

Napríklad, pre takéto zadanie grafu:

../../_images/lsk2024d.png
(70, 10) (40, 10) (70, 40)
(10, 10) (10, 40) (40, 10)
(10, 40) (10, 10) (40, 40)
(40, 10)
(40, 40) (10, 40) (40, 10) (70, 40)
(70, 40) (70, 10) (40, 40)

tento test:

if __name__ == '__main__':
    g = StareMesto('subor1.txt')
    print(*g.ulice(), sep='\n')
    print(g.vsetky((70, 10), 3))
    print(g.vsetky((10, 40), 4))
    print(g.vsetky((40, 40), 4))

vypíše napríklad:

((70, 10), (70, 40))
((10, 10), (40, 10))
((10, 10), (10, 40))
((10, 40), (40, 40))
((40, 10), (70, 10))
((40, 10), (40, 40))
((40, 40), (70, 40))
set()
{((10, 40), (40, 40), (40, 10), (10, 10), (10, 40)), ((10, 40), (10, 10), (40, 10), (40, 40), (10, 40))}
{((40, 40), (40, 10), (70, 10), (70, 40), (40, 40)), ((40, 40), (70, 40), (70, 10), (40, 10), (40, 40)), ((40, 40), (10, 40), (10, 10), (40, 10), (40, 40)), ((40, 40), (40, 10), (10, 10), (10, 40), (40, 40))}

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

Testy postupne na všetkých testovacích súboroch preverujú vlastnosti tvojich algoritmov, pri prvej chybe sa testovanie s daným súborom preruší a ďalšie časti sa netestujú:

  • 35% bodov za vytvorenie grafu

  • 65% bodov za algoritmus hľadania cyklu v grafe

Tvoj odovzdaný program musí začínať tromi riadkami komentárov:

# skuska 2023/2024 variant D
# autor: Janko Hraško
# datum: 27.6.2024