MOL je poslal zemljevid ovir na kolesarski poti. Zemljevid je shranjen kot seznam nizov, ki predstavljajo "vrstice": # predstavlja oviro, . pa prosto pot.

Ker smo prejšnji teden napisali program, ki sprejme opis ovir kot seznam trojk (x0, x1, y), bi radi pretvorili MOLov zemljevid v takšno obliko.

Ogrevalna naloga

Napiši program, ki se začne z opisom ovire v eni vrstici, na primer

ovire = ".##..####...##"

Program mora izpisati seznam parov, ki predstavljajo začetke in konce ovir. Za gornjo postavitev je to [(2, 3), (6, 9), (13, 14)]. Ne spreglej, da koordinate niso opisane po "Pythonovsko": prvi stolpec ima indeks 1 in obe meji sta vključeni ((6, 9) pokriva tudi vrstico 9, torej vsebuje 4 #).

Program obvezno preskusi na nizih ".##..####...##" in ##..#...# (ki se pretvori v [(1, 2), (5, 5), (9, 9)]). Pazi: v podatkih morajo biti napisani nizi v točno takšni obliki. Tu ne dodajaj ničesar na začetel ali konec; če želiš, pa lahko to kasneje naredi program sam.

Rešitev

Da bomo preskušali vse sitnosti naenkrat, vzemimo tale niz:

ovire = "##...#.###..##"
#        12345678901234

Vsebuje oviro na začetku in na koncu, oviro dolžine 1 in oviri, ki sta razmaknjeni za 1. Spodaj smo napisali številke, da lažje razberemo pričakovani rezultat: [(1, 2), (6, 6), (7, 9), (13, 14)].

Nalogo je možno rešiti na kup načinov. Vsem je skupno to, da se je potrebno dobro zorganizirati. Da naloga ne bi bila pretežka, sem na predavanju, namenjenem začetnikom (starejši mački pa naj se kar malo potrudijo) predlagal, da na začetek in konec niza prilepijo piko, potem pa opazujejo vse #, ki so takoj za ali tik pred piko. Zanimajo nas njihovi indeksi; tisti za piko predstavljajo začetke, tisti po pa konce ovir.

ovire = "##...#.###.####.##"


ovire = "." + ovire + "."
bloki = []
for i in range(len(ovire)):
    if ovire[i] == "#":
        if ovire[i - 1] == ".":
            zacetek = i
        if ovire[i + 1] == ".":
            bloki.append((zacetek, i))
print(bloki)
[(1, 2), (6, 6), (8, 10), (12, 15), (17, 18)]

Če vidimo #, pred katerim je ., si zapomnim, da je to začetek. Če vidimo #, za katerim je ., v seznam blokov dodamo blok od začetka do trenutnega indeksa.

Za posamične # se zgodi oboje naenkrat, zato tu nismo uporabili kakega else ali elif.

Stolpce v tej nalogi štejemo od 1 ne od 0. Naši indeksi bodo pravilni, saj smo na začetek dodali ..

Zdaj pa izboljšave.

Na predavanjih običajno stokam, da range(len(ovire)) ni lepo pisati - sploh, kadar potrebuješ tako indeks kot element. Raje pišimo:

ovire = "##...#.###..##"


ovire = "." + ovire + "."
bloki = []
for i, znak in enumerate(ovire):
    if znak == "#":
        if ovire[i - 1] == ".":
            zacetek = i
        if ovire[i + 1] == ".":
            bloki.append((zacetek, i))
print(bloki)
[(1, 2), (6, 6), (8, 10), (13, 14)]

Se lahko zgodi, da bi bil indeks i + 1 prevelik? To bi bilo možno le, če bi bil zadnji znak # in bi se torej spraševali po znaku za njim. To pa ne more biti, saj smo na konec dodali piko. Prav tako i - 1 nikoli ne bo -1, saj je ničti znak vedno . in ne #.

Še lepše je, če uporabimo čistokrvni zip. V tem primeru lahko pike dodamo kar v klicu zip-a.

ovire = "##...#.###..##"


bloki = []
for i, (prej, znak, potem) in enumerate(zip("." + ovire, ovire, ovire[1:] + "."), start=1):
    if znak == "#":
        if prej == ".":
            zacetek = i
        if potem == ".":
            bloki.append((zacetek, i))
print(bloki)
[(1, 2), (6, 6), (8, 10), (13, 14)]

Tule se je sicer zdaj zgodilo kar nekaj reči, o katerih se na predavanjih še nismo pogovarjali.

Najprej, kaj zipamo. Tole

Okrog zip-a pride še enumerate, da bomo imeli indekse; vse skupaj je potrebno razpakirati kot for i, (prej, znak, potem), saj imamo pare (indeks, element), pri čemer je element trojka.

Končno, ker morajo indeksi teči od 1, smo v enumerate dodali start=1.

Zdaj pa malo drugačna različica: zabeležimo vse spremembe.

ovire = "##...#.###..##"


ovire = "." + ovire + "."
spremembe = []
for i in range(len(ovire)):
    if ovire[i] != ovire[i - 1]:
        spremembe.append(i)
        
spremembe
[1, 3, 6, 7, 8, 11, 13, 15]

Te indekse je potrebno popariti:

list(zip(spremembe[::2], spremembe[1::2]))
[(1, 3), (6, 7), (8, 11), (13, 15)]

Žal so drugi elementi teh terk - konci blokov - preveliki. Ker terk ni mogoče spreminjati, nam (dokler se ne naučimo, kako to storiti drugače) ne preostane drugega kot prepisati jih v nov seznam. No, saj ni tako hudo.

ovire = "##...#.###..##"


ovire = "." + ovire + "."
spremembe = []
for i in range(len(ovire)):
    if ovire[i] != ovire[i - 1]:
        spremembe.append(i)
        
bloki = []
for zac, kon in zip(spremembe[::2], spremembe[1::2]):
    bloki.append((zac, kon - 1))
    
bloki
[(1, 2), (6, 6), (8, 10), (13, 14)]

Pa brez dodajanja pik na začetek in konec? Gre, samo malo več sitnosti je. Recimo tako:

ovire = "##...#.###..##"

prej = "."
bloki = []
for i, znak in enumerate(ovire, start=1):
    if znak != prej:
        if znak == "#":
            zacetek = i
        else:
            bloki.append((zacetek, i))
    prej = znak
    
if ovire[-1] == "#":
    bloki.append((zacetek, len(ovire)))
    
bloki        
[(1, 3), (6, 7), (8, 11), (13, 14)]

V spremenljivko prej beležimo, kakšen je bil prejšnji znak. V začetku se pretvarjamo, da je ".". To poskrbi, da zaznamo oviro na začetku niza. Za oviro na koncu pa poskrbimo z if po zanki.

Če ne vemo, da ima enumerate lahko tudi argument start, namesto i vedno pišemo i + 1.

Obvezna naloga

Napiši program, ki prejme celotni zemljevid in izpiše seznam ovir, kot smo ga vajeni iz prejšnje naloge. Če zemljevid definiramo z

zemljevid = [
    "......",
    "..##..",
    ".##.#.",
    "...###",
    "###.##",
]

mora izpisati [(3, 4, 2), (2, 3, 3), (5, 5, 3), (4, 6, 4), (1, 3, 5), (5, 6, 5)].

Pazi, tudi vrstice so oštevilčene od 1.

Rešitev

Vzamemo katerokoli od prejšnjih rešitev in jo zapremo v zanko

for y, ovire in enumerate(zemljevid, start=1):

ter k paru koordinat x dodamo še številko vrstice, y. Če ne vemo, da lahko funkciji enumerate podamo argument start=2, pa namesto y dodajamo y + 1.

zemljevid = [
    "......",
    "..##..",
    ".##.#.",
    "...###",
    "###.##",
]


bloki = []
for y, ovire in enumerate(zemljevid):
    ovire = "." + ovire + "."
    for i, znak in enumerate(ovire):
        if znak == "#":
            if ovire[i - 1] == ".":
                zacetek = i
            if ovire[i + 1] == ".":
                bloki.append((zacetek, i, y + 1))
print(bloki)
[(3, 4, 2), (2, 3, 3), (5, 5, 3), (4, 6, 4), (1, 3, 5), (5, 6, 5)]

Dodatna naloga

Naredi obratno: napiši program, ki na podlagi seznama ovir izpiše zemljevid. Podatki naj bodo zapisani v spremenljivki ovire, na primer

ovire = [(3, 4, 2), (2, 3, 3), (5, 5, 3), (4, 6, 4), (1, 3, 5), (5, 6, 5)]

Rešitev

Najprej ugotovimo širino in višino ter sestavimo prazen zemljevid:

sirina = visina = 0
for _, x1, y in ovire:
    if x1 > sirina:
        sirina = x1
    if y > visina:
        visina = y
        
# Kot bomo nekoč videli, je tole malo nevarno,
# ampak pri nizih deluje
zemljevid = ["." * sirina] * visina

zemljevid
['......', '......', '......', '......', '......']

Potem napolnimo zemljevid: gremo čez ovire in menjamo ustrezne vrstice zemljevida s takšnimi, v katere dodamo ovire.

for x0, x1, y in ovire:
    vrstica = zemljevid[y - 1]
    zemljevid[y - 1] = vrstica[:x0 - 1] + "#" * (x1 - x0 + 1) + vrstica[x1:]
    #                  ^^^^^^^^^^^^^^^^   ^^^^^^^^^^^^^^^^^^^   ^^^^^^^^^^^^
    #                   del pred oviro            ovira           po oviri

V resnici je kar preprosto, le o indeksih moramo razmišljati. Od y je potrebno odšteti 1, ker ima prva vrstica v ovire številko 1, Python pa šteje od 0. Iz istega razloga je potrebno odšteti 1 od x0. Dolžina ovire je x1 - x0 + 1; ena prištejemo, ker ovira obsega tudi x1. Del po oviri pa se začne po x1; tu ne prištejemo ničesar.

Preverimo rezultat:

for vrstica in zemljevid:
    print(vrstica)
......
..##..
.##.#.
...###
###.##

Celotna rešitev dodatne naloge je torej:

sirina = visina = 0
for _, x1, y in ovire:
    if x1 > sirina:
        sirina = x1
    if y > visina:
        visina = y
zemljevid = ["." * sirina] * visina

for x0, x1, y in ovire:
    vrstica = zemljevid[y - 1]
    zemljevid[y - 1] = vrstica[:x0 - 1] + "#" * (x1 - x0 + 1) + vrstica[x1:]

Zanimivo, da je del s iskanjem širine in višine celo daljši od dejanske naloge. Ko bomo znali več, bomo pisali

zemljevid = ["." * max(x1 for _, x1, _ in ovire)] * max(y for _, _, y in ovire)

In če bi bile ovire podane bolj Pythonovsko - tako da bi šteli od 0 in ne vključili gornje meje, bi bil drugi del nekoliko preprostejši:

for x0, x1, y in ovire:
    vrstica = zemljevid[y]
    zemljevid[y] = vrstica[:x0] + "#" * (x1 - x0) + vrstica[x1:]

Izziv: rešitev z numpy

Nalogo je čisto preprosto rešiti z numpy-jem. Ampak samo tistim, ki obvladajo numpy.

import numpy as np

zemljevid = [
    "......",
    "..##..",
    ".##.#.",
    "...###",
    "###.##",
]

zemljevid = np.array([[0] + [int(c == "#")
                      for c in vrstica] + [0] for vrstica in zemljevid])

zemljevid je po tem tabela v numpy-ju, ki vsebuje enke na mestih, kjer so ovire; levo in desno sta dodana še stolpca ničel.

zemljevid
array([[0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 1, 1, 0, 0, 0],
       [0, 0, 1, 1, 0, 1, 0, 0],
       [0, 0, 0, 0, 1, 1, 1, 0],
       [0, 1, 1, 1, 0, 1, 1, 0]])

Ovire se začnejo tam, kjer enica sledi ničli in končajo tam, kjer enici sledi ničla.

S tremi vrsticami numpy-ja - brez kakršnekoli zanke v Pythonu - je možno pridelati tabelo, ki je v bistvu rešitev naloge:

array([[3, 4, 2],
       [2, 3, 3],
       [5, 5, 3],
       [4, 6, 4],
       [1, 3, 5],
       [5, 6, 5]])

Znaš?

Nasveti:

Če rešiš nalogo na ta način (in si prepričan, da deluje pravilno), jo lahko oddaš kot rešitev obveznega dela domače naloge.

Rešitev

Tole je zemljevid brez prvega stolpca:

zemljevid[:, 1:]
array([[0, 0, 0, 0, 0, 0, 0],
       [0, 0, 1, 1, 0, 0, 0],
       [0, 1, 1, 0, 1, 0, 0],
       [0, 0, 0, 1, 1, 1, 0],
       [1, 1, 1, 0, 1, 1, 0]])

In tole brez zadnjega:

zemljevid[:, :-1]
array([[0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 1, 1, 0, 0],
       [0, 0, 1, 1, 0, 1, 0],
       [0, 0, 0, 0, 1, 1, 1],
       [0, 1, 1, 1, 0, 1, 1]])

Če ju odštejemo, dobimo tole:

zemljevid[:, 1:] - zemljevid[:, :-1]
array([[ 0,  0,  0,  0,  0,  0,  0],
       [ 0,  0,  1,  0, -1,  0,  0],
       [ 0,  1,  0, -1,  1, -1,  0],
       [ 0,  0,  0,  1,  0,  0, -1],
       [ 1,  0,  0, -1,  1,  0, -1]])

Enice so natančno tam, kjer se začenjajo ovire. Koordinate začetkov dobimo z

np.nonzero(zemljevid[:, 1:] - zemljevid[:, :-1] == 1)
(array([1, 2, 2, 3, 4, 4]), array([2, 1, 4, 3, 0, 4]))

Koordinate koncev dobimo na enak način, le da odštevamo v drugo smer. Ali, preprosteje, gledamo, kje so -1.

np.nonzero(zemljevid[:, 1:] - zemljevid[:, :-1] == -1)
(array([1, 2, 2, 3, 4, 4]), array([4, 3, 5, 6, 3, 6]))

Rešitev celotne obvezne naloge - če dopuščamo, da je rezultat tabela trojk namesto seznama terk - je potem:

y, x0 = np.nonzero(zemljevid[:, 1:] - zemljevid[:, :-1] == 1)
_, x1 = np.nonzero(zemljevid[:, :-1] - zemljevid[:, 1:] == 1)
ovire = np.column_stack((x0 + 1, x1, y + 1))

ovire
array([[3, 4, 2],
       [2, 3, 3],
       [5, 5, 3],
       [4, 6, 4],
       [1, 3, 5],
       [5, 6, 5]])

Tako bi to nalogo rešil profesionalni programer v Pythonu - sploh, če bi bilo ovir veliko in bi mu hitrost numpy-ja kaj pomenila.