Ovire so podane kot seznam terk (x0, x1, y)
, kjer je
y
številka vrstice, x0
in x1
pa
skrajni levi in desni stolpec ovire. Seznam ovir ni urejen ne po
vrsticah ne kakorkoli drugače.
Ovire na sliki (ki se uporabljajo v nalogah 1, 3 in 4 ter, z nekaj
dodatnimi v 2) so lahko predstavljene s seznamom
[(1, 3, 6), (2, 4, 3), (3, 4, 9), (6, 9, 5), (9, 10, 2), (9, 10, 8), (4, 6, 7)]
.
Napiši funkcijo manj_kot_tri(ovire, nstolpcev)
, ki
prejme seznam ovir in številko zadnjega stolpca. Vrniti mora urejen
seznam številk stolpcev, ki jih pokrivajo manj kot tri ovire. Za primer
na sliki vrne [1, 2, 5, 6, 7, 8, 10].
Ena možnost je, da pripravimo slovar, katerega ključi so številke
stolpcev, vrednosti pa povejo število ovir v tem stolpcu. Gremo čez vse
ovire, za vsako oviro čez vse stolpce, in prištevamo. Na koncu gremo od
1 do nstolpcev
in v seznam dodamo vse številke stolpcev, za
katere v slovarju piše, da imajo manj kot tri ovire.
def manj_kot_tri(ovire, nstolpcev):
= defaultdict(int)
ovir for x0, x1, y in ovire:
for x in range(x0, x1 + 1):
+= 1
ovir[x] return [i for i in range(1, 1 + nstolpcev) if ovir[i] < 3]
Manj fancy - a nič dosti slabša, čeprav nekoliko počasnejša - ni rešitev, v kateri gremo prek vseh stolpcev in za vsak stolpec čez vse ovire. Preštejemo, koliko ovir zapira ta stolpec. Če manj kot tri, ga dodamo.
def manj_kot_tri(ovire, nstolpcev):
= []
manj for x in range(1, 1 + nstolpcev):
= 0
ovir for x0, x1, _ in ovire:
if x0 <= x <= x1:
+= 1
ovir if ovir < 3:
manj.append(x)return manj
Napiši funkcijo proste_ovire(ovire)
, ki dobi seznam
ovir, med katerimi pa se nekatere prekrivajo (ali pa celo popolnoma
sovpadajo). Funkcija naj vrne nov seznam, v katerem so le ovire, ki se
ne prekrivajo (delno ali popolnoma) z nobeno drugo oviro.
Prva naloga vam je bila podarjena, ker je bila res preprosta. Ta naloga je pa malo bolj (ampak ne zelo) zoprna. Kot sem napovedal, je na vsakem izpitu še kakšna naloga, kjer morate znati pametno preobrniti kakšno zanko.
Napisali bomo ločeno funkcijo
prekrivanje(ovira1, ovira2)
, ki bo povedala, ali se dve
oviri prekrivata. To sploh ni nujno; namenjeno je le temu, da bo
"glavna" funkcija preglednejša.
def prekrivanje(ovira1, ovira2):
= ovira1
x10, x11, y1 = ovira2
x20, x21, y2 return y1 == y2 and (x20 <= x10 <= x21 or x10 <= x20 <= x11)
Malo preprostejša, vendar počasnejša je rešitev, ki za vsako oviro
preveri vse ovire; če naleti na oviro, ki ni prav taista ovira
(i != j
) in se prekriva, prekine zanko
(break
). Če se zanka izteče, ne da bi jo prekinili
(else
), dodamo oviro v seznam prostih.
def proste_ovire(ovire):
= []
proste for i, ovira1 in enumerate(ovire):
for j, ovira2 in enumerate(ovire):
if i != j and prekrivanje(ovira1, ovira2):
break
else:
proste.append(ovira1)return proste
Rešitev je nekoliko počasnejša zato, ker gre za vsako oviro čez vse
druge ovire. Lahko bi za vsako oviro preverili vse ovire pred njo; če se
prekrivata, bi obe označili kot ne-prosti. Takšna funkcija bo torej
najprej pripravila seznam "zastavic", ki bo dolg toliko, kolikor je
ovir. Za vsako oviro bo vseboval True
, če je prosta in
False
, če ni. V začetku bo seznam vseboval same
True
, potem pa bomo šli čez vse ovire in za vsako
preverili, ali jo prekriva katera od ovir, ki ji sledijo. Če jo, obema
spremenimo njun element v False
.
Na koncu zipnemo skupaj seznam ovir in seznam zastavic. V nov seznam
damo oviro, katere pripadajoča zastavica je True
.
def proste_ovire(ovire):
= [True] * len(ovire)
proste for i, ovira1 in enumerate(ovire):
for j in range(i):
if prekrivanje(ovira1, ovire[j]):
= proste[j] = False
proste[i] return [ovira for ovira, prosta in zip(ovire, proste) if prosta]
Ta naloga je bila nekoliko težja, vendar lažja od prvotne različice, ki je zahtevala, da funkcija briše ovire iz obstoječega seznama. To vam je bilo torej prihranjeno ... lahko pa poskusite to narediti za vajo.
Napiši funkcijo dolzina_ovir(ime_datoteke), ki prejme ime datoteke, v kateri so ovire opisane v takšni obliki:
1-3 6
2-4 3
3-4 9
(in tako naprej). Prvi števili sta začetek in konec ovire, ločena z
-
. Sledi presledek in številka vrstica. Funkcija naj vrne
skupno dolžino ovir (število "pobarvanih" kvadratkov na sliki). Ovire se
ne prekrivajo.
Za oddih spet nekoliko lažja naloga. Znati moramo odpreti datoteko,
jo brati po vrsticah, razdeliti niz glede na presledek, razdeliti del
tega niza glede na -
, spremeniti niza v števili, ter ju
odšteti in prištevati k skupni vsoti. Eh.
def dolzina_ovir(ime_datoteke):
= 0
dolzina for vrstica in open(ime_datoteke):
= vrstica.split()
xs, _ = xs.split("-")
x0, x1 += int(x1) - int(x0) + 1
dolzina return dolzina
Številke vrstice ne potrebujemo. :) Upam, da reševalcem ni vzelo
preveč časa, da so odkrili, da morajo k razliki med stolpcema prišteti
1. Če jim je, je to zgolj poučno: bodo bolj cenili, da je indeksiranje v
Pythonu narejeno tako, da s[5:8]
vsebuje 3 elemente (8 - 5)
in ne štirih (od petega do vključno osmega), tako kot
ovire.
Napiši rekurzivno funkcijo rekurzivna_dolzina(ovire), ki izračuna skupno dolžino ovir v podanem seznamu. Ovire se ne prekrivajo.
Če je seznam prazen, je skupna dolžina 0
, sicer pa
toliko, kolikor je dolga prva in vse ostale skupaj.
def rekurzivna_dolzina(ovire):
if not ovire:
return 0
return ovire[0][1] - ovire[0][0] + 1 + rekurzivna_dolzina(ovire[1:])