Angelčin zapis

Lani so na Oddelku za gospodarstvo in motorni promet Mestne občine Ljubljana izvedel, da so študenti FRI razvili programsko opremo za branje njihovih zemljevidov pik in lojtr, zato so brž pripravili nov format zapisa. Tudi ta, novi zapis je že zastarel in ga lahko izbrskate le v lanski domači nalogi. Letos je gospa Angelca (tista z dolgimi nohti) prepričala (= z neumornim najedanjem od juter do večerov spravila v obup) ostale zaposlene na oddelku, namreč da je format grd in da bi ona ovire raje zapisovala tako:

 (4) 5--
(13) 90-----------   5---- 19---
 (5) 9---           19--   30-----
(4)           9---
(13)         22---- 17---

In da če jim ni prav, bo šla do župana, ker ta je edini pameten in se vedno strinja z njo. (Že čim jo zagleda na vratih pisarne. Župan ima pač početi kaj pametnejšega kot poslušati Angelco. Zadnje čase začne nezavedno kimati že, ko na hodniku zasliši zvok njenih visokih pet.)

Jasni Angelčin Opis Ovir (prepoznamo ga po končnici datoteke, .jaoo) je sestavljen tako:

Da je zapis bolj razgiban (Angelca po osnovni izobrazbi pač ni računalnikarka, temveč je končala likovno akademijo, smer Industrijsko in unikatno oblikovanje), lahko vsebuje poljubno število presledkov na začetku ali koncu vrstice ter med navedbami posameznih ovir - tako kot jasno kaže gornji primer.

Disclaimer

Čeprav naloge pri tem predmetu temeljijo na resničnih dogodkih, avtor naloge ne ve, ali na MOL res obstaja kakšna Angelca, ki ustreza opisu, vendar te možnosti ne izključuje. Angelca v tej nalogi je torej izmišljena, podobnost z resničnimi osebami s takšnim ali drugačnim imenom pa povsem verjetna.

Obvezna naloga

Napiši naslednje funkcije.

Rešitev

koordinate

Da pridemo do začetka ovire (same številke), se moramo minusov znebiti (strip("-")), da dobimo dolžino ovire, pa jih moramo prešteti (count("-")).

def koordinate(s):
    x0 = int(s.strip("-"))
    return x0, x0 + s.count("-") - 1
koordinate("5---")
(5, 7)
koordinate("123-")
(123, 123)

vrstica

V tej nalogi je naš prijatelj split(). Poglejte, kaj naredi z nizom iz primera!

"  (4) 1---  5------- 15-".split()
['(4)', '1---', '5-------', '15-']

Prvi element je številka vrstice (ko se bomo znebili prvega in zadnjega znaka, trapastih Angelčinih oklepajev), ostale elemente pa pomečemo funkciji koordinate, da dobimo začetke in konce ovir.

def vrstica(s):
    ovire = []
    s = s.split()
    y = int(s[0][1:-1])
    for ovira in s[1:]:
        ovire.append(koordinate(ovira) + (y, ))
    return ovire
vrstica("  (4) 1---  5------- 15-")
[(1, 3, 4), (5, 11, 4), (15, 15, 4)]

Napisati s = s.split() ni prav zgledno. Spremenljivka s je s tem spremenila svoj pomen - prej je bila niz, zdaj je seznam kosov tega niza. To storimo, če ravno nimamo domišljije, kako poimenovati novo spremenljivko in če menimo, da s tem ne povzročamo prehudih nejasnosti.

V resnici bi pravi programer v Pythonu to napisal drugače. Tole je sicer tečaj programiranja in ne Pythona, vendar obstaja velika verjetnost, da boste kdaj v življenju programirali tudi v Pythonu, zato ne bo škode, če vidite tudi kakšen lep zgled praktičnega dela v tem jeziku.

def vrstica(s):
    ovire = []
    y, *xs = s.split()
    y = int(y[1:-1])
    for ovira in xs:
        ovire.append(koordinate(ovira) + (y, ))
    return ovire

Razlika je minimalna, gre le za to, kaj smo naredili z rezultatom split. Prej smo vse skupaj vrgli v en sam seznam, potem pa prebrali prvi element v y, čez ostale pa spustili zanko. Zdaj to razkosamo takoj po klicu - že iz prirejanja je očitno, da je rezultat split-a y, ostalo pa so x-i. Zvezdica pred xs pomeni, da v to spremenljivko shrani vse odvečne elemente, ki niso šli v druge spremenljivke (v našem primeru so "druge spremenljivke" pač le y).

Pravzaprav lažem. Pravi programer v Pythonu zamahne s čarobno palico in napiše

def vrstica(s):
    ovire = []
    y, *xs = s.split()
    y = int(y[1:-1])
    return [(*koordinate(ovira), y) for ovira in xs]

Naslednji teden bomo mi tudi.

preberi

Podani niz razkosamo na vrstice (splitlines()), jih podajamo funkciji vrstica in vse, kar vrne, seštevamo v nov seznam.

def preberi(s):
    ovire = []
    for vrsta in s.splitlines():
        ovire += vrstica(vrsta)
    return ovire

Tule je pomembno, da uporabimo +=, ki v seznam ovire doda vse elemente seznama, ki ga vrne vrstica in ne morda append, ki bi v seznam ovire dodal seznam, ki ga vrne vrstica.

Kaj na to poreče zaresen programer?

def preberi(s):
    return sum(map(vrstica, s.splitlines()), start=[])

map(vrstica, s.splitlines()) pokliče funkcijo vrstica za vsak element s.splitlines(), sum pa vse to lepo sešteje, če mu povemo, da mora prištevati v v začetku prazen seznam.

intervali

Ta je preprosta.

def intervali(ovire):
    intv = []
    for x0, x1 in ovire:
        intv.append(str(x0) + "-" * (x1 - x0 + 1))
    return intv

Zares pa tako

def intervali(ovire):
    return [f"{x0}{'-' * (x1 - x0 + 1)}" for x0, x1 in ovire]

zapisi_vrstico

Tu pa niti rešitev z našim znanjem ni daljša od vrstice.

def zapisi_vrstico(y, ovire):
    return "(" + str(y) + ") " + " ".join(intervali(ovire))

Profesionalec bi naredil skoraj enako, recimo tako

def zapisi_vrstico(y, ovire):
    return f"({y}) " + " ".join(intervali(ovire))

Ali, odvisno od osebnega sloga

def zapisi_vrstico(y, ovire):
    return f"({y}) {' '.join(intervali(ovire))}"

Dodatna naloga

Napiši funkcijo zapisi(ovire), ki prejme seznam ovir in vrne niz, ki vsebuje opis ovir v novi obliki. Za razliko od kaosa, ki ga dobimo od MOL, pa mora biti zapis urejen: vrstice se pojavljajo le enkrat in v pravem vrstnem redu, pa tudi ovire morajo biti urejene od leve proti desni.

Klic

zapisi([(5, 6, 4),
        (90, 100, 13), (5, 8, 13), (9, 11, 13),
        (9, 11, 5), (19, 20, 5), (30, 34, 5),
        (9, 11, 4),
        (22, 25, 13), (17, 19, 13)])

vrne niz

(4) 5-- 9---
(5) 9--- 19-- 30-----
(13) 5---- 9--- 17--- 22---- 90-----------

Spet: niz mora biti v točno takšni obliki, brez odvečnih ali manjkajočih presledkov.

Rešitev

Glede na to, da še ne poznamo slovarjev in da y ne more biti zelo velik, bi bila najbolj prikladna - in pravzaprav nič slabša od rešitve s slovarji, takšna rešitev:

def zapisi(ovire):
    vrstice = []
    for x0, x1, y in ovire:
        while len(vrstice) <= y:
            vrstice.append([])
        vrstice[y].append((x0, x1))

    zemljevid = ""
    for y, xs in enumerate(vrstice):
        if xs:
            zemljevid += zapisi_vrstico(y, sorted(xs)) + "\n"
    return zemljevid

vrstice so seznam seznamov: v vrstice[3], recimo, so začetki in konci vseh ovir v tretji vrstici.

V prvi zanki gremo čez vse ovire. V zanki while poskrbimo, da ima vrstice dovolj elementov: če se ovira nahaja v vrstici, katere številka je večja od števila doslej vzpostavljenih vrstic, dodaja nove prazne sezname. Nato dodamo vsako oviro v ustrezno vrstico.

V drugi zanki pišemo ovire v zemljevid, ki ga bomo vrnili kot rezultat. Gremo čez elemente vrstice in če je v vrstici kaj ovir, pokličemo zapisi_vrstico, da jih zapiše. Seznam ovir, xs, predtem uredimo.

Rešitev s slovarji, bi bila malenkost krajša, ideja pa je podobna.

def zapisi(ovire):
    kupcki = defaultdict(list)
    for x0, x1, y in ovire:
        kupcki[y].append((x0, x1))

    zemljevid = ""
    for y, kupcek in sorted(kupcki.items()):
        zemljevid += zapisi_vrstico(y, sorted(kupcek)) + "\n"
    return zemljevid

Gre krajše? Gre v eni vrstici?

Vedno. Vendar tule nima smisla. Prvi del je najbolj jasen takšen, kot je. Drugega pa bi dejansko skrajšal, če bi šlo zares.

def zapisi(ovire):
    kupcki = defaultdict(list)
    for x0, x1, y in ovire:
        kupcki[y].append((x0, x1))

    return "\n".join(zapisi_vrstico(y, sorted(kupcek))
                     for y, kupcek in sorted(kupcki.items()))

V resnici pa gre za problem urejanja in grupiranja teh, urejenih stvari. Zato bi kdo kak ekstremist funkcijskega programiranja v Pythonu nemara napisal

from operator import itemgetter
from itertools import groupby

def zapisi(ovire):
    return "\n".join(zapisi_vrstico(y, sorted(x[:2] for x in group))
                     for y, group in groupby(sorted(ovire, key=itemgetter(2)), itemgetter(2)))

Deluje, ni pa berljivo. Python je lep jezik, ni pa vsak jezik lep za vsak slog programiranja. Če se kdo potrudi to prebrati, bo videl, da mora brati nazaj - najprej se zgodi (drugi) sorted, nato groupby, potem zapisi_vrstico, katere rezultati se združijo z join. To bi se bralo veliko lepše v jezikih, v katerih se to zapiše naprej, recimo v Kotlinu ali Javascriptu.