Potniki

Testi

Testi: testi-potniki.py

Ocena 6

Imamo seznam imen krajev in njihovih koordinat. Recimo takšen.

[('Brežice', 68.66, 7.04),
 ('Lenart', 85.20, 78.75),
 ('Rateče', -65.04, 70.04)
]

• Napiši funkcijo koordict(kraji), ki vrne slovar, katerega ključi so imena krajev, vrednosti pa pripadajoče koordinate, na primer

  {'Brežice`: (68.66, 7.04),
  'Lenart': (85.20, 78.75),
  'Rateče': (-65.04, 70.04)
  }
  

Tako:

def koordict(koordinate):
    koord = {}
    for ime, x, y in koordinate:
        koord[ime] = (x, y)
    return koord

ali tako:

def koordict(koordinate):
    return {ime: (x, y) for ime, x, y in koordinate}

Te funkcije niste pisali kar tako, za hec! Predstavitev krajev s seznamom trojk je zoprna, če hočemo v njej poiskati kak kraj. To funkcijo ste morali napisati preprosto zato, da vam bo v kasnejših lažje poiskati koordinate določenega kraja.

• Napiši funkcijo razdalje(kraj, kraji), ki prejme ime kraja in seznam krajev (to je, seznam trojk z imenom in koordinatami). Vrne množico parov: drugi elementi so imena vseh krajev iz kraji, razen podanega kraja, prvi element pa kvadrati razdalij od podanega kraja do teh krajev. Klic razdalje("Lenart", kraji) vrne

  {(5415.895699999999, 'Brežice'),
   (22647.921700000003, 'Rateče')
  }
  

  Računaj torej razdalje tako kot običajno, le rezultata ne koreni. Zakaj tako? Razdalje bomo potrebovali zato, da kraje uredimo po oddaljenosti. Pri tem pa je vseeno, ali so te korenjene ali ne. V praktičnih programih lahko, posebej če se zelo zelo mudi (računalniška grafika, igre...) tako prihranimo nekaj časa.

Tule torej pokličemo koordict(koordinate), a kar takoj poberemo koordinate želenega kraja, x0, y0 = koordict(koordinate)[kdo]. Nato le pripravimo prazno množico ter vanjo zlagamo razdalje in imena.

def razdalja(kdo, koordinate):
    x0, y0 = koordict(koordinate)[kdo]
    r = set()
    for ime, x, y in koordinate:
        if ime != kdo:
            r.add(((x0 - x) ** 2 + (y0 - y) ** 2, ime))

Ali, preprosteje (kakor za koga):

def razdalje(kdo, koordinate):
    x0, y0 = koordict(koordinate)[kdo]
    return {((x0 - x) ** 2 + (y0 - y) ** 2, ime)
            for ime, x, y in koordinate if ime != kdo}

• Napiši funkcijo sosedi(n, kraj, kraji), ki vrne množico z n kraji, ki so najbližji podanemu kraju kraj. Argument kraji so spet trojke.

Prejšnja funkcija je pripravila vse, kar potrebujemo za to. Pokličemo jo in uredimo dobljeno množico parov (razdalja, ime). Ker gre za pare, jih uredi najprej po prvem elementu, razdalji, tiste, ki so na enaki razdalji, pa po imenu, za kar nam je vseeno. Rezultat urejanja je seznam. Vzamemo prvih n elementov. Skratka sorted(razdalje(kdo, koordinate))[:n]. To je torej seznam parov (razdalja, kraj) za najbližjih n krajev. Imena krajev zložimo v množico.

def sosedi(n, kdo, koordinate):
    najblizji = set()
    for razdalja, ime in sorted(razdalje(kdo, koordinate))[:n]:
        najblizji.add(ime)
    return najblizji

Spremenljivke razdalje ne potrebujemo, uvesti smo jo morali le, ker so v seznamu, prek katerega gremo s for, pari. Takšnim "prisilnim" spremenljivkam navadno ne dajemo posebnih imen: poimenujemo jih _. Torej

def sosedi(n, kdo, koordinate):
    najblizji = set()
    for _, ime in sorted(razdalje(kdo, koordinate))[:n]:
        najblizji.add(ime)
    return najblizji

Ali

def sosedi(n, kdo, koordinate):
    return {ime for _, ime in sorted(razdalje(kdo, koordinate))[:n]}

• Napiši funkcijo povezave(n, kraji), ki vrne slovar, katerega ključi so vsi kraji, pripadajoče vrednosti pa množice n najbližjih krajev vsakemu kraju. Če bi imeli v seznamu malo več krajev, bi klic povezave(3, kraji), lahko vrnil

  {'Brežice': {'Ribnica', 'Lenart', 'Rogaška Slatina'},
   'Lenart': {'Brežice', 'Ljutomer', 'Rogaška Slatina'},
   'Ljutomer': {'Brežice', 'Lenart', 'Rogaška Slatina'},
   'Rateče': {'Ribnica', 'Brežice', 'Rogaška Slatina'}
  }
  

  Če imamo kraje po vsej Sloveniji in želimo pet najbližjih krajev vsakega kraja, vrne slovar, katerega ključi so kraji na sliki, pripadajoče vrednosti pa množice vseh krajev, proti katerim kažejo črtice.

  

Spet smo si vse pripravili že v prejšnjih nalogah. Tu le zlagamo sosede v slovar.

def povezave(n, koordinate):
    p = {}
    for kdo, _, _ in koordinate:
        p[kdo] = sosedi(n, kdo, koordinate)
    return p

Ali

def povezave(n, koordinate):
    return {kdo: sosedi(n, kdo, koordinate) for kdo, _, _ in koordinate}

• Napiši funkcijo dvosmerno(d). Predstavljajmo si, da d vsebuje vse gornje povezave. Funkcija dvosmerno(d) naj sestavi nov slovar, pri katerem v množico sosedov vsakega kraja doda še kraje, ki "kažejo" nanj.

  Pri ključu "Trbovlje" imamo množico {"Velenje", "Celje", "Žalec", "Laško","Radeče"}. Vendar na Trbovlje kažejo tudi povezave iz Gornjega Gradu in Litije, zato dvosmerno vrne slovar, v katerem ključu "Trbovlje" pripada vrednost {"Velenje", "Celje", "Žalec", "Laško","Radeče", "Gornji Grad", "Litija"}.

  

Joj, kaj ste počeli s to ubogo funkcijo. Kopiranje slovarja, na katerega sem vas opozoril na forumu, je bil še najmanjši problem. A ni nič težkega. Gremo prek povezav. Za vsak kraj gremo prek njegovih sosedov in med sosedove sosede dodamo ta kraj.

import deepcopy

def dvosmerno(povezave):
    povezave2 = deepcopy(povezave)
    for kdo, sosedi in povezave.items():
        for sosed in sosedi:
            if sosed not in povezave2:
                povezave2[sosed] = set()
            povezave2[sosed].add(kdo)
    return povezave2

Gre tudi brez deepcopy. V tem primeru se nam splača privoščiti defaultdict.

from collections import defaultdict

def dvosmerno(povezave):
    povezave2 = defaultdict(set)
    for kdo, sosedi in povezave.items():
        povezave2[kdo].update(sosedi)
        for sosed in sosedi:
            povezave2[sosed].add(kdo)
    return povezave2

S to funkcijo ste imeli veliko težav, meni pa ni uspelo napisati testov, ki bi pokrili vse možne napake. Zaradi tega se je žal pogosto zgodilo, da je funkcija prestala teste, a povzročala težave pri vseh možnih naslednjih nalogah.

Ocena 7

• Napiši funkcijo veljavna_pot(pot, povezave), ki kot argument prejme neko pot skozi kraje, predstavljeno s seznamom njihovih imen, ter povezave, kakršne vračata funkciji povezave oz dvosmerno. Funkcija preveri, ali je pot veljavna. Pot je veljavna, če gre le prek povezav, ki se nahajajo v slovarju (se pravi, po povezavah, ki so na gornji sliki). Kraji na poti se smejo ponavljati, nikoli pa se ne smemo vrniti v kraj, iz katerega smo ravnokar prišli. Pot ["Ljubljana", "Litija", "Domžale", "Ljubljana", "Litija", "Trbovlje"] je veljavna, pot ``["Ljubljana", "Litija", "Ljubljana", "Domžale"]` pa ne, ker smo se iz Litije takoj vrnili nazaj v Ljubljano.

Preverjati je potrebno zaporedne pare (ti morajo biti povezani) in pare, med katerimi je še en krat (ti ne smejo biti enaki). To je najpreprosteje početi z dvema zankama.

def veljavna_pot(pot, povezave):
    for x, y in zip(pot, pot[1:]):
        if y not in povezave[x]:
            return False

    for x, y in zip(pot, pot[2:]):
        if x == y:
            return False

    return True

Ali:

def veljavna_pot(pot, povezave):
    return all(y in povezave[x] for x, y in zip(pot, pot[1:])) \
           and all(x != y for x, y in zip(pot, pot[2:]))

Kdor je delal s trojkami, for x, y, z in zip(pot, pot[1:], pot[2:]), je moral posebej obravnavati zadnji par na poti, saj ta ne nastopi v trojki kot x in y.

Nekateri so se funkcije lotili rekurzivno. Python po privzetih nastavitvah dopušča 1000 nivojev klicev. Ker je najdaljša pot, ki jo funkcija dobi, dolga 1000, moramo povečati to mejo.

import sys
sys.setrecursionlimit(2000)

Rekurzivna rešitev je

def veljavna_pot(pot, povezave):
    return len(pot) < 2 \
        or (pot[1] in povezave[pot[0]]
            and (len(pot) < 3 or pot[0] != pot[2])
            and veljavna_pot(pot[1:], povezave)
        )

• Napiši funkcijo izberi(izbor, prepovedan), ki vrne naključno izbran element iz seznama ali množice izbor, ki ni enak prepovedan. izbor bo običajno množica nizov in prepovedan bo eden od njih, vendar ne računaj na to. (Namig: funkcija random.choice(s) vrne naključni element seznama s. Če bi radi naključni element množice, bi bilo to množico najpametneje spremeniti v seznam.)

Naključno izbiramo, dokler ne izberemo takšnega, ki ni prepovedan.

import random

def izberi(izbor, prepovedan):
    while True:
        nasl = random.choice(list(izbor))
        if nasl != prepovedan:
            return nasl

list(izbor) je potreben, ker random.choice ne zna jemati naključnih elementov iz množice, saj deluje tako, da si izbere naključen indeks, množice pa nimajo indeksov.

Tu so nekateri iz seznama izbor najprej pobrisali, kar je prepovedano. To je zelo narobe. Funkcije ne smejo spreminjati vrednosti, ki jih dobijo kot argument. Lahko pa naredimo kopijo; z njo smemo početi, kar hočemo.

def izberi(izbor, prepovedan):
    izbor = izbor.copy()
    if prepovedan in izbor:
        izbor.remove(prepovedan)
    return random.choice(list(izbor))

• Napiši funkcijo potnik(zacetek, korakov, povezave), ki prejme ime začetnega kraja, število korakov in slovar povezav (kot v prejšnjih funkcijah). Funkcija vrne naključno (a veljavno!) pot v obliki seznama imen krajev. Seznam bo vseboval korakov + 1 elementov.

Tule so se mnogi zaplezali tako, da so sestavili naključno pot in preverili, ali je pravilna. Po naključju sestaviti pravilno pot dolžine 1000 je seveda nemogoče. Nekateri so namesto tega preverjali pravilnost poti po vsakem dodanem kraju. Tudi to je seveda prepočasno.

Potrebno je le uproabiti, kar smo pripravili do sem! Naloga je sestavljena tako, da vas vodi. Zakaj smo napisali funkcijo izberi, ki ji poleg tega prepovemo nek kraj?

def potnik(zacetek, korakov, povezave):
    pot = [zacetek]
    zadnji = zacetek
    prepovedani = ""  # V začetku ni nobenega prepovedanega kraja
    for _ in range(korakov):
        naslednji = izberi(povezave[zadnji], prepovedani)
        pot.append(naslednji)
        # v naslednjem krogu je prepovedan zadnji, zadnji pa je naslednji
        prepovedani, zadnji = zadnji, naslednji
    return pot

Dodatnih spremenljivk se lahko znebimo, saj je vse zapisano v poti. Zadnji kraj je pot[-1], prepovedan pa je predzadnji, pot[-2]. Vendar imamo problem, da pot v začetku vsebuje le en kraj, torej bi pot[-2] povzročil napako Index out of range. Namesto tega vzamemo prvega izmed zadnjih dveh krajev: pot[-2:][0]. Če seznam vsebuje le en kraj, bo pot[-2:] vrnil ta kraj. V prvem koraku bo tako prepovedan začetni kraj, a to nas nič ne moti.

def potnik(zacetek, korakov, povezave):
    pot = [zacetek]
    for _ in range(korakov):
        pot.append(izberi(povezave[pot[-1]], pot[-2:][0]))
    return pot

Ocena 8

• Napiši funkcijo prestej(s), ki prejme seznam s in vrne slovar, katerega ključi so elementi seznama, pripadajoče vrednosti števila, ki povedo, kolikokrat se je ta element pojavil v seznamu. (Da, dovoljeno je uporabljati poljubne funkcije, ki jih najdete v Pythonovih vdelanih modulih).

Eh.

from collections import Counter

def prestej(pot):
    return Counter(pot)

ali

from collections import Counter

prestej = Counter

ali

from collections import Counter as prestej

• Napiši funkcijo pristej_slovar(s, t), ki k slovarju s prišteje slovar t in ne vrne ničesar. Vrednosti v obeh slovarjih so števila. Funkcija k slovarju s doda vse ključe, ki so v t in jih ni bilo v s ter njihove pripadajoče vrednosti. Pri ključih, ki se pojavijo v obeh slovarjih, pa je v s vsota pripadajočih vrednosti. (Da, funkcija počne isto kot v domači nalogi Županske volitve, in jo lahko skopiraš od ondod.)

Nič novega.

def pristej_slovar(s, t):
    for e in t:
        if e not in s:
            s[e] = 0
        s[e] += t[e]

• Napiši funkcijo pomembnost(potnikov, korakov, povezave, normaliziraj). Argument potnikov je število potnikov, korakov je število korakov, ki jih naredi vsak od njih, in povezave so povezave. Funkcija torej potnikov-krat sestavi naključno pot (uporabljaj funkcije, ki jih že imaš!), da naredijo korakov korakov po podanih povezavah. Kot rezultat vrne slovar, katerega ključi so imena krajev, vrednosti pa povedo, kolikokrat so vsi potniki skupaj obiskali posamezni kraj.

  Argument normaliziraj je lahko True ali False. Če je False, funkcija pove, kolikokrat je bil obiskan vsak kraj. Če je True, pa število obiskov deli s skupnim številom obiskov vseh krajev, tako da je vsota vseh vrednosti v slovarju enaka 1.

Sestavljamo poti (za to imemo potnike), preštevamo ponovitve krajev (za to imamo prestej) in seštevamo te slovarje (za to imamo pristej_slovar).

Če je potrebno še normalizirati, pa sum(stevec.values()) pove, koliko je vseh krajev, potem pa vsako vrednost delimo s to vsoto.

def pomembnost(potnikov, korakov, povezave, normaliziraj):
    stevec = {}
    for _ in range(potnikov):
        pot = potnik(random.choice(list(povezave)), korakov, povezave)
        pristej_slovar(stevec, prestej(pot))

    if normaliziraj and stevec:
        vseh = sum(stevec.values())
        for k, v in stevec.items():
            stevec[k] = v / vseh
    return stevec

Ocena 9

• Napiši funkcijo razsiri(kraji, povezave), ki dobi množico krajev in slovar povezav. Vrne množico, v kateri so vsi kraji, ki so sosedi podanih krajev in niso že vsebovani v množici kraji.

  Klic razsiri({"Ljubljana", "Lenart", "Žužemberk"}) vrne množico, v kateri so vsi kraji, ki so na spodnji sliki izpisani z belo.

  

Naredimo prazno množico in v njo dodajamo vse množice sosedov krajev. Na koncu od te množice odštejemo množico krajev, saj naloga pravi, da teh ne sme biti v rezultatu.

def razsiri(kraji, povezave):
    sosedi = set()
    for kraj in kraji:
        sosedi |= povezave[kraj]
    return sosedi - set(kraji)

• **Napiši funkcijo razdalja(kraj1, kraj2, povezave), ki prejme imeni dveh krajev in slovar povezav. Kot rezultat vrne dolžino najkrajše poti iz kraj1 v kraj2