Načrtovanje poti

Mestna občina Ljubljana je objavila video o vedenju kolesarjev v Ljubljani. Naj povzamem: kolesarji so znani po divjih spustih po stopnicah, divjanju med pešci in tako naprej.^* Ker je osnovno prevozno sredstvo vašega profesorja kolo in ker tretjino letne kilometrine žal opravi v Ljubljani, vas prosi, da mu za lažje načrtovanje poti rešite tole nalogo.

Oddelek za gozdarske dejavnosti in motorni promet MOL je pripravil zemljevid na sliki. Ta kaže 21 križišč v Ljubljani, pri čemer so na zahtevo mestnih strokovnjakov za varstvo osebnih podatkov zamenjali imena lokacij s črkami od A do V. Povezave med njimi zahtevajo različne veščine: kdor hoče, na primer priti iz točke B do C, mora obvladati vožnjo med odvrženimi skiroji in slalom med cvetličnimi lonci.

Celoten seznam veščin, ki se pojavljajo v nalogi, je:

• stopnice: Spust po stopnicah
• pešci: Divjanje med pešci
• lonci: Slalom med cvetličnimi lonci
• bolt: Slalom med odvrženimi skiroji
• robnik: Skok na robnik pločnika
• gravel: Vožnja po razsutem makadamu
• trava: Oranje zelenic parkov
• avtocesta: Vožnja po avtocesti
• crepinje: Vožnja po razbiti steklovini
• rodeo: Vožnja po kolesarski poti skozi Črnuče

Zemljevid na sliki zaradi pomanjkanja prostora uporablja enočrkovne okrajšave veščin, v sami nalogi pa je zapisan takole:

A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, R, S, T, U, V = "ABCDEFGHIJKLMNOPRSTUV"

zemljevid = {
    ('A', 'B'): {'trava', 'gravel'},
    ('A', 'V'): {'lonci', 'pešci'},
    ('B', 'A'): {'trava', 'gravel'},
    ('B', 'C'): {'lonci', 'bolt'},
    ('B', 'V'): set(),
    ('C', 'B'): {'lonci', 'bolt'},
    ('C', 'R'): {'lonci', 'pešci', 'stopnice'},
    ('D', 'F'): {'pešci', 'stopnice'},
    ('D', 'R'): {'pešci'},
    ('E', 'I'): {'trava', 'lonci'},
    ('F', 'D'): {'pešci', 'stopnice'},
    ('F', 'G'): {'trava', 'črepinje'},
    ('G', 'F'): {'trava', 'črepinje'},
    ('G', 'H'): {'črepinje', 'pešci'},
    ('G', 'I'): {'avtocesta'},
    ('H', 'G'): {'črepinje', 'pešci'},

    ... in tako naprej

Ključi zemljevida so pari povezanih točk, pripadajoča vrednost pa je množica veščin, ki jih mora obvladati kolesar, če želi prevoziti to povezavo. Tako vidimo pod ključem (B, C) zapisano {"bolt", "lonci"}, kar je okrajšava za veščini Slalom med odvrženimi skiroji in Slalom med cvetličnimi lonci.

Vse povezave so dvosmerne, saj je kolesarjem po mnenju MOL itak vseeno, v katero smer in po kateri strani ceste vozijo. Če obstaja v slovarju povezava (B, C), torej obstaja tudi (C, B); obe zahtevata enake veščine. (Podvojene povezave so v bistvu nepotrebne, vendar vam bo tako lažje programirati.)

Obvezna naloga

1. Funkcija mozna_pot(pot, zemljevid) prejme pot v obliki niza z zaporedjem križišč in zemljevid v obliki iz uvoda naloge. Funkcija mora vrniti True, če je takšna pot možna (torej: če obstajajo povezave med vsemi zaporednimi križišči v nizu) in False, če ni.

   Klic mozna_pot("ABCRVRIEIPNM", zemljevid) vrne True, klic mozna_pot("ABCRVREPNM", zemljevid) pa False, ker ni povezave iz R v E.

2. Funkcijapotrebne_vescine(pot, zemljevid) prejme enake argumente kot prejšnja funkcija, s tem, da bo pot, ki jo prejme, bo vedno možna. Funkcija mora vrniti množico veščin, ki jih mora kolesar obvladati, če želi prevoziti to pot.

   Klic potrebne_vescine("RIPSTUT", zemljevid) vrne {'robnik', 'stopnice', 'gravel', 'trava'}, saj so to veščine, ki jih potrebujemo za to pot (na zemljevidu označene kot sr, g, rt in gt).

3. Funkcija nepotrebne_vescine(pot, zemljevid, vescine) prejme enake argumente, poleg tega pa še množico veščin, ki jih obvlada kolesar. Vrniti mora množico veščin, ki jih obvlada, vendar so za to pot nepotrebne.

   Klic nepotrebne_vescine("IPNMNPO", zemljevid, {'stopnice', 'gravel', 'bolt', 'rodeo'}) vrne {'stopnice', 'bolt'}, saj tidve veščini za pot "IPNMNPO" nista potrebni.

4. Funkcija kam(zemljevid, tocka, vescine) prejme zemljevid, neko točko in množico veščin, ki jih obvlada nek kolesar. Vrniti mora množico točk, ki so neposredno povezane s podano točko in jih ta kolesar lahko doseže.

   Klic kam(zemljevid, R, {"stopnice", "trava", "pešci", "robnik", "avtocesta"} vrne {U, I, D}. (Zmožnost vožnje po avtocesti je tu sicer nepotrebna, vendar nas ne ovira.)

5. Funkcija dolgcas(zemljevid) vrne množico povezav na podanem zemljevidu, ki ne zahtevajo nobene veščine. Vsak par naj vrne le enkrat - če je dolgočasna povezava med B in V, naj množica vsebuje bodisi (B, V) bodisi (V, B), ne pa obojega.

   Klic dolgcas(zemljevid) lahko vrne, recimo, {(B, V), (S, P), (J, K)}, ali pa, na primer, {(K, J), (V, B), (S, P)}...

Dodatna naloga

Napiši funkcijo koncna_tocka(pot, zemljevid, vescine), ki prejme enake argumente kot nepotrebne_vescine. Vrniti mora dve stvari: točko, do katere lahko kolesar s temi veščinami prevozi to pot, in množico veščin, ki mu manjkajo, da bi šel naprej iz te točke. Ta množica naj ne vključuje morebitnih drugih veščin, ki bi ga čakale na nadaljnji poti, temveč le manjkajoče veščine za prvo povezavo, ki je ne uspe prevoziti.

Klic koncna_tocka("ABCRVB", zemljevid, {"gravel", "trava"} vrne ("B", {'lonci', 'bolt'}). Kolesar, ki bi se namenil iti po poti "ABCRVB" bi se zataknil v točki B, ker ne zna voziti slaloma med cvetličnimi lonci in odvrženimi skiroji. Nadaljnja pot bi sicer zahtevala še druge veščine (recimo spust po stopnicah med C in R), vendar funkcija ne gleda naprej.

Dodatni izziv

Za dodatni izziv ni testov (morda pa kdaj bodo). Napiši funkcijo, ki prejme zemljevid, začetno točko in množico veščin ter vrne vse točke, ki jih lahko kolesar doseže s temi veščinami.

^* Seveda se med kolesarji v resnici najdejo tudi breobzirni divjaki. Vtis, ki ga želi pustiti video, pa je vseeno morda nekoliko pretiran. Sploh začetno divjanje po stopnicah; kakor vem, te veščine kolesarji vadijo na Golovcu, Klobuku in Rašici, ne ob Ljubljanici.

Testi