Kontrola

Na MOL-ovem Oddelku za motorni promet in gospodarske dejavnosti na vsako opozorilo o neprijetnostih na kolesarskih poteh odgovorijo, da bodo preverili in ukrepali skladno s svojimi pristojnostmi. Še več, njihovi uslužbenci vsakodnevno, praktično 24/7, kolesarijo po Ljubljani in identificirajo nevarne točke, da jih čimprej odpravijo. Funkcije, ki jih boste napisali tu, jim bodo pomagale še boljše in vestnejše opravljati njihovo delo.

Da bo naloga lažja, bomo predpostavili, da ima mesto pravokotno mrežo.

Zemljevidi so zapisani v datotekah s takšno vsebino:

.r......c..c
r.b.........
.p...r......
............
.s.....l....
.ad......a..
............
..gl......g.

Za lažje sledenje navodilom, je tule zemljevid z oštevilčenimi stolpci in vrsticami. V datoteki teh številk ni.

            11
  012345678901 
0 .r......c..c
1 r.b.........
2 .p...r......
3 ............
4 .s.....l....
5 .ad......a..
6 ............
7 ..gl......g.

• Koordinate zapisujemo tako, da navedemo številko stolpca, nato številko vrstice. Štejemo od 0. Koordinata polja s črko b je (2, 1).
• Razdalje merimo tako, da štejemo koliko vodoravnih in navpičnih korakov je potrebno narediti med črkama. Razdalja med a in g je 3, ker moramo en korak desno in dva dol. Razdalja med p in b je 2.
• Katere črke se pojavljajo v zemljevidu, ne vemo vnaprej. V nekem mestu kolesarji morda vozijo po poteh, sestavljenih iz $#!?@@!##!. Vemo le, da . pomeni, da na polju ni ničesar posebnega.

Ocena 6

1. Napiši funkcijo preberi_zemljevid(ime_dat), ki dobi ime datoteke z zemljevidom in vrne zemljevid, shranjen na poljuben način, ki se ti zdi smiseln. Vse nadaljnje funkcije, ki jih bo potrebno napisati, bodo dobile zemljevid v takšni obliki, kot ga boš sestavil v tej funkciji.

   Nasvet: preberi ostale naloge in razmisli, kako si shraniti zemljevid, da ti bo z njim udobno delati.

   Funkcija lahko vrne, karkoli želiš - seznam, slovar, ime datoteke, množico, seznam nizov ... ali celo terko, v kateri sta slovar in niz. Testi bodo preverjali samo, da funkcija vrne nekaj, kar ni None, zato sam skrbno preveri, da funkcija res vrača, kar si si zamislil, naj vrne.

2. Napiši funkcijo najblizji(x, y, c, zemljevid), ki prejme

   • koordinate neke točke (x, y),
   • iskani znak ali prazen niz (c),
   • in zemljevid v obliki, v kateri ga vrača tvoja funkcija preberi_zemljevid (zemljevid).

   Delovanje funkcije je odvisno od argumenta c:

   • Če c vsebuje znak, mora funkcija vrniti koordinate polja, ki vsebuje črko c in je najbližje podanemu polju (vendar ni enako podanemu polju!), ki vsebuje črko c. Klic najblizji(8, 2, "r", zemljevid) vrne (5, 2). Klic najblizji(1, 5, "a", zemljevid) vrne (9, 5); a je sicer tudi ravno na točki (1, 5), vendar funkcija ne sme vrniti iste točke.

   • Če je c prazen niz, funkcija vrne koordinato najbližjega polja (ki ni trenutno polje) in vsebuje poljuben znak (razen, seveda pike).

   Kadar je enako oddaljenih koordinat več, vrne tisto v bolj levem stolpcu. Če je tudi teh več (= 2, se mi zdi :), vrne tisto, ki je višje.

   Če iskana črka ne obstaja, funkcija vrne None.

3. Napiši funkcijo najpogostejsi(x, y, d, zemljevid), ki vrne najpogostejšega med znaki, ki so za največ d korakov oddaljen od trenutnega polja. Upoštevaj tudi trenutno polje. Če je takih znakov več (če so na razdalji d, recimo po trije znaki b, l in r), naj vrne tistega, ki je prej po abecedi (v tem primeru "b"). Če na tej razdalji ni nobenega znaka, vrne None.

4. Napiši funkcijo vsi_najpogostejsi(x, y, d, zemljevid), ki je podobna prejšnji funkciji, vendar vrne množico najpogostejših črk. V gornjem primeru torej namesto "b" vrne {"b", "l", "r"}. Če je najpogostejši le eden, vrne množico z enim elementom. Če ni nobenega, vrne prazno množico.

Ocena 7

1. Spremeni obstoječo funkcijo najblizji tako, da bo sprejemala dodatni argument, množico prepovedani. Funkcija najblizji(x, y, c, zemljevid, prepovedani) naj vrne enak rezultat kot najblizji, vendar ignorira polja, našteta v prepovedani.

   (Ne skrbi za teste. To ni tvoj problem. Samo dodaj argument. :)

2. Angelca meni, da je potrebno stvari delati sistematično. (To vedno ponavlja tudi županu!) Zato za vsakega nadzornika pripravi dnevni načrt: začetno točko (ta je vedno "prazna", .) in spisek mestnih kolesarskih znamenitosti (robniki, stopnice, bolt ipd).

   Nadzornik opravlja vožnjo tako, da obišče znamenitosti v vrstnem redu, ki ga je določila Angelca, pri čemer gre v vsakem koraku k znamenitosti, ki je najbližja trenutni poziciji (v smislu funkcija najblizji), pri čemer pa nikoli ne gre na znamenitost, ki jo je že obiskal, "saj to," je rekla Angelca, "ne bi imelo nobenega smisla".

   Recimo, da začne kar na (0, 0) in mora prevoziti spisek rprbr.

   • Najprej gre na r na koordinatah (0, 1). Pot je dolga 1.
   • Nato gre na p na (1, 2). To zahteva 2 koraka.
   • Nadaljuje na r na (1, 0) (na prejšnjem r je bil, torej se ne vrača tja). Tudi to je dolgo 2 koraka.
   • Nato gre na b na (2, 1). Spet 2 koraka.
   • Konča na r na (5, 2) (dva bližja r-ja je že obiskal). To je dolgo 4 korake.

   Skupno je naredil 1 + 2 + 2 + 2 + 4 = 11 korakov.

   Nek drug nadzornik začne na (0, 5) in mora obiskati asalag.

   • Gre na a na (1, 5): 1 korak.
   • Gre na s na (1, 4): 1 korak.
   • Gre na a na (9, 5): 9 korakov.
   • Gre na l na (7, 4): 3 koraki.
   • Tu bi moral obiskati a, vendar se ustavi, ker ni več nobenega a-ja, ki ga še ni obiskal. Tako do g-ja sploh ne pride.

   Skupno je naredil 1 + 1 + 9 + 3 = 14 korakov.

   Napiši funkcijo angelca(x, y, znamenitosti, zemljevid), ki vrne število korakov, ki jih bo naredil nadzornik, ki začne poti v (x, y) in mora obiskati znamenitosti na zemljevid.

Ocena 8

Ko je Angelca na dopustu, jo zamenja Johanca. Ta deluje drugače. Nadzornik dobi začetno točko (na kateri ni ničesar, le .) in niz z opisom premikov.

Na primer, da začne na (1, 1) in mora slediti poti ><>4v^12^13v1<2^>>>>>>2v^4v4<^

• >: Najprej gre desno. Vidi b.
• <: Gre levo. Tam ni ničesar.
• >: Gre desno. Tam je b, vendar ga je že videl, zato ga ne zabeleži.
• 4v: Nato gre za 4 dol. Vidi d.
• ^: Gre gor. Tam ne vidi ničesar.
• 12^: Gre še 12-krat gor. Tam ne vidi sploh ničesar, saj tega niti ni na zemljevidu.
• 13v: Gre 13-krat dol, torej je spet tam, kjer je bil d. Ker je ta d že videl, ne šteje.
• 1<: Gre za 1 levo. Tam vidi a.
• 2^: Gre za 2 gor. Tam ni ničesar. s, ki ga je preskočil, spregleda!
• >>>>>>: Nato gre šestkrat >. Ničesar.
• 2v: Gre za 2 dol, pri čemer preskoči l.
• ^ Gre gor in vidi l, ki ga je prej preskočil.
• ^v: Gre dol in gor. Ponovno vidi l, vendar ga ne zabeleži, ker je tam že bil.
• 4v4<^: v nadaljevanju se spusti pod zemljevid, gre levo in ko se vrne gor, naleti na (drug) l ter ga zabeleži.

Napiši funkcijo, johanca(x, y, pot, zemljevid). Funkcija mora vrniti niz z zaporedjem znamenitosti, ki jih je videl kolesar. V gornjem primeru vrne bdall.

Pot je, kot kaže gornji primer, sestavljena iz zaporedja znakov v, ^, < in >. - Če je pred znakom številka (ki ima lahko poljubno število mest), to pomeni, da naredi več korakov v tisto smer. Ker brezglavo divja, ne vidi znamenitosti, ki so vmes. Tako je, recimo, pri "Gre za 2 gor. - Če pot vodi ven iz zemljevida, se pač vozi tam - le da tam pač ne vidi ničesar. - Ko vidi nekaj, kar je že videl (kot recimo d v gornjem primeru), to ignoriramo. - Gornje velja le za znamenitosti na *istih koordinatah. Ko v gornjem primeru naleti na nov l, ga zabeleži.

Ocena 9

• Angelca ima sestrično v nekem velemestu in ta ima podobno velik vpliv na tamkajšnjega župana. Zato moraš poskrbeta, da bo funkcija angelca delovala tudi na bistveno večjem zemljevidu. Testi bodo preverjali, da se funkcija izvede v doglednem času - biti mora dovolj hitra, da preživi teste. Če si jo že prej napisal učinkovito, ti ni potrebno storiti ničesar. Če nisi - razmisli in popravi.

• Johanca tudi. :)

• Ker želijo tudi v teh, velikih mestih, pritegniti kolesarje k ogledu kolesarskih znamenitosti, napiši še funkcijo najboljsa_cetrt(a). Ta poišče kvadrat s stranico a, ki vsebuje največ znamenitosti. Funkcija vrne koordinate njegovega zgornjega levega oglišča. Tudi ta funkcija se mora končati v doglednem času.

  Če je enako dobrih kvadratov več, vrne najbolj levega, med enako dobrimi najbolj levimi pa najbolj zgornjega.

Ocena 10

Kljub veliki skrbi za popisovanje nevarnih točk, nekatere vseeno ostajajo. Problem se utegne skrivati tule. Angelco in Johanco so dali za nekaj časa izpolnjevati stolpce v Excelu in nadzorniki se vozijo po drugačnem postopku.

Prvi del

Vsak nadzornik ima pri sebi n obrazcev. Pot začne v neki predpisani točki (x, y), ki je gotovo prazna. V vsakem koraku si izbere neko znamenitost, ki je oddaljena največ d. Popiše jo. Nato izbere naslednjo točko, oddaljeno d. Popiše in gre do naslednje. To počne toliko časa, dokler mu ne zmanjka obrazcev. K znamenitostim, ki jih je že popisal, se nikoli ne vrača.

Napiši funkcijo dosegljive(x, y, d, n, zemljevid), ki vrne množico točk, ki jih lahko doseže nadzornik. To ne pomeni, da lahko nadzornik obišče vse točke, temveč, da lahko obišče vsako.

Drugi del

Na točkah, označenih z *, so MOL-ove izpostave. Če nadzornik obišče izpostavo, tam dobi nove obrazce, tako da jih ima spet n.

• Tudi izpostave, ki jih obišče, smejo biti od trenutne pozicije oddaljene največ d.
• Isto izpostavo sme obiskati večkrat.
• Izpostave ne sme obiskati, če ima še vedno pri sebi n obrazcev. Kot pravi Angelca, to ne bi imelo nobenega smisla.

Dopolni funkcijo dosegljive, da bo upoštevala še ta pravila.

Nadzornik, ki nadzira spodnji zemljevid in začne pot na (11, 5), dela korake dolžine do 3 ter ima pri sebi največ 2 obrazca, lahko obišče {(7, 4), (11, 0), (10, 7), (8, 0), (9, 5)}.

            11
  012345678901 
0 .r..*...c..c
1 r.b.........
2 .p...r...*..
3 .*..........
4 .s.....l....
5 .ad......a..
6 ..*.........
7 ..gl......g.

Predlog: nalogo je možno rešiti rekurzivno ali iterativno. Rekurzivna rešitev bo najbrž preprostejša in bližja temu, kar smo se učili. Čez teden bom bistveno dopolnil zapiske o rekurziji. V drugem delu bo rekurzija eksplodirala, če je ne boste ukrotili s trikom, ki sem ga pokazal na predavanju (in bo seveda tudi v zapiskih).

Če se boste naloge lotili rekurzivno: funkcija dosegljive skoraj gotovo ne bo rekurzivna, pač pa bo poklicala, drugo, rekurzivno funkcijo, katere ime in argumente si zamislite sami.

Vzpodbuda: če razumete rekurzijo in se je znate lepo lotiti, je naloga za oceno 10 lahka in prijetna, rešitev pa kratka in elegantna. Ni pa ravno čisto trivialna.

Testi