Rešitev

Odstrani enake

Napiši funkcijo odstrani_enake(s, t), ki prejme dva enako dolga seznama. Funkcija primerja istoležne pare njunih elementov in če sta oba elementa enaka, ju pobriše iz seznamov. Funkcija ne vrača ničesar, temveč spreminja prejeta seznama. V spodnjem primeru pobriše pare 3, 2 in 4.

>>> a = [1, 3, 2, 13, 2, 4, 4]
>>> b = [8, 3, 13, 8, 2, 4, 5]
>>> odstrani_enake(a, b)
>>> a
[1, 2, 13, 4]
>>> b
[8, 13, 8, 5]

Rešitev

Tole je klasičen vzorec brisanje po seznamih: uporabiti je potrebno zanko while. Če poskusimo kaj v slogu

for e in s:
    if potrebno_pobrisati(e):
        s.remove(e)

to ne bo nujno pobrisalo te pojavitve e-ja temveč prvo, na katero remove naleti. Poleg tega pa bo zanka for preskočila element, ki sledi e-ju in je prišel na e-jevo mesto.

Tudi

for i, e in enumerate(s):
    if potrebno_pobrisati(e):
        del s[i]

ne deluje. Pobriše sicer pravi, i-ti element seznama, vendar se element z indeksom i + 1 pri tem prestavi na i-to mesto in se izmakne zanki.

Pravi vzorec je torej

i = 0
while i < len(s):
    if potrebno_pobrisati(s[i]):
        del s[i]
    else:
        i += 1

Druga, prav tako legalna možnost je sestavljanje novega seznama, vendar moramo v tem primeru paziti, kako zamenjamo elemente obstoječega seznama z novimi:

t = []
for e in s:
    if not potrebno_pobrisati(e):
        t.append(e)
s[:] = t

Če bi v zadnji vrstici napisali s = t, bi ostala vsebina seznama, ki smo ga v začetku imenovali s (in ki je bil podan kot argument funkciji) nespremenjena.

Zdaj pa končno rešimo nalogo.

def odstrani_enake(s, t):
    i = 0
    while i < len(s):
        if s[i] == t[i]:
            del s[i]
            del t[i]
        else:
            i += 1

Zelo podobno nalogo so imeli tudi v prvi skupini. Njihova je bila nekoliko težja ... zato pa je bila v drugi skupini nekoliko težja tretja naloga.

Diff

Napiši funkcijo diff(datoteka1, datoteka2), ki prejme imeni dveh datotek in vrne seznam razlik med njima. Vrnjeni seznam naj vsebuje trojke (številka vrstice, niz z vrstico iz prve datoteke, niz z vrstico iz druge datoteke). Datoteki vsebujeta enako število vrstic. Prva vrstica naj ima številko 1. Vrsticam odstrani znake za novo vrstico.

Recimo, da imamo datoteki

Ana
Berta
Cecilija
Dani
Ema

in

Ana
Berta
Cilka
Dani
Eva Ema

Funkcija vrne [(3, 'Cecilija', 'Cilka'), (5, 'Ema', 'Eva Ema')].

Rešitev

Tole je očitno naloga iz branja datotek, pri ocenjevanju pa sem upošteval tudi spretnost programiranja, uporabo zip in tako naprej.

Najhitreje gre tako:

def diff(dat1, dat2):
    razlike = []
    for i, (vrstica1, vrstica2) in enumerate(zip(open(dat1), open(dat2)), start=1):
        if vrstica1 != vrstica2:
            razlike.append((i, vrstica1.strip(), vrstica2.strip()))
    return razlike

Magija je seveda v zanki. Odpremo obe datoteki: open(dat1), open(dat2). Namesto da bi šli prek njiju z ločenima zankama, ju zadrgnemo skupaj: zip(open(dat1), open(dat2)). Vendar bomo potrebovali še zaporedne številke, zato enumerate(zip(open(dat1), open(dat2))). enumerate začne šteti z 0. Nič hudega, v append-u bi pač pisali i + 1. Lahko pa dodamo še argument start=1, pa bo štel od 1.

Zdaj pa se ozrimo še levo od in. Tam piše i, (vrstica1, vrstica2). To je potrebno zato, ker smo z zip sestavili pare, nato pa jih z enumerate oštevilčili. Če bi pisali for i, vrstica1, vrstica2, to ne bi delovalo, saj nam enumerate(zip(...)) ne sestavi trojk temveč pare, v kateri je drugi element spet par.

Mesta

Imamo seznam, ki vsebuje imema tekmovalcev in število točk, ki so jih dosegli, npr. [("Ana", 15), ("Berta", 13), ("Cilka", 12), ("Dani", 12), ("Ema", 8), ("Fanči", 6), ("Greta", 6)]. Seznam je že urejen po padajočem številu točk. Točke so nenegativna cela števila.

Napiši funkcijo mesta(s), ki prejme takšen seznam in vrne takšen seznam, v katerem bo i-ti element vseboval seznam vseh, ki so uvrščeni na i-to mesto. Za gornji primer vrne [["Ana"], ["Berta"], ["Cilka", "Dani"], [], ["Ema"], ["Fanči", "Greta"], []]. Cilka in Dani sta v istem seznamu, ker si delita tretje mesto in četrti seznam je prazen, ker nihče ni četrti. Podobno je z Fanči in Greto: sta v istem seznamu in naslednji seznam je prazen. Isto mesto si lahko deli tudi več oseb – celo vse. Za nekaj primerov poglej (tudi) teste.

Rešitev

Tole pa je naloga iz iznajdljivosti.

Sam sem jo rešil tako:

def mesta(s):
    mesta = []
    zadnji = None
    zadnje_tocke = -1
    for ime, tocke in s:
        if tocke != zadnje_tocke:
            zadnji = [ime]
            mesta.append(zadnji)
            zadnje_tocke = tocke
        else:
            zadnji.append(ime)
            mesta.append([])
    return mesta

V zadnje_tocke si zapomnim, koliko točk je imel zadnji, ki sem ga dodal v seznam, v zadnji pa zadnji seznam, v katerega sem koga dodal. mesta je seznam, ki ga sestavljam. Znotraj zanke v vsakem koraku zagotovo nekaj dodam v mesta. Če je število točk trenutnega tekmovalca različno od točk prejšnjega, sestavimo nov zadnji seznam, v njem je to ime, in ta seznam gre v mesta. Če je število točk enako, pa dodam v mesta prazen seznam, tole ime pa gre v zadnji.

Večina študentov, ki je uspela rešiti to nalogo, se je izmazala s slovarji. Recimo tako:

from collections import defaultdict
def mesta(s):
    po_tockah = defaultdict(list)
    for oseba, tocke in s:
        po_tockah[tocke].append(oseba)

    mesta = []
    for tocke in sorted(po_tockah, reverse=True):
        na_mestu = po_tockah[tocke]
        mesta.append(na_mestu)
        mesta += [[]] * (len(na_mestu) - 1)
    return mesta

V prvem delu grupiramo tekmovalce v slovar, katerega ključi so števila točk, vrednosti pa imena tekmovalcev s takšnim številom točk. Nato gremo po vrsti po različnih številih točk. V končni seznam vsakič dodamo seznam tekmovalcev nato pa še ustrezno število praznih seznamov. (Pozorni študent bo opazil, da so vsi ti prazni seznami isti. Tule bi to moralo biti vseeno, saj vanje ne bomo ničesar dodajali.)

Dovolj lihih

Napiši rekurzivno funkcijo dovolj_lihih(s, n), ki vrne True, če je v seznamu s vsaj n lihih števil in False, če jih ni toliko.

(Rekurzivna naj bo prav ta funkcija s prav temi argumenti. Ne piši pomožnih funkcij.)

Rešitev

Če je prvo število liho, mora biti v ostanku seznama vsaj še n - 1 lihih števil. Sicer pa jih mora biti še n. Torej

def dovolj_lihih(s, n):
    if n == 0:
        return True
    if not s:
        return False
    if s[0] % 2 == 1:
        return dovolj_lihih(s[1:], n - 1)
    else:
        return dovolj_lihih(s[1:], n)

Potem opazimo, da lahko združimo zadnji vrstici v eno.

def dovolj_lihih(s, n):
    if n == 0:
        return True
    if not s:
        return False
    return dovolj_lihih(s[1:], n - s[0] % 2)

Ali pa združimo kar vse pogoje.

def dovolj_lihih(s, n):
    return n == 0 or s and dovolj_lihih(s[1:], n - s[0] % 2)

Parkirišče

Napiši razred Parkirisce, obdarjen z naslednjimi metodami.

• Konstruktor prejme število parkirnih mest na parkirišču.
• prosto() vrne True, če je na parkirišču kaj prostih mest in False, če jih ni.
• parkiraj(registracija, cas) pokličemo, ko ob podanem času na parkirišče pripelje avto s podano registracijo. Če je parkirišče polno, metoda ne naredi ničesar, sicer pa zabeleži, kar je potrebno za delovanje ostalih metod. Metoda ne vrne ničesar.
• odpelji(registracija, cas) pokličemo, če avto s podano registracijo ob podanem času zapusti parkirišče. Metoda vrne ceno parkirnine; ta znaša toliko evrov, kolikor je začetih ur: če je avto parkiran 2.45 ure, plača 3 evre. (V modulu math se nahaja potencialno uporabna funkcija ceil.) Predpostaviti smeš, da je avto, ki je odpeljal s parkirišča, dejansko bil parkiran na parkirišču.
• zasluzek() vrne vsoto vseh parkirnin za avte, ki so že zapustili parkirišče.

Časi po podani v urah. Če avto pripelje ob 10 uri in 45 minut, je argument cas enak 10.75 (10 in tri četrt). (To je preprosto: minute naj te ne vznemirjajo, za izračun parkirnine pa čase parkiranja le zaokrožaš navzgor.)

Rešitev

Konstruktor si bo očitno moral zapomniti število parkirnih mest in pripraviti slovar, katerega ključi bodo registracije, vrednosti pa časi parkiranja (saj bomo v tem slovarju kasneje iskali po registracijah). Poleg tega bo potrebno shranjevati vsoto pobranih parkirnin.

Ko se odločimo glede tega, so metode preproste.

class Parkirisce:
    def __init__(self, kapaciteta):
        self.kapaciteta = kapaciteta
        self.parkirani = {}
        self.parkirnine = 0

    def prosto(self):
        return len(self.parkirani) < self.kapaciteta

    def parkiraj(self, registracija, cas):
        if self.prosto():
            self.parkirani[registracija] = cas

    def odpelji(self, registracija, cas):
        cena = int(math.ceil(cas - self.parkirani.pop(registracija)))
        self.parkirnine += cena
        return cena

    def zasluzek(self):
        return self.parkirnine

Zelo me je žalostilo, da večina študentov še vedno piše:

    def prosto(self):
        if len(self.parkirani) < self.kapaciteta:
            return True
        else:
            return False

Vsi bodo dosegli svoj cilj, samo jaz ga ne bom dosegel, je rekel kolega Srečko.