Naloge: Čudni poštar

Čudni poštar

Tole so reševali otroci na nekem tekmovanju.

Poštar Smiljan deli pošto tako, da ne gre po ulici po vrsti, temveč gre vedno k hiši, ki ima vsaj eno števko skupno s hišo, pred katero stoji trenutno. Tako lahko gre od hiše 23 k hiši 28, 31, ali 72, na pa k hiši 19, saj 19 nima ne števke 2 ne števke 3.

Zaradi tega včasih ne more dostaviti vse pošte! Danes bi moral odnesti pošto k hišam s številkami 11, 19, 29, 36, 40, 44, 52, 61, 70, 74, 83.

Koliko hišam bo lahko prinesel pošto, če začne pri pametni številki in kar se da pametno izbira pot?

Naloga je inspirirala funkcije, ki jih boste napisali danes.

Pari hiš

Napišite funkcijo pari_his(stevilke), ki dobi seznam številk in vrne množico vseh parov hiš, ki imajo vsaj eno skupno števko.

>>> pari_his([12, 23, 26, 54])
{(12, 23), (12, 26), (23, 12), (23, 26), (26, 12), (26, 23)}

Če gornji klic v resnici vrne {(26, 23), (12, 26), (23, 26), (23, 12), (12, 23), (26, 12)}, se ne vznemirjajte, saj je to v resnici eno in isto.

Namigi: najbrž boste potrebovali dvojno zanko. Ne pa trojne: razmislite, kako najpreprosteje ugotoviti, ali imata dve številki skupno števko. Ne pozabite, da se učimo o množicah. In ne pozabite, da je mogoče število x spremeniti v niz, če pokličemo str(x). Končno, ne spreglejte, da v množici ne sme biti parov ene in iste hiše, npr. (12, 12).

Legalne poti

Napišite funkciji legalna_pot(pot, pari) in legalna_pot_bp(pot, pari).

Funkcija legalna_pot(pot, pari) prejme neko pot, podano kot seznam, in množico parov, kakršne vrača funkcija pari_his. Funkcija naj vrne True, če bo poštar pripravljen prehoditi takšno pot, in False, če ne.

>>> pari = pari_his([12, 23, 26, 54])
>>> legalna_pot([23, 12, 26, 12], pari)
True

Druga funkcija, legalna_pot_bp(pot, pari), naj poleg tega preveri, da se nobena hiša v poti ne ponovi.

>>> legalna_pot_bp([23, 12, 26, 12], pari)
False

Graf številk

Napišite funkcijo graf_stevilk(pari), ki prejme seznam parov in vrne graf, zapisan kot slovar, katerega ključi so točke (številke), vrednosti pa množice točk, v katere je mogoče priti iz njih. Če jo pokličemo s pari iz naloge z Bobra,

graf_stevilk(
    {(83, 36), (36, 83), (36, 61), (61, 36), (61, 11), (11, 61),
     (61, 19), (19, 61), (11, 19), (19, 11), (19, 29), (29, 19),
     (29, 52), (52, 29),
     (70, 74), (74, 70), (74, 44), (44, 74),
     (44, 40), (40, 44), (40, 70), (70, 40),
     (40, 74), (74, 40)}),

mora vrniti

{83: {36},
 36: {83, 61},
 61: {36, 11, 19},
 11: {61, 19},
 19: {61, 29, 11},
 29: {19, 52},
 52: {29},
 70: {74, 40},
 74: {70, 44, 40},
 44: {74, 40},
 40: {70, 44, 74}}

Za malo razmišljanja: Dosegljivost

Napišite funkcijo dosegljivi(stevilka, graf), ki prejme začetno hišno številko in graf, kakršnega vrne prejšnja funkcija. Kot rezultat naj vrne množico vseh hiš, ki so dosegljive iz določene hiše.

>>> dosegljivi(36, graf)
{83, 36, 61, 11, 19, 29, 52}
>>> dosegljivi(74, graf)
{70, 74, 44, 40}

Za malo lomit zobe: Najdaljša pot

Rešite nalogo, ki so jo morali reševati otroci. ;)

Konkretno, napišite funkcijo najdaljsa_pot_od(zacetek, graf), ki prejme začetno številko in graf, kot rezultat pa vrne seznam s številkami na najdaljši poti, ki jo lahko opravi poštar, če začne na tej številki.

Nato napišite še funkcijo najdaljsa_pot(graf), ki vrne seznam s številkami na najdaljši poti, pri čemer sama ugotovi, kje začeti.

Pri reševanju naloge vam bo zelo v pomoč, kar se bomo učili čez dva tedna. :) (Rekurzija.)