Najprej so tule rešitve vseh nalog - v neki ne-prezahtevni obliki. Razlaga in druge različice so spodaj.

# 1
def ne_na_lihih(s):
    return set(s) - set(s[1::2])


# 2
def intervali(s):
    res = []
    zac = 0
    while zac < len(s):
        kon = zac + 1
        while kon < len(s) and s[kon] == s[kon - 1] + 1:
            kon += 1
        res.append((s[zac], s[kon - 1]))
        zac = kon
    return res

def razpisi(intervali):
    res = []
    for a, b in intervali:
        res += range(a, b + 1)
    return res


# 3
def indeksi_rec(s,e):
    if not s:
        return []
    if s[-1] == e:
        return indeksi_rec(s[:-1], e) + [len(s)-1]
    else:
        return indeksi_rec(s[:-1], e)

def indeksi_gen(s, e):
    return [i for i, e1 in enumerate(s) if e1 == e]


# 4
import random
def predelaj(stavek, sopomenke):
    sopomenke1 = {}
    for so in sopomenke:
        for beseda in so:
            sopomenke1[beseda] = list(so - {beseda})

    novi_stavek = []
    for b in stavek.split():
        if b in sopomenke1:
            novi_stavek.append(random.choice(sopomenke1[b]))
        else:
            novi_stavek.append(b)
    return " ".join(novi_stavek)


#5
from collections import defaultdict
class PicerijaNaZalogo:
    zasluzki = {"margerita": 1, "klasika": 2, "zelenjavna": 1, "siri": 3}

    def __init__(self):
        self.peceno = defaultdict(int)
        self._zasluzek = 0

    def speci(self, vrsta):
        self.peceno[vrsta] += 1

    def prodaj(self, vrsta):
        if self.peceno[vrsta]:
            self.peceno[vrsta] -= 1
            self._zasluzek += self.zasluzki[vrsta]

    def zasluzek(self):
        return self._zasluzek

    def __str__(self):
        return ", ".join(sorted(set(v for v, k in self.peceno.items() if k)))

    def __len__(self):
        return sum(self.peceno.values())

1. Ne na lihih

Napiši funkcijo ne_na_lihih(s), ki prejme seznam, in vrne množico vseh elementov seznama, ki se nikoli ne pojavijo na lihih mestih (indeksih). Klic ne_na_lihih([12, 17, 17, 5, 3]) vrne {12, 3}. 5 je izpuščena, ker se pojavi samo na lihem mestu, 17 pa se sicer na sodem, vendar tudi na lihem.

Namig: malo razmisli, preden se zaprogramiraš. Naloga je v resnici trivialna.

Rešitev

Iščemo množico vseh elementov (set(s)), razen tistih, ki so na lihih mestih (s[1::2]), torej

def ne_na_lihih(s):
    return set(s) - set(s[1::2])

Nalogo se da seveda rešiti tudi na bolj zapletene načine. Na tega sta jo rešila le dva ali trije.

2. Intervali

Napiši funkcijo intervali(s), ki prejme seznam števil in vrne seznam parov, ki predstavljajo začetke in konce intervalov naraščajočih zaporednih števil v tem seznamu. Tako mora klic intervali([4, 5, 6, 7, 15, 21, 22, 23]) vrniti seznam [(4, 7), (15, 15), (21, 23)].

Napiši še funkcijo razpisi(ints), ki dela ravno obratno – prejme, recimo [(4, 7), (15, 15), (21, 23)] in vrne [4, 5, 6, 7, 15, 21, 22, 23].

Rešitev

Ta naloga se je (po pričakovanjih) izkazala za najtežjo. (Razen rekurzije, ki v resnici ni težka, samo študenti se je bojijo.) Naloge, kakršne je, recimo, prva, bi bile v večini jezikov enako zoprna kot je ta, druga. V Pythonu je prva trivialna, ker imamo množice, rezine ... Tule pa nam ne ponudi kake preproste bližnjice.

Nalogo so le redki rešili popolnoma pravilno, zato pa so dobili točke tudi tisti, ki so šli po pravi poti. Ena je ta:

def intervali(s):
    res = []
    zac = 0
    while zac < len(s):
        kon = zac + 1
        while kon < len(s) and s[kon] == s[kon - 1] + 1:
            kon += 1
        res.append((s[zac], s[kon - 1]))
        zac = kon
    return res

Gremo po seznamu; zac bo začetek zaporedja elementov. Pri vsakem začetku poiščemo, z notranjo zanko, ustrezan konec; kon bo indeks elementa za zadnjim elementom zaporedja. Ko poznamo začetek in konec, dodamo v seznam, ki ga bomo vrnili par (s[zac], s[kon - 1]). Novi začetek bo, kjer je konec tega.

Notranja zanka teče, dokler še nismo na koncu seznama in je naslednji element za 1 večji od prejšnjega. Zunanja teče do takrat, ko bi bil začetek izven seznama.

Primer precej podobne rešitve, ki jo je napisal eden od študentov, je

def intervali(s):
    if not s:
        return []
    prev, start = s[0], s[0]
    out = []
    for x in s[1:]:
        if x - prev != 1:
            out.append((start, prev))
            start = x
        prev = x
    out.append((start, prev))
    return out

Rešitev, ki je bolj v mojem slogu, uporablja zip - ker pač vedno, kadar primerjam sosednje elemente, pomislim na zip. Vendar je gornja pravzaprav lepša. No, takole gre z zipom:

def intervali(s):
    if not s:
        return []
    ints = []
    f = s[0]
    for e1, e2 in zip(s, s[1:]):
        if e2 != e1 + 1:
            ints.append((f, e1))
            f = e2
    ints.append((f, e2))
    return ints

f je prva vrednost zaporedja, e1 zadnja in e2 prva vrednost naslednjega zaporedja. Spremenljivki e1, e2 gresta prek zaporednih parov, dokler ne pridemo do mesta, ko se ne razlikujeta za 1. Takrat shranimo meje trenutnega zaporedja ((f, e1)) in začnemo novo, f = e2. Kar zoprna reč.

Tule je še ena inovativnejša rešitev.

def intervali(s):
    if not s:
        return []
    meje = [(e, f) for e, f in zip(s, s[1:]) if f != e + 1]
    return [(e[1], f[0]) for e, f in zip([(None, s[0])] + meje, meje + [(s[-1], None)])]

Najprej poiščemo meje. Za seznam intervali([4, 5, 6, 7, 15, 16, 17, 1, 2, 3]) bi bile meje [(7, 15), (17, 1)]. To reč pozipamo tako, da enkrat dodamo spredaj [(None, s[0])], drugič dodamo zadaj [(s[-1], None)]. Tako dobimo grozljivi [((None, 4), (7, 15)), ((7, 15), (17, 1)), ((17, 1), (3, None))]. Z zanko for se zapeljemo čez te terke terk in poberemo prvi element prve podterke in ničti element druge, pa dobimo [(4, 7), (15, 17), (1, 3)]

Tole bi se dalo razvleči še na kakšen elegantnejši način, a pustimo.

Obstaja še veliko rešitev tega problema; kdor se želi poglobiti v Python, se lahko pozabava z njimi. Recimo s takšno.

from itertools import groupby
def intervali(s):
    res = []
    for _, g in groupby(((x, y) for x, y in enumerate(s)), key=lambda x: x[1] - x[0]):
        first = next(g)[1]
        res.append((first, first + len(list(g))))
    return res

Drugi del, razpisi je preprost.

def razpisi(intervali):
    res = []
    for a, b in intervali:
        res += range(a, b + 1)
    return res

3. Indeksi

Napiši rekurzivno funkcijo indeksi_rec(s, e), ki prejme seznam in vrednost ter vrne seznam indeksov, na katerih se pojavi ta vrednost. indeksi_rec([6, 2, 4, 6, 6, 3], 6) vrne [0, 3, 4].

Napiši tudi (nerekurzivno) funkcijo indeksi_gen(s, e), ki izračuna enak rezultat, vendar z izpeljanim seznamom. Vsa funkcija je torej le en sam return.

Rešitev

Zahteva, da mora biti funkcija rekurzivna oziroma biti narejena z izpeljanim seznamom, je mišljena resno. Rešitev, kot je,

def indeksi_rec(s, e):
    res = []
    for i, e1 in enumerate(s):
        if e1 == e:
            res.append(i)
    return res

ni rekurzivna, predvsem pa je trivialna. To sodi v oktober, ne januar. Spomnite se predavanja "ne me zezat", kjer smo take funkcije že kar "mehanično" preobračali v

def indeksi_gen(s, e):
    return [i for i, e1 in enumerate(s) if e1 == e]

No, to je pravzaprav rešitev drugega dela.

Rekurzivna pa je takšna:

def indeksi_rec(s,e):
    if not s:
        return []
    if s[-1] == e:
        return indeksi_rec(s[:-1], e) + [len(s)-1]
    else:
        return indeksi_rec(s[:-1], e)

Če je seznam prazen, vrnemo prazen seznam indeksov. Sicer pogledamo zadnji(!) element. Če je enak iskanemu, bomo vrnili indekse tega elementa v vsem seznamu brez tega, zadnjega elementa, in še ta element zraven. Sicer pa vrnemo pač le indekse elementov v vseh elementih razen zadnjega.

Če gre komu na živce, da dvakrat ponavljamo indeksi_rec(s[:-1], e), ga lahko potolažimo s skrajšano različico (ki je ne bomo komentirali: kogar zanimajo takšne perverznosti, naj sam uživa v raziskovanju):

def indeksi_rec(s, e):
    return s and (indeksi_rec(s[:-1], e) + [len(s) - 1] * (e == s[-1]))

Priznati moram, da se branja od zadaj nisem spomnil sam: tako je reševal eden od študentov (ki se je potem sicer žal malo zaplezal, a sem mu vseeno dal skoraj vse točke). Razlog je v tem, da rekurzijo po seznamih skoraj vedno delamo od leve proti desni in ne obratno; razloge za to boste spoznali ob funkcijskih jezikih na drugi stopnji študija, če se boste vpisali nanjo. Moja rešitev je bila zato bolj zapletena:

def indeksi_rec(s, e):
    if not s:
        return []
    ost = [x + 1 for x in indeksi_rec(s[1:], e)]
    if s[0] == e:
        return [0] + ost
    else:
        return ost

Stvar je podobna kot z zadnjim elementom, le da gre v rekurzivni klic seznam brez prvega elementa - zato so vsi indeksi, ki jih vrne, za 1 premajhni.

Tudi mojo rešitev se da obrniki v eno vrstico, vendar - gornja je lepša.

def indeksi_rec(s, e):
    return s and [0] * (s[0] == e) + [x + 1 for x in indeksi_rec(s[1:], e)]

4. Sopomenke

Sopomenke lahko predstavimo z množico besed, kot, recimo {"fant", "deček", "pob"}. Takšne množice lahko zberemo v seznam, recimo [{"fant", "deček", "pob"}, {"cesta", "pot", "kolovoz", "makadam"}, {"kis", "jesih"}].

Napišite funkcijo predelaj(stavek1, sopomenke), ki dobi stavek in sopomenke, ter vrne stavek, v katerem so vse besede, ki imajo sopomenke, zamenjane z naključno izbrano sopomenko. Tako lahko predelaj("fant in dekle sta vzela pot pod noge", [{"fant", "deček", "pob"}, {"cesta", "pot", "kolovoz", "makadam"}, {"kis", "jesih"}, {"noge", "tace"}, {"dekle", "punca", "frajla"}])

vrne, recimo "pob in punca sta vzela kolovoz pod tace".

Rešitev

Strategija je preprosta: split, zamenjave, join. Bistvo naloge so hotele biti zamenjave - vendar ste se mnogi izgubili v tehnikalijah. Kdor ni vedel za split, je izpadel v prvem krogu. Kdor je pozabil na join se je mučil s sestavljanjem stavka.

Pravzaprav sem upal, da se bo kdo spomnil na tole: če iščemo sopomenke za neko besedo, bi bilo dobro imeti slovar sopomenk za vse besede. Dobimo ga tako

sopomenke1 = {}
for i, so in enumerate(sopomenke):
    for beseda in so:
        sopomenke1[beseda] = list(so - {beseda})

Sestavili bomo torej slovar sopomenke1, katerega ključi so besede, pripadajoče vrednosti pa seznami sopomenk te besede (brez te besede same). Gremo torej čez seznam terk s sopomenkami. Za vsako množico besed gremo čez te besede in v slovar dodamo seznam besed iz te množice - brez te besede.

Zdaj, ko smo to obdelali, spišimo celo funkcijo:

import random
def predelaj(stavek, sopomenke):
    sopomenke1 = {}
    for so in sopomenke:
        for beseda in so:
            sopomenke1[beseda] = list(so - {beseda})

    novi_stavek = []
    for b in stavek.split():
        if b in sopomenke1:
            novi_stavek.append(random.choice(sopomenke1[b]))
        else:
            novi_stavek.append(b)
    return " ".join(novi_stavek)

V drugem delu razkopljemo stavek na besede. Za vsako preverimo, ali je v slovarju sopomenk in v tem primeru v novi_stavek (ki je v resnici seznam besed, ki bodo v novem stavku), dodamo naključno izbrano sopomenko. Če beseda nima sopomenk, dodamo kar to besedo.

Na koncu te besede zlepimo v nov stavek. Večino drugega dela,

        if b in sopomenke1:
            novi_stavek.append(random.choice(sopomenke1[b]))
        else:
            novi_stavek.append(b)

lahko skrajšamo, če se spomnimo na get:

        novi_stavek.append(random.choice(sopomenke1.get(b, [b])))

Tale sopomenke1.get(b, [b]) bo v primeru, da slovar nima sopomenk, vrnil seznam [b], torej seznam, ki vsebuje originalno besedo. random.choice potem ne bo imel veliko izbire, saj bo vrnil kar originalno besedo. Tako dobimo

import random
def predelaj(stavek, sopomenke):
    sopomenke1 = {}
    for so in sopomenke:
        for beseda in so:
            sopomenke1[beseda] = list(so - {beseda})
    novi_stavek = []
    for b in stavek.split():
        novi_stavek.append(random.choice(sopomenke1.get(b, [b])))
    return " ".join(novi_stavek)

Če se nočemo zafrkavati s po nepotrebnem predolgimi funkcijami, pa napišemo kar

import random
def predelaj(stavek, sopomenke):
    sopomenke1 = {beseda: list(so - {beseda}) for so in sopomenke for beseda in so}
    return " ".join(random.choice(sopomenke1.get(b, [b])) for b in stavek.split())

5. Picerija

V neki piceriji pek peče pice na zalogo. Napišite razred PicerijaNaZalogo z metodami

  • speci(vrsta), ki je namenjena temu, da jo kličemo, ko pek speče pico podane vrste (vrsta bo vedno "margerita", "klasika", "zelenjavna", ali "siri"). Metoda mora nekako zabeležiti, da je zdaj na voljo ena pica te vrste več.

  • prodaj(vrsta) pokličemo, ko prodamo pico podane vrste, torej imamo zdaj eno manj. Če pice te vrste ni na zalogi, funkcija ne naredi ničesar.

  • zasluzek() vrne dosedanji zaslužek; z margerito zasluži en evro, s klasiko dva, z zelenjavo enega in s siri tri.

    Poleg tega poskrbite za izpis in dolžino. Če je p neka picerija, naj

  • len(p) vrne število trenutno pečenih pic,

  • print(p) izpiše seznam vseh vrst pic, ki so trenutno pečene, urejen po abecednem redu, ločene z vejicami (glej primer v testih). Tudi če je neke pice več, naj jo izpiše le enkrat.

Rešitev

Nalogo ste pretežno reševali lepo, le, da je potrebno za len(p) in print(p) definirati __len__ in __str__ se mnogi niste spomnili. No, pa lepše je, če količino pizz shranjujemo v slovarju, saj se tako rešimo gore if-ov. Sicer pa ima letošnja generacija z razredi veliko manj težav kot prejšnje. Pohvalno.

from collections import defaultdict
class PicerijaNaZalogo:
    zasluzki = {"margerita": 1, "klasika": 2, "zelenjavna": 1, "siri": 3}

    def __init__(self):
        self.peceno = defaultdict(int)
        self._zasluzek = 0

    def speci(self, vrsta):
        self.peceno[vrsta] += 1

    def prodaj(self, vrsta):
        if self.peceno[vrsta]:
            self.peceno[vrsta] -= 1
            self._zasluzek += self.zasluzki[vrsta]

    def zasluzek(self):
        return self._zasluzek

    def __str__(self):
        return ", ".join(sorted(set(v for v, k in self.peceno.items() if k)))

    def __len__(self):
        return sum(self.peceno.values())

Hitre rešitve

Ker vas je kar nekaj, ki jih zanimajo takšne reči, so tu zbrane še hitre rešitve vseh nalog (razen zadnje, kjer nimamo kaj).

# 1
def ne_na_lihih(s):
    return set(s) - set(s[1::2])

# 2
def intervali(s):
    if not s:
        return []
    meje = [(e, f) for e, f in zip(s, s[1:]) if f != e + 1]
    return [(e[1], f[0]) for e, f in zip([(None, s[0])] + meje, meje + [(s[-1], None)])]

from functools import reduce
def razpisi(intervali):
    return reduce(list.__add__, (list(range(a, b + 1)) for a, b in intervali), [])

# 3
def indeksi_rec(s, e):
    return s and (indeksi_rec(s[:-1], e) + [len(s) - 1] * (e == s[-1]))

def indeksi_gen(s, e):
    return [i for i, e1 in enumerate(s) if e1 == e]

# 4
import random
def predelaj(stavek, sopomenke):
    sopomenke1 = {beseda: list(so - {beseda}) for so in sopomenke for beseda in so}
    return " ".join(random.choice(sopomenke1.get(b, [b])) for b in stavek.split())
Last modified: Friday, 29 January 2016, 10:52 PM