Menjave

Napiši funkcijo menjave(razpored, zamenjave), ki prejme seznam z začetnim razporedom nekih oseb, na primer ["Ana", "Berta", "Cilka", "Dani", "Ema], in seznam parov števil, ki predstavljajo menjave. Seznam menjav [(0, 4), (1, 2), (0, 2)] pomeni, da se najprej zamenjata osebi na mestih 0 in 4, nato osebi na mestih 1 in 2, nato osebi na mestih 0 in 2.

Funkcija mora spremeniti podani seznam razpored tako, da bo ustrezal končnemu razporedu. V gornjem primeru je to ["Berta", "Cilka", "Ema", "Dani", "Ana"]. Kot rezultat pa mora funkcija vrniti množico vseh oseb, ki so bile kdaj na mestu 0. V gornjem primeru so to {"Ana", "Ema", "Berta"}.

Rešitev

Vedeti moramo le, da e-ti in f-ti element zamenjamo z razpored[e], razpored[f] = razpored[f], razpored[e]. Na začetku in po vsaki menjavi dodamo v množico razpored[0]. To je to.

def menjave(razpored, zamenjave):
    na0 = {razpored[0]}
    for e, f in zamenjave:
        razpored[e], razpored[f] = razpored[f], razpored[e]
        na0.add(razpored[0])
    return na0

Pari

Napiši funkcijo najblizji_par(s), ki prejme seznam različnih števil in vrne par najbližjih števil. Števili naj bosta urejeni po velikosti. Klic najblizji_par([2, -2, 7, 10, 5, 20]) vrne (5, 7). Kadar obstajata dva para z enako razliko, naj vrne tistega z manjšimi števili.

Napiši funkcijo pari(s), ki prejme seznam števil in vrne seznam najbližjih parov, dobljenih po naslednjem postopku. Prvi par sta najbližji števili v seznamu s (izbrani na enak način kot v prejšnjem odstavku). Drugi par sta najbližji števili izmed preostalih števil v seznamu. Tretji par sta najbližji števili izmed preostalih ... in tako naprej. Če ima seznam liho število elementov, preostali element ignoriramo.

Klic pari([2, 5, 6.5, -2, 10, 20]) vrne [(5, 6.5), (-2, 2), (10, 20)].

Rešitev

Glavna znanost tule je prva funkcija, predvsem zaradi urejanja in pogojev. Ena možna rešitev je taka.

def najblizji_par(s):
    naj_e = naj_f = None
    for e in s:
        for f in s:
            if e < f and (naj_e is None
                          or f - e < naj_f - naj_e
                          or f - e == naj_f - naj_e and e < naj_e):
                naj_e, naj_f = e, f
    return naj_e, naj_f

(naj_e, naj_f) sta tisto, kar bomo vrnili. V začetku sta None. Nato moramo narediti gnezdeni zanki prek seznama, ker moramo pač pogledati vse pare.

Par (e, f) nas zanima, če je e manjši od f. Če ni, gre bodisi za en in isti element, ne za par. Če je e večji od f, pa par preskočimo, saj ga bomo (ali pa smo ga že) videli tudi z obrnjenima e in f.

Zdaj, ko vemo, da je f večji od e, je preprosto računati razliko. Novi par je boljši od doslej znanega najboljšega, če je to sploh prvi par, na katerega smo naleteli (naj_e is None) ali pa je razlika med e in f manjša od najmanjše, ali pa je enaka najmanjši, vendar je e manjši od naj_e (in posledično seveda tudi f manjši od naj_f).

Se lahko izognemo temu, da bi morali preveriti vse pare? Seveda. Števila uredimo po velikosti in najbližji par bo gotovo zaporeden. Tako imamo le eno zanko, pa tudi pogoj f > e ni več potreben. Tudi na f - e == naj_f - naj_e nam ni več potrebno paziti: če večkrat naletimo na isto razliko, bomo obržali prvo, saj ima ta najmanjši e in f - seznam je namreč urejen po velikosti.

def najblizji_par(s):
    s = sorted(s)
    naj_e = naj_f = None
    for e, f in zip(s, s[1:]):
        if naj_e is None or f - e < naj_f - naj_e:
            naj_e, naj_f = e, f
    return naj_e, naj_f

Kaj pa, če bi sestavili kar seznam razlik in v njem poiskali najmanjšo razliko? Da bomo iz nje lahko razbrali celotni par, pa dodamo v seznam še e. To bo poskrbelo tudi, da bomo, kadar bo več enakih razlik, vzeli tisto z najmanjšima elementoma.

def najblizji_par(s):
    s = sorted(s)
    razlike = [(f - e, e) for e, f in zip(s, s[1:])]
    min_raz, e = min(razlike)
    return e, e + min_raz

Če se želimo izogniti računanju, pa v seznam damo kar razliko, e in f. Poiščemo minimum in vrnemo le e in f.

def najblizji_par(s):
    s = sorted(s)
    razlike = [(f - e, e, f) for e, f in zip(s, s[1:])]
    return min(razlike)[1:]

In tako pridemo do

def najblizji_par(s):
    return min((f - e, e, f) for e, f in zip(sorted(s), sorted(s)[1:]))[1:]

Ta, zadnja rešitev, ni najbolj učinkovita, saj dvakrat uredi seznam. Vse te rešitve pa so (vsaj v teoriji) hitrejše od rešitev z dvema zankama. Pri rešitvi z dvema zankama čas izvajanja narašča s kvadratom dolžine seznama, pri tej, z urejanjem, pa je čas izvajanja sorazmeren n log(n), kjer je n dolžina seznama. Več o tem se boste učili pri algoritmih in podatkovnih strukturah.

Kakorkoli že sestavimo prvo funkcijo: druga funkcija je potem preprosta.

def pari(s):
    r = []
    while len(s) > 1:
        e, f = najblizji_par(s)
        r.append((e, f))
        s.remove(e)
        s.remove(f)
    return r

Dokler ima seznam več kot en element, pokličemo prejšnjo funkcijo, da izvemo najbližji par. Par dodamo v seznam, ki ga bomo vrnili kot rezultat, poleg tega pa tadva elementa pobrišemo iz seznama. Tule imamo primer, ko je potrebno, smiselno in varno uporabiti remove: indeksov elementov e in f ne poznamo, tako da del ne pride v poštev, poleg tega pa so vsi elementi seznama s različni, torej bo remove pobrisal "pravega". (Pa tudi, če bi se isti element lahko pojavil večkrat, bi nam bilo vseeno, katerega pobriše.)

Bomboni

Ana in Berta sta dobili oštevilčene škatlice. V vsaki je en bombon. Nato istočasno odpirata škatlice: vsaka odpre eno, vzame bombon (če je še tam) in jo zapre nazaj. Ker sta Ana in Berta še majhni, sproti pozabljata, katero škatlico sta že izpraznili. Če hkrati poskušata odpreti isto škatlico, vzame bombon mama. Da se ne kregata.

Recimo, da Ana odpira škatlice v takšnem vrstnem redu: [4, 1, 4, 7, 4, 3, 5, 6, 8, 5, 3, 2, 4, 6] in Berta v takšnem: [1, 3, 5, 4, 6, 1, 2]. Najprej dobita bombone iz škatlic 4 in 1. Nato nesrečna Ana odpre škatlo 1, kjer ni več bombona, Berta pa poje bombon iz škatle 3. Nato Ana odpre škatlico 4 (smola!) Berta poje bombon iz škatlice 5 ...

Ana je dobila bombone iz škatlic 4, 7 in 8, Berta pa bombone iz škatlic 1, 3, 5, 6 in 2. Seveda se lahko zgodi, da ena odpira škatlice dlje (npr. Ana, ki jih odpira še dolgo po tem, ko Berta že bruha).

Napiši funkcijo bomboni(s, t), ki prejme dva seznama, kot sta zgornja, in vrne par števil, ki pove, koliko bombonov je dobil kdo. V gornjem primeru vrne 3 in 5. Funkcija naj se izvede v doglednem času tudi, če je bombonov veliko.

Rešitev

Zapomniti si bo potrebno, katere škatlice so bile že odprte. Ta podatek bomo najpreprosteje in najhitreje shranjevali v množico.

Potem gremo lepo prek parov elementov v s in t (zip(s, t)) in štejemo bombone.

def bomboni(s, t):  # ne deluje za različno dolge sezname
    porabljeno = set()
    bombonov_s = bombonov_t = 0
    for e, f in zip(s, t):
        if e == f:
            porabljeno.add(e)
        if e not in porabljeno:
            bombonov_s += 1
            porabljeno.add(e)
        if f not in porabljeno:
            bombonov_t += 1
            porabljeno.add(f)
    return bombonov_s, bombonov_t

V prvem pogoju e == f, ne zmaga nihče, e (in z njim f, saj sta ista) je porabljen in ga v naslednjih if-ih ne dobi nihče.

Vendar funkcija ne deluje, če sta seznama različno dolga. zip(s, t) bo tekel le do dolžine krajšega seznama.

Predpostavimo, da je daljši seznam s. V tem primeru v zanki nismo odprli škatlic s[len(t):]. Koliko bombonov je v njih? Številke v repu seznama spremenimo v množico in odštejemo množico že porabljenih, set(s[len(t):]) - porabljeno. V vseh teh škatlicah bodo še bomboni -- in ker smo s[len(t):] spremenili v množico, bomo vsakega šteli le enkrat. Funkcijo torej popravimo tako, da v return-u prištejemo bombone iz repov seznamov.

def bomboni(s, t):
    porabljeno = set()
    bombonov_s = bombonov_t = 0
    for e, f in zip(s, t):
        if e == f:
            porabljeno.add(e)
        if e not in porabljeno:
            bombonov_s += 1
            porabljeno.add(e)
        if f not in porabljeno:
            bombonov_t += 1
            porabljeno.add(f)
    return (bombonov_s + len(set(s[len(t):]) - porabljeno),
            bombonov_t + len(set(t[len(s):]) - porabljeno))

Izmenična vsota

Napiši rekurzivno funkcijo izmenicna_vsota(s), ki vrne vrednost s[0] – s[1] + s[2] – s[3] + s[4] – s[5] + ...

Rešitev

Izmenično vsoto seznama s dobimo tako, da od prvega elementa odštejemo izmenično vsoto ostalih! Namreč, s[0] – s[1] + s[2] – s[3] + s[4] – s[5] + ... = s[0] – (s[1] - (s[2] – (s[3] - (s[4] – s[5] - (...))))).

def izmenicna_vsota(s):
    if not s:
        return 0
    return s[0] - izmenicna_vsota(s[1:])

Ali pa kar

def izmenicna_vsota(s):
    return len(s) and s[0] - izmenicna_vsota(s[1:])

Če se tega trika ne domislimo, pa jemljemo po dva elementa.

def izmenicna_vsota(s):
    if not s:
        return 0
    if len(s) == 1:
        return s[0]
    return s[0] - s[1] + izmenicna_vsota(s[2:])

Naloge

Napiši razred Naloge z naslednjimi metodami.

  • dodaj(ime_naloge, rok) zabeleži, da je potrebno do podanega roka opraviti nalogo s podanim imenom.
  • opravi(ime_naloge, cas) pokličemo, ko opravimo nalogo; pri tem podamo čas, ko smo jo opravili.
  • naslednja_naloga() vrne ime naloge z najzgodnejšim rokom ali None, če ni čakajočih nalog.
  • cakajocih() vrne število čakajočih nalog.
  • zamujenih() vrne število nalog, ki so bile opravljene po podanem roku.

Konstruktur dodaj po želji. Argumentov ne sme pričakovati. Prvi dve metodi naj ne vrneta ničesar. V kakšnih enotah je podan čas, te ne zanima. Nalog ne dodajamo in ne opravljamo nujno po vrsti.

Rešitev

Kot vedno se moramo tudi tu najprej odločiti, kako bo razred shranjeval podatke. dodaj bo znala dodajati kamorkoli. V opravi bo potrebno poiskati nalogo z določenim imenom, kar diši po slovarju, katerega ključi bodo imena nalog, vrednosti pa časi. Z naslednja_naloga pa bo problem: med podatkovnimi strukturami, ki smo jih spoznali, ni nobene, ki bi učinkovito sproti urejala. Število čakajočih bo preprosto ugotoviti ne glede na podatkovno strukturo. Zamujene pa bomo očitno šteli.

Se pravi: naloge bodo shranjene v slovarju, katerega ključi bodo imena, vrednosti pa roki. Takoj, ko je odločitev za nami, je ostanek trivialen.

class Naloge:
    def __init__(self):
        self.naloge = {}
        self._zamujenih = 0

    def dodaj(self, naloga, rok):
        self.naloge[naloga] = rok

    def opravi(self, naloga, cas):
        rok = self.naloge.pop(naloga)
        if rok < cas:
            self._zamujenih += 1

    def naslednja_naloga(self):
        if self.naloge:
            return min(self.naloge, key=self.naloge.get)

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

    def zamujenih(self):
        return self._zamujenih

V opravi smo se spomnili, da imajo slovarji metodo pop, ki ji podamo ključ in vrne pripadajočo vrednost, mimogrede pa ju še pobriše iz slovarja -- natančno to, kar potrebujemo tu.

V naslednja_naloga pa smo naredili en hec z min. Kdor ga ne razume (in mislim, da se ga tudi nismo učili), bo šel pač po malo daljši poti.

    def naslednja_naloge(self):
        naslednja = nasl_rok = None
        for naloga, rok in self.naloge.items():
            if naslednja is None or rok < nasl_rok:
                naslednja, nasl_rok = naloga, rok
        return naslednja