Zmagozmagovalci

V zadnji nalogi so se kolesarji pomerili v neki dirki na izpadanje. Problem vseh tekem na izpadanje je, da na koncu vemo le, da je zmagovalec boljši od ostalih, ne pa tudi, v kakšnem vrstnem redu bi končali tekmo ostali, če ne bi izpadli.

V neki dirki so sodelovale Jana, Tina, Berta, Dani, Greta, Liza in Micka. Zmagala je Jana, torej lahko vemo, da je hitrejša od njih. V neki drugi so bile Liza, Olga, Rezka in Vera. Zmagala je Liza. Potem lahko vemo ne le, da je Liza hitrejša od Rezke, temveč tudi, da je Jana hitrejša od Rezke (saj je hitrejša od Olge, ki je hitrejša od Rezka).

Obvezna naloga

Napiši funkcijo hitrejsi(kolesar1, kolesar2, razmerja), prejme imeni dveh kolesarjev in vrne ime hitrejšega od njiju. Če ni znano, kdo je hitrejši, pa vrne None. Klic hitrejsi("Olga", "Dani", razmerja) vrne Dani, ker je Dani hitrejša od Cilke in ta od Olge. Klic hitrejsi("Berta", "Micka") vrne None, ker ne obstaja pot ne od Berte do Micke ne obratno.

Najtoplejše priporočilo: ta funkcija najbrž ne bo rekurzivna. Pač pa si napiši drugo, pomožno funkcijo, ki bo rekurzivna in ki jo bo funkcija hitrejsi poklicala dvakrat. (Prvič zato, da preveri, ali je prvi hitrejši od drugega. Drugič zato, da preveri, ali je morda obratno.)

Kdor želi, pa lahko najprej reši dodatno nalogo in napisano funkcijo uporabi v obvezni nalogi.

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

Dodatna naloga

Napiši funkcijo dokazov(kolesar1, kolesar2, razmerja), ki vrne število dokazov, da je kolesar1 hitrejši kot kolesar2.

• 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 kolesar1 ni hitrejši kot kolesar2 (ker razmerje ni znano ali pa je celo počasnejši) funkcija vrne 0.

Testi