Naloga se navezuje na nalogo Šikaniranje oziroma Lokacije ovir in 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. Vadimo namreč izpeljane sezname, množice in generatorje.
Funkcije se lahko kličejo med sabo, izjemoma pa ne smete pisati dodatnih funkcij, ki jih naloga ne zahteva.
Ovire bodo podane s seznamom trojk (y, x0, x1)
, ki
predstavljajo vrstico ter začetni in končni stolpec z oviro. Seznam ni
urejen in je lahko videti, recimo, tako
1, 3, 6),
[(1, 8, 10),
(2, 1, 4),
(3, 5, 8),
(2, 7, 9),
(7, 10, 10),
(7, 12, 13),
(5, 8, 10),
(5, 1, 3),
(2, 15, 19)] (
Napišite naslednje funkcije.
vrstice(ovire)
vrne seznam vseh vrstic z ovirami.
Vrstice so naštete v enakem vrstnem redu kot v seznamu in se lahko
ponavljajo. Za gornji primer funkcija vrne
[1, 1, 2, 3, 2, 7, 7, 5, 5, 2]
.ovirane_vrstice(ovire)
vrača podoben seznam, le da je
urejen. Za gornji primer vrne
[1, 1, 2, 2, 2, 3, 5, 5, 7, 7]
.ovirane_vrstice_uni(ovire)
vrne podoben seznam, le da
se vrstice ne ponavljajo. Za gornji primer vrne
[1, 2, 3, 5, 7]
. (Namig: v množico.)ovire_v_vrstici(ovire, vrstica)
vrne množico začetkov
in koncev vseh ovir v podani vrstici. Klic
ovire_v_vrstici(ovire, 2)
vrne
{(1, 4), (7, 9), (15, 19)}
.stevilo_ovir(ovire, vrstica)
vrne število ovir v podani
vrstici.dolzina_ovir(ovire)
vrne skupno dolžino vseh ovir.prosta_pot(ovire, stolpec)
vrne True
, če
nobena od ovir ne zapira podanega stolpca, in False
, če
takšna ovira obstaja.vrstice
mora vrniti seznam vseh indeksov y
,
ki se pojavijo v ovire
.
def vrstice(ovire):
return [y for y, _, _ in ovire]
Naloga ovirane_vrstice
na spomni, da obstaja funkcija
sorted
. Podamo ji lahko kar generator: vse, kar bo
zgeneriral, bo zložila v seznam in ga uredila.
def ovirane_vrstice(ovire):
return sorted(y for y, _, _ in ovire)
Tretja naloga nas spomni, kako dobimo unikatne stvari: tako da jih
vržemo v množico. Množico podamo sorted
, ki bo elemente
množice zložil v seznam in ga uredil.
def ovirane_vrstice_uni(ovire): # namig: v množico
return sorted({y for y, _, _ in ovire})
V četrti nalogi uporabimo pogoje: zanimajo nas začetki in konci,
(x0, y0)
v vseh tistih trojkah y, x0, x1
v
seznamu ovire
, za katere velja, da je y
enak
vrstica. Če to namesto v slovenščini povemo v Pythonu, dobimo:
def ovire_v_vrstici(ovire, vrstica):
return {(x0, x1) for y, x0, x1 in ovire if y == vrstica}
Število ovir v vrstici je lahko dolžina seznama, ki ga vrne funkcija
ovire_v_vrstici
.
def stevilo_ovir(ovire, vrstica):
return len(ovire_v_vrstici(ovire, vrstica))
Če te funkcije nimamo ali pa se želimo izogniti sestavljanju seznama,
lahko uporabimo sum
: y == vrstica
bo bodisi
resničen, True
ali neresničen, False
, kar je
enak0 1
ali 0
.
def stevilo_ovir(ovire, vrstica):
return len(ovire_v_vrstici(ovire, vrstica))
Dolžino ovir dobimo tako, da odštejemo x1 - x0
za vsako
oviro - pa še 1
prištejemo, ker ovira vključuje tudi
zgornjo mejo.
def dolzina_ovir(ovire):
return sum(x1 - x0 + 1 for _, x0, x1 in ovire)
Pot je prosta, če ni nobenega ovire, ki bi jo zapirala.
def prosta_pot(ovire, stolpec):
return not any(x0 <= stolpec <= x1 for _, x0, x1 in ovire)
De Morgan pa bi vedel povedati, da je to isto, kot če rečemo, da za vse ovire velja, da je ne zapirajo.
def prosta_pot(ovire, stolpec):
return all(not x0 <= stolpec <= x1 for _, x0, x1 in ovire)
Tole so naloge za študentko iz približno pete vrste in za vse druge, ki jih zanima, zakaj je potrebno pri
[<izraz> for <spremenljivka> in <seznam> if <pogoj>]
razmišljati drugače kot pri
s = []
for <spremenljivka> in <seznam>:
if <pogoj>:
s.append(<izraz>)
Naloge niso težke, morda pa so poučne. Da bodo še poučnejše,
predlagam, da izmed funkcij, ki ste jih sprogramirali zgoraj, v spodnjih
funkcijah kličete kvečjemu funkcijo ovirane_vrstice_uni
.
Morda bo še boljše, če vse funkcije najprej sprogramirate s klasično
zanko, da boste videli, zakaj takšne zanke ne morete preprosto predelati
v izpeljan slovar. (Spoiler: ker ne morete "updateati" vrednosti v
slovarju, ki ga še ni.)
stevila_ovir(ovire)
vrne slovar, katerega ključi so
številke vrstic, ki vsebujejo vsaj eno oviro, vrednosti pa število ovir
v tej vrstici.zacetki(ovire)
vrne slovar, katerega ključi so številke
vrstic z vsaj eno oviro, vrednosti pa najbolj levi ovirani stolpec.ovire_po_vrsticah(ovire)
vrne slovar, katerega ključi
so številke vrstic z vsaj eno oviro, vrednosti pa množice začetkov in
koncev ovir v tej vrstici.Brez izpeljanega slovarja bi prvo nalogo rešili tako:
from collections import defaultdict
def stevila_ovir(ovire):
= defaultdict(int)
stevila for y, _, _ in ovire:
+= 1
stevila[y] return stevila
Zato pridemo na idejo, da bi se na podoben način lotili tudi z izpeljanim slovarjem.
from collections import defaultdict
def stevila_ovir(ovire):b
return {y: ?!?!?![y] + 1 for y, _, _ in ovire}
Problem je, kajpa, v ?!?!?!. K čemu bomo prišteli 1? Tega slovarja še ni.
Zato sem na predavanjih poudarjal, da ta slovar nastane takšen, kot je. Med nastajanjem ga ne moremo spreminjati, se sklicevati nanj... Rešitev v eni vrstici bo morala biti
from collections import defaultdict
def stevila_ovir(ovire):b
return {y: ?!?!?! for y, _, _ in ovire}
pri čemer bo ?!?!?! že dokončna vrednost, število vseh ovir v podani vrstici.
Napisati moramo torej
def stevila_ovir(ovire):
return {y: stevilo_ovir(ovire, y)
for y in ovire}
Če funkcije stevilo_ovir
še ne bi imeli, pa bi število
ovir pač izračunali prav tu:
def stevila_ovir(ovire):
return {y: sum(yo == y for yo, _, _ in ovire)
for y in ovire}
Tu je nerodno, da se to računa za vsako oviro, torej bomo za vsako vrstico tolikokrat šteli ovire, koliko ovir je v tej vrstici. To ne bo vplivalo na končni rezultat, bo pa, seveda, na hitrost. Temu se izognemo tako, da gremo čez množico oviranih vrstic.
def stevila_ovir(ovire):
return {y: stevilo_ovir(ovire, y)
for y in ovirane_vrstice(ovire)}
Ali, če nobene od teh dveh funkcij še ne bi imeli:
def stevila_ovir(ovire):
return {y: sum(yo == y for yo, _, _ in ovire)
for y in {y for y, _, _ in ovire}}
Treba pa je pošteno povedati, da je ta rešitev verjetno počasnejša od
prve, tiste z običajno zanko, saj se zanka
for yo, _, _ in ovire
tu izvede tolikokrat, kolikor je
zasedenih vrstic.
Tole je ista finta, le da namesto funkcije stevilo_ovir
iščemo minimume.
def zacetki(ovire):
return {y: min(x0 for yo, x0, _ in ovire if y == yo)
for y in ovirane_vrstice(ovire)}
In tole je spet isto, le da tokrat sestavljamo sezname.
def ovire_po_vrsticah(ovire):
return {
for yo, x0, x1 in ovire if yo == y}
y: {(x0, x1) for y in ovirane_vrstice(ovire)}
Če bi najprej sprogramirali ovire_po_vrsticah
, ostali
dve funkciji izpeljemo iz nje:
def stevila_ovir(ovire):
return {y: len(x0x1)
for y, x0x1 in ovire_po_vrsticah(ovire).items()}
def zacetki(ovire):
return {y: min(x for x, _ in x0x1)
for y, x0x1 in ovire_po_vrsticah(ovire).items()}