Kolesarjenje po Manhattnu
Kolesarjenje po Manhattnu
Niso pa, o nikakor, vsa mesta tako srečna kot Ljubljana. Tule je primer iz New Yorka, konkretno, Manhattna. Kolesarske steze so kratke, predvsem pa pravokotne ena na drugo in zato neprijetne zaradi ostrih zavojev. (Disclaimer: avtor naloge je bil nazadnje v New Yorku pred dvajsetimi leti in, iskreno, nima pojma. Prav gotovo pa kolesarjem v New Yorku ni tako prijetno kot v Ljubljani: gospa Angelca je vendarle ena sama.)
Ta naloga se ocenjuje, zato vam ne sme manjkati. Za nalogo za določeno oceno je potrebno pravilno rešiti tudi vse naloge za nižjo oceno.
V nalogi bomo delali s povezavami in mrežami.
Povezava je podana s četverko
(x0, y0, x1, y1)
, kjer(x0, y0)
predstavljata koordinato enega in(x1, y1)
koordinato drugega krajišča.- Koordinate x tečejo od leve proti desni, y tečejo od zgoraj navzdol. Vse koordinate so cela števila.
- Vrstni red je poljuben in nepomemben:
(x0, y0, x1, y1)
in(x1, y1, x0, y0)
sta ena in ista povezava. Tako je osamljena vodoravna povezava na vrhu opisana z(11, 10, 13, 10)
ali pa z(13, 10, 11, 10)
. - Vodoravna in navpična povezava se lahko sekata ali dotikata s krajišči.
- Dve vodoravni oz. dve navpični povezavi ne moreta imeti skupne točke. To pomeni, da se ne prekrivata, niti se ne dotikata s krajišči.
Mreža pa nam bode slovar, katerega ključi so pari povezav (torej pari četvork, kot smo jih opisali zgoraj), ki se sekajo, pripadajoča vrednost pa je točka, v kateri se povezavi sekata.
Eden od ključev je, recimo
((13, 15, 13, 16), (13, 16, 21, 16))
, pripadajoča vrednost pa je(13, 16)
, saj se povezavi(13, 15, 13, 16)
in(13, 16, 21, 16)
sekata v točki(13, 16)
.- Povezave v ključih so urejene: v vsaki povezavi je prva točka,
x0, y0
levo oz. višje od druge, in prva povezava se začne levo od druge, če imata obe enako prvo koordinato, pa se prva povezava začne višje od druge. Ključ torej mora biti natančno takšen, ne pa((13, 16, 21, 16), (13, 15, 13, 16))
(napačen vrstni red povezav), ali((13, 16, 13, 15), (13, 16, 21, 16))
napačen vrstni red točk prvi povezavi.
- Povezave v ključih so urejene: v vsaki povezavi je prva točka,
Zemljevid povezav v večini testnih primerov je takšen.
Predstavljen je s seznamom
povezave = [
(11, 10, 13, 10),
(2, 12, 8, 12),
(6, 11, 6, 13),
(0, 16, 10, 16),
(3, 18, 3, 13),
(7, 14, 3, 14),
(9, 17, 9, 14),
... in tako naprej
Z izjemo prvih dveh nalog, bodo povezave vedno pravilne, torej navpične ali vodoravne in dolge vsaj 1.
Ocena 6
Napiši naslednje funkcije:
pravilna(povezava)
dobi kot argument četverko(x0, y0, x1, y1)
in mora vrnitiTrue
, če četverka predstavlja pravilno povezavo, inFalse
če ne. Povezava je pravilna, če je vodoravna ali navpična (ne pa poševna) in če njena dolžina ni 0.- Klica
pravilna((18, 5, 13, 5))
inpravilna((5, 18, 5, 13))
vrnetaTrue
, saj gre za vodoravno oz. navpično povezavo. - Klic
pravilna((10, 18, 12, 4))
vrneFalse
, ker je povezave poševna. - Klic
pravilna((10, 18, 10, 18))
vrneFalse
, ker je povezava dolga0
.
- Klica
pravilne(povezave)
dobi seznam takšnih povezav in vrneTrue
, če so vse povezave v njem pravilne, inFalse
, če seznam vsebuje eno ali več nepravilnih povezav.urejena(povezava)
prejme povezavo in vrne povezavo, v kateri so pari urejeni: prva točka je levo oz. višje od druge.- Klic
urejena((18, 5, 13, 5))
vrne(13, 5, 18, 5)
. - Klic
urejena((13, 5, 18, 5))
pa vrne(13, 5, 18, 5)
, saj je povezava že urejena.
- Klic
na_povezavi(x, y, povezava)
vrneTrue
, če podana točka(x, y)
leži na povezavi inFalse
, če ne.- Klic
na_povezavi(14, 5, (18, 5, 13, 5))
vrneTrue
. - Klic
na_povezavi(13, 6, (18, 5, 13, 5))
vrneFalse
. - Klic
na_povezavi(10, 5, (18, 5, 13, 5))
vrneFalse
.
- Klic
povezave_tocke(x, y, povezave)
prejme koordinato točke in seznam povezav. Vrniti mora množico povezav, na katerih leži ta točka (v resnici bo imela ta množica največ dva elementa, saj gresta lahko prek neke točke največ dve povezavi). Povezave v množici morajo biti urejene v smislu, da je prva točka levo oz. višje od druge. (Urejene so posamične povezave. Množice je nemogoče urejati.)- Klic
povezave_tocke(3, 15, povezave)
vrne{(3, 13, 3, 18)}
, čeprav je v seznamu povezav ta povezava zapisana kot(3, 18, 3, 13)
.
- Klic
secisce(povezava1, povezava2)
prejme dve povezavi (torej dve četvorki) in vrne točko, v kateri se sekata, oziromaNone
, če se ne sekata.- Klic
secisce((10, 20, 10, 25), (8, 22, 18, 22))
vrne(10, 22)
. - Klic
secisce((8, 20, 18, 20), (1, 25, 0, 25))
vrneNone
.
- Klic
Ocena 7
Napišite naslednje funkcije.
krizisca(povezave)
prejme seznam povezav in vrne mrežo. Kako je videti mreža, je opisano na vrhu naloge.mozna_pot(pot, mreza)
prejme pot, podano kot seznam povezav, in mrežo. Vrniti moraTrue
, če vse povezave v poti dejansko obstajajo in je možno prevoziti podani seznam povezav v podanem vrstnem redu, ne da bi kje zapustili kolesarske poti, inFalse
, če ne. (Povedano bolj tehnično: preveri mora, ali vse povezave na poti obstajajo in ali se zaporedne povezave sekajo oz. dotikajo).razdalja(pot, mreza)
vrne razdaljo, ki jo prevozi kolesar na podani poti.- Predpostavi, da začne kolesar svojo pot na sečišču prve in druge povezave v seznamu. Po prvi pravzaprav sploh ne vozi.
- Pot nadaljuje od sečišča prve in druge do sečišča druge in tretje.
- Tam zavije na tretjo in vozi do sečišča s četrto.
- Tako nadaljuje do sečišča med predzadnjo in zadnjo povezavo. Po zadnji ne vozi.
Pri tej nalogi smemo predpostaviti, da je podana
pot
možna in da vsebuje vsaj dve povezavi.
Ocena 8
Za oceno 8 samo poskrbi, da bodo funkcije za oceno 6, razen funkcij secisce
in na_povezavi
napisane z enim samim izrazom - torej z enim samim return
, ki mu sledi izraz, izpeljana množica, klic kake primerne funkcije...
Seveda bi lahko v eni vrstici napisali tudi secisce
in, prevsem, na_povezavi
, vendar nočem, da bi pisali grde programe. Funkcije, ki jih morate napisati v eni vrtici, pa se dejansko da napisati lepo.
Ocena 9
Za oceno 9 poskrbi, da bodo tudi vse naloge za oceno 7 napisane z enim samim izrazom.
Poleg tega napiši funkcijo svg(povezave, ime_datoteke)
, ki v datoteko s podanim imenom izriše zemljevid, kakršen je na sliki v začetku naloge, vendar naj vsebuje le povezave (črte in kroge na krajiščih), ne pa tudi mreže. Datoteka mora biti v obliki .svg; za izris uporabi isti koordinatni sistem kot na sliki. Da je datoteka pravilna, bodo preverili testi, v lastno veselje pa jo lahko tudi odpreš v primernem programu, recimo spletnem brskalniku.
Za podani zemljevid je datoteka videti tako:
<svg xmlns="http://www.w3.org/2000/svg" viewBox="-3 7 29 17">
<circle cx='11' cy='10' r='0.1' />
<circle cx='13' cy='10' r='0.1' />
<line x1="11" y1="10" x2="13" y2="10" stroke="black" stroke-width="0.1" />
<circle cx='2' cy='12' r='0.1' />
<circle cx='8' cy='12' r='0.1' />
<line x1="2" y1="12" x2="8" y2="12" stroke="black" stroke-width="0.1" />
<circle cx='6' cy='11' r='0.1' />
<circle cx='6' cy='13' r='0.1' />
<line x1="6" y1="11" x2="6" y2="13" stroke="black" stroke-width="0.1" />
<circle cx='0' cy='16' r='0.1' />
<circle cx='10' cy='16' r='0.1' />
<line x1="0" y1="16" x2="10" y2="16" stroke="black" stroke-width="0.1" />
<circle cx='3' cy='18' r='0.1' />
<circle cx='3' cy='13' r='0.1' />
<!--In tako naprej za vse povezave -->
</svg>
Ni potrebno, da je vsebina datoteke natančno takšna. Barve in debeline ter podobno okrasje si lahko izmisliš sam(a); za teste je pomembnno, da izris obsega naštete črte in kroge ter do so koordinate pravilne. Poleg tega moraš primerno nastaviti viewBox
v elementu svg
, da bo zemljevid pravilno prikazan: prvi dve števili sta koordinati zgornjega levega kota, drugi dve pa širina in višina. V tem primeru sem viewBox
nekoliko razširil, da se zemljevid ne zajeda v rob.
Ocena 10
Napiši naslednje funkcije.
povezane(mreza)
prejme mrežo in vrne slovar, katerega ključi so posamične povezave, pripadajoče vrednosti pa množice povezav, s katerimi je ta povezava povezana.Vrnjeni slovar vsebuje, recimo,
(8, 15, 13, 15): {(9, 14, 9, 17), (11, 13, 11, 20), (12, 14, 12, 17), (13, 15, 13, 16)},
ker je povezava
(8, 15, 13, 15)
povezana z naštetimi štirimi povezavami.Komentar: sam sem to funkcijo napisal z običajno zanko. Koristen je razmislek, zakaj je to zoprno narediti z izpeljanim slovarjem.
dostopne(povezava, mreza)
vrne množico vseh povezav, ki so dostopne iz dane povezave (= neposredno ali posredno povezavne s to povezavo). Množica vključuje tudi to povezavo.Pomoč: sestavljaj seznam, v katerem je v začetku izhodiščna povezava, potem pa za vsak element v seznamu dodaš povezave, iz katerih je ta element dostopen. Pri tem moraš paziti, da se ne zaciklaš: nobene povezave ne dodaj dvakrat.
Če že veš za rekurzivne funkcije: nismo se jih še učili in tule jih tudi ne potrebuješ. Lažje je brez.
pot(sx, sy, ex, ey, mreza)
mora vrniti seznam z zaporedjem povezav, ki vodijo od podane začetne točke (sx
,sy
) do končne točke (ex
,ey
). Če takšne poti ni mogoče opraviti, ker ena od točk (ali obe) ne leži na povezavi ali pa med točkama ni povezav, funkcija vrneNone
.Za vrnjeno pot mora torej veljati, da začetna točka leži na prvi povezavi, da končna točka leži na končni povezavi, in da je pot med njima možna. Testi bodo za preverjanje pravilnosti rešitve uporabljali kar tvoje funkcije
na_povezavi
inmozna_pot
. Če vrnejo napako, je morda problem v teh dveh funkcijah in ne vpot
. (To je, upam, malo verjetno, saj sta tudi tidve funkciji prej preverjeni.)Pomoč: prejšnjo nalogo smo reševali kot vajo za to. Stvar je podobna, le da ne sestavljaj seznama povezav temveč seznam poti, ki jih dopolnjuješ z novimi končnimi povezavami. Tudi tu gre čisto lepo brez rekurzije. Rešitev ni posebej učinkovita z vidika pomnilnika.
Če si že slišal za Dijkstrov algoritem: ne kompliciraj. Seveda lahko rešuješ tudi z njim, vendar je za to nalogo dovolj, da poiščeš eno od možnih poti. (Če se boš pametno lotil, boš najbrž poiskal najkrajšo pot v smislu najmanjšega števila uporabljenih povezav - čeprav se za to ne boš eksplicitno trudil. Tako bo naneslo.)
Testi
29. november 2024, 10:56 |