1. tréningové zadanie - skúška z 4.6.2018

Usilovný ježko

Usilovný ježko behá po chodníkoch záhradky a na svoj pichľavý chrbát zbiera všetky kusy ovocia, ktoré pri tom nájde. Lenže na chrbát sa toho veľa nezmestí, preto sa rozhodol, že z každého druhu ovocia bude brať len po jednom kuse. Keďže je ale dosť chamtivý, nezvládne prejsť okolo ovocia a nezobrať ho. Aby sme ježka netrápili, zostavíme mu takú trasu, aby prešiel okolo všetkých typov ovocia ale popri každom druhu len raz. Ešte bude treba dodržať to, aby neprešiel po žiadnom chodníku viac ako raz.

Mapa záhradky tvorí neorientovaný ohodnotený graf, v ktorom hrany reprezentujú chodníky a vrcholy sú križovatky, kde sa chodníky rozvetvujú. Na niektorých chodníkoch sa môže nachádzať jeden kus nejakého ovocia (chodník môže byť aj bez ovocia). Program potom pre zadaný štartový vrchol nájde ľubovoľnú trasu, ktorou sa vyzbierajú všetky druhy ovocia a pritom neprejde po žiadnom chodníku viackrát. Niektorý druh ovocia sa môže nachádzať na viacerých chodníkoch, vtedy nájdená trasa prejde len cez jeden z týchto chodníkov.

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

  • každý riadok popisuje jeden chodník ako dvojicu vrcholov, na ktorých sa môže nachádzať jeden kus ovocia nejakého druhu;

  • vrcholy (križovatky chodníkov) sú znakové reťazcom (napr. '3', 'v1', 'abc'), ovocie je označené tiež nejakým reťazcom (napr. 'a', 'jablko', '7');

  • ak sa na chodníku nenachádza žiadne ovocie, riadok súboru obsahuje len 2 mená vrcholov;

  • ak sa na chodníku nachádza nejaké ovocie, v riadku súboru sú okrem dvoch mien vrcholov aj meno ovocia a to v poradí: prvý vrchol, ovocie, druhý vrchol;

  • graf je neorientovaný, preto, ak je vrchol A spojený chodníkom s B, tak potom aj vrchol B susedí s vrcholom A, zrejme to platí aj pre ovocie – možno to budete musieť do grafu dodefinovať.

Zadefinujte triedu Zahradka:

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

    def vrcholy(self):
        return ()             # vrati mnozinu alebo postupnost vrcholov

    def hrana(self, v1, v2):
        return None           # vrati retazec alebo None

    def typy_ovocia(self):
        return ()             # vrati mnozinu alebo postupnost mien ovocia

    def start(self, v1):
        return []             # vrati postupnost vrcholov cesty alebo []

kde

  • metóda __init__(self, meno_suboru): prečíta súbor a vytvorí z neho neorientovaný ohodnotený graf; zvoľte si ľubovoľnú reprezentáciu grafu, pričom si môžete zadefinovať aj vlastné podtriedy, napr. podtriedu Vrchol;

  • metóda vrcholy(self): vráti zoznam mien všetkých vrcholov grafu ako množinu alebo postupnosť (list alebo tuple);

  • metóda typy_ovocia(self): vráti zoznam mien všetkých druhov ovocia, ktoré sa nachádzajú v grafe; tento zoznam metóda vráti ako množinu alebo postupnosť (list alebo tuple);

  • metóda hrana(self, v1, v2): vráti hodnotu na hrane z vrcholu v1 do vrcholu v2; ak takáto hrana neexistuje, metóda vráti None, inak vráti meno ovocia, resp. prázdny reťazec (ak na hrane nie je žiadne ovocie);

  • metóda start(self, v1): pomocou backtrackingu nájde ľubovoľnú cestu, ktorá prejde cez každý typ ovocia práve raz a po žiadnej hrane grafu neprejde viackrát (výsledok bude typu list); ak takáto cesta neexistuje, metóda vráti [ ].

Napr. pre takéto zadanie grafu:

5 d 6
1 4
4 a 2
3 a 2
1 c 2
3 4
4 5
1 3
5 b 3

tento test:

if __name__ == '__main__':
    z = Zahradka('subor1.txt')
    for v1, v2 in ('3','2'), ('2','3'), ('5','4'), ('2','6'), ('5','1'):
        print(f'hrana({v1!r}, {v2!r}) = {z.hrana(v1, v2)!r}')
    print('typy ovocia =', z.typy_ovocia())
    for v1 in sorted(z.vrcholy()):
        print(f'trasa z {v1!r}:', z.start(v1))

vypíše napr.:

hrana('3', '2') = 'a'
hrana('2', '3') = 'a'
hrana('5', '4') = ''
hrana('2', '6') = None
hrana('5', '1') = None
typy ovocia = {'c', 'b', 'a', 'd'}
trasa z '1': ['1', '4', '2', '1', '3', '5', '6']
trasa z '2': []
trasa z '3': ['3', '2', '1', '4', '3', '5', '6']
trasa z '4': ['4', '1', '2', '4', '3', '5', '6']
trasa z '5': ['5', '4', '1', '2', '4', '3', '5', '6']
trasa z '6': ['6', '5', '4', '1', '2', '4', '3', '5']

Uvedomte si, že ak existuje viac ciest štartujúcich z nejakého zadaného vrcholu, backtracking môže vrátiť ľubovoľnú z nich.

Z úlohového servera L.I.S.T. si stiahnite kostru programu skuska.py. Pozrite si testovacie dáta v súboroch 'subor1.txt', 'subor2.txt', 'subor3.txt', …, ktoré bude používať testovač. Aby ste mohli spúšťať skúškové testy, program uložte do súboru skuska.py. Riešenie (bez dátový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ú:

  • 42% bodov za vytvorenie grafu

  • 58% bodov za algoritmus hľadania cesty v grafe