Programiranje 1 (23/24)

Da so kolesarske steze v Najlepšem mestutm™️ bolj estetske, je na vsakem prečkanju stranske ceste uvoz in izvoz na kolesarsko okrašen z okrasnim robnikom v višini nekaj centimetrov. Robnik hkrati povečuje varnost, saj upočasni kolesarje, razen tistih na polno vzmetenih gorskih kolesih. Poleg tega med dežjem robnik usmerja potok vode, po dežju pa še nekaj časa zadržuje mlake, katerih namen je pranje koles in hlač, s čimer MOL poskrbi, da bo imelo najlepše mesto tudi najlepše kolesarke in kolesarje.

Zemljevid na sliki kaže povezave med križišči (zaradi varstva osebnih podatkov so njihova imena zamenjana s črkami), na povezavah pa je označeno število robnikov, čez katere je potrebno skočiti ob vožnji od enega križišča do drugega.

Zemljevid je podan v obliki slovarja, katerega ključi so terke z imeni povezanih križišč, pripadajoče vrednosti pa število robnikov med njima. Začne se tako:

zemljevid = {("A", "B"): 5, ("A", "V"): 5,
             ("B", "A"): 5, ("B", "C"): 3, ("B", "V"): 0,
             ("C", "B"): 3, ("C", "R"): 11,
             ...
             }

Če imamo odkod = "A" in kam = "V", potem zemljevid[(odkod, kam)] pove število robnikov med odkod in kam (v tem primeru 5).

Če določen par ne nastopa kot ključ, potem med tema križiščema ni neposredne povezave.

Vse spodnje funkcije naj načelno delujejo s poljubnim zemljevidom, čeprav testi uporabljajo samo zemljevid na sliki!

Ogrevalna naloga

Napiši funkcijo izpisi_pot(pot), ki prejme pot v obliki zaporedja križišč, na primer "FGIR". Funkcija naj izpiše pare vseh zaporednih vozlišč, torej, na primer

('F', 'G')
('G', 'I')
('I', 'R')

Za to funkcijo ni testov. Delaš jo kot pripravo za druge funkcije.

Naloga

Napiši naslednje funkcije:

• robnikov(zemljevid, pot) prejme zemljevid v gornji obliki in pot v obliki niza, na primer FGIR. Vrniti mora število robnikov, ki jih bo kolesar prevozil na takšni poti.

  Klic robnikov(zemljevid, "FGIR") vrne 21 (od F do G naleti na 4 robnike, od G do I na 10 in od I do R na 7).

• prevozno(zemljevid, pot) vrne True, če je podano pot možno prevoziti, torej, če obstajajo povezave med vsemi zaporednimi pari križišč. Če pot ni možna, vrne križišče, v katerem obtiči kolesar.

  Klic prevozno(zemljevid, "FGIR") vrne True, klic prevozno(zemljevid, "FGIKH") pa vrne "I", saj pot iz I v K ni možna. (Prav tako ni možna pot iz K v H, vendar se kolesar že prej ustavi v I).

• guma(zemljevid, pot, trpeznost) prejme zemljevid in pot, poleg tega pa trpežnost gume. Trpežnost gume se na vsakem robniku zmanjša za 1. Ko pade na 0, je guma pokončana, zračnica predrta in prazna, tako da se mora kolesar ustaviti. Funkcija mora vrniti križišče, na katerem se bo ustavil kolesar - bodisi zato, ker bo konec gume, bodisi zato, ker določena povezava sploh ne obstaja (tako kot pri prejšnji funkciji). Če vse povezave obstajajo in guma zdrži, kolesar pride do konca in funkcija vrne zadnje križišče.

  • Klic guma(zemljevid, "FGIMNPOPI", 1000) vrne "I", saj vse povezave obstajajo in guma je fantastična.
  • Klic guma(zemljevid, "FGIMNPOPI", 25) vrne "M": guma spusti na enem od robnikov med M in N.
  • Klic guma(zemljevid, "FGIMRDE", 1000) vrne "M", saj ni povezave med M in R.

• potencial(zemljevid) je namenjena običajnemu kolesarju, ki si, kot vemo, želi na poti srečati čimveč robnikov. Potencial točke je največje število robnikov na kaki izmed povezav, ki vodijo iz njega. Tako je, ne primer, potencial točke U enak 7, potencial točke K je 8, najbolj imenitna točka pa je R, katere potencial je 11. Funkcija potencial(zemljevid) prejme zemljevid in vrne slovar, katerega ključi so imena križišč, pripadajoče vrednosti pa njihov potencial. Za zemljevid s slike vrne (narekovaji so zaradi preglednosti izpuščeni):

{A: 5, B: 5, C: 11, D: 10, E: 4, F: 10, G: 10,
 H: 5, I: 10, J: 4, K: 8, L: 5, M: 10, N: 2,
 O: 2, P: 2, R: 11, S: 4, T: 5, U: 7, V: 5}