Načrtovanje poti

Mestna občina Ljubljana je objavila video o vedenju kolesarjev v Ljubljani. Na kratko: 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.

Zemljevid na sliki kaže 21 križišč v Ljubljani (na zahtevo mestnih strokovnjakov za varstvo 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
• 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): "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

1. Funkcija 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));

• vrednosti niso več nizi temveč množice veščin.

  Klic

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

  vrne

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

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

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

3. 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', 'makadam', 'trava'}, saj so to veščine, ki jih potrebujemo za to pot (na zemljevidu označene kot sr, g, rt in gt).

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

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

5. Funkcija tocke_vescine(zemljevid, vescina) vrne niz z vsemi točkami, iz katerih vodijo povezave, ki zahtevajo določeno veščino. Vsaka črka naj se pojavi le enkrat. Črke naj bodo urejene po abecedi.

   Klic tocke_vescin(zemljevid, "avtocesta") vrne "GIM", saj se veščina avtocesta pojavlja na povezavah, ki vodijo iz točk G, I in M.

   Klic tocke_vescine(zemljevid, "rodeo") vrne "MN", ker imajo pravo kolesarsko stezo z rodeom samo Črnučani.

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, {"makadam", "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.

^* 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; to vidimo na Golovcu, Klobuku in Rašici, ne ob Ljubljanici.

Testi