Skúška 2023/2024 - Variant A - 30.5.2024


Podmorská výskumná stanica sa skladá z viacerých modulov, ktoré sú nejako pospájané prechodovými tunelmi. Každý takýto modul má zásoby kyslíka a potravín len na niekoľko dní prežitia a preto si výskumníci musia dobre zvážiť, v akom poradí budú tieto moduly obývať. Predpokladáme, že každý modul, v ktorom výskumníci bývali, sa po ich odchode automaticky uzamkne a nedá sa už do neho znovu vojsť - toto platí pre všetky moduly okrem štartového, ktorý bude slúžiť ako únikový pre ukončenie celej expedície a cez neho sa dostanú opäť na povrch.

Úlohou bude pre zadaný štartový modul navrhnúť také poradie modulov, v ktorých budú postupne výskumníci prebývať, ktoré im zabezpečí čo najdlhšie trvajúcu podmorskú expedíciu. Zrejme prvý a posledný modul v tomto poradí bude rovnaký a teda štartový.

V súbore máme informácie o moduloch a prechodových tuneloch. Meno každého modulu začína jedným alebo viac písmenami a je ukončené celým číslom, ktoré pre tento modul vyjadruje počet dní na prežitie. Napríklad, abc42 označuje meno modulu, v ktorom sa dá prežiť 42 dní. Všetky moduly majú rôzne mená. V súbore sú informácie v tvare dvojíc mien modulov, napríklad:

abc42-abc11
xy37-abc11
a42-abc42

Zadefinuj metódy triedy Expedicia:

class Expedicia:
    def __init__(self, meno_suboru):
        self.m = []
        self.g = []
        ...

    def start(self, modul):
        ...
        return ...

    def zablokuj(self, *moduly):
        ...

    def __getitem__(self, modul):
        return ...

Metódy:

  • __init__(meno_suboru) prečíta zadaný textový súbor a vytvorí reprezentáciu neorientovaného neohodnoteného grafu pomocou tabuľky susedností (atribút g bude dvojrozmerný zoznam hodnôt True a False), pričom poradie vrcholov v tomto grafe bude uložené v atribúte m (typu list); okrem týchto dvoch atribútov nepoužívaj žiadne ďalšie štruktúrované atribúty (typu list, tuple, dict) - povolené sú len pomocné atribúty typu množina, resp. lokálne premenné ľubovoľných typov

  • start(modul) nájde cyklus v grafe (začína aj končí v zadanom module), ktorý umožní čo najdlhšie prebývanie v moduloch (maximálny súčet dní); ak je takýchto cyklov viac, metóda vráti ľubovoľný z nich; ak bol štartový modul zrušený, metóda vráti [], ak je v grafe tento štartový vrchol izolovaný, metóda vráti [modul]; napríklad, aj takýto cyklus môže byť korektným riešením: [modul, modul1, modul]

  • zablokuj(*moduly) nejako si označí vrcholy, ktoré by sa nemali používať, lebo sa zatopili vodou; toto zablokovanie bude fungovať len pre najbližšie volanie metódy start() a hneď potom sa tieto moduly odblokujú

  • __getitem__ vráti číselnú informáciu o počte dní pre tento modul, napríklad pre abc42 vráti celé číslo 42

Testovač môže spúšťať metódu start() viackrát s rôznymi štartovými modulmi, pripadne s rôzne zablokovanými modulmi.

Napríklad, pre takéto zadanie grafu:

a12-b15
b15-d18
c23-b15
d18-c23
d18-e15
e15-a12

takýto test:

if __name__ == '__main__':
    e = Expedicia('subor1.txt')
    print('moduly =', e.m)
    for m1, m2 in ('e15', 'd18'), ('e15', 'c23'):
        i1, i2 = e.m.index(m1), e.m.index(m2)
        print(f'tunel z {m1!r} do {m2!r} =', e.g[i1][i2])
    print("e['c23'] =", e['c23'])
    print(e.start('a12'))
    e.zablokuj('c23')
    print(e.start('a12'))
    e.zablokuj('c23')
    print(e.start('d18'))
    e.zablokuj('a12')
    print(e.start('d18'))
    e.zablokuj('b15')
    print(e.start('d18'))
    e.zablokuj('b15', 'e15')
    print(e.start('a12'))
    e.zablokuj('d18')
    print(e.start('d18'))

vypíše, napríklad:

moduly = ['a12', 'd18', 'e15', 'c23', 'b15']
tunel z 'e15' do 'd18' = True
tunel z 'e15' do 'c23' = False
e['c23'] = 23
['a12', 'e15', 'd18', 'c23', 'b15', 'a12']
['a12', 'e15', 'd18', 'b15', 'a12']
['d18', 'e15', 'a12', 'b15', 'd18']
['d18', 'c23', 'b15', 'd18']
['d18', 'c23', 'd18']
['a12']
[]

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

  • Nemeň mená už zadaných atribútov (metód a premenných).

  • Do existujúcej triedy môžeš pridávať vlastné atribúty a metódy (okrem typu list, tuple a dict).

  • Pri testovaní riešenia sa bude kontrolovať aj štruktúra vytvoreného grafu.

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

  • 40% bodov za vytvorenie grafu

  • 40% bodov za algoritmus hľadania maximálneho cyklu

  • 20% bodov za hľadanie trasy, ktorá bude bez zablokovaných vrcholov

  • pozri si testovacie dáta v súboroch 'subor1.txt', 'subor2.txt', 'subor3.txt', …, ktoré bude používať testovač

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

# skuska 2023/2024 variant A
# autor: Janko Hraško
# datum: 30.5.2024