Načrtovanje poti

Rok za oddajo: sreda, 30. november 2022, 11.15

Mestna občina Ljubljana je objavila video o vedenju kolesarjev v Ljubljani. Na kratko: MOL izpostavlja tipične navade ljubljanskih kolesarjev, kot so divji spusti po stopnicah, divjanje med pešci in tako naprej. Ker je osnovno prevozno sredstvo vašega profesorja kolo in ker tretjino letne kilometrine žal opravi v Ljubljani, pri čemer se od (domnevne večine) ostalih kolesarjev razlikuje po tem, da nekaterih od teh veščin ne oblada, vas prosi, da mu za lažje načrtovanje poti rešite tole nalogo.

Zemljevid na sliki kaže 21 točk v Ljubljani (zaradi varstva osebnih podatkov smo imena lokacij zamenjali s črkami od A do V) in povezave med njimi. Povezave 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
  • črepinje: 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): "gravel trava",
    (A, V): "pešci lonci",
    (B, C): "bolt lonci",
    (B, V): "",
    (C, R): "stopnice pešci lonci",
    (D, F): "stopnice pešci",
    (D, R): "pešci",
    (E, I): "trava lonci",
    (F, G): "trava črepinje",
    (G, H): "črepinje pešci",
    (G, I): "avtocesta",
    (H, J): "robnik bolt",
    (I, M): "avtocesta",
    (I, P): "gravel",
    (I, R): "stopnice robnik",
    (J, K): "",
    (J, L): "gravel bolt",
    (K, M): "stopnice bolt",
    (L, M): "robnik pešci",
    (M, N): "rodeo",
    (N, P): "gravel",
    (O, P): "gravel",
    (P, S): "",
    (R, U): "trava pešci",
    (R, V): "pešci lonci",
    (S, T): "robnik trava",
    (T, U): "gravel trava",
    (U, V): "robnik lonci trava"
}

Ključi zemljevida so pari povezanih točk, pripadajoča vrednost pa je niz, ki vsebuje s presledkom ločene okrajšave veščin. 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 (ker je kolesarjem po mnenju MOL itak vseeno, v katero smer in po kateri strani ceste vozijo). Če obstaja povezava med B in C obstaja tudi med C in B ter zahteva enake veščine.

Obvezna naloga

Napiši naslednje funkcije

  • mnozica_vescin(s) prejme niz z okrajšanimi imeni veščin, ločenimi s presledkom in vrne množico s polnimi imeni teh veščin. Klic mnozica_vescin("robnik bolt stopnice") vrne {"Skok na robnik pločnika", "Slalom med odvrženimi skiroji", "Spust po stopnicah"}.

    Rešitev, ki vsebuje čreva v slogu

    if vescina == "trava":
    ...
elif vescina == "gravel":
    ...
elif vescina == "robnik":
    ...

    ne bo priznana kot pravilna. Lepo uporabite, kar smo se učili na predavanjih. Iz tega razloga funkcija mnozica_vescin ne sme vsebovati pogojnih stavkov, v nalogi pa (izjemoma) ne smete definirati dodatnih funkcij (razen zahtevanih).

  • dvosmerni_zemljevid(zemljevi) prejme zemljevid (slovar, kakršen je gornji) in vrne nov zemljevid, ki se od podanega razlikuje po tem, da

    • se vse povezave pojavijo tudi v obrnjeni smeri (če je v podanem zemljevidu ključ (B, C), je v vrnjenem zemljevidu poleg njega tudi ključ (C, B));
    • so nizi okrajšav zamenjani z množicami, kakršne vrača funkcija mnozica_vescin.

    Klic

    dvosmerni_zemljevid({(A, B): "robnik bolt",
                     (A, C): "bolt rodeo pešci",
                     (C, D): ""}

    vrne

    {('A', 'B'): {'Slalom med odvrženimi skiroji',
              'Skok na robnik pločnika'},
 ('B', 'A'): {'Slalom med odvrženimi skiroji',
              'Skok na robnik pločnika'},
 ('A', 'C'): {'Divjanje med pešci',
              'Slalom med odvrženimi skiroji',
              'Vožnja po kolesarski poti skozi Črnuče'},
 ('C', 'A'): {'Divjanje med pešci',
              'Slalom med odvrženimi skiroji',
              'Vožnja po kolesarski poti skozi Črnuče'},
 ('C', 'D'): set(),
 ('D', 'C'): set()}

    Toplo priporočam, da to funkcijo uporabite v nekaterih od naslednjih funkcij.

  • 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.

  • potrebne_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

    {'Skok na robnik pločnika',
 'Spust po stopnicah',
 'Vožnja po razsutem makadamu',
 'Oranje zelenic parkov'}

    saj so to veščine, ki jih potrebujemo za to pot (na zemljevidu označene kot sr, g, rt in gt).

  • 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 so za to pot nepotrebne.

    Klic

    nepotrebne_vescine("IPNMNPO", zemljevid, {'Spust po stopnicah',
                                          'Vožnja po razsutem makadamu',
                                          'Slalom med odvrženimi skiroji',
                                          'Vožnja po kolesarski poti skozi Črnuče'})

    vrne {'Spust po stopnicah', 'Slalom med odvrženimi skiroji'}, ker tidve veščini za pot "IPNMNPO" nista potrebni.

Dodatna naloga

Ker ima tadva tedna večina študentov kolokvije (in ker, kot rečejo v Bosni, "ne laje pas zbog sela" - v glavi imam samo smrkelj in nič inspiracije :), je dodatna naloga ta teden res lahka.

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.

Če uspe kolesar priti do konca, funkcija očitno vrne zadnjo točko in prazno množico.

Klic koncna_tocka("ABCRVB", zemljevid, {"Vožnja po razsutem makadamu", "Oranje zelenic parkov"} vrne ("B", {'Slalom med cvetličnimi lonci', 'Slalom med odvrženimi skiroji'}). 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.

Testi