Programiranje 1 (22/23)

Ta naloga se ocenjuje, zato je ne smete izpustiti. Rešiti jo morate vsaj za oceno 6. Za določeno oceno je potrebno pravilno rešiti tudi vse naloge za nižje ocene.

Za oceno 6

Za to oceno naj bodo križišča, po katerih vozi kolesar, označena z eno samo črko. Poznamo poti, po katerih sta vozila dva kolesarja. Napiši funkciji

• skupna_krizisca(pot1, pot2), kjer sta pot1 in pot2 niza, ki predstavljata poti, vrne število križišč, ki sta jih obiskala oba kolesarja. skupna_krizisca("ABCDCAB", "DAEBA") vrne 3, saj sta oba obiskala A, B in D (A celo večkrat, vendar vsako križišče štejemo samo enkrat).
• skupni_odseki(pot1, pot2) vrne število povezav, ki sta jih prevozila oba kolesarja. skupni_odseki("ABCDCAB", "DABCABCD") vrne 4, saj sta oba prevozila A-B, B-C, C-D in C-A. A-B sta sicer prevozila dvakrat, vendar vsako povezavo štejemo le enkrat. Povezave so usmerjene - A-B ni isto kot B-A.

Za oceno 7

• Napiši funkcijo preberi_zemljevid(ime_datoteke), ki prejme ime datoteke, v kateri je shranjen zemljevid v naslednji obliki:

  PeF-EF: robnik, bolt
  PeF-FRI: robnik, avtocesta
  FRI-BF: 
  BF-FE: robnik, trava, pešci
  

  Vsaka vrstica predstavlja povezavo. Levo od dvopičja imamo začetno in končno točko povezave, ločeno z -. Ime križišča je lahko sestavljeno iz več znakov. Dvopičju vedno sledi presledek, nato pa seznam veščin. Veščine so ločene z (levo stično) vejico.

  Funkcija mora vrniti zemljevid v obliki slovarja, katerega ključi so terke z imenoma križišč, pripadajoča vrednost pa seznam veščin, ki jih zahteva povezava. V gornjem primeru vrne

  {('BF', 'FE'): {'pešci', 'robnik', 'trava'},
   ('FRI', 'BF'): set(),
   ('PeF', 'EF'): {'bolt', 'robnik'},
   ('PeF', 'FRI'): {'avtocesta', 'robnik'}}
  

• Napiši funkcijo zapisi_zemljevid(ime_datoteke, zemljevid), ki prejme ime datoteke in zemljevid v obliki slovarja, kakršen je gornji. Funkcija zapiše zemljevid v datoteko, enako gornji obliki.

  Testi za to funkcijo delujejo tako, da jo pokličejo, da shrani zemljevid, nato pa pokličejo kar funkcijo preberi_zemljevid(ime_datoteke), da preverijo, ali je zapisani zemljevid pravilen. Če testi javijo napako, je lahko problem tudi v funkciji preberi_zemljevid (čeprav najbrž ne, saj je ta stestirana na istih podatkih v ločenem testu).

Za oceno 8

Kolesarja vozita kot v nalogi za oceno 6. Za vsak odsek porabita enako časa. Napiši funkcijo skupni_odsek(pot1, pot2), ki vrne dolžino najdaljšega skupnega odseka poti. Pri tem morata biti odseka "poravnana", na istem mestu, se pravi tako, da ga kolesarja dejansko prevozita istočasno.

Klic

#              vv  vvvvv   vvv
skupni_odsek("ABCDEFGHIJKLMNOP",
             "XBDEMFGHIJXOANOP")

vrne 5, saj je najdaljši skupni odsek FGHIJK.

Klic skupni_odsek("ABCDEF", "XABCDEF") vrne 0, saj kolesarja ne prevozita ABCDEF istočarno -- prvi je vedno eno križišče pred drugim.

Za oceno 9

Ker je prva prioriteta Mestne občine Ljubljana varnost kolesarjev, so sprejeli predpis, po katerem smemo iz vsakega križišča voziti le v križišča, katerih ime je po abecedi kasnejše od trenutnega: iz D smemo v R, obratno pa ne.

Napiši funkcijo uporabne_vescine(zacetek, zemljevid), ki vrne množico veščin, ki nam lahko pridejo prav, če začnemo svojo pot v točki zacetek. Klic uporabne_vescine("R", zemljevid) vrne {'trava', 'lonci', 'robnik', "pešci"}, saj iz R lahko potujemo (samo) v U in V, pri čemer potrebujemo štiri veščine, naštete v množici.

Za oceno 10

Napiši funkcijo dolzina_poti(zacetek, konec, zemljevid), ki vrne dolžino najkrajše možne poti (to je, število povezav) od točke zacetek do konec, če smemo, kot veleva novi nori predpis, iz vsakega križišča peljati le v vozlišče, ki je kasneje po abecedi. Če pot ni možna, naj funkcija vrne None.

Klic dolzina_poti("F", "U", zemljevid) vrne 4, saj iz F v U gremo po poti F-G-I-R-U. Po krajši poti, F-D-R-U ne smemo, ker iz F ne smemo v D.

Klic dolzina_poti("C", "I", zemljevid) vrne None, saj pot iz C v I ni možna.

Testi