Naloga

Pod Meglenim gorovjem je, kot nekateri vedo že dolgo, nekateri pa so morali čakati na film, cel labirint votlin. Bilbu bi bilo veliko lažje, če bi imel zemljevid. Mi ga imamo.

Zemljevid lahko shranimo tudi v obliki slovarja, v katerem so ključi številke sob, vrednosti pa sobe, v kateri pridemo po levi in po desni poti. Kadar kakšne poti ni, je ustrezni element enak None.

zemljevid = {0: [6, 3], 6: [5, 81], 3: [8, 24], 5: [2, 18], 81: [None, None], 8: [42, None], 24: [63, 13], 2: [7, 27], 18: [None, 35], 42: [None, 66], 63: [61, None], 13: [4, 12], 7: [None, None], 27: [None, None], 35: [None, None], 66: [None, None], 61: [None, None], 4:[None, None], 12: [None, None]}

Ogrevalna naloga

Napiši funkcijo prehodi_pot(zemljevid, soba, pot), ki kot argument prejme zemljevid (npr. zgornji slovar), začetno sobo (ta bo vedno 0, a to naj te ne moti) in pot, podano kot zaporedje znakov L in D (levo in desno). Kot rezultat mora vrniti sobo, v katero pelje podana pot.

>>> prehodi_pot(zemljevid, 0, "LLD") 18 >>> prehodi_pot(zemljevid, 0, "DDDD") 12 >>> prehodi_pot(zemljevid, 0, "L") 6 >>> prehodi_pot(zemljevid, 0, "") 0

Funkcija mora delovati za poljubni zemljevid, ne le za zgornjega.

>>> prehodi_pot({0: [1, 2], 1: [None, None], 2: [None, None]}, 0, "L") 1

Predpostaviti smeš, da je pot pravilna in se nikoli ne odpravi v hodnik, ki ga ni. Funkcijo lahko napišeš rekurzivno ali pa tudi ne, kakor želiš.

Obvezna naloga

Prstan se seveda vedno nahaja v sobi številka 42. Napiši funkcijo globina_prstana(zemljevid, soba), ki prejme zemljevid in številko začetne sobe, kot rezultat pa vrne globino te sobe - torej dolžino poti do nje. Na gornjem zemljevidu je globina sobe 42 enaka 3. Funkcija mora seveda delovati tudi na poljudnih drugih zemljevidih.

Dodatna naloga

Napiši funkcijo pot_do_prstana(zemljevid, soba), ki vrne pot do sobe številka 42. V gornjem primeru mora vrniti niz "DLL".

Rešitev

Prehodi pot

Nanizajmo nekaj rešitev, od preprostih do zanimivih.

Prva ni nič posebnega: korakamo po poti; ko vidimo L, stopimo v zemljevid[soba][0], ko D, v zemljevid[soba][1].

def prehodi_pot(zemljevid, soba, pot): for korak in pot: if korak == "L": soba = zemljevid[soba][0] else: soba = zemljevid[soba][1] return soba

Python ima nek grozni izraz if-else. Uporabimo ga lahko, da povemo, da je naslednja soba zemljevid[soba][0], če je korak == "L", sicer pa zemljevid[soba][0]. Ali, z istimi besedami v Pythonu:

def prehodi_pot(zemljevid, soba, pot): for korak in pot: soba = zemljevid[soba][0] if korak == "L" else zemljevid[soba][1] return soba

Če pogledamo pozorneje, vidimo, da gremo vedno v zemljevid[soba][nekaj], pri čemer je nekaj 0, če je korak == "L", sicer pa 1. Torej:

def prehodi_pot(zemljevid, soba, pot): for korak in pot: soba = zemljevid[soba][0 if korak == "L" else 1] return soba

To pa je kajpak brez zveze: rečemo lahko preprosto korak == "D". Ta izraz, korak == "D" ima vrednost False (kar je isto kot 0), kadar je korak enak "L" in True (kar je isto kot 1), kadar je korak enak "D".

def prehodi_pot(zemljevid, soba, pot): for korak in pot: soba = zemljevid[soba][korak == "D"] return soba

Korakanje lahko, če vemo kaj več, prepustimo tudi funkciji reduce:

from functools import reduce def prehodi_pot(zemljevid, soba, pot): return reduce(lambda soba, korak:zemljevid[soba][korak=="D"], pot, soba)

Najlepša rešitev te naloge pa je pravzaprav kar rekurzivna.

def prehodi_pot(zemljevid, soba, pot): return pot and prehodi_pot(zemljevid, zemljevid[soba][pot[0] == "D"], pot[1:]) or soba

Če je pot različna od 0, funkcija vrne tisto sobo, ki jo dobi z (novim) klicem same sebe, pri čemer kot argument da naslednjo sobo in pot brez prvega znaka.

Če pa je pot prazna, vrne trenutno sobo.

Funkcija ne bi delala dobro, kadar bi rekurzivni klic funkcije prehodi_pot vrnil 0. Tako, kot so sestavljeni naši zemljevidi, se to ne zgodi. Če bi se tega bali, pa napišemo, kot je bolj prav (in manj pregledno):

def prehodi_pot(zemljevid, soba, pot): return prehodi_pot(zemljevid, zemljevid[soba][pot[0] == "D"], pot[1:]) if pot else soba

Globina prstana

Zmenili se bomo takole: če pod trenutno sobo ni sobe 42, naj funkcija vrne None. Naloga je postavljena tako, kot da soba 42 vedno obstaja, zato o tem, kaj naj funkcija vrne, kadar te sobe ni, ne govori - saj nima smisla. V rekurzivnem klicu pa bomo to potrebovali: ko bomo poklicali funkcijo za neko sobo v nižjem nadstropju, bo funkcija vrnila bodisi globino sobe 42, bodisi None.

Zdaj, ko smo se dogovorili o tem, je reč preprosta. Če smo že v sobi 42, vrnemo globino 0 (if soba == 42: return 0. Sicer pogledamo sobi na obeh straneh (for spodaj in zemljevid[soba]). Če spodnja soba obstaja (if spodaj is not None - enako dobro bi bilo tudi if spodaj, pa tudi if spodaj != None bi delovalo), potem pogledamo, kako globoko pod to, spodnjo sobo, je prstan (g = globina_prstana(zemljevid, spodaj)). Če funkcija vrne None, pod to spodnjo sobo ni prstana. Vendar nas to ne zanima, zanima nas primer, ko funkcija ne vrne None, temveč globino (if g is not None). V tem primeru je od trenutne sobe do prstana toliko, kolikor je bilo od spodnje sobe do prstana in še 1 zraven (return 1 + g).

def globina_prstana(zemljevid, soba): if soba == 42: return 0 for spodaj in zemljevid[soba]: if spodaj is not None: g = globina_prstana(zemljevid, spodaj) if g is not None: return 1 + g

Zanka for gre čez obe spodnji sobi, na podoben način, kot smo pri preiskovanju rodbine celjskih grofov delali zanko prek otrok. Če ne na eni ne na drugi strani ne najde ničesar, tudi ne vrne ničesar, torej vrne None.

Pot do prstana

Funkcija, ki izračuna pot do prstana, je na las podobna funkciji za izračun globine. Razlikujeta se le po tem, kaj vračata: ena vrača globino, druga pot. Če smo že v sobi 42, smo prej vrnili 0, zdaj prazno pot, "". Če se prek spodnje sobe pride do prstana, smo prej vrnili globino, ki smo ji prišteli 1, zdaj vrnemo pot, ki ji prištejemo korak, ki vodi v spodnjo sobo.

Zanko prek spodnjih sob napišemo malenkost drugače kot prej: namesto for spodaj in zemljevid[soba] zdaj pišemo for spodaj, smer in zip(zemljevid[soba], "LD"), da dobimo številko spodnje sobe in še korak, ki vodi vanjo, "L" ali "D".

def pot_do_prstana(zemljevid, soba): if soba == 42: return "" for spodaj, smer in zip(zemljevid[soba], "LD"): if spodaj is not None: pot = pot_do_prstana(zemljevid, spodaj) if pot is not None: return smer + pot
Last modified: Saturday, 30 November 2013, 6:02 PM