Izvedši, da je njihov zemljevid s pikami in lojtrami neuporaben in živcira študente računalništva, kognitivne znanosti, upravne informatike in digitalnega jezikoslovja, so začali na Oddelku za gospodarstvo in motorizirani promet Mestne občine Ljubljana pripravljati podatke v drugačni obliki. Zato bo potrebno napisati nove funkcije za njihovo branje.
Ovire so zapisane v večvrstičnem nizu:
4: 5-6
13: 90-100, 5-8, 9-11
5: 9-11, 19-20, 30-34
4: 9-11
13: 22-25, 17-19
To pomeni, da je v 4. vrstici ovira od 5 do 6. V 13. vrstici so ovire od 90 do 100, od 5 do 8 in od 9 do 11. V 5. so od ... In potem so se spomnili, da je v 4. vrstici še ena ovira. In v 13. še dve.
Oblika vsake posamične vrstice je torej takšna: imamo številko
vrstice, ki ji sledi dvopičje, temu pa pari koordinat
(x0, x1)
. Med koordinatama je -
, med pari pa
vejice. Kot vidimo zgoraj.
Če je s
večvrstični niz, ga razbijemo v seznam
posamičnih vrstic tako, da pokličemo s.splitlines()
.
Če imamo niza prva = "Prva vrstica"
in
druga = "Druga vrstica"
, ga zložimo v dvovrstični niz, tako
da seštejemo prva + "\n" + druga
. Kombinacija
\n
pomeni prehod v novo vrstico.
Napiši naslednje funkcije.
vrstica(s)
prejme niz z eno vrstico in vrne seznam
trojk (x0, x1, y)
, ki predstavljajo ovire v tej
vrstici.
Klic vrstica("4: 1-3, 5-11, 15-33")
vrne seznam
[(1, 3, 4), (5, 11, 4), (15, 33, 4)]
.
preberi(s)
celoten, večvrstični niz z ovirami in
vrne seznam ovir. Ovire naj bodo shranjene v takšnem vrstnem redu, v
kakršnem se pojavljajo.
Če jo pokličemo z gornjim nizom, vrne
[(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)]
intervali(xs)
prejme seznam parov
(x0, x1)
in vrne seznam nizov, ki opisujejo te
intervale.
Klic intervali([(6, 10), (12, 16), (20, 22), (98, 102)])
vrne ["6-10", "12-16", "20-22", "98-102"]
.
zapisi_vrstico(y, xs)
prejme številko vrstice in
seznam parov (x0, x1)
. Vrniti mora opis ene vrstice.
Klic zapisi_vrstico(5, [(6, 10), (12, 16)]))
vrne niz
"5: 6-10, 12-16"
. Pazi: nobenih odvečnih ali manjkajočih
presledkov ali vejic!
vrstica
Vrstico moramo najprej razdeliti glede na ":"
. Ker vemo,
da bo samo eden, bomo rezultat funkcije takoj razpakirali na dva dela,
niz s številko vrstice (ys
- s
kot "string")
in niz s koordinatami x (xs
). ys
nato
razbijemo glede na ", "
in čez dobljene kose poženemo zanko
for
; vsak kos, končno, razbijemo še po -
da
dobimo začetek in konec ovire. Trojke z začetkom in koncem ovire ter
koordinato y
vestno zlagamo v seznam.
def vrstica(s):
= []
ovire = s.split(":")
ys, xs = int(ys)
y for x0x1 in xs.split(", "):
= x0x1.split("-")
x0s, x1s int(x0s), int(x1s), y))
ovire.append((return ovire
Dve opazki. ys
pretvorimo v int
kar pred
zanko, namesto da bi to počeli vsakič posebej. Program je zaradi tega za
vrstico daljši, je pa za (pri tako malo podatkih neopazno) malenkost
hitrejši.
Druga: trojko s koordinatami sestavimo kar ob klicu funkcije
append
.
preberi
Tu ni kaj: celoten niz razbijemo v vrstice s splitlines
,
čez dobljeni seznam poženemo zanko for
in za vsako vrstico
pokličemo vrstica
ter njene rezultate zlagamo v seznam.
def preberi(s):
= []
ovire for v in s.splitlines():
+= vrstica(v)
ovire return ovire
intervali
Pripravimo prazen seznam. Gremo čez ovire in za vsako v seznam dodamo
niz. Sestavljanje niza je nekoliko okorno -
str(x0) + "-" + str(x1)
. Nekoč se bomo naučili, da gre tudi
lažje.
def intervali(xs):
= []
intv for x0, x1 in xs:
str(x0) + "-" + str(x1))
intv.append(return intv
zapisi_vrstico
Naloga preverja, ali znamo poklicati join
. :) Potrebno
je vzeti številko vrstice in dvopičje, k temu pa dodati z vejico
združeni seznam, ki nam ga pripravi prejšnja funkcija.
def zapisi_vrstico(y, xs):
return str(y) + ": " + ", ".join(intervali(xs))
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
5, 6, 4),
zapisi([(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-6, 9-11
5: 9-11, 19-20, 30-34
13: 5-8, 9-11, 17-19, 90-100
Spet: niz mora biti v točno takšni obliki, brez odvečnih ali manjkajočih presledkov ali vejic.
Pripravimo seznam seznamov, ki ima za elemente toliko praznih seznamov, kolikor je vrstic. Vsak, očitno, pripada eni vrstici. Nato gremo čez seznam ovir in vsako oviro vržemo v pripadajoči seznam. Na koncu se zapeljemo čez te sezname in vsakega, ki ni prazen, izpišemo v zemljevid.
def zapisi(ovire):
# Poišči število vrstic
= 0
visina for _, _, y in ovire:
if y > visina:
= y
visina
# Pripravi seznam seznamov; vrstice[i] bo seznam ovir v i-ti vrstici
# Na začetek pa damo še en prazen seznam, da se bodo indeksi začeli z 1.
= [[]]
vrstice for _ in range(visina):
vrstice.append([])
# Vsako oviro v pripadajoči seznam
for x0, x1, y in ovire:
vrstice[y].append((x0, x1))
# In zdaj le še izpišemo sezname v zemljevid
= ""
zemljevid for y, vrstica in enumerate(vrstice):
if vrstica:
+= zapisi_vrstico(y, vrstica) + "\n"
zemljevid return zemljevid
Ni tako grozno, ne?
Še lepše gre s slovarji. Konkretno, z defaultdict
-om. Te
smo, ah, smola, spoznali šele na naslednjih predavanjih, po roku za
oddajo naloge. Vseeno poglejmo rešitev.
def zapisi(ovire):
= defaultdict(list)
vrstice for x0, x1, y in ovire:
vrstice[y].append((x0, x1))
= ""
zapis for y, vrstica in sorted(vrstice.items()):
+= zapisi_vrstico(y, sorted(vrstica)) + "\n"
zapis return zapis
Vzeli smo defaultdict(list)
: če uporabimo nek ključ, ki
ga ni v slovarju, se ta sam od sebe pojavi, pripadajoča vrednost pa je
prazen slovar.
V prvem delu funkcije gremo čez ovire in dodajamo pare
(x0, x1)
v pripadajoče vrstice y
.
V drugem delu gremo čez slovar. Vzamemo vse pare (ključ, vrednost),
ki jih dobimo z items
. S sorted
jih uredimo;
ker gre za terke, jih bo sorted
uredil po prvem elementu,
če sta prva elementa enaka, pa po drugem. (Da bi bila prva elementa
enaka, se tu ne more zgoditi. Razmisli, zakaj!). Za vsako vrstico dodamo
v zapis
zapis te vrstice, ki ga dobimo tako, da pokličemo
funkcijo zapisi_vrstico
z urejenim seznamom ovir v tej
vrstici. Preverjanje, ali je vrstica morda brez ovir, zdaj ni več
potrebno, saj takih vrstic v slovarju ne bo.