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.

Oddelek za gospodarstvo in motorni promet pri Mestni občini Ljubljana je za popularizacijo kolesarjenja uvedel sistem nagradnih točk za uporabo različnih veščin. Vožnja po travi je vredna tri točke, divjanje med pešci štiri točke, vožnja po avtocesti deset točk in tako naprej. Kolesar, ki zbere določeno število nagradnih točk, dobi vozniško dovoljenje za motorno vozilo kategorije C (+ koncesijo za parkiranje na pločniku).

Točkovanje:

• črepinje: 1,
• robnik: 1,
• lonci: 1,
• gravel: 2,
• bolt: 2,
• rodeo: 2,
• trava: 3,
• pešci: 4,
• stopnice: 6,
• avtocesta: 10.

Nekaj sprememb v primerjavi z nalogo Načrtovanje poti:

• Veščine so iste kot zadnjič, le da uporabljamo samo okrajšave.
• Ključi v zemljevidu so enaki, vendar sta v zemljevidu že obe smeri, tako da se vam ni potrebno zafrkavati s funkcijo dvosmerni_zemljevid.
• Vrednosti v zemljevidu so množice okrajšanih veščin, na primer {"pešci", "avtocesta"}. (Da bi neka povezava zahtevala divjanje med pešci na avtocesti, mogoče zveni hecno, a glede na to, da so po mnenju MOL površine za pešce in kolesarje primerne tudi za parkiranje (slike na desni je posneta nedaleč od PeF), tudi preusmeritev prometa na pločnike ne bi bila preveliko presenečenje.)
• funkcije zemljevida ne dobijo kot argument, temveč uporabljajo kar globalno spremenljivko zemljevid.

Pri reševanju mi boste hvaležni za spodnjo sliko.

Vse ocene so pisane v razponu ene ocene: ali boste dobili, na primer 8 ali 9, je odvisno od elegance vaše rešitve.

Za oceno 6-7

• Napiši funkcijo vrednost_povezave(povezava), ki vrne število nagradnih točk, ki jih dobi kolesar, če prevozi povezavo. Povezava je podana kot terka z imeni križišč, na primer ("A", "B"), torej v enaki obliki kot ključi zemljevida. Število točk je enako vsoti točk, ki jih dobi za potrebne veščine. Če so potrebne veščine za neko povezavo {"pešci", "avtocesta", "bolt"}, mora funkcija vrniti 16 (to je, 4 + 10 + 2).

• Napiši funkcijo najboljsa_povezava(pot), ki prejme pot in vrne tisto povezavo na tej poti, ki mu prinese največ točk. Pot je podana v obliki niza, npr. "ABVRU", rezultat pa naj bo v obliki terke, npr. ("V", "R").

• Napiši funkcijo vrednost_poti(pot), ki vrne število nagradnih točk, ki jih dobi kolesar za določeno pot, to je, vsoto nagradnih točk za vse povezave na tej poti. Če mora na poti večkrat uporabiti različno veščino, dobi točke za vsako uporabo. Če pot ni možna zaradi manjkajočih povezav, mora funkcija vrniti None.

Za oceno 7-8

• Napiši funkcijo enkratna_vrednost_poti(pot), ki vrne vrednost poti, pri čemer pa se vsaka uporabljena veščina šteje samo enkrat. Če kolesar, na primer, dvakrat vozi po travi, dobi vseeno le tri točke (kolikor je vredna vožnja po travi) in ne šestih. Če pot ni možna zaradi manjkajočih povezav, mora funkcija vrniti None.

• Napiši funkcijo mozna_pot(pot, vescine), ki vrne True, če je s podano množico veščin možno prevoziti podano pot, pri čemer pa smemo vsako veščino uporabiti le enkrat. Če se na poti, na primer, dvakrat pojavijo stopnice, se pred drugimi stopnicami ustavi. (Če sploh ne zna voziti po stopnicah, pa se ustavi že pred prvimi stopnicami.) Pazite tudi na to, da nekatere povezave na poti morda sploh ne bodo obstajale; v tem primeru seveda vrnete False.

Za oceno 8-9

• Napiši funkcijo do_nagrade(pot, meja), ki vrne točko na poti, do katerega lahko pelje kolesar, tako da skupno število njegovih nagradnih točk še ne preseže podane meje meja (po čemer mu MOL za izkazano objestnost podeli častno vozniško dovoljenje). Pri tem štetju se vsaka uporabljena veščina lahko šteje večkrat (kot pri nalogi vrednost_poti, ne kot pri enkratna_vrednost_poti).

  Če pot zaradi kake manjkajoče povezave ni možna, funkcija vrne točko, kjer se je kolesar prisiljen ustaviti.

  Lahko pa se zgodi tudi, da pride do konca poti. V tem primeru funkcija seveda vrne zadnjo točko.

Za oceno 9-10

V teh dveh funkcijah bomo kolesarja spet omejili tako, da sme vsako veščino uporabiti samo enkrat.

• Napiši funkcijo sosede(tocka, vescine), ki prejme neko točko in množico veščin, ki so mu še na voljo. Funkcija naj vrne seznam parov. Prvi elementi parov so sosednje točke, do katerih ima kolesar s temi veščinami dostop. Drugi element so veščine, ki mu bodo preostale, če gre v to točko.

  Ker se kolesar rad pokaže, naj funkcija ignorira povezave, ki ne zahtevajo nobene veščine. Pot iz P v S ni možna, kot da je ne bi bilo.

  Vrstni red elementov v seznamu je lahko poljuben. (Testi ga bodo potem za lažje preverjanje uredili, a to ni tvoja skrb.)

  Klic

  sosede("I", {"avtocesta", "trava", "lonci", "stopnice", "bolt"})
  

  vrne seznam

  [("G", {"trava", "lonci", "stopnice", "bolt"}),
   ("M", {"trava", "lonci", "stopnice", "bolt"}),
   ("E", {"avtocesta", "stopnice", "bolt"}),
  ]
  

  S podanimi veščinami gre lahko v G in M (pri čemer v pripadajoči množici ni več avtoceste) in v E (pri čemer potem ne more več voziti po travi in med lonci. Med sosedi pa ni R, ker ne obvlada (več?) robnikov in P (gravel).

• Napiši funkcijo dosegljive(tocka, vescine), ki vrne množico točk, ki so kolesarju dosegljive iz podane točke s podanimi veščinami, če sme vsako veščino uporabiti samo enkrat, poleg tega pa noče voziti po povezavah, ki ne zahtevajo nobene veščine. Množica vključuje tudi trenutno točko.

  Klic dosegljive(I, {"avtocesta", "trava", "lonci", "stopnice", "bolt", "gravel", "rodeo"}) vrne {"I", "G", "E", "P", "M", "N", "K"}.

  • I: tu začne;
  • G: sem lahko pride ker obvlada avtocesto, naprej pa ne more, ker ne obvlada črepinj;
  • E: pozna travo in lonce, iz E pa ne more več nikamor;
  • V točko R ne more, ker ne obvlada robnikov
  • P: sem pride, ker obvlada gravel. V S ne gre, ker mu je pod častjo, v O pa ne more, ker je gravel že uporabil. (Tudi v N ne more iz P, pač pa bo tja prišel iz M);
  • M: pri tem porabi avtocesto, pot pa lahko nadaljuje v
  • N: kjer uporabi rodeo (in iz N še v P, ki pa ga itak doseže že po drugi poti);
  • K: prav tako dosegljiv iz M.

  Namig: iz vsake točke je dosegljiva ta točka in vse točke, ki so dosegljive iz njenih sosed, vendar pri zmanjšanem naboru veščin.

  Ne boj se, nič se ne bo zaciklalo, saj pri vsakem klicu uporabimo kakšno veščino.

Testi