Zadanie skúšky z 26.6.2020


V Kocúrkove zorganizovali tanečnú zábavu. Všetky dievčence a mládenci z dediny si prišli zatancovať. Organizátor vymyslel, že na úvod zábavy vytvoria čo najväčší kruh z tanečníkov, pričom každá dvojica vedľa seba stojacich v kruhu sa už navzájom poznala. Z tohto dôvodu organizátor už pri vstupe do sály zistil od každého účastníka jeho zoznam známych. Mohlo sa stať, že A pozná B a pritom B zabudol uviesť A vo svojom zozname známych, takže bude treba s tým počítať (doplniť A do zoznamu B). Pri zostavovaní kruhu môže mať organizátor ešte jednu podmienku navyše: v kruhu by sa mali pravidelne striedať dievčence a mládenci. Našťastie z mena účastníka vieme jednoznačne určiť, či je to dievča alebo mládenec: len mená dievčeniec končia písmenom 'a'.

V reči grafov riešime takýto problém: daný je neorientovaný neohodnotený graf, v ktorom sú tanečníci vo vrcholoch a dva vrcholy sú spojené hranou, keď sa príslušní tanečníci navzájom poznajú. Potom pre daný štartový vrchol treba nájsť čo najdlhší cyklus, ktorý vychádza z tohto vrcholu. Niekedy môže byť daná ešte jedna podmienka na vrcholy cyklu navyše: v cykle nesmú byť vedľa seba dva vrcholy rovnakého typu.

Celý graf je popísaný v textovom súbore takto:

  • každý riadok obsahuje zoznam mien (aspoň 2) oddelených medzerami

  • pre prvé meno v tomto zozname zvyšné mená označujú jeho známych

  • napríklad, ak riadok obsahuje tri mená A B C, označuje to, že osoba A má známych B a C, čo znamená, že aj B má známeho A, aj C má známeho A, ale neznamená to, že B a C sa navzájom poznajú (môžu, ak sú popísaní v niektorom z ďalších riadkov súboru)

Napríklad súbor:

Zuzana Juraj Marek Pavol
Ivan Jana Zuzana Adam Gaba
Gaba Barbora Marek Ivan
Dusan Marek Juraj
Adam Barbora Emil
Jana Emil Pavol Ivan
Klara Pavol Juraj

popisuje graf s 12 vrcholmi, ktoré sú spojené 17 (neorientovanými) hranami.

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

class Zabava:
    def __init__(self, meno_suboru):
        self.zoz = []
        self.tab = []
        ...

    def index(self, meno):
        return None

    def poznaju_sa(self, meno1, meno2):
        return None

    def kruh(self, meno, striedat=False):
        return None

kde metódy:

  • __init__(meno_suboru): prečíta súbor a vytvorí z neho graf pomocou reprezentácie „tabuľka susedností“; do atribútu self.tab priraď dvojrozmernú maticu susedností, ktorá bude obsahovať len 0 a 1; v atribúte self.zoz bude zoznam mien vrcholov presne v tom poradí, v akom sú v dvojrozmernej matici;

  • index(meno): pre zadané meno vráti jeho index v zozname mien (v atribúte self.zoz); ak také meno v zozname neexistuje, metóda vráti None; tento index označuje číslo riadka aj stĺpca pre daný vrchol v matici susedností;

  • poznaju_sa(meno1, meno2): vráti True, ak existuje hrana medzi týmito vrcholmi, inak vráti False; ak meno1 alebo meno2 nie sú vrcholmi grafu, metóda vráti None;

  • kruh(meno, striedat=False): pomocou backtrackingu nájde najdlhší cyklus, ktorý obsahuje vrchol s menom meno; ak má parameter striedat hodnotu True, v cykle sa musia striedať mládenci a dievčence; cyklus vráti v tvare zoznamu (list) mien (reťazcov) dĺžky aspoň 3, pričom platí, že aj prvý a posledný prvok v tomto zozname „sa poznajú“; ak taký cyklus neexistuje, metóda vráti None.

Uvedom si, že počas behu backtrackingu nemá zmysel pokračovať vo vytváraní cyklu, ak sa už našiel taký, ktorý prechádza cez všetky vrcholy (tzv. Hamiltonovská kružnica). Pre graf s väčším počtom hrán to môže výrazne vylepšiť čas behu riešenia.

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

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

if __name__ == '__main__':
    z = Zabava('subor1.txt')
    print('zoznam mien:', z.zoz)
    print('susedia pre meno Ivan:', z.tab[z.index('Ivan')])
    print('kruh pre meno Zuzana:', z.kruh('Zuzana', False))
    print('kruh pre meno Dusan (so striedanim):', z.kruh('Dusan', True))
    print('kruh pre meno Klara (so striedanim):', z.kruh('Klara', True))

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

zoznam mien: ['Adam', 'Juraj', 'Klara', 'Zuzana', 'Emil', 'Dusan', 'Marek',
              'Ivan', 'Barbora', 'Gaba', 'Pavol', 'Jana']
susedia pre meno Ivan: [1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1]
kruh pre meno Zuzana: ['Marek', 'Dusan', 'Juraj', 'Klara', 'Pavol', 'Jana',
                       'Emil', 'Adam', 'Barbora', 'Gaba', 'Ivan', 'Zuzana']
kruh pre meno Dusan (so striedanim): None
kruh pre meno Klara (so striedanim): ['Juraj', 'Zuzana', 'Marek', 'Gaba',
                                      'Ivan', 'Jana', 'Pavol', 'Klara']

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.