PALMA junior
Úloha o stavebných povoleniach

Autorské riešenie
[stiahni py]

• Počet riešiteľov: 10 / 11 = 91 %

• Úspešnosť riešenia: 5,5 / 7 = 76 %

Našou úlohou je zistiť, či pre zoznam povolení a ich predpokladov je možné získať vopred určené povolenie. Pozrime sa najskôr na to, ako zoznam povolení interpretovať. Na základe zoznamu:

[['B2', 'C1', 'B1'], ['C1', 'B2'], ['C1']]

vieme povedať:

• z prvého podzoznamu

  • ak chceme získať povolenie B1, musíme najskôr získať povolenia B2 a C1

• z druhého podzoznamu:

  • ak chceme získať povolenie B2, musíme najskôr získať povolenie C1

• z tretieho podzoznamu:

  • povolenie C1 vieme získať priamo bez potreby nejakých iných, predchádzajúcich povolení.

Ak by sme túto úlohu riešili prakticky, bez počítača, zrejme by sme začali vybavovať (získavať) povolenia, ktoré je možné získať priamo (hľadali by sme podzoznamy, ktoré majú len jeden prvok). Ak by sme ich získali, tak zoznam povolení môžeme následne upraviť.

Napr. ak získame povolenie C1, zoznam povolení môžeme upraviť nasledovne:

[['B2', 'C1', 'B1'], ['C1', 'B2'], ['C1']]
↓
[['B2', 'B1'], ['B2']]  

Ak sa v nejakom podzozname vyskytlo povolenie C1, môžeme ho z podzoznamu odstrániť - už ho nepotrebujeme získať, pretože ho už máme.

Ak nejaký podzoznam obsahoval len povolenie C1, môžeme odstrániť celý podzoznam - získali sme všetky povolenia z tohto podzoznamu.

Takto by sme mohli postupovať, až kým sa nám nepodarí získať vopred určené povolenie. Keďže vieme, že nie vždy je to možné, pripravíme sa aj na túto situáciu. Táto situácia nastane vtedy, ak sme vopred určené povolenie ešte nezískali a:

• zoznam povolení je už prázdny,

alebo

• v zozname povolení už neexistuje žiadne povolenie, ktoré by sa dalo získať priamo alebo pre jeho získanie sú splnené všetky predpoklady.

Výsledný program môže vyzerať nasledovne:  

# Python
import copy

def najdi_priamo_ziskatelne_povolenie(podmienky):
    for podmienka in podmienky:
        if len(podmienka) == 1:
            return podmienka[0]
    return None


def uprav_podmienky(ziskane_povolenie, podmienky):
    for podmienka in podmienky:
        if ziskane_povolenie in podmienka[:-1]:
            podmienka.remove(ziskane_povolenie)
    if [ziskane_povolenie] in podmienky:
        podmienky.remove([ziskane_povolenie])


def da_sa_ziskat(povolenie, podmienky):
    podmienky = copy.deepcopy(podmienky)
    while podmienky:
        akt_povolenie = najdi_priamo_ziskatelne_povolenie(podmienky)
        if akt_povolenie == povolenie:
            return True
        elif akt_povolenie is None:
            return False
        uprav_podmienky(akt_povolenie, podmienky)
    return False

Všimnime si ešte niekoľko detailov:

• Zoznam podmienok priebežne upravujeme. Vo funkcii da_sa_ziskat sme si preto vytvorili jeho kópiu. Keďže meníme aj jeho podzoznamy, museli sme si vytvoriť aj kópiu podzoznamov copy.deepcopy(podmienky).

• Cyklus while sa opakuje, kým v zozname podmienok sú ešte nejaké podmienky. V každej iterácii vyberieme jedno, priamo získateľné povolenie.

  • Ak je to vopred určené povolenie, môžeme skončiť. Vopred určené povolenie sa dá získať.

  • Ak také povolenie neexistuje, môžeme skončiť. Vopred určené povolenie a nedá získať.

  • Inak upravíme podmienky, pretože sme získali jedno z povolení.

  • Ak cyklus skončil, zrejme sme vopred určené povolenie nezískali.

• Pre sprehľadnenie celého programu sme si vytvorili pomocné funkcie:

  • najdi_priamo_ziskatelne_povolenie - nájde a vráti povolenie, ktoré sa dá priamo získať alebo None, ak také povolenie neexistuje.

  •  uprav_podmienky - upraví podmienky podľa toho, aké povolenie sme získali.

Vaše zaujímavé riešenia a najčastejšie chyby

Väčšina z vás si s úlohou poradila. Niektorí z vás neošetrili prípady, keď pre dané vopred určené povolenie už nie sú potrebné ďalšie povolenia. Niekoľko z vás použilo rekurziu. V tomto prípade to nebolo potrebné. Oceňujeme prístup tímu Šedá eminencia dodekahedrónov, ktorý tento problém transformoval na orientovaný graf (v zmysle štruktúry s vrcholmi a hranami) a jeho prehľadávaním do hĺbky hľadal cykly.