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

Obvezna naloga

Napišite naslednje funkcije.

Rešitev

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)

Dodatne naloge

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

Rešitev

Števila ovir

Brez izpeljanega slovarja bi prvo nalogo rešili tako:

from collections import defaultdict

def stevila_ovir(ovire):
    stevila = defaultdict(int)
    for y, _, _ in ovire:
        stevila[y] += 1
    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.

Začetki

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

Ovire po vrsticah

In tole je spet isto, le da tokrat sestavljamo sezname.

def ovire_po_vrsticah(ovire):
    return {
        y: {(x0, x1) for yo, x0, x1 in ovire if yo == y}
        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()}