Rovi

Nekje so izkopali podzemni rov po teh navodilih: "^2 >6 ^6 <1 v3 <6 v4". Rezultat je videti tako.

Dva metra nižje so izkopali takšen rov: ">4 ^3 >4 ^3 <6 v8 >1 ^5". Rezultat je na sliki.

Če narišemo oba skupaj, je to videti tako.

Povsod, kjer sta rova eden nad drugim so naredili jašek, ki omogoča prehod med rovoma. Takšnih jaškov bo tu torej osem.

Predpostaviti smeš, da se rova vedno samo sekata, nikoli pa ne tečeta eden na drugim. V tem primeru bi se zgornji rov lahko namreč vdrl v spodnjega.

Predpostaviti smeš, da so vse razdalje pozitivna cela števila.

Ne smeš pa predpostaviti, da so vse razdalje enomestne. Možen je tudi rov ">100 ^42 <13".

Obvezni del

Za začetek napiši funkcijo v_pot(s), ki prejme niz, kot so gornji, in ga razbije v seznam terk: prvi element terke je smer, drugi razdalja. Klic v_pot(">100 ^42 <13") vrne [(">", 100), ("^", 42), ("<", 13)].

Nato napiši funkcijo tocke(s), ki prejme gornji seznam terk in sestavi seznam vseh celoštevilskih koordinat, prek katerih gre rov. Klic tocke([(">", 3), ("v", 2), (">", 2)]) vrne [(0, 0), (1, 0), (2, 0), (3, 0), (3, -1), (3, -2), (4, -2), (5, -2)]. Rov se vedno začne na koordinatah (0, 0).

Končno, napiši funkcijo presecisca(s, t), ki prejme dve poti kot niz in vrne seznam njunih presečišč. Upoštevaj, da so črte lahko tudi zelo dolge.

Nasvet 1: funkcija naj pokliče prejšnji funkciji.

Nasvet 2: tule bo nujno uporabiti slovarje (ali kaj podobnega). Če boste uporabljali sezname, bo funkcija preživela prvi test, ne pa drugega, saj je tam točk preveč.

V slovarju, ki ga boš naredil(a), bodo vrednosti nepomembne, pomembni bodo le ključi. Spomni se konca predavanj. Pogledaš lahko tudi dokumentacijo za funkcijo dict.fromkeys. Mogoče ti pride prav. Če ne znaš, mi napiši mail.

Rešitev

Najprej funkcija pot: niz je potrebno razbiti na seznam nizov, kot je, na primer "^12", nato pa iti prek tega razbitja ter njegove elemente predelati v terke in zlagati v seznam.

def v_pot(s):
    pot = []
    for korak in s.split():
        pot.append((korak[0], int(korak[1:])))
    return pot

Zdaj pa tocke.

Kot smo na hitro pogledali na predavanjih, se nam splača sestaviti slovar smeri = {"<": (-1, 0), ">": (1, 0), "v": (0, -1), "^": (0, 1)}. Če imamo neko smer, bomo z dx, dy = smeri[smer] prebrali, kakšne so spremembe koordinat pri premiku v to smer. Nadaljevanje je potem preprosto.

def tocke(s):
    smeri = {"<": (-1, 0), ">": (1, 0), "v": (0, -1), "^": (0, 1)}

    x, y = 0, 0
    tocke = [(x, y)]
    for smer, razdalja in s:
        dx, dy = smeri[smer]
        for i in range(razdalja):
            x += dx
            y += dy
            tocke.append((x, y))
    return tocke

Ostanejo še presečišča.

def presecisca(s, t):
    tocke1 = dict.fromkeys(tocke(v_pot(s)))
    skupne = []
    for tocka in tocke(v_pot(t)):
        if tocka in tocke1:
            skupne.append(tocka)
    return skupne

Niz s pretvorimo prek funkcij v_pot in potem prek tocke, nato pa z dict.fromkeys sestavimo slovar, katerega ključi so točke, ki jih bomo potem lahko hitro iskali.

Zdaj gremo prek točk drugega seznama in za vsako preverimo, ali je v slovarju. Če je, ga dodamo v seznam skupne.

Spreminjanje v slovar je tule ključno: če izpustimo dict.fromkeys in namesto tocke1 = dict.fromkeys(tocke(v_pot(s))) pišemo tocke1 = tocke(v_pot(s)), bo funkcija še vedno delovala in preživela krajši test, pri daljšem pa bo prepočasna.

Dodatna naloga

Recimo, da se odpravimo po enem rovu, nato v enem od presečišč skočimo v drugi rov in se po njem (v nasprotni smeri od smeri kopanja) vrnemo na začetek. Mesto, kjer bomo preskočili v drugi rov si izberemo tako, da bo naša skupna pot čim krajša. Če v gornjem primeru začnemo pot v modrem rovu, bomo v rdečega preskočili v tretjem presečišču, in naša pot bo dolga 12 korakov. Če bi preskočili v prvem presečišču, bi morali opraviti še zelo dolgo pot po rdečem rovu. (Da bi preskočili v prvem presečišču in šli DOL, ne velja, saj to ni potovanje v nasprotni smeri kopanja).

Napiši funkcijo najkrajsa_razdalja(s, t), ki prejme dve poti (kot niza) in vrne najkrajšo možno razdaljo, ki jo moramo prehoditi.

Nasvet: funkcija tocke(s) vrne le seznam točk. Boljše bi bilo, če bi vrnila slovar, ki bi povedal, kakšna je razdalja do vsake točke. S tem si boš lahko več pomagal(a).

Rešitev

Kot svetuje nasvet, najprej pripravimo uporabnejšo različico funkcijo tocke_koraki, ki namesto seznama vrne slovar, katerega ključi so koordinate, vrednosti pa število korakov, ki jih potrebujemo do tja.

def tocke_koraki(s):
    smeri = {"<": (-1, 0), ">": (1, 0), "v": (0, -1), "^": (0, 1)}

    x, y = 0, 0
    tocke = {(x, y): 0}
    korakov = 0
    for smer, razdalja in s:
        dx, dy = smeri[smer]
        for i in range(razdalja):
            x += dx
            y += dy
            korakov += 1
            if (x, y) not in tocke:
                tocke[(x, y)] = korakov
    return tocke

Zdaj pa sestavimo takšna slovarja točk. Gremo čez prvega (uporabljali bomo items, da dobimo tako koordinato kot razdaljo) in za vsako točko preverimo, ali se pojavi tudi v drugem seznamu. Če je skupno število korakov manjše od najmanjšega, ki smo ga našli doslej, si ga zapomnimo.

def najkrajsa_pot(s, t):
    tocke1 = tocke_koraki(v_pot(s))
    tocke2 = tocke_koraki(v_pot(t))
    najkrajse = None
    for tocka, korakov in tocke1.items():
        if tocka != (0, 0) and tocka in tocke2:
            skupno = korakov + tocke2[tocka]
            if najkrajse is None or skupno < najkrajse:
                najkrajse = skupno
    return najkrajse