Rešitev

Briši ponovitve

Napiši funkcijo brisi_ponovitve(s), ki prejme seznam pozitivnih celih števil in ga popravi takole: v seznamu pusti največ eno enko, največ dve dvojki, največ tri trojke, štiri štirice in tako naprej (do poljubno velikih števil). Vse nadaljnje ponovitve pobriše. Funkcija ne vrne ničesar, temveč spreminja podani seznam.

>>> a = [1, 3, 4, 1, 3, 2, 2, 3, 5, 3, 2, 3, 4]
>>> brisi_ponovitve(a)
>>> a
[1, 3, 4, 3, 2, 2, 3, 5, 4]

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. Šteti moramo ponovitve elementa. Za to je, kot vemo, najprikladnejši slovar s privzetimi vrednostmi.

def brisi_ponovitve(s):
    ponovitev = defaultdict(int)
    i = 0
    while i < len(s):
        e = s[i]
        if ponovitev[e] == e:
            del s[i]
        else:
            ponovitev[e] += 1
            i += 1

Večina študentov ni reševala tako, temveč so sestavljali nov seznam in šteli ponovitve elementa e kar v njem.

def brisi_ponovitve(s):
    t = []
    for e in s:
        if t.count(e) < e:
            t.append(e)
    s[:] = t

Ni narobe in celo preprosteje je. Zavedati pa se moramo, da t.count(e) ni zastonj: ta funkcija gre čez seznam s in znotraj tega v vsakem koraku čez seznam t (v count-u). Čas izvajanja funkcije zato ne narašča linearno z dolžino s temveč s kvadratom dolžine s.

Največji v vseh

Napiši funkcijo najvecji_v_vseh(s), ki dobi seznam seznamov števil, s. Vrniti mora največje število, ki se pojavi v vseh (pod)seznamih. Če seznami nimajo nobenega skupnega elementa, funkcija vrne None. Klic najvecji_v_vseh([[5, 1, 2, 3], [3, 1, 8], [42, 5, 3, 1]]) vrne 3. V vseh treh seznamih se namreč pojavita 1 in 3; 3 je večja.

Pričakuj dolge sezname! Če je tvoja rešitev počasna in testi zmrznejo, jih prekini, sicer bo računalnik vedno počasnejši.

Rešitev

Tole je naloga iz množic. Najprej je namreč potrebno preiskati elemente, ki se pojavijo v vseh podseznamih, torej presek. Nato poiščemo maksimum preseka. Recimo tako.

def najvecji_v_vseh(s):
    if not s:
        return None
    presek = set(s[0])
    for t in s:
        presek &= set(t)
    return max(presek, default=None)

Če ne vemo, da ima funkcija max tudi argument default, ki se uporabi, kadar je presek prazen, pa pišemo

   if presek:
        return max(presek)

Krajše bi šlo tako.

from functools import reduce

def najvecji_v_vseh1(s):
    return max(reduce(set.intersection, map(set, s), set(s[0]) if s else set()), default=None)

vendar to ni posebej pregledno.

Vrstni red

Napiši funkcijo vrstni_red(ime_datoteke), ki prejme ime datoteke z rezultati nekega tekmovanja v naslednji obliki:

Ana Anžič: 5:12
Berta Bertolin: 4:48
Cilka Centrih: 5:05
Dani Dolinar: 10:12
Ema Evelina Estrih: 4:45

Funkcija vrne seznam imen tekmovalcev, urejen po časih od manjših proti večjim. Če imata dva tekmovalca enak čas, ju uredi po abecedi. Za gornji primer vrne ["Ema Evelina Estrih", "Berta Bertolin", "Cilka Centrih", "Ana Anžič", "Dani Dolinar"].

Rešitev

Tole je le preprosta naloga iz branja datotek. Rešimo jo lahko tako.

def vrstni_red(ime_datoteke):
    tekmovalci = []
    for vrstica in open(ime_datoteke):
        ime, ure, minute = vrstica.split(":")
        tekmovalci.append((int(ure), int(minute), ime))
    tekmovalci.sort()
    return [ime for _1, _2, ime in tekmovalci]

Če ne znamo uporabljati izpeljanih seznamov, rezultat zložimo počasneje -- zadnjo vrstico zamenjamo z

    red = []
    for _1, _2, ime in tekmovalci:
        red.append(ime)
    return red

Če se nam heca, pa napišemo

def vrstni_red(ime_datoteke):
    return [ime
            for _1, _2, ime in sorted((int(ure), int(minute), ime)
                                      for ime, ure, minute in (vrstica.split(":")
                                                               for vrstica in open(ime_datoteke)))]

Ne spreglejte, da se nisem preveč mudil s pretvarjanjem časov: če v terko zložimo najprej ure in minute (ali karkoli že ti časi so), se bodo te že uredila v pravi vrstni red.

Preveri vsoto

Napiši rekurzivno funkcijo preveri_vsoto(s, n), ki prejme seznam števil in domnevno vsoto teh števil. Funkcija vrne True, če je domnevna vsota točna in False, če ni.

Rekurzivna naj bo prav ta funkcija s prav temi argumenti. Ne piši pomožnih funkcij. Duhovitosti v smislu rekurzivne funkcije, ki izračunajo vsoto, ne veljajo.

Rešitev

Seznam s ima res vsoto n, če ima seznam s[1:] vsoto n - s[0].

Poskrbeti moramo le še za konec.

Tule je moje napačno razmišljanje. Če je seznam prazen in n enak 0, smo zmagali. Če ni tako in drži le eno od tega, smo izgubili. Sicer preverjamo ostanek.

def preveri_vsoto(s, n):  # Ne deluje pravilno!
    if n == len(s) == 0:
        return True
    if n == 0 or s == []:
        return False
    return preveri_vsoto(s[1:], n - s[0])

Vse pogoje je seveda preprosto zložiti v enega:

def preveri_vsoto(s, n):  # Ne deluje pravilno!
    return n == len(s) == 0 or s != [] and n > 0 and preveri_vsoto(s[1:], n - s[0])

Kot me je par ur po objavi te rešitve opozoril eden od študentov, moja funkcija vrne False, če jo pokličemo z preveri_vsoto([0, 0], 0), čeprav je vsota očitno pravilna.

Pravilna rešitev je preprostejša.

def preveri_vsoto(s, n):
    if s == []:
        return n == 0
    else:
        return preveri_vsoto(s[1:], n - s[0])

ali, krajše,

def preveri_vsoto(s,n):
    return n == 0 if not s else preveri_vsoto(s[1:], n-s[0])

Bravo, Matic!

Čakalnica

Napiši razred Cakalnica z naslednjimi metodami:

• prihod(ime, cas) zabeleži, da je ob podanem času v čakalnico vstopila oseba s podanim imenom. Predpostaviti smeš, da se metoda pokliče v trenutku, ko oseba vstopi. To pomeni, da bo čas pri vsakem klicu večji od časa pri predhodnem klicu;
• cakajocih() vrne število oseb v čakalnici;
• naslednji(cas) vrne ime naslednje osebe, ki je na vrsti. Osebe pridejo na vrsto v takšnem vrstnem redu, v kakršnem so prihajale. Če je čakalnica trenutno prazna, vrne None. Metoda kot argument prejme trenutni čas; potrebuje ga zaradi naslednjih dveh metod;
• skupni_cas_cakanja() vrne skupni čas čakanja vseh osebe, ki so že bile na vrsti (ne pa tistih, ki so še v čakalnici);
• povprecni_cas_cakanja() vrne povprečni čas čakanja za vse osebe, ki so že bile na vrsti (ali 0, če ni bila na vrsti še nobena oseba).

Konstruktor napiši, če meniš, da ga potrebuješ. Argumentov pa ne sme imeti.

Čas je vedno podan oz. vrnjen v urah. Če nekdo pride ob 10:45, je cas enak 10.75 (10 in tri četrt). Če je skupni čas čakanja uro in pol, metoda skupni_cas_cakanja vrne 1.5 (ne 1.30).

Rešitev

Pri tej nalogi je bilo nenavadno (in žalostno), da so se študenti masovno odločali, da bi jo bilo pametno rešiti s slovarjem. Ne. Tu potrebujemo vrstni red (na katerega slovarji nič ne dajo), iskanja pa ne (in slovarji so namenjeni prav iskanju).

Potrebovali bomo seznam čakajočih, skupni čas čakanja in število teh, ki so odšli. V seznamu čakajočih bodo seveda imena in časi prihodov.

Ko se odločimo glede teh reči, so vse metode čisto očitne.

class Cakalnica:
    def __init__(self):
        self.cakajoci = []
        self.cas_cakanja = 0
        self.odslih = 0

    def prihod(self, ime, cas):
        self.cakajoci.append((ime, cas))

    def naslednji(self, trenutni_cas):
        if self.cakajoci:
            ime, cas = self.cakajoci.pop(0)
            self.cas_cakanja += trenutni_cas - cas
            self.odslih += 1
            return ime

    def cakajocih(self):
        return len(self.cakajoci)

    def skupni_cas_cakanja(self):
        return self.cas_cakanja

    def povprecni_cas_cakanja(self):
        return self.cas_cakanja / (self.odslih or 1)