Programiranje 1 (23/24)

Nizozemska ima gosto mrežo kolesarskih poti, s številnimi križišči, ki so oštevilčena brez posebnega reda. V vsakem križišču so preprosto smerokazi s številkami sosednjih križišč.

MOL povzame idejo in jo dopolni: za kolesarje bodo uvedli krožišča in naredili celo aplikacijo za navigacijo. Ta bo dajala navodila v slogu

• na naslednjem krožišču zavijte na četrti izvoz,
• na naslednjem krožišču zavijte na prvi izvoz,
• na naslednjem krožišču zavijte na drugi izvoz.

Ker pa MOL meni, da so ~~programerji dragi in je za kolesarje škoda denarja~~ kolesarji inteligentni, bodo navodila namesto v stavkih zapisana kar z zaporedjem številk. Če smo v A in so navodila 4 1 2, bomo peljali, kot kaže slika.

Za oceno 6

1. Napiši funkcijo preberi(ime_datoteke), ki prejme ime datoteke in vrne zemljevid. Datoteka je sestavljena tako, da prva vrstica ustreza prvemu krožišču (ali uvozu/izvodu), druga drugemu, tretje tretjemu in tako naprej. Vsaka vrstica vsebuje številke krožišč, s katerimi je posamično krožišče povezano. Krožišča so našteta po vrsti, vendar se lahko začnejo s poljubnim.

   Gornjemu zemljevidu ustreza datoteka

   3
   4
   1 8 7 6 4
   5 2 3 6
   10 4 11
   11 4 3
   3 8 11
   3 16 9 7
   11 8 16 14
   5 11 13
   10 5 6 7 9 14
   13
   12 10 14
   13 11 9 16
   16
   14 9 8 15
   

   Četrta vrstica, recimo, vsebuje 5 2 3 6, ker je četrto križišče povezano s križišči 5, 2, 3 in 6. Lahko pa bi pisalo tudi 2 3 6 4, 3 6 5 2 ali 6 5 2 3, saj se opis začne s poljubnim od teh štirih krožišč.

   Funkcija naj vrne slovar, katerega ključi so številke križišč, pripadajoče vrednosti pa seznami številk (int!) sosednjih križišč. Funkcija naj "preobrne" seznam ta, da se bodo začeli z najmanjšo številko, križišča pa morajo biti še vedno po vrsti. Tako bo ključu 4 pripadal element [2, 3, 6, 5] (in ne [5, 2, 3, 6], ko bi direktno prebrali iz datoteke, in tudi ne [2, 3, 5, 6], kot bi dobili, če bi seznam le uredili).

   (Možna ideja: če se ne spomniš ničesar boljšega, vzemi prvi element in ga postavi na konec; to ponavljaj toliko časa, dokler prvi ni najmanjši.)

2. Napiši funkcijo mozna_pot(pot, zemljevid), ki prejme seznam številk krožišč/krajišč in zemljevid. Vrne naj True, če je takšno pot možno prevoziti, in False, če ne.

   Pot je možno prevoziti, če se začne in konča s končno povezavo (prepoznate jo po tem, da je povezana le z enim krožiščem), če vmes ni končnih povezav, če se nobeno krožišče ne ponovi (iz krožišča 6 ne moremo zapeljati v krožišče 6) in če so vsa krožišča na poti dejansko povezana.

3. Napiši funkcijo hamiltonova(pot, zemljevid), ki pove (True ali False), če je pot Hamiltonova. Pot je Hamiltonova, če je možna (prejšnja funkcija), gre prek vseh krožišč in to prek vsakega natančno enkrat.

Za oceno 7

Napiši funkcijo navodila(pot, zemljevid), ki prejme zaporedje krožišč in vrne navodila (seznam števil), ki povedo, kako prevoziti to pot. Pot bo vedno možna.

Klic navodila([1, 3, 6, 4, 2], zemljevid) mora vrniti [3, 2, 2]: če začnemo v 1, prispemo v 3, kjer moramo zaviti na 3. izvoz, znajdemo se na 6, kjer gremo na 2. izvoz, pridemo v 4, kjer gremo spet na 2. izvoz pa smo na 2.

Namig: naloga je precej lažja, kot je morda videti. Najlažje jo je rešiti tako, da opazuješ trojke. Recimo, da greš iz 6 v 11 v 10. Lahko poveš, na kateri izvoz bo šel v 11? Veš, kje boš prišel noter in kje ven, ne? To, s katero številko se začne naštevanje v seznamu sosedov, je pravzaprav nepomembno, pomembna je le razlika. In kadar so stvari krožne, utegne priti prav ostanek po deljenju, ki se lepo vede tudi pri negativnih številih: -2 % 5 je enako 3 (če bi moral iti dva izvoza v napačni smeri, je pri petkrakem križišču to isto kot trije v pravi).

Naloga je celo tako lahka, da jo lahko, ne da bi se pretegnili, rešimo v eni sami vrstici.

Za oceno 8

Naloga za oceno 8 je obratna nalogi za oceno 7. Napiši funkcijo prevozi(zacetek, navodila, zemljevid), ki dobi začetno točko (pri gornjem zemljevidu bo to vedno 1, 2, 12 ali 15) in navodila, kakršna vrača prejšnja funkcija. Vrniti mora zaporedje prevoženih vozlišč.

Klic prevozi(1, [3, 2, 2], zemljevid) vrne [1, 3, 6, 4, 2]

Za oceno 9

1. Napiši funkcijo sosedi(doslej, zemljevid), ki prejme neko množico številk krožišč in uvozov (doslej), ter vrne množico številk vseh vozlišč, s katerimi so ta vozlišča povezana (razen teh vozlišč). Tako, recimo, klic({1, 3, 7}, zemljevid) vrne {4, 6, 11, 8}.

2. Napiši funkcijo razdalja(x, y, zemljevid), ki prejme številki dveh uvozov (lahko pa tudi dveh krožišč!) in vrne razdaljo med njima. Razdalja je definirana kot število povezav, ki jih je potrebno prevoziti med njima; razdalja med 3 in 11 je enaka 2.

Namig: nalogo lahko rešiš takole. Sestavi množico {x}. V množico dodaj njene sosede. Nato v dobljeno množico dodaj njene sosede. In spet. In spet. Prej ko slej boš dodal(a) y. Razdalja med x in y je enako število potrebnih "razširjanj" množice. S tole nalogo se boš verjetno namučil(a) manj kot z nalogo za oceno 8!

Za oceno 10

Napiši funkcijo najkrajsa_navodila(x, y, zemljevid), ki vrne najkrajša navodila, ki nas pripeljejo od x do y. Pri tem bosta x in y vedno številki uvozov (in ne krožišč).

Namig: mogoče se ti splača napisati funkcijo, podobno funkciji sosedi, ki pa ne prejme in vrača množice, temveč prejme slovar, katerega ključi so takšni, kot so bili prej elementi množice, pripadajoča vrednost pa je številka krožišča, iz katerega se pride v krožišče, ki ga predstavlja ključ. Ta funkcija gre torej prek ključev in v slovar dodaja nove ključe -- sosede teh ključev, kot vrednost pa jim priredi ključ, zaradi katerega je bil ta ključ dodan. (Če je bilo to povedano nekoliko kriptično, je to nekoliko namerno. Za oceno 10 morate tudi kaj potuhtati!) Ko boste imeli to funkcijo, jo uporabite podobno kot sosedi v prejšnji nalogi. Potem pa sledite temu slovarju od končne točke do začetne. Tako boste dobili pot v obratni smeri. Obrnite jo. Funkcijo, ki iz poti (seznama številk) naredi navodila, pa že imate.

Klic najkrajsa_navodila(15, 1) vrne [3, 3, 4], saj moramo na 16 na tretji izhod, na 8 na tretjega in na 3 na četrtega.

Naloga za oceno 10 ni težka, vendar utegneš morda potrebovati kak sproten nasvet po mailu. Loti se čimprej in naj ti ne bo nerodno vprašati za pomoč!

Testi