p1: Orbite

Tudi tokratno nalogo je navdihnil Advent of Code, konkretno naloga Universal Orbit Map. Dve izmed (lažjih) funkcij sta enaki tistim, ki jih je bilo potrebno sprogramirati tam.

Testi

Testi: testi-orbite.zip

Naloga

Planet COM ima samo eno luno; recimo ji B. Luna B pa ima, zanimivo, dve svoji luni; recimo jima G in C ter se ne ukvarjajmo s tem, ali imajo lune lahko svoje lune in kaj imajo o tem povedati astronomi. Okrog lune G kroži luna H, okrog lune B pa luna C. Ker to postaja zapleteno, raje pokažimo s sliko:

                          YOU
                         /
        G - H       J - K - L
       /           /
COM - B - C - D - E - F
               \
                I - SAN

Ocena 6

Napiši funkcijo preberi_orbite(ime_datoteke), ki kot argument prejme datoteko z lunami v takšni obliki:

COM)B
B)C
C)D
D)E
E)F
B)G
G)H
D)I
E)J
J)K
K)L
K)YOU
I)SAN

vrniti pa mora slovar s temi podatki. Ključ slovarja je posamična luna, pripadajoča vrednost pa je luna (oz. planet), okrog katere ta luna kroži.

>>> preberi_orbite("example.txt")
{'B': 'COM', 'C': 'B', 'D': 'C', 'E': 'D', 'F': 'E', 'G': 'B',
'H': 'G', 'I': 'D', 'J': 'E', 'K': 'J', 'L': 'K', 'SAN': 'I', 'YOU': 'K'}

Rešitev

Naloga zahteva, da znamo prebrati datoteko in da vemo za metodo split, ter to, kar vrne, pametno zložiti v slovar.

def preberi_orbite(ime_datoteke):
    orbite = {}
    for vrstica in open(ime_datoteke):
        center, satelit = vrstica.strip().split(")")
        orbite[satelit] = center
    return orbite

Napiši funkcijo lune(orbite), ki prejme slovar, kakršen je gornji in vrne nov slovar: njegovi ključi so lune oz. planet, vrednost pa množica lun, ki krožijo okrog nje oz. njega.
```
>>> lune(orbite)
{'B': {'C', 'G'},
'C': {'D'},
'COM': {'B'},
'D': {'E', 'I'},
'E': {'F', 'J'},
'G': {'H'},
'I': {'SAN'},
'J': {'K'},
'K': {'L', 'YOU'}}
```
Rešitev

Gremo čez par reči v slovarju (orbite.items()). Tisto, kar je bila prej vrednost, bo zdaj ključ. Tisto, kar so bili prej ključi,zlagamo v množico. Če uporabimo defaultdict, je funkcija kar kratka.
```
from collections import dict

def lune(orbite):
    krozilci = defaultdict(set)
    for satelit, center in orbite.items():
        krozilci[center].add(satelit)
    return krozilci
```
Tule je precej študentov delalo nekakšne dvojne zanke prek orbite.items(), zaradi česar je bila funkcija zelo počasna. Dokler testiramo zgolj to funkcijo, se ta počasnost še ni poznala. Ker kasnejše funkcije zelo velikokrat pokličejo to funkcijo, pa so nekatere (predvsem funkcija n_odvisnikov) v tem primeru postale zelo počasne in se izvajala več minut namesto, da bi se končalo v trenutku.
Napiši funkcijo prestej_korake(odkod, kam, orbite), ki dobi začetno in končno luno ter slovar, kakršnega vrača funkcija preberi_orbite. Vrniti mora število korakov od odkod do kam, pri čemer je en korak skok z lune "dol" na luno oz. planet, okrog katere ta luna kroži (torej vedno samo z desne strani proti levi strani slike).

Od "J" do "C" trije koraki (J - E - D - C), zato
```
>>> prestej_korake("J", "C", orbite)
3
```
Predpostaviti smeš, da funkcije nikoli ne bomo klicali z argumenti, pri katerih je pot po teh pravili nemogoča -- na primer od J do I ali od C do J.

Rešitev

Tudi to je le naloga iz uporabe slovarjev. Slovar orbite nam pove, okoli katere lune kroži posamezna luna. Vzamemo to luno. In potem luno, okoli kroži ta. In luno okoli katere kroži ta. To ponavljamo, dokler ne pridemo do cilja, vmes pa štejemo korake.
```
def prestej_korake(odkod, kam, orbite):
    korakov = 0
    while odkod != kam:
        odkod = orbite[odkod]
        korakov += 1
    return korakov
```
Žalostno veliko študentov namesto odkod = orbite[odkod] še vedno piše
```
for kljuc, vrednost in orbite.items():
    if kljuc == odkod:
        naslednja = vrednost
odkod = naslednja
```
To je počasno. In grdo. In nevarno, ker se lahko pri tem zmotimo. In, predvsem, kaže, da avtor takšne rešitve ne razume točno, čemu služijo slovarji. :(
Napiši funkcijo prestej_korake_r(odkod, kam, orbite), ki počne natančno isto, vendar je narejena rekurzivno.

Rešitev

Če bi radi izračunali, koliko je od te lune do cilja (ki je nekje na levi), moramo le preveriti, koliko je od leve lune do cilja. Od te je pač en korak več.

Če smo že na cilju, pa je koravkov 0.
```
def prestej_korake_r(odkod, kam, orbite):
    if odkod == kam:
        return 0
    return 1 + prestej_korake_r(orbite[odkod], kam, orbite)
```
Te naloge se ne da reševati takole:
```
def prestej_korake_r(odkod, kam, orbite):
    if odkod == kam:
        return 0

    korakov = 0
    prestej_korake_r(orbite[odkod], kam, orbite)
    korakov += 1
    return korakov
```
Daljša razlaga podobno napačnega razmišljanja lahko preberete ob rešitvi naslednje funkcije.
Napiši funkcijo n_odvisnikov(luna, orbite), ki prešteje, koliko lun kroži okrog lune luna in okrog teh lun, in okrog lun, ki krožijo okrog teh lun in tako do konca. Z drugimi besedami, za podano luno vrne število vseh lun, ki so povezane z njo s povezavami proti desni.

Okrog lune E in lun, ki krožijo okrog nje (in tako naprej) krožijo F, J, K, L in YOU, zato
```
>>> n_odvisnikov("E", orbite)
5
```
Okrog COM pa posredno ali neposredno kroži vseh 13 lun, zato
```
>>> n_odvisnikov("COM", orbite)
13
```
Rešitev

Odvisnikov je toliko, kolikor lun kroži okrog te lune, k temu pa moramo prešteti še odvisnike vseh sinov.
```
def n_odvisnikov(luna, orbite):
    odvisniki = lune(orbite)[luna]
    return len(odvisniki) + sum(
        n_odvisnikov(luna, orbite) for luna in odvisniki)
```
Ali, enako le malo dajše, tako:
```
def n_odvisnikov(luna, orbite):
    odvisniki = lune(orbite)[luna]
    odvisnikov = len(odvisniki)
    for odvisnik in odvisniki:
        odvisnikov += n_odvisnikov(odvisnik, orbite)
    return odvisnikov
```
Tule je prav, da opazimo, da funkcija kliče lune(orbite) in da se ta klic dogaja vedno ponovno in ponovno in ponovno, ob vsakem rekurzivnem klicu. Slabo napisana funkcija lune za 1000 lun ne bo porabila 1000 korakov, temveč 1000 * 1000. Ker funkcija n_odvisnikov za 1000 lun 1000-krat pokliče lune, bo vse skupaj zahtevalo 1000 * 1000 * 1000 = 1 milijardo korakov.

Če je funkcija lune napisana solidno, to še ne bo problem. Če nas to skrbi, pa se rešimo tako:
```
def n_odvisnikov(luna, orbite):
    obrnjene = lune(orbite)
    return n_odvisnikov0(luna, obrnjene)

def n_odvisnikov0(luna, obrnjene):
    odvisniki = obrnjene[luna]
    return len(odvisniki) + sum(
        n_odvisnikov0(luna, obrnjene) for luna in odvisniki)
```
Zdaj funkcija n_odvisnikov obrnjene slovar lun v pravo obliko in pokliče rekurzivno funkcijo n_odvisnikov0, ki prejme seznam lun v takšni obliki, tako da ga ni potrebno pretvarjati ob vsakem rekurzivnem klicu znova.

Tudi veliko naslednjih funkcij bi potrebovalo seznam v takšni obliki in so zaradi pretvarjanja nekoliko počasnejše. A še počasnejše bi bile, če pretvarjanja ne bi bilo. Naloge so bile podane v tej obliki prav zato, da bi bili študenti pri vsaki prisiljeni sami presoditi, kakšen slovar jim bo prišel najbolj prav.

S to nalogo so imeli študenti žalostno hude probleme. To pomeni, da ne berejo zapiskov predavanj. :( Naloga je natančno enaka nalogi, v kateri smo šteli potomce v rodbini Novakovih.

Tule je tipičen, a poučen primer napačnega razmišljanja.
```
def n_odvisnikov(luna, orbite):
    odvisnikov = 0
    odvisniki = lune(orbite)[luna]
    for x in odvisniki:
        n_odvisnikov(x, orbite)
    odvisnikov += len(odvisniki)
    return odvisnikov
```
Avtorji takšne rešitve (precej sem jih videl v tem tednu) najbrž razmišljajo takole. Pripravim si spremenljivko n_odvisnikov, v katero bom sešteval odvisnike. Torej odvisnikov = 0. K temu potem prištejem število odvisnikov te lune. To potem ponovim za vsako luno, ki je pripeta na to luno (for x in podlune: n_odvisnikov(x, orbite):).

Napaka v razmišljanju je v tem, da si predstavljate, da bo obstajala samo ena spremenljivka odvisnikov in vse funkcije bodo prištevale vanjo (odvisnikov += len(podlune)). Vendar si istočasno predstavljate, da se bo vrstica odvisnikov = 0 zgodila le enkrat, v prvem klicu funkcije, v nadaljnjih klicih pa se bo skrivnostno preskočila.

A oboje očitno ne more biti res. Ali je spremenljivka odvisnikov le ena -- vendar se potem vedno znova postavlja na 0, ali pa imamo ob vsakem klicu funkcije novo spremenljivko. Res je seveda drugo. Ko funkcija pokliče samo sebe, ima ta, nova "inkarnacija" funkcije svojo spremenljivko odvisnikov, ki z ono, prvo, nima zveze.

Funkcijo lahko malo preobrnemo -- premešamo vrstice, katerih vrstni red ni pomemben.
```
def n_odvisnikov(luna, orbite):
    odvisniki = lune(orbite)[luna]

    for x in odvisniki:
        n_odvisnikov(x, orbite)

    odvisnikov = 0
    odvisnikov += len(odvisniki)
    return odvisnikov
```
Zdaj pa pogledamo zadnje tri vrstice in uvidimo, da funkcija pravzaprav počne to:
```
def n_odvisnikov(luna, orbite):
    odvisniki = lune(orbite)[luna]
    for x in odvisniki:
        n_odvisnikov(x, orbite)
    return len(odvisniki)
```
Funkcija n_odvisnikov ne spreminja "sveta" okrog sebe. Klic te funkcija nima "stranskih učinkov". Ko pokličemo n_odvisnikov(x, orbite) in zavržemo rezultat tega klica, je to isto, kot če bi funkcije sploh ne klicali. Gornja funkcija je torej enaka kot
```
def n_odvisnikov(luna, orbite):
    odvisniki = lune(orbite)[luna]
    return len(odvisniki)
```
Kako to popraviti, sem nakazal zgoraj. Funkcijo n_odvisnikov(x, orbite) kličemo zato, da bi izračunala število odvisnikov lune x. Ta rezultat moramo uporabiti, ne zavreči.

Prva rekurzivna funkcija, ki smo jo programirali, je bila vsota. Smo jo morda sprogramirali tako?
```
def vsota(s):
    v = 0
    vsota(s[1:])
    v += s[0]
    return v
```

Ocena 7

Napiši funkcijo pot_do(odkod, kam, orbite), ki je podobna funkciji prestej_korake, vendar ne vrne števila korakov temveč seznam lun na poti, vključno z odkod in kam. Funkcija naj ne bo rekurzivna. Rekurzivno različico boš napisal za oceno 8.
```
>>> pot("J", "C", orbite)
["J", "E", "D", "C"]
```
Spet smeš predpostaviti, da pot, po kateri sprašuje funkcija, obstaja.

Rešitev

Tole je čisto isto kot štetje korakov, le da zlagamo lune v seznam, ki ga na koncu vrnemo.
```
def pot_do(odkod, kam, orbite):
    pot = [odkod]
    while odkod != kam:
        odkod = orbite[odkod]
        pot.append(odkod)
    return pot
```
Napiši funkcijo pot_v_niz(pot), ki prejme seznam, kakršnega vrača prejšnja funkcija in vrne niz, v katerem so lune ločene z znakom ->.
```
>>> pot_v_niz(["J", "E", "D", "C"])
"J -> E -> D -> C"
```
Rešitev

Iz te naloge lahko doktoriramo, lahko pa vemo, da imajo nizi metodo join.
```
def pot_v_niz(pot):
    return " -> ".join(pot)
```
Če vemo o Pythonu kaj več, pa funkcijo kar priredimo. Celotna rešitev naloge je lahko kar.
```
pot_v_niz = " -> ".join
```
Napiši funkcijo navodila(pot, ime_datoteke), ki prejme pot, kakršno vrne prejšnja funkcija in ime datoteke. V datoteko shrani zapis navodil v obliki, ki jo kaže spodnji primer.

Klic navodila("F -> E -> D -> C -> B", "pot.txt") v datoteko pot.txt zapiše naslednje besedilo
```
Iz F pojdite na E.
Potem zavijte na D.
Potem zavijte na C.
Potem zavijte na B.
Vaš cilj, B, bo pod vami.
```
V prvi vrstici torej vedno piše "Iz ... pojdite na ...", v naslednji(h) pa "Potem zavijte na ...". Na koncu naj napiše, da bo cilj pod vami.

Rešitev

To nalogo je bilo potrebno dodati za preprosto vajo iz oblikovanja nizov in pisanja datotek.
```
def navodila(pot, ime_datoteke):
    dat = open(ime_datoteke, "wt")
    lune = pot.split(" -> ")
    if len(lune) >= 2:
        dat.write(f"Iz {lune[0]} pojdite na {lune[1]}.\n")
    for luna in lune[2:]:
        dat.write(f"Potem zavijte na {luna}.\n")
    dat.write(f"Vaš cilj, {lune[-1]}, bo pod vami.")
```

Ocena 8

Napiši funkcijo pot_do_r(odkod, kam, orbite), ki počne isto kot funkcija pot_do, le da je napisana rekurzivno.

Rešitev

Pot od te lune do cilja je enaka poti od naslednje lune do cilja, le še korak do naslednje lune moramo dodati.

Razmišljanje je torej čisto enako kot pri rekurzivnem štetju korakov, le da rezultat ni število temveč seznam.
```
def pot_do_r(odkod, kam, orbite):
    if odkod == kam:
        return [odkod]
    return [odkod] + pot_do_r(orbite[odkod], kam, orbite)
```
Napiši funkcijo odvisniki(luna, orbite), ki je podobna funkciji n_odvisnikov, vendar ne vrne števila povezanih lun na desni temveč množico odvisnih lun.
```
>>> odvisniki("E", orbite)
{'F', 'J', 'YOU', 'L', 'K'}
```
Rešitev

Vrniti moramo množico direktnih odvisnikov podane lune, ki ji potem dodamo še vse odvisnike ter direktnih odvisnikov.
```
def odvisniki(luna, orbite):
    moji = lune(orbite)[luna]
    vsi = set(moji)
    for luna in moji:
        vsi |= odvisniki(luna, orbite)
    return vsi
```
Nalogo je možno rešiti tudi brez rekurzije.

V seznam odvisnikov najprej dodamo kar samo luno - odstranili jo bomo na koncu. Nato gremo z zanko čez seznam odvisnikov in za vsakega odvisnika dodamo v seznam njegove odvisnike. To je eden od primerov, ko gremo z zanko čez seznam, ki ga medtem spreminjamo in to celo pravilno deluje. Ko pridemo do konca, smo dodali vse odvisnike vseh odvisnikov. Ker naloga zahteva, da vrnemo množico, vrnemo množico, v kateri so vsi odvisniki razen prvega, to je, podane lune same.
```
def odvisniki(luna, orbite):
    orbite_nazaj = lune(orbite)
    vsi = [luna]
    for odvisnik in vsi:
        vsi += orbite_nazaj[odvisnik]
    return set(vsi[1:])
```
Zakaj nismo že od vsega začetka uporabljali množice? Ker množica nima vrstnega reda, z zanko for ne moremo iti prek množice, ki se medtem spreminja. To ne le ne bi delovalo, temveč Python tega v resnici ne pusti.

Ocena 9

Napiši funkcijo pot_med(odkod, kam, orbite), ki vrne (najkrajšo) pot med dvema lunama. Tokrat je dovoljeno iti proti levi in potem nazaj proti desni, torej po vseh povezavah na sliki.
```
>>> pot_med("SAN", "K")
["SAN", "I", "D", "E", "J", "K"]
```
Rešitev

Nalogo ste reševali na različne zvite načine. Najbolj preprost pa je tale: poiščemo pod od obeh lun do začetne. Ob poti bosta imeli nekaj enakih skupnih končnih elementov. Te odbijemo. Zapomnimo pa si zadnjega odbitega - tam bo potrebno zaviti. Rešitev je enaka poti do zadnjega odbitega in poti od njega do cilja -- kar je ravno okrog obrnjena pot od cilja do zadnjega odbitega.
```
def pot_med(luna1, luna2, orbite):
    pot1 = pot_do(luna1, "COM", orbite)
    pot2 = pot_do(luna2, "COM", orbite)
    while pot1 and pot2 and pot1[-1] == pot2[-1]:
        pot1.pop()
        skupni = pot2.pop()
    return pot1 + [skupni] + pot2[::-1]
```
Tu smo kar predpostavili, da se prvi planet imenuje COM. Če si tega ne bi upali, pač ne bi mogli uporabiti funkcije pot_do, temveč bi iskali pot do začetka.
```
def do_zacetka(luna, orbite):
    pot = [luna]
    while pot[-1] in orbite:
        pot.append(orbite[pot[-1]])
    return pot

def pot_med(luna1, luna2, orbite):
    pot1 = do_zacetka(luna1, orbite)
    pot2 = do_zacetka(luna2, orbite)
    while pot1 and pot2 and pot1[-1] == pot2[-1]:
        pot1.pop()
        skupni = pot2.pop()
    return pot1 + [skupni] + pot2[::-1]
```
Na eno od lun bodo postavili bazo. Baza oskrbuje lune, ki krožijo do tri korake naprej (na sliki: proti desni). Luna D lahko oskrbuje I, SAN, E, F, J, K, ne more pa oskrbovati L in YOU, ker sta predaleč.

Napiši funkcijo baza(lune, orbite), ki prejme seznam poseljenih lun (lune) in, seveda, orbite. Funkcija pove, na katero luno je potrebno postaviti bazo, da bo oskrbovala čim več lun.
```
>>> baza(["I", "E", "J", "K"], orbite)
"D"
```
Baza na D lahko oskrbuje vse štiri lune, baza na C ali E bi oskrbovala tri, baza na B ali J bi oskrbovala 2, baza na I ali K pa eno.

Če je možnih več enako dobrih izbir, naj vrne poljubno od njih.

Rešitev

Da rešitev ne bo predolga, bomo uporabili razred Counter. Spoznali smo ga na predavanjih o slovarjih; v modulu collections dela družbo defaultdict-u.

Predstavljajmo si, da lune glasujejo, kje bo baza. Gremo čez vse lune. Vsaka glasuje zase, poleg tega pa se pri vsaki zapeljemo še za tri korake na levo in "oddajamo" glasove za te, leve lune. Tista, ki prejme največ glasov, je zmagala. To luno dobimo z most_common. most_common(1) vrne seznam najpogostejših 1 lun (se pravi najpogostejšo luno). Vzamemo prvi element tega seznama. Ta je par: ime lune in število glasov. Zanima nas element lune, torej prvi element. Zato vrnemo glasov.most_common(1)[0][0].
```
def baza(lune, orbite):
    glasov = Counter()
    for luna in lune:
        glasov[luna] += 1
        for korak in range(3):
            luna = orbite[luna]
            glasov[luna] += 1
            if luna not in orbite:
                break
    return glasov.most_common(1)[0][0]
```
Ne spreglejmo še
```
            if luna == "COM":
                break
```
Ta je potreben zato, ker lahko ob teh treh korakih nazaj že prej trčimo na začetek.

Ocena 10

Napiši funkcijo sirina_orbite(luna, razdalja, orbite), ki vrne število lun, ki krožijo na podani razdalji od podane lune. Na razdalji 2 od lune D krožijo 3 lune: J, F in SAN.

Rešitev

Predstavljajmo si rodbino. Znali bi izračunati število sinov. Znali bi izračunati tudi število vnukov -- vsakega sina vprašamo, koliko sinov ima. Znamo izračunati tudi število pravnukov -- vsakega sina vprašamo, koliko vnukov ima.

V splošnem je potomcev na nivoju n toliko, kolikor imajo vsi sinovi skupan potomcev na nivoju n - 1.
```
def sirina_orbite(odkod, n, orbite):
    if n == 0:
        return 1
    sirina = 0
    for luna in lune(orbite)[odkod]:
        sirina += sirina_orbite(luna, n - 1, orbite)
    return sirina
```
Zdaj pa poglejmo nek drug sistem lun.

Skiciral ga je nek začetniški astronom - poimenoval je lune in zabeležil relacije med njimi. Potreboval je par dni. Ali noči. In lune so se medtem premikale.

Kaj opaziš? Da sta luni D in F pravzaprav najbrž ista luna - verjetno ju je popisal v dveh različnih nočeh! Vse, kar jima sledi, je namreč enako. Seveda imajo lune drugačna imena (izmislil si jih je on), pa na sliki tudi ni vse enako obrnjeno - G je "zgornja" luna D-ja, K pa je "srednja" luna F-ja, ampak to je vendar isto. Celotna struktura je enaka.

Prav tako bi bili lahko isti, recimo P in M.

Zdaj pa si predstavljajmo, da na sliki ne bi bilo lune J. V tem primeru D in F ne bi bila več (najbrž) isti, pač pa bi bili lahko še vedno isti P in M. Ali pa celo K in G.

Če ne bi bilo lune O, bi bili lahko isti kvečjemu P in M...

Napiši funkcijo enaka_struktura(luna1, luna2, orbite), ki vrne True, če sta strukturi pod lunama luna1 in luna2 enaki in False če nista.

Funkcija mora delovati tudi, če okrog česa kroži več, recimo 5 lun. Lahko pa predpostaviš, da jih ni bistveno več kot 5.

Nasvet: ker so lune, ki krožijo okrog določene lune, navedene v poljubnem vrstnem redu, bo potrebno pod vsako luno najbrž poskusiti vse možne vrstne rede -- ko primerjaš dve luni, pustiš lune, ki so okrog ene, v originalnem vrstnem redu, vrstni red lun okrog druge pa mešaš. Pri tem lahko uporabiš funkcijo permutations, ki jo najdeš v modulu itertools. Če boš tej funkciji slučajno podal(a) množico, ne bo srečna; pretvori jo v seznam.

Če se dobro lotiš, bo funkcija kar elegantna in imela približno deset vrstic.

#### Rešitev


Poiskati moramo takšno permutacijo potomcev teh dveh lun, da se ujemajo vse strukture pod njimi. Če jo najdemo, vrnemo `True`. Če je ni, vrnemo `False`.

```python
from itertools import permutations

def enaka_struktura(luna1, luna2, orbite):
    lune1 = lune(orbite)[luna1]
    lune2 = lune(orbite)[luna2]
    if len(lune1) != len(lune2):
        return False
    for p in permutations(list(lune2)):
        if all(enaka_struktura(pod1, pod2, orbite)
            for pod1, pod2 in zip(lune1, p)):
            return True
    return False
```

Za κῦδος

Potrebno bo popraviti napako astronoma - začetnika. Ugotoviti je potrebno, katera luna ustreza kateri.

Napiši funkcijo pari_lun(luna1, luna2, orbite), ki počne podobno kot prejšnja, le da vrača drugačen rezultat. Če sta strukturi pod luna1 in luna2 različni, vrne None. Sicer pa vrne pare lun, ki so v bistvu ista luna.

Pari so shranjeni kot terke. Vsaka terka je urejena po abecedi, celoten seznam pa je urejen po abecedi terk.
```
>>> pari_lun("D", "F", orbite)
[('D', 'F'), ('G', 'K'), ('H', 'J'), ('I', 'L'), ('M', 'P'),
 ('N', 'O'), ('R', 'T'), ('S', 'U'), ('V', 'Z')]
```
Luni D ustreza F, luni G ustreza K, luni H ustreza J, luni I ustreza L, luni M ustreza P ...

Odgovor bi lahko bil tudi:
```
[('D', 'F'), ('G', 'K'), ('H', 'L'), ('I', 'J'), ('M', 'P'),
 ('N', 'O'), ('R', 'T'), ('S', 'U'), ('V', 'Z')]
```
Namesto parov H-J in I-L imamo namreč lahko tudi H-L in I-J.

Napiši pravo, lepo funkcijo, ne takšne, ki teka po vsem slovarju gor in dol in poskuša najti neke pare, ki bi ustrezali.

Funkcija ne bo bistveno daljša od prejšnje.

Rešitev

Tole je precej podobno preverjanju strukture.

Funkcija rekurzivno kliče sebe. Če najde ustrezno permutacijo, vrne pare, sicer ne vrne ničesar (in torej vrne None). Kadar kaj vrne, pa doda te pare k preostalim uspešno najdenim parom.
```
def pari_lun(luna1, luna2, orbite):
    lune1 = lune(orbite)[luna1]
    lune2 = lune(orbite)[luna2]
    if len(lune1) == len(lune2):
        for p in permutations(list(lune2)):
            pari = [tuple(sorted([luna1, luna2]))]
            for pod1, pod2 in zip(lune1, p):
                podpari = pari_lun(pod1, pod2, orbite)
                if podpari is None:
                    break
                pari += podpari
            else:
                return sorted(pari)
```

Last modified: Thursday, 25 March 2021, 8:26 PM

Course Activities

Recent Courses

Testi

Naloga

Ocena 6

Rešitev

Rešitev

Rešitev

Rešitev

Rešitev

Ocena 7

Rešitev

Rešitev

Rešitev

Ocena 8

Rešitev

Rešitev

Ocena 9

Rešitev

Rešitev

Ocena 10

Rešitev

Za κῦδος

Rešitev