Prepovedana števila

Napiši funkcijo dovoljeno(s), ki dobi seznam intervalov prepovedanih števil, na primer [(5, 10), (0, 3), (15, 20), (7, 9), (2, 8)]. Intervali vključujejo meje (npr. prepovedana so vsa števila od 5 do vključno 10). Vrniti mora prvo dovoljeno celo število, večje ali enako 0. V gornjem primeru je to 11.

Rešitev

Nalogo je mogoče rešiti na veliko načinov. Izmed preprostejših je najbolj eleganten ta.

def dovoljeno(s):
    i = 0
    while True:
        for od, do in s:
            if od <= i <= do:
                break
        else:
            return i
        i += 1

Temelji na triku iz Pythona (ki ga v večini drugih jezikov ni, torej morda ni najbolj primeren za predmet o programiranju v splošnem): else za for. Zunanja zanka le šteje od 0 to neskončno. V notranji zanki preverimo, ali je število i prepovedano. Če je, jo prekineno. Če je ne prekinemo, se pravi, če gre prek vseh intervalov in noben ne vključuje števila, pa se break ne izvede, torej se izvede else, ki vrne to število.

Še malenkost imenitneje je, če vemo, da ima modul itertools funkcijo count(n), ki vrne vsa cela števila od n naprej; če jo pokličemo brez argumentov, pa šteje od 0. Tako dobimo:

from itertools import count

def dovoljeno(s):
    for i in count():
        for od, do in s:
            if od <= i <= do:
                break
        else:
            return i

Če ne želimo uporabljati else-a po zanki, lahko napišemo ločeno funkcijo.

def prepovedano(i, s):
    for od, do in s:
        if od <= i <= do:
            return True
    return False

def dovoljeno(s):
    i = 0 
    while prepovedano(i, s):
        i += 1
    return i

Tole je tudi nekako najlepša rešitev za Programiranje 1. Kratka, jasna.

Najbolj Pythonovska rešitev (ki presega Programiranje 1), je takšna:

def dovoljeno(s):
    return next(x for x in count() if not any(od <= x <= do for od, do in s))

Saj bi večino bi še razumeli, samo next-a ne poznamo.

Rešitve, ki so jih oddajali študenti, pa so šle pogosto v to smer, da bi zbrali vsa prepovedana števila in potem poiskali prvo, ki ni prepovedano. Navadno v tem smislu:

def dovoljeno(s):
    prepovedana = set()
    for od, do in s:
        for x in range(od, do + 1):
            prepovedana.add(x)

    i = 0
    while i in prepovedana:
        i += 1
    return i

Nekdo je zapisal, da "gotovo obstaja boljša rešitev, z unijami". Res je.

def dovoljeno(s):
    prepovedana = set()
    for od, do in s:
        prepovedana |= set(range(od, do + 1))

    i = 0
    while i in prepovedana:
        i += 1
    return i

Obstajajo teoretični razlogi, zakaj so rešitve z množicami boljše (hitrejše) od onih, ki smo jih napisali zgoraj. A nanje boste morali počakati do tretjega letnika.

Reke

Napiši funkcijo reke(s), ki prejme seznam parov: prvi element je ime reke, drugi pa ime reke, v katero se ta reka izliva, na primer [("Sora", "Sava"), ("Savinja", "Sava"), ("Mura", "Drava"), ("Drava", "Donava"), ("Sava", "Donava"), ("Ljubljanica", "Sava"), ("Kamniška Bistrica", "Sava")].

Funkcija mora vrniti seznam parov, v katerem je prvi element reka, drugi pa seznam vseh rek, ki se izlivajo vanjo. Vrstni red rek je lahko poljuben. V gornjem primeru lahko funkcija vrne, recimo,

[("Sava", ["Sora", "Savinja", "Ljubljanica", "Kamniška Bistrica"]),
 ("Donava", ["Drava", "Sava"]),
 ("Drava", ["Mura"])]

Rek je lahko tudi zelo veliko! (Če se test zatakne, ker je funkcija prepočasna, pritisni rdeči kvadratek, »Stop«.)

Rešitev

Da je rek lahko tudi veliko, naj bi bil jasen namig, da bo tu potrebno uporabljati slovarje. Pa tudi sicer je bolj praktično reševati z njimi kot na kake druge načine.

Sestaviti nam je torej slovar, katerega ključi bodo reke, vrednosti pa seznami njihovih pritokov. Da se ne zafrkavamo s tem, ali nek ključ že obstaja ali ne, uporabimo defaultdict.

Na koncu je potrebno ta slovar pretvoriti v seznam parov, v katerih je prvi element ime reke, drugi seznam pritokov. To pa je točno to, kar nam vrne items. No, skoraj točno to: items vrne nekaj, kar se vede podobno kot seznam, potem pa ga z list pretvorimo v pravi seznam.

from itertools import defaultdict

def reke(s):
    pritoki = defaultdict(list)
    for pritok, reka in s:
        pritoki[reka].append(pritok)
    return list(pritoki.items())

Če se ne spomnimo na pretvarjanje z list, se zadnja vrstica pač malo razvleče.

from itertools import defaultdict

def reke(s):
    pritoki = defaultdict(list)
    for pritok, reka in s:
        pritoki[reka].append(pritok)

    rezultat = []
    for reka, njeni_pritoki in pritoki.items():
        rezultat.append((reka, njeni_pritoki))
    return rezultat

Še vedno pa je naloga lažja, kot bi človek sklepal po, ehm, težavah, ki so jih imeli z njo študenti.

Ujemanja

Napiši rekurzivno funkcijo (nobenih zank!) ujemanja(s, t), ki prejme dva seznama in primerja njune istoležne elemente. Vrniti mora množico vseh elementov, v katerih se seznama ujemata. Klic

ujemanja([5, 1, 2, 6, 7, 6, 8, 4, 12],
         [4, 4, 2, 6, 5, 2, 8, 3])

vrne {2, 6, 8}. Seznama sta očitno lahko tudi različno dolga.

Rešitev

Če je katerikoli seznam prazen, vrnemo prazno množico. Sicer pa sestavimo množico za elemente od prvega naprej, nato pa dodamo še prvega, če je potrebno.

def ujemanja(s, t):
    if not s or not t:
        return set()
    naprej = ujemanja(s[1:], t[1:])
    if s[0] == t[0]:
        naprej.add(s[0])
    return naprej

Izdelki študentov so šli bolj v to smer.

def ujemanja(s, t):
    if not s or not t:
        return set()
    if s[0] == t[0]:
        return {s[0]} | ujemanja(s[1:], t[1:])
    else:
        return ujemanja(s[1:], t[1:])

Tudi prav.

Ena nesrečnica je namesto return {s[0]} | ujemanja(s[1:], t[1:]) napisala return {s[0]}.add(ujemanja(s[1:], t[1:])). To sem šel kot skoraj pravilno, saj je imela lepe misli in dobre namene. Vendar metoda add ni unija, tako da jih kot argument ne moremo podati množice, temveč le en element. Poleg tega metoda add ne vrne ničesar, temveč le doda element v množico. Ta return zato vedno vrne None.

Parkirna hiša

Napiši razred ParkirnaHisa.

  • Konstruktor prejme število parkirnih mest.
  • Metoda prihod(registracija, cas) prejme registracijo avtomobila in trenutni čas. Vrniti mora številko prvega prostega parkirnega mesta in zabeležiti, da je le-to zasedeno. Mesta so oštevilčena z zaporednimi števili, začenši z 0. Če je parkirna hiša polna, vrne None.
  • Metoda odhod(registracija, cas) prejme registracijo avtomobila in trenutni čas. Vrniti mora, koliko časa je bil avtomobil parkiran, poleg tega pa zabeleži, da je mesto spet prosto.
  • Metoda zasedenost() vrne število trenutno parkiranih avtomobilov.

Rešitev

Kaj mora razred vedeti, kakšne podatke mora hraniti? Vedeti mora, kdo je parkiran na katerem mestu in kdaj je prišel. Torej bomo imeli seznam parkirnih mest. Imel bo toliko elementov, kolikor je mest, vrednost pa bo bodisi par (registracija, čas), ali pa None, če je mesto prosto.

Ko se odločimo glede tega, samo še napišemo metode.

class ParkirnaHisa:
    def __init__(self, n_parkirisc):
        self.parkirna_mesta = [None] * n_parkirisc

    def prihod(self, registracija, cas):
        for mesto, zasedeno in enumerate(self.parkirna_mesta):
            if not zasedeno:
                self.parkirna_mesta[mesto] = (registracija, cas)
                return mesto

    def odhod(self, registracija, cas):
        for mesto, (reg, prihod) in enumerate(self.parkirna_mesta):
            if reg == registracija:
                self.parkirna_mesta[mesto] = None
                return cas - prihod

    def zasedenost(self):
        return len(self.parkirna_mesta) - self.parkirna_mesta.count(None)

V obeh zankah uporabljamo enumerate, ker bomo spreminjali določen element seznama, torej potrebujemo njegov indeks. V prihod imamo for mesto, zasedeno in enumerate(self.parkirna_mesta) in preverjamo ali je zasedeno None ali ne (pri čemer lahko namesto zasedeno == None oz. zasedeno is None pišemo kar not zasedeno; če je zasedeno terka z dvema elementoma je resnična). Ko torej najdemo prosto mesto, vanj zapišemo registracijo in čas ter vrnemo njegovo številko. Če ga ne najdemo, ne vrnemo ničesar, torej vrnemo None.

V metodi odhod pišemo for mesto, (reg, prihod) in enumerate(self.parkirna_mesta), saj nas zanimata tako registracija kot prihod. Ko odkrijemo mesto s pravo registracijo, nanj "parkiramo" None in vrnemo razliko med trenutnim časom in časom parkiranja.

Zasedenost pa izračunamo tako, da preštejemo prosta mesta (count(None)) in njihovo število odštejemo od dolžine seznama.

Nekdo je (kar smiselno) razmišljal o tem, da ni lepo, da v metodi odhod z zanko iščemo avtomobile po garaži, zato je dodal še slovar, v katerem je za vsak avto pisalo, kje je parkiran. Če bi v resnici programirali takšen sistem, bi dejansko naredili nekaj podobnega. (Točneje: v resnici ne bi imeli slovarjev, temveč bi podatkovno bazo indeksirali tudi po registracijah. Ampak to je v bistvu isto.) Skratka: lepa ideja. Le program zaplete, ker je potem potrebno vzdrževati še slovar ali dva, namesto enega samega seznama.

Sicer pa moram po pregledovanju izpitov opozoriti, da se je več študentov zmotilo na ta način, da so registracijo in čas zapisovali na ta način:

    def prihod(registracija, cas):
        self.registracija = registracija
        self.cas = cas

To ne gre in kaže na napako v razmišljanju. Registracija ni lastnost parkirne hiše. Lastnost parkirne hiše je (kvečjemu) seznam registracij avtomobilov, ki so parkirani v njej. Gornja metoda očitno ne more delovati, saj lahko hrani le eno samo registracijo.

Interpolacija

Napiši funkcijo interpolacija(s), ki prejme seznam nekih meritev. Nekatere meritve manjkajo: tam se v seznamu namesto števila nahaja None. Lahko se zgodi, da je teh None tudi več zapored. Funkcija mora vrniti nov seznam, v katerem so None zamenjani s poprečjem zadnjega števila pred None (oz serijo None-ov) in prvega po None. Če so None na začetku, naj jih zamenja s prvim elementom, ki ni None. Če so na koncu, jih zamenja z zadnjim, ki ni None.

Če funkcija prejme seznam [None, 3, 5, 2, None, None, None, None, 6, 1, None, None], vrne [3, 3, 5, 2, 4, 4, 4, 4, 6, 1, 1, 1].

Rešitev

Če so bile ostale naloge lahke -- ali pa bi vsaj morale biti lahke -- je bila ta kar ... spodobna.

Ena tistih, pri katerih je bilo treba razmisliti, kako se jih lotiti, saj se sicer zavozlajo. Funkcijo bo najlažje razložiti kar sproti, s komentarji.

def interpolacija(s):
    t = []                      # t je seznam, ki ga bomo na koncu vrnili
    i = 0
    while i < len(s):           # gremo do konca seznama
        if s[i] is not None:    # prepisujemo vsa števila, ki niso None
            t.append(s[i])
            i += 1

        else:                   # ko naletimo na None
            while i < len(s) and s[i] is None:  # preskočimo vse, ki so None
                i += 1

            if not t:           # če je seznam, ki ga bomo vrnili, še prazen,
                poprecje = s[i] # so bili to Noni od začetka seznama. Poprečje je tedaj
                                # kar trenutni element, s[i] (prvi element s, ki ni None)
            elif i == len(s):   # če pa smo prišli do konca seznama, so bili vsi 
                poprecje = t[-1]  # ti None na koncu in je "poprečje" zadnji element,
                                # ki smo ga dodali v t (zadnji ne-None)
            else:               # sicer pa izračunamo sredino med zadnjim ne-Noneom 
                poprecje = (t[-1] + s[i]) / 2  # in trenutnim (prvi za Nonei)
            t += [poprecje] * (i - len(t))  # nato v t tolikokrat dodamo poprecje, kolikor
                                # je bilo Noneov bilo pa jih je toliko, kolikor elementov
                                # manjka v t-ju, se pravi, kolikor je t krajši
                                # od indeksa trenutnega elementa v s.
    return t
Last modified: Tuesday, 23 June 2020, 5:45 PM