Programiranje 1 (23/24)

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 obvlada (večine ostalih pa noče prakticirati), vas prosi, da mu za lažje načrtovanje poti rešite tole nalogo. Hvala vnaprej.

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",
    ... in tako naprej
}

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, saj lahko MOL poljubno površino, namenjeno kolesarjem, označi kot dvosmerno. Če v zemljevidu obstaja ključ (A, B), obstaja tudi ključ (B, A).

Naloga

Napiši naslednje funkcije (poleg njih pa, po želji, poljubno število drugih funkcij):

• mozna_pot(pot, vescine, zemljevid) prejme pot v obliki niza z zaporedjem križišč, seznam veščin, ki jih obvlada kolesar, in zemljevid v obliki iz uvoda naloge. Funkcija mora vrniti točko, do katere bo uspel pripeljati kolesar, torej točko, iz katere ne bo mogel naprej, ker želena povezava ne obstaja ali pa je med veščinami, ki so potrebne, da jo prevozi, tudi ena ali več veščin, ki jih kolesar ne obvlada.

  • Klic mozna_pot("RIPOPSTUVR", ["stopnice", "robnik", "gravel", "trava"], zemljevid) vrne "U", saj luzer ne zna slalomirati med cvetličnimi lonci, postavljeni med U in V.

  • Klic mozna_pot("RIPOPAB", ["stopnice", "robnik", "gravel", "trava"], zemljevid) vrne "P", saj med P in A ni povezave.

  • Klic mozna_pot("RIPOPS", ["stopnice", "robnik", "gravel", "trava"], zemljevid) vrne "S", saj na poti ni nič takšnega, česar ne bi obvladal.

• boljsa_pot((pot1, pot2, zemljevid) prejme dve poti in vrne tisto, ki zahteva več različnih veščin, saj imajo takšne kolesarji menda rajši. Če obe poti zahtevata enako število različnih veščin, vrne pot1.

  Pri pisanju te funkcije smete predpostavljati, da vse povezave obstajajo.

• manjkajoce_vescine(pot, vescine, zemljevid) prejme pot, ki bi jo kolesar rad prevozil in veščine, ki jih obvlada. Vrniti moral število različnih veščin, ki se jih mora še naučiti, da bo lahko prevozil to pot.

  Tudi v tej funkciji smete predpostaviti, da vse povezave obstajajo.

  Klic manjkajoce_vescine("RIPOPSTUVRIPSTUVR", ["stopnice", "robnik", "gravel"], zemljevid)) vrne 3, ker se mora kolesar za to pot naučiti še vožnje po travi, med cvetličnimi lonci in med pešci.

• skupni_podvig(pot, vescine1, vescine2, zemljevid) simulira vožnjo dveh kolesarjev, ki obvladata različne veščine. Vozita se na istem kolesu: eden vozi, drugi sedi na prtljažniku, štangi ali krmilu. Vsako povezavo na poti prevozi tisti, ki obvlada vse potrebne veščine za povezavo. Če jo zmoreta oba, vozi vsak pol povezava. Če je ne zmore noben, je pot končana.

  Funkcija mora vrniti par s številom povezav, ki jih prevozi prvi, in številom povezav, ki jih prevozi drugi kolesar.

  V tej funkciji ne smete predpostaviti, da vse povezave na poti obstajajo.

  Poglejmo klic

  skupni_podvig("RVABCRD",
                ["trava", "lonci", "bolt", "gravel", "stopnice"],
                ["bolt", "lonci", "pešci"],
                zemljevid))
  

  • Odseka RV in VA prevozi drugi kolesar, saj zahteva lonce in pešce; prvi pešcev ne obvlada.
  • Odsek AB prevozi prvi kolesar.
  • Odsek BC prevozita oba, torej vsak pol.
  • Odseka CR ne zna prevoziti nobeden: prvi ne obvlada pešcev, drugi pa stopnic. Zato se njuna pot tu konča.
  • Odseka RD se ne lotita, saj ne prideta do njega.

  Klic torej vrne (1.5, 2.5).

Testi

Preden oddaš rešitev, jo preveri s testi!