Programiranje 1 (23/24)

Prometni strokovnjaki, zaposleni na Oddelku za motorni promet in gospodarske dejavnosti MOL, so sestavili študijo, ki je pokazala, da bi bilo za prometno varnost kolesarjev najboljše, če bi bile kolesarske steze le na eni strani ceste. (Obenem bi na drugi strani ceste pridobili prostor za širitev ceste za en pas.) Nadalje so prometni strokovnjaki ugotovili, da bi bile takšne kolesarske steze potem preozke za dvosmerni promet, zato so se odločili, da bodo povezave med križišči enosmerne. Situacija je prikazana na sliki.

Na ugovore kolesarjev, da bodo nekatera križišča zato postala nedosegljiva ali pa se spremenila v slepo ulico (npr. E in S), je MOL odgovoril: "Vaši pomisleki so popolnoma neutemeljeni. Kot je razvidno iz slike, so naši prometni strokovnjaki sestavili zemljevid tako, da se kolesar ne more ujeti v cikel, torej, nobena pot ga ne more pripeljati v križišče, v katerem je že bil. Takšna ureditev je inovacija v svetovnem merilu, na katero smo še posebej ponosni." (Ta odgovor je dejansko pomemben za vaše reševanje naloge!)

Zemljevid je podan v obliki

poti = {
   A: {B: {"gravel", "trava"}, V: {"pesci", "lonci"}},
   B: {V: set()},
   C: {B: {"bolt", "lonci"}, R: {"stopnice", "pesci", "lonci"}},
   D: {},
   E: {},
   F: {D: {"stopnice", "pesci"}},
   ...

Ključi so vsa križišča. Pripadajoče vrednosti so slovarji, kateri ključi so sosednja vozlišča, pripadajoče vrednosti pa veščine, potrebne na poti. Vaše naloge veščine ne zadevajo, zato jih ignorirajte. (Tu so na zalogo, za prihodnje naloge. :)

Obvezna naloga

• Napišite funkcijo obstaja_pot(od, do), ki vrne True, če je iz križišča od možno priti do križišča do, in False, če ni. (True vrne tudi, če sta od in do pravzaprav isto križišče.)

• Napišite funkcijo dosegljive(od), ki vrne množico vseh križišč, ki so dosegljiva iz podanega križišča (vključno s tem križiščem). Klic dosegljiva("O") vrne {"O", "S", "P", "N"}.

Dodatna naloga

• Napišite funkcijo dolzina_poti(od, do), ki vrne dolžino najkrajše poti (v smislu števila povezav) med podanima točkama. Če sta od in do isto križišče, vrne 0. Klic dolzina_poti("I", "S") vrne 2. (Med I in S obstaja tudi daljša pot, I-R-U-T-S, vendar mora funkcija vrniti dolžino najkrajše poti).

  Če pot med točkama ni možna, vrne 99.

• Napišite funkcijo najkrajsa_pot(od, do), ki vrne niz z najkrajšo potjo med podanima točkama. Če sta od in do isto križišče, vrne od (ali do :). Klic najkrajsa_pot("G", "S") vrne "GIPS". (Med G in S obstaja tudi daljša pot, "GIRUTS", vendar mora funkcija vrniti dolžino najkrajše poti). Če je najkrajših poti več, lahko vrne poljubno med njimi,

  Če pot med točkama ni možna, vrne None.

Po želji lahko napišete le eno od teh dveh funkcij, druga funkcija pa kliče to funkcijo. Ali pa uporabljata ena drugo na kak drug način. Zavoljo poučnosti pa predlagam, da napišete vsako funkcijo neodvisno od druge.

Testi