Slovarji

Teža tovora

Mama Metka in ata Jože se selita. Naročila sta ljudi s selitvenega servisa, ki bodo njuno pohištvo s tovornjakom preselili na novo lokacijo. Podatke o tem, kakšen tovor bodo naložili na tovornjak in kolikšna je masa posameznih kosov tovora, si bodo tovornjakarji beležili v slovarju.

Na primer, slovar

  selitveni_tovor = {'televizor' : 17, 'postelja' : 100, 'miza' : 35, 'zofa': 40, 'omara': 17}

pove, da bodo na tovornjak naložili 17 kg težak televizor, 100 kg težko posteljo, 35 kg težko mizo, 40 kg težko zofo in 17 kg težko omaro.

1. podnaloga

Sestavite funkcijo teza_tovora(tovor), ki sprejme tak slovar in vrne skupno težo tovora. Zgled:

>>> teza_tovora(selitveni_tovor)
209

Uradna rešitev

def teza_tovora(tovor):
    """Koliko je skupna teža tovora, podanega v slovarju tovor?"""
    skupaj = 0
    for teza in tovor.values():
        skupaj += teza
    return skupaj

2. podnaloga

Sestavite funkcijo lahko_pelje(tovor, nosilnost), ki ugotovi, ali tovornjak z nosilnostjo nosilnost lahko pelje tovor, dan s slovarjem tovor. Zgled:

>>> lahko_pelje(selitveni_tovor, 333)
True

>>> lahko_pelje(selitveni_tovor, 208)
False

Uradna rešitev

def lahko_pelje(tovor, nosilnost):
    """Ali tovornjak z nosilnostjo nosilnost lahko pelje tovor, dan s slovarjem tovor?"""
    return teza_tovora(tovor) <= nosilnost

def lahko_pelje_V2(tovor, nosilnost):
    """Ali tovornjak z nosilnostjo nosilnost lahko pelje tovor, dan s slovarjem tovor?"""
    # izračunajmo težo tovora
    skupaj = 0
    for teza in tovor.values():
        skupaj += teza
    # in preverimo, če gre
    return skupaj <= nosilnost

3. podnaloga

Sestavite funkcijo enaka_tovora(tovor1, tovor2), ki ugotovi, če sta tovora, podana v slovarjih tovor1 in tovor2 enaka! Tovora sta enaka, če vsebujeta iste predmete z isto težo. Zgled:

tovor1 = {'zibelka': 15, 'namizna lučka': 2, 'kuhinjska posoda': 14}
tovor2 = {'kuhinjska posoda': 13, 'zibelka': 15, 'namizna lučka': 2}
tovor3 = {'kuhinjska posoda': 14, 'namizna lučka': 2, 'zibelka': 15}

>>> enaka_tovora(tovor1, tovor3)
True

>>> enaka_tovora(tovor1, tovor2)
False

Uradna rešitev

def enaka_tovora(tovor1, tovor2):
    """Ali sta tovora, podana v slovarjih tovor1 in tovor2 enaka?"""
    # ali imata slovarja enako ključev (enako dolžino)
    if len(tovor1) != len(tovor2):
        return False
    # sedaj je dovolj, če preverimo, če so vsi ključi enega slovarja v drugem
    # in dajo isto vrednost
    for predmet, teza in tovor1.items():
        # je predmet tudi v drugem slovarju
        if not predmet in tovor2:
            return False
        # sta teži v obeh slovarjih enaki
        if teza != tovor2[predmet]:
            return False
    # vsi testi so OK
    return True

def enaka_tovora_V2(tovor1, tovor2):
    """Ali sta tovora, podana v slovarjih tovor1 in tovor2 enaka?"""
    # lahko pa enostavno upoštevamo, da v objektu, ki ga vrne metoda items()
    # vrstni red ni pomemben, torej bosta slovarja enaka, če
    # bosta imela enaka items()
    return tovor1.items() == tovor2.items()

4. podnaloga

Sestavite funkcijo smiselen_tovor(tovor, minTeža, maxTeža), ki "prečisti" slovar z danimi težami tako, da vrne slovar, v katerem so le tisti predmeti, katerih teža je med minTeža in maxTeža. Zgled:

>>> smiselen_tovor(selitveni_tovor, 18, 100)
{'postelja' : 100, 'miza' : 35, 'zofa': 40}

>>> smiselen_tovor(selitveni_tovor, 41, 80)
{}

Uradna rešitev

def smiselen_tovor(tovor, minTeža, maxTeža):
    """Vrne slovar, v katerem so le tisti predmeti,
       katerih teža je med minTeža in maxTeža."""
    noviTovor = dict()
    # pregledamo celoten tovor in v nov slovar dodamo predmete
    # z ustrezno težo
    for predmet, teža in tovor.items():
        if minTeža <= teža <= maxTeža:
            noviTovor[predmet] = teža
    return noviTovor

def smiselen_tovor_V2(tovor, minTeza, maxTeza):
    """Vrne slovar, v katerem so le tisti predmeti,
       katerih teža je med minTeža in maxTeža."""
    return {k:v for k, v in tovor.items() if minTeza<=v<=maxTeza}

5. podnaloga

Sestavite funkcijo najkrajsi_opis(tovor), ki vrne po abecedi urejeno tabelo tistih predmetov, ki imajo najkrajši opis. Zgled:

>>> najkrajsi_opis(selitveni_tovor)
['miza', 'zofa']

>>> najkrajsi_opis(dict())
[]

Uradna rešitev

def najkrajsi_opis(tovor):
    """Vrne po abecedi urejeno tabelo tistih predmetov, ki imajo najkrajši opis."""
    #če je slovar prazen vrnemo prazen seznam
    if len(tovor)==0: return []

    # pogledamo koliko znakov sestavlja opis tistega predmeta, ki ima najkrajši opis
    najkrajsi = min([len(i) for i in tovor.keys()])

    # v slovarju tovor obdržimo le tiste predmete, ki imajo toliko znakov, kot predmet
    # z najkrajšim opisom
    ostanejo = [i for i in tovor if len(i) == najkrajsi]

    # dobljeni seznam sortiramo
    ostanejo_sortirani = sorted(ostanejo)
    return ostanejo_sortirani

def najkrajsi_opis_V2(tovor):
    """Vrne po abecedi urejeno tabelo tistih predmetov, ki imajo najkrajši opis."""
    if len(tovor)==0: return []
    return sorted([i for i in tovor if len(i)==min([len(i) for i in tovor.keys()])])

6. podnaloga

Sestavite funkcijo najlazji_predmet(tovor), ki vrne po abecedi urejeno tabelo tistih predmetov, ki so najlažji. Zgled:

>>> najlazji_predmet(selitveni_tovor)
['omara', 'televizor']

>>> najlazji_predmet(dict())
[]

Uradna rešitev

def najlazji_predmet(tovor):
    """Vrne po abecedi urejeno tabelo tistih predmetov, ki so najlažji."""
    if not tovor: # če je slovar prazen, vrnemo prazno tabelo
        return list()
    # kandidat za najlažjega naj bo za 1 večja teža kot je prvi iz slovarja
    for predmet, teza in tovor.items():
        najlazji = teza + 1
        tab_najlazjih = ['karkoli'] # tega na koncu tako ali tako ne bo!
        break # po prvem prehodu takoj zapustimo zanko
    # sedaj pa pregledujemo 'zares'
    for predmet, teza in tovor.items():
        # je predmet lažji?
        if teza < najlazji : # nov kandidat za najlažjega
            tab_najlazjih = [predmet]
            najlazji = teza
        elif teza == najlazji : # dodamo
            tab_najlazjih.append(predmet)
    return sorted(tab_najlazjih)

def najlazji_predmet_V2(tovor):
    """Vrne po abecedi urejeno tabelo tistih predmetov, ki so najlažji."""
    if len(tovor)==0: return []
    return sorted([i for i in tovor if tovor[i]==min(tovor.values())])

Kuhamo in pečemo

1. podnaloga

Babica Metka za nedeljski obisk s sorodniki pripravlja jabolčno pito. Ker je malce prepozno izvedela, da bodo poleg njenih sorodnikov prišli tudi nekateri družinski prijatelji, si je za recept pripravila premalo sestavin. Pomagajte ji recept popraviti, tako da sestavite funkcijo pomnozi(recept, faktor), ki sestavi in vrne nov recept. Ta naj vsebuje iste sestavine kot prvotni recept, le da so vse količine v njem pomnožene z danim faktorjem.

>>> pomnozi({'moka': 300, 'sladkor': 120, 'maslo': 100, 'rumenjak': 2, 'jabolka': 5}, 2)
{'moka': 600, 'sladkor': 240, 'maslo': 200, 'rumenjak': 4, 'jabolka': 10}

Uradna rešitev

def pomnozi(recept, faktor):
    """Vrne nov recept, spremenjen za faktor."""
    novR = dict()
    for sestavina, kolicina in recept.items():
        novR[sestavina] = kolicina * faktor
    return novR

def pomnoziV2(recept, faktor):
    """Vrne nov recept, spremenjen za faktor."""
    # uporabimo izpeljane slovarje (dict comprehension)
    return {sestavina: kolicina * faktor for sestavina, kolicina in recept.items()}

2. podnaloga

Sestavite funkcijo imamo_sestavine(recept, shramba), ki preveri, ali ima Metka v shrambi dovolj sestavin, da pripravi dani recept. Sestavine, ki jih ima v shrambi, so predstavljene s slovarjem na enak način kot sestavine v receptu.

>>> imamo_sestavine({'jajca': 3, 'moka': 500}, {'moka': 600})
False

Uradna rešitev

def imamo_sestavine(recept, shramba):
    """Imamo v shrambi dovolj sestavin za dani recept?"""
    for sestavina, kolicina in recept.items():
        if shramba.get(sestavina, -1) < kolicina: # uporaba get, da ne dobimo izjeme pri neobstoječih sestavinah
            return False # že če ena manjka, ne gre
    return True # vsega imamo dovolj!

3. podnaloga

Sestavite funkcijo potrebno_kupiti(recept, shramba), ki vrne slovar sestavin s pripadajočimi količinami, ki jih mora Metka še kupiti, da bo lahko pripravila jed po danem receptu.

>>> potrebno_kupiti({'jajca': 3, 'moka': 500}, {'moka': 450, 'sladkor': 1000})
{'jajca': 3, 'moka': 50}

Uradna rešitev

def potrebno_kupiti(recept, shramba):
    """vrne slovar sestavin s pripadajočimi količinami, ki jih moramo še dokupiti,
       da bomo lahko skuhali jed po danem receptu."""
    kupiti = dict()
    for sestavina, kolicina in recept.items():
        razlika = kolicina - shramba.get(sestavina, 0) # če sestavine še nimamo, je enako, kot če jo imamo 0!
        if razlika > 0:
            kupiti[sestavina] = razlika
    return kupiti

Šifriranje

Babica Metka in njen vnuk Boštjan sta si izmislila nadvse zanimivo igrico. Odločila sta se, da si bosta pošiljala skrivna sporočilca zakodirana s substitucijsko šifro.

Substitucijska šifra je enostaven način šifriranja, pri katerem vsako črko iz dane abecede zamenjamo z neko drugo črko. Tako šifro predstavimo s slovarjem, ki ima za ključe vse črke iz abecede, pripadajoče vrednosti pa so črke, s katerimi jih zašifriramo.

Tako slovar {'A': 'B', 'C': 'C', 'B': 'D', 'D': 'A'} pove, da se 'A' zašifrira v 'B', 'B' v 'D', 'D' v 'A', 'C' pa se ne spremeni.

1. podnaloga

Sestavite funkcijo sifriraj(sifra, beseda), ki vrne besedo, zašifrirano z dano šifro. Predpostavite lahko, da vse črke v besedi nastopajo v šifri. Zgled:

>>> sifriraj(nasa_sifra, "IGRICA")
'BPLBZO'

Uradna rešitev

def sifriraj(sifra, beseda):
    """S slovarjem sifra zasifriramo besedo. Vrnemo niz, ki
       predstavlja ustrezno zašifrirano besedo."""
    tabZasifCrk = list()
    for crka in beseda: # zašifriramo posamezno črko
        tabZasifCrk.append(sifra[crka])
    return ''.join(tabZasifCrk) # vrnemo kot niz

2. podnaloga

Sestavite funkcijo je_sifra(slovar), ki ugotovi, ali slovar predstavlja šifro, torej ali je bijekcija črk na neki abecedi. Zgled:

>>> je_sifra(nasa_sifra)
True

Namig: pri bijektivni preslikavi je poljuben element iz množice B slika točno enega elementa množice A.

Uradna rešitev

def je_sifra(slovar):
    """Ali slovar predstavlja šifro?"""
    # Pogledamo, če je množica ključev slovarja enaka množici vrednosti.
    # Ker so ključi v slovarju enolični, je velikost množice ključev enaka
    # kar številu črk v abecedi. Če sta torej množici ključev in vrednosti
    # enaki, je slovar surjektiven in s tem tudi injektiven.
    return set(slovar.keys()) == set(slovar.values())

3. podnaloga

Sestavite funkcijo inverz(sifra), ki vrne inverz dane šifre, če ta obstaja. V nasprotnem primeru funkcija vrne None. Zgled:

>>> inverz({'A': 'D', 'B': 'A', 'D': 'J', 'J': 'B'})
{'A': 'B', 'B': 'J', 'J': 'D', 'D': 'A'}

Namig: inverz obstaja samo kadar je slovar, ki predstavlja šifro, bijekcija črk na neki abecedi.

Uradna rešitev

def inverz(sifra):
    """Vrne slovar, ki predstavlja obratno šifro, oziroma None, če ne gre."""
    if not je_sifra(sifra):
        return None
    inv = dict()
    for k, v in sifra.items():
        inv[v]=k
    return inv

4. podnaloga

Sestavite funkcijo odsifriraj(sifra, beseda), ki sprejme šifro in zašifrirano besedilo, vrne pa odšifrirano besedilo. Če slovar ni bijekcija (in se torej besedilo ne da nujno odšifrirati), naj funkcija vrne None. Zgled:

>>> odsifriraj(nasa_sifra, 'BPLBZO')
'IGRICA'

Uradna rešitev

def odsifriraj(sifra, beseda):
    """Vrne odšifrirano besedo, ki je bila šifrirana s šifro v slovarju sifra."""
    inv = inverz(sifra)
    if inv: # če inverz ne obstraja, dobimo None, kar se tolmači kot False
        return sifriraj(inv, beseda)
    else:
        return None # če inverza ni, ne moremo dešifrirati!

Permutacije

Babica Metka bi rada svojemu vnuku Boštjanu zelo rada pomagala do boljše ocene pri matematiki. Ker trenutno pri pouku obravnavajo permutacije, o katerih sama ne ve prav dosti, ji priskočite na pomoč.

Permutacijo naravnih števil od $1$ do $n$ lahko predstavimo s slovarjem. Na primer permutacijo, ki slika $1$ v $3$, $3$ v $1$, število $2$ pa pusti pri miru, predstavimo s slovarjem {1: 3, 2: 2, 3: 1}.

1. podnaloga

Sestavite funkcijo slika(permutacija, x), ki kot argumenta dobi slovar permutacija, ki predstavlja permutacijo, in število x. Funkcija naj vrne sliko števila x s podano permutacijo. Zgled:

>>> slika({1: 3, 2: 4, 3: 2, 4: 1}, 4)
1

Uradna rešitev

def slika(permutacija, x):
    """Vrne sliko števila s podano permutacijo."""
    return permutacija[x]

2. podnaloga

Sestavite funkcijo slike(permutacija, x, n), ki vrne zaporedje slik, ki ga dobimo, če začnemo s številom x in na njem n-krat uporabimo permutacijo permutacija. Zgled:

>>> slike({1: 3, 2: 4, 3: 2, 4: 1}, 1, 2)
[1, 3, 2]

Uradna rešitev

def slike(permutacija, x, n):
    """Vrne seznam slik, ki ga dobimo, če začnemo s številom x in
       na njem n-krat uporabimo permutacijo."""
    r = []
    for i in range(n + 1):
        r.append(x)
        x = permutacija[x]
    return r

def slike_rekurzivno(permutacija, x, n):
    """Vrne seznam slik, ki ga dobimo, če začnemo s številom x in
       na njem n-krat uporabimo permutacijo."""
    # Funkcijo definiramo rekurzivno. Če je n > 0, naredimo sliko y, nato
    # pa dodamo še seznam n - 1 slik elementa y.
    if n == 0:
        return [x]
    else:
        y = permutacija[x]
        ostale = slike_rekurzivno(permutacija, y, n - 1)
        return [x] + ostale

3. podnaloga

Sestavite funkcijo cikel(permutacija, x), ki vrne celoten cikel, ki se začne s številom x. Zgled:

>>> cikel({1: 3, 2: 2, 3: 1}, 1)
[1, 3]
>>> cikel({1: 3, 2: 2, 3: 1}, 2)
[2]

Uradna rešitev

def cikel(permutacija, x):
    """Vrne seznam, ki predstavlja cikel, ki ga dobimo, če začnemo s številom x
       in na njem tolikokrat uporabimo permutacijo, da zopet pridemo do števila
       x."""
    # Dokler slika zadnjega elementa, ki smo ga dodali v cikel, ni enaka
    # začetnemu elementu y, dodamo sliko ter ponavljamo.
    cikel = [x]
    y = permutacija[x]
    while y != x:
        cikel.append(y)
        y = permutacija[y]
    return cikel

4. podnaloga

Sestavite funkcijo cikli(permutacija), ki vrne seznam disjunktnih ciklov dane permutacije. Vsak cikel naj se začne z najmanjšim številom v ciklu, cikli pa naj bodo urejeni po začetnem številu. Zgled:

>>> cikli({1: 3, 2: 2, 3: 1})
[[1, 3], [2]]

Uradna rešitev

def cikli(permutacija):
    """Vrne seznam disjunktnih ciklov dane permutacije.
       Vsak cikel se začne z najmanjšim številom v ciklu, cikli pa so urejeni po
       začetnem številu."""
    # V seznam cikli si shranjujemo do sedaj izračunane cikle, v množico
    # ugotovljena pa vsa tista števila, za katera smo že ugotovili, kateremu
    # ciklu pripadajo.
    cikli = []
    ugotovljena = set()
    # Nato gremo zaporedoma čez vsa števila od 1 do n. Če za neko število
    # še nismo ugotovili, kam spada, je najmanjše v svojem ciklu. Zato
    # izračunamo njegov cikel, ga dodamo k ciklom, vsa števila iz cikla pa
    # dodamo med ugotovljena.
    for i in range(1, len(permutacija) + 1):
        if i not in ugotovljena:
            c = cikel(permutacija, i)
            cikli.append(c)
            ugotovljena.update(c)
    return cikli

5. podnaloga

Sestavite funkcijo je_permutacija(slovar), ki vrne True, če dan slovar predstavlja permutacijo, in False sicer. Zgled:

>>> je_permutacija({1: 3, 2: 5, 5: 1})
False

Uradna rešitev

def je_permutacija(slovar):
    """Vrne True, če dan slovar predstavlja permutacijo, in False sicer."""
    # Za vsa števila od 1 do n bomo pogledali, če nastopajo tako v domeni
    # kot v sliki permutacije. Imeli bomo seznam je_v_domeni, ki ima na
    # mestu i - 1 zapisano, če smo ugotovili, da i je v domeni permutacije.
    # Podobno storimo za sliko.
    n = len(slovar)
    je_v_domeni = [False for i in range(n)]
    je_v_sliki = [False for i in range(n)]

    # Nato gremo čez vse ključe k in pripadajoče vrednosti v v slovarju.
    # Če sta tako k kot v med 1 in n, označimo, da sta v domeni in sliki,
    # sicer pa vemo, da slovar ne predstavlja permutacije.
    for k, v in slovar.items():
        if 1 <= k <= n and 1 <= v <= n:
            je_v_domeni[k - 1] = True
            je_v_sliki[v - 1] = True
        else:
            return False

    # Na koncu pogledamo, ali so v domeni in sliki nastopala vsa števila.
    # Funkcija all vrne True natanko takrat, ko so vsi elementi v seznamu
    # enaki True.
    return all(je_v_domeni) and all(je_v_sliki)

Usmerjeni grafi

Kadar nas zanima, kam se lahko iz danega kraja odpravimo, lahko odpremo zemljevid in pogledamo, v katere kraje nas iz danega kraja vodijo ceste. Recimo iz Celja se lahko odpravimo proti Velenju, Laškem ali Rogaški Slatini, iz Logatca se lahko odpravimo proti Idriji, Postojni in Vrhniki, iz Vrhinike se lahko odpravimo nazaj proti Logatcu ali proti Ljubljani.

Tak zemljevid lahko predstavimo tudi z usmerjenim grafom. Usmerjen graf $G$ sestavljata množica vozlišč $V(G)$ in množica usmerjenih povezav $A(G)$. Vsaki usmerjeni povezavi pripada vozlišče, ki ga imenujemo začetek povezave, in vozlišče, ki ga imenujemo konec povezave.

Običajno si vozlišča predstavljamo kot točke v ravnini, povezave pa kot puščice med njimi. Puščica je usmerjena od začetnega proti končnemu vozlišču.

Usmerjene grafe lahko predstavimo na več načinov. Lahko ga podamo kot množico vozlišč in seznam parov usmerjenih povezav:

V = {'Logatec', 'Vrhnika', 'Ljubljana', 'Postojna', 'Idrija'}
A = [('Logatec', 'Vrhnika'), ('Logatec', 'Postojna'), ('Logatec', 'Idrija'), ('Vrhnika', 'Logatec'), ('Vrhnika', 'Ljubljana')]

Lahko pa ga podamo v obliki slovarja naslednikov:

{'Logatec': ['Vrhnika', 'Postojna', 'Idrija'], 'Vrhnika': ['Logatec', 'Ljubljana']}

(V zgornjem primeru smo predpostavili, da se iz Postojne, Idrije in Ljubljane, ne da priti nikamor (kar seveda ni res))

Ključi v tem slovarju so vozlišča, vrednost pri posameznem ključu u pa je seznam vseh vozlišč, ki so nasledniki vozlišča u. (Vozlišče $v$ je naslednik vozlišča $u$, če v digrafu obstaja usmerjena povezava $(u, v)$.)

V nadaljevanju predpostavite, da grafi ne bodo imeli izoliranih vozlišč (to so vozlišča, ki niso niti začetek niti konec katere od povezav).

1. podnaloga

Napišite funkcijo slovar_naslednikov(seznam_povezav), ki kot argument dobi seznam povezav digrafa, sestavi in vrne pa naj pripadajoči slovar naslednikov. Zgled:

>>> slovar_naslednikov([('a', 'b'), ('c', 'b'), ('c', 'd'), ('d', 'a'), ('a', 'c')])
{'a': ['b', 'c'], 'c': ['b', 'd'], 'd': ['a']}

Seznami naslednikov naj bodo urejeni.

Uradna rešitev

def slovar_naslednikov(seznam_povezav):
    """Sprejme seznam povezav digrafa ter vrne slovar naslednikov."""
    slovar = dict()
    for u, v in seznam_povezav:
        if u not in slovar:
            slovar[u] = []
        slovar[u].append(v)
    for u in slovar:
        slovar[u].sort()
    return slovar

2. podnaloga

Sestavite funkcijo seznam_povezav(digraf), ki kot argument dobi usmerjen graf, ki je podan kot slovar naslednikov. Funkcija naj sestavi in vrne seznam usmerjenih povezav. (Torej, funkcija seznam_povezav naj naredi ravno obratno kot funkcija slovar_naslednikov.) Zgled:

>>> seznam_povezav({'a': ['b', 'c'], 'c': ['b', 'd'], 'd': ['a']})
[('a', 'b'), ('a', 'c'), ('c', 'b'), ('c', 'd'), ('d', 'a')]

Seznam povezav, ki ga vrne funkcija, naj bo urejen.

Uradna rešitev

def seznam_povezav(digraf):
    """Sprejme usmerjen graf, ki je podan kot slovar naslednikov ter vrne seznam usmerjenih povezav."""
    sez_pov = []
    for u, nasl in digraf.items():
        for v in nasl:
            sez_pov.append((u, v))
    sez_pov.sort()
    return sez_pov

# Alternativna rešitev
def seznam_povezav_alt(digraf):
    """Sprejme usmerjen graf, ki je podan kot slovar naslednikov ter vrne seznam usmerjenih povezav."""
    return sorted((u, v) for u, nasl in digraf.items() for v in nasl)

3. podnaloga

Napišite funkcijo nasprotni_graf(digraf), ki dobi usmerjen graf v obliki slovarja naslednikov, sestavi in vrne pa naj nasprotni graf (tudi v obliki slovarja naslednikov). Nasprotni graf grafa $G$ ima enako množico vozlišč kot $G$, povezave pa imajo obrnjeno smer. Zgled:

>>> nasprotni_graf({'a': ['b', 'c'], 'c': ['b', 'd'], 'd': ['a']})
{'a': ['d'], 'c': ['a'], 'b': ['a', 'c'], 'd': ['c']}

Seznami naslednikov naj bodo urejeni.

Uradna rešitev

def nasprotni_graf(digraf):
    """Sprejme usmerjen graf v obliki slovarja naslednikov ter vrne nasprotni graf
       (tudi v obliki slovarja naslednikov)."""
    nasprotni = dict()
    for u, nasl in digraf.items():
        for v in nasl:
            if v not in nasprotni:
                nasprotni[v] = []
            nasprotni[v].append(u)
    for u in nasprotni:
        nasprotni[u].sort()
    return nasprotni

# Alternativna rešitev
def nasprotni_graf_alt(digraf):
    """Sprejme usmerjen graf v obliki slovarja naslednikov ter vrne nasprotni graf
       (tudi v obliki slovarja naslednikov)."""
    return slovar_naslednikov((u, v) for v, u in seznam_povezav(digraf))

4. podnaloga

Usmerjene grafe lahko sestavimo iz večih usmerjenih podgrafov. Vsak posamezen podgraf je predstavljen s slovarjem, za katerega velja, da ima vsako vozlišče le enega naslednika.

Sestavite funkcijo sestavljen_graf(tabela_podgrafov), ki bo iz dane tabele usmerjenih podgrafov sestavila slovar, ki bo predstavljal graf v obliki slovarja naslednjikov. Vrednosti naj bodo v tabelah zapisane v enakem vrstnem redu, kot nastopajo v tabeli podgrafov. Zgled:

>>> sestavljen_graf([{'a': 'b', 'c': 'b'}, {'a': 'c', 'c': 'd', 'd': 'a'}])
{'a': ['b', 'c'], 'c': ['b', 'd'], 'd': ['a']}

Uradna rešitev

def sestavljen_graf(tabelaSlovarjev):
    """Sprejme tabelo usmerjenih podgrafov ter vrne graf v obliki slovarja naslednikov."""
    novSlovar = dict()
    for slovar in tabelaSlovarjev: # obdelamo vse slovarje
        for kljuc in slovar:
            if kljuc in novSlovar: # če se je ta ključ že pojavil
                novSlovar[kljuc].append(slovar[kljuc]) # dodamo njegovo vrednost
            else:
                novSlovar[kljuc] = [slovar[kljuc]] # sicer pa je to nov ključ
    return novSlovar

Ljubezen nam je vsem v pogubo

Otroci v šoli se hitro zatreskajo drug v drugega. Socialno omrežje zaljubljenosti otrok v šoli podamo s slovarjem, ki ime otroka preslika v množico imen vseh otrok, v katere je ta otrok zaljubljen (ena oseba je lahko zaljubljena v več oseb). Na primer, slovar

sola = {'Ana': {'Bine', 'Cene'},
     'Bine': set(),
     'Cene': {'Bine'},
     'Davorka': {'Davorka'},
     'Eva': {'Bine'}}

nam pove, da je Ana zaljubljena v Bineta in Cenete, Bine ni zaljubljen, Cene ljubi Bineta, Davorka samo sebe in Eva Bineta.

1. podnaloga

Sestavite funkcijo narcisoidi(d), ki sprejme slovar zaljubljenih otrok v šoli in vrne množico tistih, ki ljubijo same sebe. Zgled (če je slovar sola enak kot zgoraj):

>>> narcisoidi(sola)
{'Davorka'}

Uradna rešitev

def narcisoidi(d):
    """Sprejme slovar zaljubljenih ter vrne množico tistih, ki ljubijo sami sebe."""
    narciski = set()
    for oseba in d:
        if oseba in d[oseba]:
            narciski.add(oseba)
    return narciski

# Alternativna rešitev
def narcisoidi_alt(d):
    """Sprejme slovar zaljubljenih ter vrne množico tistih, ki ljubijo sami sebe."""
    return {oseba for oseba in d if oseba in d[oseba]}

2. podnaloga

Sestavite funkcijo ljubljeni(d), ki sprejme slovar zaljubljenih otrok v šoli in vrne množico tistih, ki so ljubljeni. Zgled (če je slovar sola enak kot zgoraj):

>>> ljubljeni(sola)
{'Bine', 'Davorka', 'Cene'}

Uradna rešitev

def ljubljeni(d):
    """Sprejme slovar zaljubljenih ter vrne množico tistih, ki so ljubljeni."""
    ret = set()
    for oseba, ljubcki in d.items():
        ret.update(ljubcki)
    return ret

# Alternativna rešitev
def ljubljeni_alt(d):
    """Sprejme slovar zaljubljenih ter vrne množico tistih, ki so ljubljeni."""
    return {ljubljen for oseba in d for ljubljen in d[oseba]}

3. podnaloga

Sestavite funkcijo pari(d), ki sprejme slovar zaljubljenih otrok v šoli in vrne množico vseh parov, ki so srečno zaljubljeni. Vsak par naj se pojavi samo enkrat in sicer tako, da je sta zaljubljenca našteta po abecedi. Na primer, če imamo slovar

sola2 = {'Ana': {'Bine', 'Cene'},
      'Bine': {'Ana'},
      'Cene': {'Bine'},
      'Davorka': {'Davorka'},
      'Eva': {'Bine'}}

kjer vidmo, da sta Ana in Bine zaljubljena, dodamo par ('Ana', 'Bine'). Zgled:

>>> pari(sola2)
{('Ana', 'Cene')}

Uradna rešitev

def pari(d):
    """Sprejme slovar zaljubljenih ter vrne množico vseh parov, ki so srečno zaljubljeni."""
    ret = set()
    for oseba, ljubcki in d.items():
        for ljubcek in ljubcki:
            if oseba < ljubcek and oseba in d[ljubcek]:
                ret.add((oseba, ljubcek))
    return ret

# Alternativna rešitev
def pari(d):
    """Sprejme slovar zaljubljenih ter vrne množico vseh parov, ki so srečno zaljubljeni."""
    return {tuple(sorted((x, y))) for x in d for y in d[x] if x in d[y] and x!=y}

4. podnaloga

Sestavite funkcijo ustrezljivi(oseba, d), ki sprejme ime osebe ter slovar zaljubljenih, vrne pa množico vseh ljudi, ki so do dane osebe še posebej ustrežljivi. Posebej ustrežljivi so seveda za to, ker so bodisi zaljubljeni v dano osebo, bodisi so zaljubljeni v osebo, ki je posebej ustrežljiva do nje, in tako naprej.

Na primer, v slovarju sola2, ki je definiran zgoraj, so do Ceneta posebej ustrežljivi Ana (ki je zaljubljena vanj), Bine (ki je zaljubljen v Ano), Eva (ki je zaljubljena v Bineta) ter seveda Cene (ki je zaljubljen v Bineta). Zgled (če je slovar sola2 enak kot zgoraj):

>>> ustrezljivi('Cene', sola2)
{'Ana', 'Bine', 'Cene', 'Eva'}

Uradna rešitev

def ustrezljivi(oseba, d):
    """Sprejme ime osebe in slovar zaljubljenih ter vrne množico vseh,
       ki so do dane osebe še posebej ustrežljivi."""
    ustrezljivi = set()  # Seznam, v katerega nabiramo ustrežljive osebe
    # Najprej dodamo tiste, ki ljubijo prvo osebo
    dodani = {o for o in d if oseba in d[o]}
    # Dokler smo koga dodali, dodajamo ustrežljive
    while len(dodani) > 0:
        ustrezljivi.update(dodani)
        # Sedaj pa dodajamo tiste, ki ljubijo nazadnje dodane osebe
        dodani = {o for o in d for dodan in dodani
                  if dodan in d[o] and o not in ustrezljivi}
    return ustrezljivi

LEGO kocke

Boštjan rad sestavlja LEGO kocke. Če bo do konca leta priden, mu bo babica Metka za Božič podarila škatlo kock. Ker se kocke pojavljajo v veliko različnih oblikah, ima Metka pri izbiranju ustreznega paketa kock kar nekaj težav...

Vsako LEGO kocko lahko opišemo z dvema lastnostima: tipom (torej obliko) in barvo. Predpostavili bomo, da se LEGO kocke lahko pojavljajo le v 3 različnih barvah: rdeči, modri in rumeni. Tipov LEGO kock pa je ogromno, zato jih bomo predstavili kar z nizi kot na primer '2x2', '4x1-tanka' ali pa 'nogice'.

Sprejmimo dogovor, da nobeno ime tipa ne vsebuje pike.

1. podnaloga

Vsebino škatle podamo s tabelo vseh kock, ki so v njej. Vsaka kocka je opisana z nizom, ki vsebuje tip kocke in barvo, ki sta ločeni s piko. Npr. kocka tipa '2x2' rdeče barve je predstavljena z nizom '2x2.rdeča'.

Napišite funkcijo slovar_kock(skatla), ki sprejme tabelo skatla in sestavi slovar vsebovanih kock, urejen po tipih ter po barvah, kot prikazuje primer:

>>> slovar_kock(['2x2.rdeča', '2x2.rdeča', 'nogice.modra', '2x2.modra'])
{'nogice': {'modra': 1}, '2x2': {'rdeča': 2, 'modra': 1}}

Uradna rešitev

def slovar_kock(skatla):
    """Sprejme tabelo skatla ter vrne slovar vsebovanih kock, urejen po tipih in barvah."""
    vrni={}
    for kocka in skatla:
        tip, barva = kocka.split(".")
        if vrni.get(tip): # če kocka že obstaja
            if vrni[tip].get(barva): # če barva že obstaja
                vrni[tip][barva]+=1

            else: vrni[tip].update({barva: 1})
        else: vrni[tip] = {barva: 1}
    return vrni

2. podnaloga

Boštjan je v sestavljanju LEGO kock zelo dober. Njegovi modeli sestojijo iz najrazličnejših tipov kock, ki pa jih včasih ni možno kupiti vseh v isti škatli.

Napišite funkcijo lahko_sestavimo(skatla, model), ki dobi dva slovarja kock, in vrne True natanko tedaj, ko je možno modelček (za katerega potrebujemo kocke, ki so podane s slovarjem model) sestaviti s kockami, ki so v škatli.

>>> model = {'4x1': {'modra': 1}, '2x2': {'rdeča': 2, 'modra': 1}}
>>> skatla = {'4x1': {'modra': 3, 'rdeča': 2}, '2x2': {'rdeča': 4, 'modra': 1, 'rumena': 5}}
>>> lahko_sestavimo(skatla, model)
True
>>> model_2 = {'4x1': {'rumena': 1}, '2x2': {'rdeča': 1, 'rumena': 2}}
>>> lahko_sestavimo(skatla, model_2)
False

Uradna rešitev

def lahko_sestavimo(skatla, model):
    """Vrne True, če je možno model sestaviti s kockami, ki so v škatli, in False sicer."""
    for tip in model:
        if not skatla.get(tip): return False
        for barva in model[tip]:
            if not skatla[tip].get(barva): return False
            elif skatla[tip][barva] < model[tip][barva]: return False
    return True

3. podnaloga

Boštjana ne moti, če kocke iz katerih sestavlja svoje modele, niso vse ustreznih barv, bolj mu je pomembno to, da model sploh lahko sestavi.

Napišite funkcijo hitro_sestavljanje(skatla, model), ki vrne True, če je možno modelček sestaviti “na hitro”, torej tako, da barve niso pomembne (še vedno pa je pomembno, da uporabimo kocke ustreznega tipa).

>>> model = {'4x1': {'modra': 2}, '2x2': {'rdeča': 2, 'modra': 1}}
>>> skatla_1 = {'4x1': {'rdeča': 3}, '2x2': {'rdeča': 1, 'rumena': 5}}
>>> skatla_2 = {'4x1': {'rumena': 3, 'rdeča': 2}, '2x2': {'rumena': 1, 'rdeča': 1}}
>>> hitro_sestavljanje(skatla_1, model)
True
>>> hitro_sestavljanje(skatla_2, model)
False

Uradna rešitev

def hitro_sestavljanje(skatla, model):
    """Vrne True, če je možno model s kockammi, ki so v škatli, sestaviti na hitro
       (torej tako, da barve niso pomembne (še vedno pa je pomembno, da uporabimo
       kocke ustreznega tipa), in False sicer."""
    for tip in model:
        if not skatla.get(tip): return False
        kolicina_model = sum([model[tip][barva] for barva in model[tip]])
        kolicina_skatla = sum([skatla[tip][barva] for barva in skatla[tip]])
        if kolicina_model > kolicina_skatla: return False
    return True

Električne naprave

Boštjan je za vse električne naprave, ki jih imata doma babica Metka in dedek Jože, ugotovil ime proizvajalca in podatke shranil v slovar. Zgled takega slovarja:

naprave = {
    'hladilnik': 'Gorenje', 'pralni stroj': 'Whirlpool',
    'kavni mlinček': 'Bosch', 'mikrovalovna pečica': 'Gorenje',
    'parni čistilnik': 'Philips', 'laserski tiskalnik': 'Lexmark',
    'sušilnik las': 'Philips'
}

Jože pa je sestavil slovar, v katerem so ključi naprave, vrednosti pa kategorije, kamor te naprave sodijo. Zgled:

kategorije = {
    'hladilnik': 'bela tehnika', 'parni čistilnik': 'sesalniki',
    'grelnik vode': 'kuhinjski aparati', 'pralni stroj': 'bela tehnika',
    'sušilnik las': 'nega las', 'mikrovalovna pečica': 'kuhinjski aparati',
    'laserski odstranjevalec dlačic': 'brivniki in depilatorji'
}

1. podnaloga

Boštjan in Jože bi rada združila podatke in za vsako blagovno znamko, ki se pojavi v Boštjanovem slovarju, ugotovila, katere kategorije naprav "pokriva" glede na Jožev slovar. Napišite funkcijo blagovne_znamke(naprave, kategorije), ki vrne slovar, kjer so ključi imena proizvajalcev, njihove pripadajoče vrednosti pa so množice kategorij, s katerimi se proizvajalec ukvarja.

Če sta slovarja naprave in kategorije enaka kot zgoraj:

>>> blagovne_znamke(naprave, kategorije)
{'Lexmark': set(), 'Philips': {'sesalniki', 'nega las'}, 'Whirlpool': {'bela tehnika'},
 'Gorenje': {'bela tehnika', 'kuhinjski aparati'}, 'Bosch': set()}

Bodite pozorni na to, da se lahko v Boštjanovem slovarju pojavijo tudi naprave, ki jih Jože nima v svojem slovarju, in obratno.

Uradna rešitev

def blagovne_znamke(naprave, kategorije):
    """Vrne slovar, kjer so ključi imena proizvajalcev, njihove pripadajoče
       vrednosti pa so množice kategorij, s katerimi se proizvajalec ukvarja."""
    blagZnamke = dict()
    for naprava, znamka in naprave.items():
        if znamka not in blagZnamke:
            blagZnamke[znamka] = set() # nova znamka, začnemo s prazno množico
        if naprava in kategorije:
            blagZnamke[znamka].add(kategorije[naprava]) # dodamo vse ustrezne kategorije
    return blagZnamke