Programiranje 1 (22/23)

Da so kolesarske steze v Najlepšem mestu™️ 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 in s tem najsrečnejše kolesarke in kolesarje.

Zemljevid na sliki prikazuje 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 iz 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')

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

Dodana naloga

Najlepše križišče je križišče, ki je obkroženo z največ robniki. Za gornji zemljevid je to nedvomno vozlišče R, saj na povezavah okrog njega naštejemo kar 34 (11 + 4 + 7 + 7 + 5) robnikov.

Napiši funkciji

• najlepse(zemljevid), ki vrne najlepše križišče. Za gornji zemljevid torej "R". Če si naziv najlepšega križišča deli več križišč, lahko funkcija vrne kateregakoli izmed njih.
• najlepsa(zemljevid, n), ki vrne urejen seznam n najlepših križišč. Klic najlepsa(zemljevid, 3) vrne ["R", "I", "M"].

Testi