Naloga vsebuje teste. Naloga je rešena samo, če prestane vse teste. Poglej navodila za poganjanje testov.

MOL je poslal zemljevid ovir na kolesarski poti. Zemljevid je shranjen kot seznam nizov, ki predstavljajo "vrstice": `#` predstavlja oviro, `.` pa prosto pot. Tipičen primer korektno zašikanirane kolesarske steze je

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

Napiši naslednje funkcije.

## 1. Dolžina ovir

`dolzina_ovir(vrstica)` prejme eno vrstico, na primer `".##.####...##."` in vrne skupno dolžino ovir, torej, število znakov `#` (v tem primeru 8).

### Rešitev

Pripravimo si vrstico, da bomo imeli na čem preskušati funkcije. (Domači nalogi so priloženi testi, ki jih sami kličejo in preskušajo.)

    vrstica = ".##.####...##."

Prešteti moramo število `#` v nizu.

Če ne vemo ničesar od tega, česar se še nismo učili, to storimo z zanko.

    def dolzina_ovir(vrstica):
        ovir = 0
        for znak in vrstica:
            if znak == "#":
                ovir += 1
        return ovir

    dolzina_ovir(vrstica)

    8

Če se spomnimo, da je `True` isto kot `1` in `False` isto kot `0`, lahko seštevamo kar `znak == "#"`. Ta izraz bo imel vrednost `True` ali `False` torej `0` ali `1`.

    def dolzina_ovir(vrstica):
        ovir = 0
        for znak in vrstica:
            ovir += znak == "#"
        return ovir

    dolzina_ovir(vrstica)

    8

Ali je to lepo ali ne, je stvar okusa. Dobro pa je vedeti, da bomo znali nekoč napisati

    def dolzin_ovir(vrstica):
        return sum(znak == "#" for znak in vrstica)

    dolzina_ovir(vrstica)

    8

Vse to je, po drugi strani, nesmiselno, saj nizi znajo sami povedati, kolikokrat vsebujejo določen znak. Kot se bomo naučili prav v tem tednu, lahko nalogo rešimo preprosto z

    def dolzina_ovir(vrstica):
        return vrstica.count("#")

    dolzina_ovir(vrstica)

    8

## 2. Število ovir

`stevilo_ovir(vrstica)` prejme vrstico in vrne število ovir v vrstici. Za gornji primer mora vrniti 3, saj imamo najprej eno dvojno šikano, nato eno četverno in potem spet eno dvojno - skupaj tri.

### Razmislek in priprava

Ovir je toliko kot začetkov ovir. Torej toliko kot znakov `#`, ki se nahajajo neposredno za znakom `.` ali pa na začetku niza.

Spet si pripravimo vrstico - tokrat takšno, ki bo imela oviro tudi čisto na začetku in na koncu, saj bosta prav tidve povzročali sitnosti.

    vrstica = "##.##.####...#....#"

Tu imamo torej `5` ovir.

Očitno spet potrebujemo zanko, s katero bomo pregledali vse znake v nizu `vrstica`. Vendar bomo poleg trenutnega znaka potrebovali tudi prejšnjega.

### Grda rešitev: ne počnite tega ...

Začnimo z najgršo rešitvijo: zanko prek indeksov.

    def stevilo_ovir(vrstica):
        ovir = 0
        for i in range(len(vrstica)):
            if vrstica[i] == "#" and (i == 0 or vrstica[i - 1] == "."):
                ovir += 1
        return ovir

    stevilo_ovir(vrstica)

    5

Ta rešitev deluje, to pa je tudi vse, kar lahko dobrega povemo o njej.

No, mnogi jo imajo za dobro, ker je enaka rešitvi, ki bi jo napisali v kakem drugem jeziku, ki so se ga učili od prej in ki temelji na tem, da na veliko indeksiramo levo in desno, naprej in nazaj. S tem v principu ni nič narobe, to včasih počnemo tudi v Pythonu. Python pa omogoča tudi drugačen način razmišljanja pri progrmairanju, in ta včasih vodi do lepših, jasnejših, preprostejših rešitev. Poglejmo.

### Rutinska rešitev v Pythonu: `zip` čez pare

Da dobimo pare zaporednih znakov, uporabimo `zip(vrstica, vrstica[1:])`.

    def stevilo_ovir(vrstica):
        ovir = 0
        for prej, zdaj in zip(vrstica, vrstica[1:]):
            if prej == "." and zdaj == "#":
                ovir += 1
        return ovir

    stevilo_ovir(vrstica)

    4

Funkcija vrne `4`, ker smo spregledali prvo oviro. Seveda, pred njo ni pike. Ali, z vidika gornjega programa, prvi znak niza `vrstica`, v našem zoprnem primeru ravno `#`, se nikoli ne pojavi v `zdaj`, temveč le v `prej`.

To bo preprosto rešiti: ker vemo, da bomo oviro na začetku vedno spregledali, prištejmo 1, če je prvi znak `#`.

    def stevilo_ovir(vrstica):
        ovir = 0
        for prej, zdaj in zip(vrstica, vrstica[1:]):
            if prej == "." and zdaj == "#":
                ovir += 1
        if vrstica[0] == "#":
            ovir += 1
        return ovir

    stevilo_ovir(vrstica)

    5

Ali število ovir kar v začetku nastavimo na 0 namesto na 1.

    def stevilo_ovir(vrstica):
        if vrstica[0] == "#":
            ovir = 1
        else:
            ovir = 0
        for prej, zdaj in zip(vrstica, vrstica[1:]):
            if prej == "." and zdaj == "#":
                ovir += 1
        return ovir

    stevilo_ovir(vrstica)

    5

Lahko pa uporabimo operator `if - else` (ekvivalenkt `? :` iz drugih jezikov), če vemo zanj.

    def stevilo_ovir(vrstica):
        ovir = 1 if vrstica[0] == "#" else 0
        for prej, zdaj in zip(vrstica, vrstica[1:]):
            if prej == "." and zdaj == "#":
                ovir += 1
        return ovir

    stevilo_ovir(vrstica)

    5

Pythonov operator `if - else` je čuden, nekoliko zanemarjen (ne brez razloga). Python ga je dobil šele, ko je dopolnil že 12 let, po tem, ko so leta in leta cincali, ali sploh in kako. Kogar zanima več, lahko prebere povzetek debate, ki nudi tudi zanimiv vpogled v to, kako se oblikuje jezik, kot je Python.

Tu se ga brez težav znebimo, če se spomnimo, da je `True` enak `1` in `False` enak `0`.

    def stevilo_ovir(vrstica):
        ovir = vrstica[0] == "#"
        for prej, zdaj in zip(vrstica, vrstica[1:]):
            if prej == "." and zdaj == "#":
                ovir += 1
        return ovir

    stevilo_ovir(vrstica)

    5

Tudi enica, ki jo prištevamo znotraj zanke, je samo stvar pogoja, torej bo delovalo tudi

    def stevilo_ovir(vrstica):
        ovir = vrstica[0] == "#"
        for prej, zdaj in zip(vrstica, vrstica[1:]):
            ovir += prej == "." and zdaj == "#"
        return ovir

    stevilo_ovir(vrstica)

    5

Ker sta `prej` in `zdaj` niza, ju lahko tudi seštejemo in skrajšamo pogoj.

    def stevilo_ovir(vrstica):
        ovir = (vrstica[0] == "#")
        for prej, zdaj in zip(vrstica, vrstica[1:]):
            ovir += (prej + zdaj == ".#")
        return ovir

    stevilo_ovir(vrstica)

    5

Oklepaji, v katere sem zaprl pogoje, so nepotrebni, vendar povečajo čitljivost. Tale kombinacija `+=` in`==` je sicer videti strašljiva in malenkost nepregledna.

### Ustvarjalnejša rešitev: tudi zip čez pare

Rešitev je sicer čisto lepa, najbrž pa nam gre na živce ločeno obravnavanje prvega znaka. Meni že.

Lepo bi bilo, če bi bil z začetku `zdaj` prvi znak. Kaj pa naj bo potem `prej`? Preprosto: pika!

    def stevilo_ovir(vrstica):
        ovir = 0
        for prej, po in zip("." + vrstica, vrstica):
            ovir += prej + po == ".#"
        return ovir

Razumemo trik? Prej smo `zip`-ali

    print(vrstica)
    print(vrstica[1:])

    ##.##.####...#....#
    #.##.####...#....#

Zdaj pa zipamo

    print("." + vrstica)
    print(vrstica)

    .##.##.####...#....#
    ##.##.####...#....#

V prejšnjem primeru se je prvi znak pojavil le v prvi vrstici, v vlogi `prej`, poparjen z drugim znakom. Zdaj pa se prvič pojav v drugi vrstici, poparjen s piko, ki jo dodamo preden.

Če zdaj primerjamo rešitev, ki sem jo ozmerjal z grdo,

    def stevilo_ovir(vrstica):
        ovir = 0
        for i in range(0, len(vrstica)):
            if vrstica[i] == "#" and (i == 0 or vrstica[i - 1] == "."):
                ovir += 1
        return ovir

in tole, zadnjo

    def stevilo_ovir(vrstica):
        ovir = 0
        for prej, po in zip("." + vrstica, vrstica):
            ovir += (prej + po == ".#")
        return ovir

vidimo, zakaj se splača pomisliti malo drugače, brez indeksov.

### Rešitev zares

Če dobro pogledamo zadnjo rešitev, pa vidimo, da štejemo le pojavitve `".#"` v dopolnjenem nizu. Najkrajša rešitev naloge je torej

    def stevilo_ovir(vrstica):
        return ("." + vrstica).count(".#")

    stevilo_ovir(vrstica)

    5

## 3. Najširša ovira

`najsirsa_ovira(vrstica)` vrne dolžino najdaljše ovire. V gornjem primeru je to 4.

### Rešitev

Prešteti moramo število zaporednih pojavitev `#`. Ko naletimo na `.`, postavimo števec nazaj na 0. Ob vsakem povečanju števila, preverimo, ali je večje od največjega doslej.

    def najsirsa_ovira(vrstica):
        dolzina = 0
        naj_dolzina = 0
        for c in vrstica:
            if c == "#":
                dolzina += 1
                if dolzina > naj_dolzina:
                    naj_dolzina = dolzina
            else:
                dolzina = 0
        return naj_dolzina

Natančneži bi ugovarjali, da je funkcija počasna, saj bi lahko preverjanje `if dolzina > naj_dolzina` opravili, ko se ovira konča, torej znotraj `else`, pred `dolzina = 0`. To je res, sitnost pa je v tem, da se `else` ne zgodi le, ko se ovira konča, temveč vsakič, kadar ni ovire. Poleg tega bi se morali posebej poukvarjati s primerom, da se ovira dotika konca vrstice.

Spet drugi so nezadovoljni zaradi dolžine programa. Nekateri bi zlovoljno dodali celo, da tole ni nič krajše, kot če bi programirali v Cju. Kako bi torej to rešili v pravem Pythonu?

Če bi moral to rešiti zares, v praksi, bi mi najprej prišlo na misel tole.

    def najsirsa_ovira(vrstica):
        return max(map(len, vrstica.split(".")))

Ali, tole - hitrejše, kadar je pik veliko:

    def najsirsa_ovira(vrstica):
        return max(map(len, vrstica.replace(".", " ").split()))

## 4. Pretvori vrstico

1. `pretvori_vrstico(vrstica)` vrne seznam parov `(x0, x1)`, ki predstavljajo začetke in konce ovir. Za gornji primer vrne `[(2, 3), (5, 8), (12, 13)]`. Pazi, stolpci so oštevilčeni od 1, ne 0.

### Rešitev

Tole je glavna naloga. Na srečo smo se ob reševanju druge naloge naučili ključnega trika: če na začetek niza prištejemo ".", bomo lažje zaznali začetek prve ovire, če so nam jo nemara podtaknili na čisti začetek vrstice. Če prištejemo piko še na konec, bomo lažje zaznali zadnjo, če je morda čisto na koncu.

Tokrat se bomo za začetek pregrešili in delali z indeksi.

    def pretvori_vrstico(vrstica):
        vrstica = "." + vrstica + "."
        bloki = []
        for i, znak in enumerate(vrstica):
            if znak == "#":
                if vrstica[i - 1] == ".":
                    zacetek = i
                if vrstica[i + 1] == ".":
                    bloki.append((zacetek, i))
        return bloki

`znak` bo vseboval trenutni znak, `i` pa njegov indeks.

Zanimajo nas samo znaki `#`.

- Če je pred njim, na indeksu `i - 1`, pika, je to začetek ovire. Zapomnimo si ga.
- Če je za njim, na indeksi `i + 1`, pika, je to konec ovire. Dodamo oviro, ki se je začela pri `zacetek` (ki smo si ga morda zapomnili v enem prejšnjih krogov zanke, morda pa ravnokar, če je bila ovira slučajno dolga le en znak).

V tej nalogi stolpce štejemo od `1`, Pythonov `enumerate` pa (privzeto) teče od `0`. To je ravno prav: ker smo na začetek dodali piko, so se vsi indeksi povečali za `1`.

Preverimo, ali to res deluje. Spomnimo se, vrstica je

    vrstica

    '##.##.####...#....#'

in pokličimo

    pretvori_vrstico(vrstica)

    [(1, 2), (4, 5), (7, 10), (14, 14), (19, 19)]

Zakaj delamo z indeksi, ne z `zip`, tako kot `prej`?

Lahko. Prvi razlog je, da vseeno potrebujemo indekse, torej nam `enumerate` ne uide. Iz tega sledi druga sitnost: enumerirali bomo zip. Zip bo naredil pare znakov, `enumerate` bo naredil pare indeksov in parov, ki jih je naredil `zip`. To bo zapletlo razpakiranje v `for`.

Vendar gre in za resnega programerja je to gotovo lepša rešitev.

    def pretvori_vrstico(vrstica):
        bloki = []
        for i, (prej, znak) in enumerate(zip("." + vrstica, vrstica + ".")):
            if prej + znak == ".#":
                zacetek = i + 1
            elif prej + znak == "#.":
                bloki.append((zacetek, i))
        return bloki

Zaresnemu programerju pa se s temi otročarijami ne da ukvarjati in uporabi regularne izraze (ki bi mu, mimogrede, tudi prejšnje naloge naredili trivialne).

    import re

    def pretvori_vrstico(vrstica):
        return [(m.start() + 1, m.end()) for m in re.finditer("#+", vrstica)]

## 5. Pretvori zemljevid

`pretvori_zemljevid(vrstice)` prejme celoten zemljevid, kot ga vidimo v uvodnem delu naloge, in vrne seznam trojk `(x0, x1, y)`, ki predstavljajo ovire. Za gornji zemljevid mora vrniti `[(3, 4, 2), (2, 3, 3), (5, 5, 3), (4, 6, 4), (1, 3, 5), (5, 6, 5)]`. Seznam naj bo urejen po vrsticah in znotraj tega po stolpcih (tako kot v primeru). Pazi, tudi vrstice so oštevilčene od 1, ne 0.

### Rešitev

Gremo čez oštevilčene vrstice. Vsako pretvorimo in v seznam ovir dodajamo dobljene koordinate začetkov in koncev, ki jim dodamo še vrstico.

    def pretvori_zemljevid(zemljevid):
        ovire = []
        for y, vrstica in enumerate(zemljevid, start=1):
            for x0, x1 in pretvori_vrstico(vrstica):
                ovire.append((x0, x1, y))
        return ovire

Tu se moramo predvsem upreti skušnjavi, da bi ponovno programirali to, kar smo že naredili v `pretvori_vrstico`. Potrebno je preprosto poklicati funkcijo, ki jo že imamo.

## 6. Izboljšave

`izboljsave(prej, potem)` prejme dva zemljevida - en je starejši, drugi novejši. Funkcija mora vrniti seznam novo postavljenih ovir; tudi ta mora biti urejen po vrsticah in znotraj tega po stolpcih. Mirno smeš predpostaviti, da MOL ne odstranjuje postavljenih ovir, temveč jih zgolj dodaja. Prav tako nobena ovira ni "razširjena"; nove ovire niso postavljene neposredno levo ali desno od obstoječih. Predpostaviti smeš tudi, da nova kolesarska steza ni širša. (No, tudi ožja ne; enake oblike je.)

### Rešitev

Kako brez potrebe so si nekateri zapletli to nalogo! Primerjali vrstice iz obeh zemljevidov!

Čisto preprosto je: s `pretvori_zemljevid` dobimo sezname ovir prej in potem, ter ustvarimo nov seznam, ki vsebuje, kar je v `potem` in ni bilo v `prej`.

    def izboljsave(prej, potem):
        prej = pretvori_zemljevid(prej)
        potem = pretvori_zemljevid(potem)
        nove = []
        for ovira in potem:
            if ovira not in prej:
                nove.append(ovira)
        return nove

## 7. Huligani

`huligani(prej, potem)`; zgodi se, da pridejo huligani in kradejo ovire ter s tem ogrožajo varnost kolesarjev. Funkcija `huligani` naj zato vrne dva seznama: seznam vseh novih in seznam vseh odstranjenih ovir. Tu se lahko zgodi, da se nova ovira delno prekriva z neko prejšnjo.

### Rešitev

Tule se je potrebno zgolj poglobiti v razmišljanje MOL in huliganov. Prometni strokovnjaki na Oddelku za gospodarstvo in motorni promet Mestne občine Ljubljana vedo, da je kolesarska steza izboljšana, če je na njej več ovir. Če je `potem` več ovir kot `prej`, je to torej `izboljsava`. Huligani zmotno mislijo, da je izboljšava, če ovira izgine, torej če je bilo `prej` več ovir kot `potem`.

Funkcija `huligani` mora vračati dve stvari. Prva je točno tisto, kar vrača funkcija `izboljsave`, drugo pa tisto, kar bi vrnila funkcija `izboljsave`, če bi - sledeč perverzni logiki sovražnikov ovir na kolesarskih stezah - obrnili čas nazaj.

    def huligani(prej, potem):
        return izboljsave(prej, potem), izboljsave(potem, prej)

## Celotna rešitev

### Elegantne, a razumne rešitve

Tule so zbrane rešitve, ki ne zahtevajo ničesar, česar se še nismo učili. V primerjavi z rešitvami iz gornjega besedila, smo poenostavili `najsirsa_ovira`, saj ni razloga, da ne bi klicala kar funkcije `pretvori_vrstica`. Tako se dejansko le enkrat zafrkavamo z zanko prek vrstice.

    def dolzina_ovir(vrstica):
        return vrstica.count("#")

    def stevilo_ovir(vrstica):
        return ("." + vrstica).count(".#")

    def najsirsa_ovira(vrstica):
        naj = 0
        for od, do in pretvori_vrstico(vrstica):
            if do - od + 1 > naj:
                naj = do - od + 1
        return naj

    def pretvori_vrstico(vrstica):
        vrstica = "." + vrstica + "."
        bloki = []
        for i, znak in enumerate(vrstica):
            if znak == "#":
                if vrstica[i - 1] == ".":
                    zacetek = i
                if vrstica[i + 1] == ".":
                    bloki.append((zacetek, i))
        return bloki

    def pretvori_zemljevid(zemljevid):
        ovire = []
        for y, vrstica in enumerate(zemljevid, start=1):
            for x0, x1 in pretvori_vrstico(vrstica):
                ovire.append((x0, x1, y))
        return ovire

    def izboljsave(prej, potem):
        prej = pretvori_zemljevid(prej)
        potem = pretvori_zemljevid(potem)
        nove = []
        for ovira in potem:
            if ovira not in prej:
                nove.append(ovira)
        return nove

    def huligani(prej, potem):
        return izboljsave(prej, potem), izboljsave(potem, prej)

## Zaresne rešitve

Tole pa so lepe rešitve v pravem Pythonu. Tako bi z nalogo opravil profesionalec. Pokažem predvsem zato, da dobite malo občutka o tem, kako učinkovito je mogoče programirati v Pythonu.

    import re

    def dolzina_ovir(vrstica):
        return vrstica.count("#")

    def stevilo_ovir(vrstica):
        return ("." + vrstica).count(".#")

    def najsirsa_ovira(vrstica):
        return max(od - do + 1 for od, do in pretvori_vrstico(vrstica))

    def pretvori_vrstico(vrstica):
        return [(m.start() + 1, m.end()) for m in re.finditer("#+", vrstica)]

    def pretvori_zemljevid(vrstice):
        return [(x0, x1, y)
                for y, vrstica in enumerate(zemljevid, start=1)
                for x0, x1 in pretvori_vrstico(vrstica)]

    def izboljsave(prej, potem):
        prej = pretvori_zemljevid(prej)
        potem = set(pretvori_zemljevid(potem))
        return [ovira for ovira in prej if ovira not in potem]

    def huligani(prej, potem):
        return izboljsave(prej, potem), izboljsave(potem, prej)

Morda opomba glede funkcije `izboljsave`: rešiti bi jo bilo možno v eni vrstici, kot razliko množic,

    def izboljsave(prej, potem):
        return list(set(pretvori_zemljevid(potem)) - set(pretvori_zemljevid(prej)))

če množice ne bi pomešale vrstnega reda. Kasnejše urejanje v slogu

    def izboljsave(prej, potem):
        return sorted(set(pretvori_zemljevid(potem)) - set(pretvori_zemljevid(prej)),
                      key=pretvori_zemljevid(potem).index)

pa je brez zveze. Najbrž ne pridobimo ničesar; metoda `index`, ki jo potrebujemo za to, da vrnemo elemente seznama v prvotni vrstni red, je počasna. Vse skupaj je le nepregledno. Je pa, seveda, zabavno.

Dodatek: eden od študentov je povedal, da deluje tudi

    def izboljsave(prej, potem):
        return sorted(set(pretvori_zemljevid(potem)) - set(pretvori_zemljevid(prej)),
                      key=lambda x: x[2])

To uredi ovire po drugem elementu, vrstici. Mislim, da deluje slučajno: da bi zares delovalojih je treba urediti najprej po vrsticah, znotraj tega pa še po stolpcih,

    def izboljsave(prej, potem):
        return sorted(set(pretvori_zemljevid(potem)) - set(pretvori_zemljevid(prej)),
                      key=lambda x: (x[2], x[0]))

To je v resnici hitrejše od vseh gornjih programov (ne da bi se pri tako majhnem številu ovir to kaj poznalo...). Deluje pa zato, ker vemo, da morajo biti ovire urejene po vrsticah in stolpcih. V splošnem pa: če imamo dva seznama in želimo dobiti seznam vsega, kar je v prvem, ne pa tudi v drugem, bomo z `list(set(s) - set(t))` izgubili vrstni red.

Rešitev, ki jo je našel študent, pa tu deluje in je seveda odlična ideja.