Nagradne točke

Rok za oddajo: sreda, 14. december 2022, 11.15

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. Nalogo oddate kot običajno, v eni datoteki.

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 MOL že od pomladi odkriva, da so pločniki lahko tudi parkirišča, tudi preusmeritev prometa na pločnike ne bi bila preveliko presenečenje.)

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

Za oceno 6

  • Napiši funkcijo vrednost_povezave(povezava, zemljevid), 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(zemljevid), ki vrne povezavo, za katero dobimo največ točk. Če je takšnih povezav več, lahko vrne poljubno izmed njih. (Vedno bosta vsaj dve, namreč ena in ista povezava v eno in drugo smer.)

  • Napiši funkcijo vrednost_poti(pot, zemljevid), 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. Pot je podana v obliki niza, kot smo že vajeni. Predpostaviti smete, da je pot možna.

Za oceno 7

  • Napiši funkcijo najbolj_uporabna(pot, zemljevid), ki prejme tisto veščino, ki se največkrat pojavi na podani poti. Če je takšnih veščin več, lahko vrne poljubno med njimi. Če za neko pot ne rabi nobene veščine naj funkcije vrne None.

Za oceno 8

  • Napiši funkcijo mozna_pot(pot, zemljevid, 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.

  • Gornja funkcija je pravzaprav nesmiselna: zakaj bi vsako veščino uporabili samo enkrat? Zato napiši še funkcijo koncna_tocka(pot, zemljevid, vescine), ki vrne točko, do katere uspemo priti s podanimi veščinami, pri čemer so veščine podane kot množica parov; prvi element para je ime veščine, drugi pa število, ki pove, kolikokrat smemo to veščino uporabiti. Če so vescine enake {("pešci", 3), ("trava", 1), ("črepinje", 2)}, sme kolesar največ trikrat zapeljati med pešce, enkrat po travi in dvakrat po črepinjah. Če bi, recimo, trikrat naletel na črepinje, se bo pred tretjimi črepinjami ustavil. Spet se lahko zgodi, da se pot ustavi zato, ker neka povezava ne obstaja.

  • Gornja funkcija je pravzaprav nesmiselna: zakaj bi omejevali število uporab veščine? Se lahko sploh kdo kdaj naveliča vožnje po črepinjah? Zato napiši še funkcijo do_nagrade(pot, zemljevid, meja), ki vrne mesto, do katere lahko pelje kolesar, tako da skupno število nagradnih točk pri tem še ne preseže podane meje meja, po kateri bi mu Zoki slovesno izročil plaketo in vozniško dovoljenje.

    Č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

  • Poskrbi, da bodo vse funkcije za oceno 6 napisane z izpeljanimi seznami oziroma generatorji. Vsebujejo naj le return. (Če funkcija vrednost_povezave vsebuje slovar, ga prestavi ven iz funkcije, da ne bo vznemirajal testov.)

  • Napiši funkcijo naslednje_tocke(tocke, zemljevid, vescine). Ta prejme zemljevid in množico veščin, ki jih kolesar obvlada (in jih lahko uporabi poljubnokrat). Argument tocke vsebuje neko množico točk na zemljevidu. Funkcija naj vrne množico, ki vsebuje vse elemente množice tocke, poleg tega pa še vse tiste točke zemljevida, ki so povezane s temi točkami s povezavami, ki jih lahko prevozi kolesar s temi veščinami.

    Klic naslednje_tocke({V, F}, zemljevid, {"pešci", "stopnice", "lonci", "rodeo"}) vrne {V, A, B, R, F, D}, saj se kolesar, ki je vešč naštetih veščin, lahko premakne iz V v A, B, R in iz F v D. Iz V v, recimo U pa ne more, ker ne obvlada robnikov in vožnje po travi.

    Tudi funkcija naslednje_tocke naj bo napisana v eni vrstici, ker res ni potrebe po tem, da bi bila kaj daljša.

Za oceno 10

  • Napiši funkcijo dosegljive(tocka, zemljevid, vescine), ki vrne množico vseh točk, ki jih lahko v poljubnem številu korakov doseže kolesar, ki je v začetku v podani točki tocka in obvlada podane vescine.

Nasvet: pomagaj si s prejšnjo funkcijo.

Tolažba: sploh ni težko. Če boš spreten, bo dolgo pet vrstic. In to brez kakšnih generatorjev in podobnih čudes.

Za dodatni izziv

Ocena 11

Napiši funkcijo dosegljive_n(tocka, zemljevid, meja), ki vrne množico vseh točk na zemljevidu, ki jih lahko doseže kolesar, ne da bi pri tem nabral več kot meja nagradnih točk.

(V rezultatih bo pisalo, da ste dosegli oceno 11, vendar je to samo za kudos. Pri ocenjevanju se bo upoštevala ocena 10.)

Ocena 12

Pa še malo težja: kolesar se nahaja na podani točki na zemljevidu in ne zna ničesar. Na srečo je tam tudi zlata ribica, ki mu bo izpolnila tri želje, to je, dala tri veščine. Katere tri veščine si mora izbrati, da bo lahko z njimi (začenši v podani točki) obiskal čim več točk zemljevida?

Napiši funkcijo naj_vescine(tocka, zemljevid, zelje), ki prejme začetno točko, zemljevid in število želja, ki ti jih bo izpolnila ribica. (Običajne ribice, vemo, izpolnijo tri, ampak morda bomo naleteli na kakšno bolj leno ribico ali pa, nasprotno, na ribico, ki ima ravno dober dan in izpolni več želja). Funkcija mora vrniti par: optimalno množico veščin in število točk, ki jih lahko obiščemo (vštevši začetno). Če je možnih več množic veščin, ki dovoljujejo isto število obiskanih točk, vrne poljubno izmed teh množic.

Klic naj_vescine("A", zemljevid, 2) vrne ({"pešci", "lonci"}, 5), saj lahko s tema dvema veščinama dosežemo pet točk (A, V, B, R, D).

Objavljeni testi za to nalogo še niso dokončni. Dodal bom še teste, v katerih je graf večji in predvsem, obstaja veliko več različnih veščin. Ideja, da poskusite vse možne kombinacije treh veščin, na njem ne bo več delovala.

Je ta naloga zelo težka? Mislil sem, da je, dokler mi ni asistent, doc. Tomaž Hočevar, povedal, kako jo kar preprosto prijeti.

Pomoč: če boste hoteli uporabiti množico kot ključ v slovarju ali pa jo dodati v množico, namesto tipa set uporabite frozenset. Če sta a in b dve množici, lahko napišete tudi, recimo frozenset(a | b) in dobite unijo a in b kot zamrznjeno množico, ki jo lahko dodate v množico ali uporabite kot ključ v slovarju.

(Nekdo je vprašal, če bo ta, ki reši to nalogo, za nagrado s tem opravil predmet. Skoraj. Še vedno bo moral na izpit, vendar si bo med pisanjem požvižgaval, da mu ne bi bilo dolgčas.)

Testi