Ovire v vrstici

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 slovarje.

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)]

Obvezna naloga

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.

Dodatne naloge

Tole so naloge, ki pokažejo, 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.

Testi