Tokratna naloga bo zelo kratka. V vsaki funkciji bo potrebno napisati samo eno vrstico. Točneje, tokratna naloga bo krajša, ko bi si želeli: v vsaki funkciji boste smeli napisati samo eno vrstico.
Spet se vračamo k isti nalogi, ki smo jo reševali že dvakrat: prvič smo jo imenovali Šikaniranje, drugič pa Funkcijske ovire.
Tokrat jih bomo reševali s pomočjo izpeljanih seznamov. Če vam kaj pomaga (najbrž vam vsaj malo) imate poleg testov že napisane funkcije, ki rešijo naloge ... le predolge so. :)
Napišite funkcije
stevilo_ovir(ovire)
,dolzina_ovir(ovire)
,sirina(ovire)
,dodaj_vrstico(bloki, y)
globina(ovire, x)
senca(ovire)
tako, da bodo vsebovale samo stavek return
in ... kar je
pač potrebno, da izračunate, kar morajo izračunati.
Število ovir je že napisano v vrstici. Daljše skoraj ne gre. :)
def stevilo_ovir(ovire):
return len(ovire)
dolzina_ovir(ovire)
mora vrniti vsoto
dolžin vseh ovir. Dolžina ovire (x0, x1, y)
je
x1 - x0 + 1
, vsota tega je
sum(x1 - x0 + 1 ... za vsako oviro
.
def dolzina_ovir(ovire):
return sum(x1 - x0 + 1 for x0, x1, _ in ovire)
Ker y
ne potrebujemo, tretjo vrednost iz trojke
poimenujemo kar _
.
sirina(ovire)
je enaka največjemu (po
angleško: maksimalnemu) x1
.
def sirina(ovire):
return max(x1 for _, x1, _ in ovire)
dodaj_vrstico(ovire, y)
gre čez seznam
parov in jih zlaga v seznam trojk, ki poleg x1
in
x0
vsebujeta še y
.
def dodaj_vrstico(bloki, y):
return [(x0, x1, y) for x0, x1 in bloki]
Če hočemo poudariti, da je y
dodan k tistemu, kar smo
imeli prej, pa
def dodaj_vrstico(bloki, y):
return [blok + (y, ) for blok in bloki]
Ne spreglejte: ne blok + (y)
, temveč
blok + (y, )
. (y)
bi bila samo številka, ne
terka.
globina(ovire, x)
mora vrniti najmanjši
y
med vsemi x0, x1, y
, za katere velja, da je
x
med x0
in x1
, torej
x0 <= x <= x1
.
To bi lahko bilo tole:
def globina(ovire, x):
return min(y for x0, x1, y in ovire if x0 <= x <= x1)
vendar ne deluje v primeru, da v stolpcu ni nobene ovire. Tedaj
(y for x0, x1, y in ovire if x0 <= x <= x1)
ne
zgenerira ničesar in max
ne ve, kaj vrniti. Pogledši dokumentacijo
funkcije min
izvemo, da ji lahko podamo še argument
default
, s katero predpišemo vrednost, ki naj jo vrne v
takšnem primeru. V naši nalogi želimo, da tedaj vrne None
,
torej
def globina(ovire, x):
return min((y for x0, x1, y in ovire if x0 <= x <= x1), default=None)
senca(ovire)
mora sestaviti seznam s
toliko elementi, kolikor je stolpcev in vsak vsebuje True
,
če globina
za ta stolpec vrne None
in
False
, če ne.
def senca(ovire):
return [globina(ovire, x) is None for x in range(1, sirina(ovire) + 1)]
Napišite funkcijo indeksi(s, subs)
, ki prejme niza
s
in subs
ter vrne seznam indeksov znotraj
s
, na katerih se pojavi subs
. Klic
indeksi("pepelka peče prepelice", "pe")
vrne
[0, 2, 8, 16]
, saj se pe
pojavi na indeksih 0,
2, 8 in 16. Tudi ta funkcija sme seveda obsegati samo
return
.
Potem napišite v eni vrstici funkcijo
pretvori_vrstico(vrstica)
.Funkcijo indeksi
so nekateri študenti zelo zapletli, ker
so si poskušali pomagati z zanko, v kateri bi klicali
index
. To je zelo težko. Veliko preprosteje je pomisliti
drugače: kaj hoče funkcija? Kaj moramo vrniti? Vse tiste indekse, za
katere velja, da se na njih začenja podniz subs
. Kako torej
preverimo, ali se na i
-tem mestu s
-ja začenja
subs
? s[i:i + len(subs)] == subs
. Lahko pa
uporabimo tudi metodo startswith
, ki pove, ali se niz začne
s podanim nizom: s[i:].startswith(subs)
.
Funkcija indeksi
je torej:
def indeksi(s, subs):
return [i for i in range(len(s)) if s[i:].startswith(subs)]
Zdaj pa pretvorimo vrstico. Zanima nas, kje so začetki ovir. Ovire za
začnejo tam, kjer najdemo .#
. Da bomo našli tudi ovire, ki
bi bile čisto na začetku, na začetek prištejemo piko. Ovire se torej
začenjajo na indeksi("." + s, ".#")
. Vendar bodo ti indeksi
žal za 1 premajhni: če imamo s = "#"
, se ovira začne na
1
(ker v teh nalogah pač štejemo od 1). Klic
indeksi("." + s, ".#")
, ali, konkretneje,
indeksi(".#", ".#")
bo vrnil [0]
. Nič hudega:
indeksom bi sicer lahko prištevali 1 kdaj kasneje, a preprosteje, če
nizu s
namesto ene same pike prištejemo dve, pa se bodo vsi
indeksi povečali za 1
. Stolpci, v katerih se začenjajo
ovire, so torej indeksi(".." + s, ".#")
.
Pa konci? Zdaj iščemo "#."
. Da pravilno zaznamo tudi
oviro, ki bi bila čisto na koncu niza, nizu prištejemo še
"."
. Da povečamo indekse za 1
, dodamo piko na
začetku (namesto pike bi lahko na začetek dodali tudi karkoli drugega).
Konci ovir so torej na indeksi("." + s + ".", subs)
.
Funkcija mora vrniti pare začetkov in koncev.
def pretvori_vrstico(vrstica):
return list(zip(indeksi(".." + vrstica, ".#"), indeksi("." + vrstica + ".", "#.")))
Še preostali dve:
pretvori_zemljevid(zemljevid)
(tule boste verjetno
potrebovali reduce
in add
),naj_stolpec(ovire)
.Ni tako težko.
Generator
(dodaj_vrstico(pretvori_vrstico(vrstica), y) for y, vrstica in enumerate(zemljevid, start=1))
gre čez vrstice; za vsako poišče začetke in konce vrstic ter v pare doda
številke vrstic, y
. Problem je, da tako dobimo sezname
seznamov ovir v vrsticah. Vse "podsezname" je potrebno sešteti v en sam
seznam. To lahko storimo s funkcijo sum
, če ji podamo
začetni element. Funkcija sum
privzeto začne prištevati k
0
, mi želimo, da prišteva k praznemu seznamu.
def pretvori_zemljevid(zemljevid):
return sum((dodaj_vrstico(pretvori_vrstico(vrstica), y)
for y, vrstica in enumerate(zemljevid, start=1)), start=[])
Funkcija naj_stolpec
je pa bolj zoprna. Iščemo nekakšen
max(((x, globina(ovire, x)) for x in range(1, sirina(ovire) + 1)
,
pri čemer pa moramo pare primerjati po drugem elementu.
Ena možnost je, da uporabimo key
, ki mu podamo
lambda-funkcijo. Ta prejema elemente, katerih maksimum iščemo in za
vsakega vrne ključ, glede na katerega ga primerjamo. V našem primeru
imamo pare, ki jih primerjamo po drugem elementu, torej
def naj_stolpec(ovire):
return max(((x, globina(ovire, x)) for x in range(1, sirina(ovire) + 1)),
=lambda x: x[1]) key
Če lambd ne poznamo (vsaj letos smo se o njih učili le na dodatnih
predavanjih), se znajdemo tako, da zamenjamo vrstni red elementov v
paru: namesto (x, globina(ovire, x))
sestavljamo pare
(globina(ovire, x), x)
. Funkcija max
jih bo
primerjala po prvem elementu in tako izbrala pravi največji element -- a
funkcija mora vrniti par, v katerem je na prvem mestu x
, ne
globina. Nič hudega, ga pač obrnemo pred vračanjem, tako da na konec
dodamo [::-1]
.
def naj_stolpec(ovire):
return max((globina(ovire, x), x)
for x in range(sirina(ovire) + 1) if globina(ovire, x) is not None)[::-1]
Žal nas zafrknejo stolpci brez ovir. Tam globina
vrne
None
. Funkcija mora v tem primeru vrniti ta stolpec ... a
namesto tega vrne napako, da poskušamo primerjati None
in
število.
Če delamo z lambdami, to rešimo tako, da funkcija, ki računa ključ, v
primeru, da je drugi element enak None
vrne 1000. Recimo,
da tako daleč ne bo nobene ovire. Če nas to moti, pa lahko vrača tudi
neskončno, float("inf")
.
def naj_stolpec(ovire):
return max(((x, globina(ovire, x)) for x in range(1, sirina(ovire) + 1)),
=lambda x: float("inf") if x[1] is None else x[1]) key
Rešitev brez lambde pa je zabavna. Takole storimo.
def naj_stolpec(ovire):
return ([(x, None)
for x in range(1, sirina(ovire) + 1) if globina(ovire, x) is None]
+ [max((globina(ovire, x), x)
for x in range(sirina(ovire) + 1) if globina(ovire, x) is not None)[::-1]]
0] )[
Seštevamo dva seznama. Prvi seznam vsebuje pare
(x, None)
za vse tiste x
, kjer ni ovir. Drugi
seznam pa vsebuje samo en element, namreč maksimalni element, ki ga
dobimo natančno tako, kot smo opisali zgoraj, vendar upoštevamo le tiste
x
, pri katerih ovire obstajajo.
Oba seznama torej seštejemo in nato vrnemo prvi element seznama, ki ga dobimo kot vsoto. Če obstaja kak stolpec brez ovir, bodo te v prvem seznamu in vrnili bomo prvo med njimi. Če stolpcev brez ovir ni, pa bo prvi seznam prazen in vrnili bomo prvi (in edini) element drugega. :)