Dirke na Čopovi

Ko sem na forum pisal neko sporočilo o kolesarjenju pa Manhattnu, me je zgrabilo domoljubje in se sem odločil, da bi enkrat za spremembo pripravil tudi nalogo o kolesarjenju po Ljubljani.

V videu o vedenju kolesarjev nas je MOL poučil, da je osnovno opravilo ljubljanskih kolesark divjanje med pešci. (V tej nalogi bom govoril o kolesarkah, čeprav MOL v svojem videu kritizira samo kolesarje, kolesarke pa ignorira, kot da nismo v 21. stoletju.) To je popolnoma res! Tako se po zadnjih statistikah vede 98 % ljubljanskih kolesark in le 2 % takšno vedenje obsojata. (Obstaja možnost, da se je Angelca zmotila pri izpolnjevanju Excela in zamenjala celici, vendar to za našo nalogo niti ni pomembno.)

Kolesarke se torej dobivajo vsako sredo ob 16.00 na dirki, na katerih se spusté od Pošte do ciljne črte na Prešernovem trgu. Vsakič zabeležijo, kdo je zmagal in kdo so bile poraženke. Vrstni red poraženk ni zabeležen, prav tako nihče ne meri časov.

• Neko sredo so na dirki sodelovale Jana, Tina, Greta, Berta, Greta, Liza, Micka in Dani. Zmagala je Jana, torej lahko vemo, da je hitrejša od ostalih šestih.
• Neko drugo sredo so prišle Liza, Olga, Rezka in Vera. (Najavila se je tudi Fanči, vendar se je morala potem učiti za kolokvij iz Uvoda v računalništvo.) Zmagala je Liza.

Iz obeh dirk skupaj lahko sklepamo tudi, da je Jana hitrejša od Rezke, čeprav nista nikoli sodelovali na isti tekmi. Vemo namreč, da je Jana hitrejša od Lize, Liza pa od Rezke.

Obvezna naloga

Nekatere od teh funkcij bodo skoraj gotovo rekurzivne (če si hočete dobro), nekatere pa skoraj gotovo ne bodo (če si hočete dobro).

• Napiši funkcijo hitrejsa(prva, druga, razmerja), ki prejme imeni dveh kolesark in vrne True, če obstaja dokaz, da je prva hitrejša kot druge. Dokaz je lahko neposreden (pomerila sta se na isti dirki) ali posreden (kot opisujemo zgoraj). Če takšen dokaz ne obstaja (ali pa morda velja celo nasprotno), vrne False.

  Argument razmerja je slovar, katerega ključi so imena kolesark, pripadajoče vrednosti pa imena tistih, od katerih je ta kolesrka preverjeno hitrejša. Tako ključu "Ana" pripada množica {"Tina", "Berta", "Dani", "Greta", "Liza", "Micka"}. Kot ključi nastopajo vse kolesarke, tudi tiste, ki niso hitrejše od nikogar. V testih se bo pojavljal slovar, ki predstavlja stanje na sliki, pa tudi drugačni slovarji.

  Klica hitrejsa("Berta", "Greta", razmerja) in hitrejsa("Berta", "Poldka", razmerja) vrneta True, klica hitrejsa("Berta", "Jana", razmerja) in hitrejsa("Berta", "Vera", razmerja) pa False.

• Napiši funkcijo skalpi(kolesarka, razmerja), ki prejme ime kolesarke in vrne množico kolesark, od katerih je ta kolesarka hitrejša. Da naloga ne bo pretežka, mora ta množica vsebovati tudi podano kolesarko.

  Klic skalpi("Berta", razmerja) vrne {"Berta", "Cilka", "Olga", "Poldka", "Iva", "Klara", "Helga", "Ema", "Nina", "Greta"}.

• Napiši funkcijo izlocanje(kandidatke, razmerja), ki vrne prejme množico imen kandidatke in razmerja. Vrniti mora množico imen kolesark, ki jih ni (neposredno ali posredno) premagala nobena druga kolesarka iz te množice.

  Klic izlocanje({"Žana", "Dani", "Ema", "Iva", "Fanči", "Vera"}, razmerja) vrne {"Žana", "Dani", "Iva"}.

Dodatna naloga

Napiši funkcijo dokazov(prva, druga, razmerja), ki vrne število dokazov, da je prva hitrejša kot druga. Če prva ni hitrejša kot druga (ker razmerje ni znano ali pa je celo počasnejšia), funkcija vrne 0.

• Klic dokazov("Jana", "Cilka", razmerja) vrne 4. Da je Jana hitrejša od Cilke lahko dokažemo z zaporedjem Jana - Berta - Cilka, Jana - Dani - Ana - Cilka, Jana - Dani - Cilka in Jana - Dani - Fanči - Cilka.

• Klic dokazov("Dani", "Liza", razmerja) vrne 3, saj imamo poti Dani - Fanči - Liza, Dani - Liza in Dani - Micka - Liza.

Še bolj dodatna naloga

• Napiši funkcijo uredi(razmerja), ki vrne "urejen" seznam kolesark. Seznam je urejen tako, da so hitrejše kolesarke pred počasnejšimi, na primer Jana mora biti pred Cilko, saj je hitrejša od nje. Ali je Ana predali za Greto, pa je vseeno, prav tako je vseeno, ali je Jana pred ali za Špelo.

  Testov za funkcijo uredi še ni, morda pa bodo.

Testi