Dirke na Čopovi

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.

Podobno kot smo imeli na predavanju (globalni) slovar rodbina, ki je predstavljal rodbino (ključi so bili osebe, vrednosti seznam potomcev), imamo tule seznam zmage, katere ključi so imena kolesark, vrednosti pa množice vseh kolesark, ki jih je ta kolesarka kdaj premagala. (Gornji primer zveni, kot da je Jana v isti dirki premagala vseh šest kolesark, ki so povezane z njo. V resnici bi lahko šlo tudi za zmage iz različnih dirk.)

Obvezna naloga

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

  • Klic hitrejsa("Berta", "Greta") vrne True, saj je Berta premagala Greto.
  • Klic hitrejsa("Berta", "Poldka") vrne True, saj je Berta hitrejša od Cilke, ta od Nine in ta od Poldke.
  • Klica hitrejsa("Berta", "Jana") vrne False. Očitno; Jana je hitrejša od Berte.
  • Tudi klic hitrejsa("Berta", "Vera") vrne False. To ne pomeni, da je Vera hitrejša od Berta; morda je, morda ni. Gotovo pa ni nobenega zaporedja Berta je premagala nekoga, ki je premagal nekoga ... ki je premagal Vero, torej ni dokaza, da je Berta hitrejša od Vere. Zato False.

• Napiši funkcijo skalpi(kolesarka), 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") vrne {"Berta", "Cilka", "Olga", "Poldka", "Iva", "Klara", "Helga", "Ema", "Nina", "Greta"}.

  Funkcijo skalpi se da "nagoljufati" tako, da si pomagamo kar s funkcijo hitrejsa. Lahko; za vajo pa predlagam, da napišete funkcijo skalpi tako, da bo klicala le sebe, ne funkcije hitrejsa.

Prva naloga je praktično enaka nečemu, kar smo delali na predavanju, druga pa nečemu z vaj.

Dodatna naloga

• Napiši funkcijo dokazov(prva, druga), 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") 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") vrne 3, saj imamo poti Dani - Fanči - Liza, Dani - Liza in Dani - Micka - Liza.

• Po drugi strani pa nas skrbi, da moč dokaza pada s številom posrednikov. Napiši funkcijo zanesljivo_hitrejsa(prva, druga, n), ki je podobna funkciji iz obveznega dela, vendar vrne True, če je prva kolesarka boljša kot druga prek največ n posrednikov.

  • Klic zanesljivo_hitrejsa("Berta", "Poldka", 2) vrne True, saj je Berta dokazano hitrejša od Poldke prek dveh ali manj posrednikov (npr. Berta-Cilka-Olga-Poldka ali tudi Berta-Klara-Nina-Poldka).
  • Tudi zanesljivo_hitrejsa("Berta", "Poldka", 3) ali zanesljivo_hitrejsa("Berta", "Poldka", 4) seveda vrne True. Za pot od Berte do Poldke zadoščata dva posrednika, kar je očitno (še) manj kot dovoljeni trije oz. štirje.
  • Pač pa klic zanesljivo_hitrejsa("Berta", "Poldka", 1) vrne False, saj ni nobene poti od Berte do Poldke, ki bi imela le enega posrednika.

Še bolj dodatna naloga

Napiši funkcijo uredi(zmage), ki prejme slovar z zmagami (najbrž enak kot gornji) in 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 pred ali za Greto, pa je vseeno, prav tako je vseeno, ali je Jana pred ali za Špelo, saj ne moremo vedeti, katera od njih je hitrejša.

Primer pravilne ureditve, je, recimo

['Zoja', 'Jana', 'Špela', 'Črtomira', 'Tina', 'Žana', 'Berta',
 'Dani', 'Klara', 'Greta', 'Ana', 'Iva', 'Micka', 'Fanči',
 'Nina', 'Ema', 'Cilka', 'Liza', 'Helga', 'Urša', 'Olga',
 'Rezka', 'Vera', 'Poldka', 'Saša']

Lahko pa tudi:

['Zoja', 'Špela', 'Žana', 'Jana', 'Črtomira', 'Tina', ...

Testi