Razlike v hitrosti ljubljanskih kolesarjev ne izhajajo toliko iz
njihovih hitrosti po normalnem terenu kot iz njihove spretnosti.
Konkretno, kolesar za vsako povezavo potrebuje 4
časovne
enote + pribitek zaradi različnih ovir. Pribitki so različni za vsakega
kolesarja. Opisani so v slovarju; če so pri nekem konkretnem kolesarju
pribitki enake
{"črepinje": 2, "bolt": 4, "stopnice": 1, "pešci": 5}
, bo
za povezavo, ki zahteva veščini črepinje in pešci
potreboval 4 + 2 + 5 = 11 časovnih enot.
V vseh funkcijah uporabljaj (globalno) spremenljivko
zemljevid
. (Torej, v funkciji mirno uporabljaj
zemljevid
, kot da bi ga funkcija dobila kot argument.)
Zemljevid bo vseboval povezave v obe smeri (ključa (A, B)
in (B, A)
). Pripadajoče vrednosti bodo množice veščin, kot
smo navajeni.
Argument pribitki
je vedno slovar, ki pove, koliko
pribitka na čas povzroči posamezna veščina. Vsi kolesarji so veterani
ljubljanskih kolesarskih poti in torej obvladajo vse potrebne veščine.
Vse povezave na poti bodo vedno obstajale.
cas_za_povezavo(povezava, pribitki)
naj vrne čas, ki ga
kolesar potrebuje za podano povezavo.cas(pot, pribitki)
vrne čas, ki ga kolesar potrebuje za
podano pot.povezava_spotike(pribitki)
vrne tisto povezavo na
zemljevidu (npr. terko (R, I)
, ki kolesarju vzame največ
časa. Če je takšnih več, vrne tisto, ki je zadnja po abecedi (in
obrnjena tako, da je zadnja po abecedi, recimo (M, I)
in ne
(I, M)
. (Glede tega se ne vznemirjaj preveč; zgodilo se bo
samo od sebe.))cas_za_povezavo
Vrniti moramo 4 + vsoto pribitkov za vse veščine, ali, če prevedemo iz slovenščine v Python,
def cas_za_povezavo(povezava, pribitki):
return 4 + sum(pribitki[vescina] for vescina in zemljevid[povezava])
Tisti, ki so mu generatorski izrazi magija, gre pač po starem in piše
def cas_za_povezavo(povezava, pribitki):
= 4
cas for vescina in zemljevid[povezava]:
+= pribitki[vescina]
cas return cas
Vrniti moramo čas za povezavo za vse povezave na poti. Na hitro tako
from itertools import pairwise
def cas(pot, pribitki):
return sum(cas_za_povezavo(povezava, pribitki) for povezava in pairwise(pot))
Na počasi pa tako
def cas(pot, pribitki):
= 0
skupni_cas for povezava in pairwise(pot):
+= cas_za_povezavo(povezava, pribitki)
skupni_cas return skupni_cas
Ob tem je potrebno omeniti tri stvari.
V funkciji cas
kličemo funkcijo
cas_za_povezavo
. Kdor je ne, bo pač moral znotraj te, druge
funkcije, ponoviti vse, kar je naredil že v prvi. Če bo enako ravnal v
vseh naslednjih, bo vsaka funkcija dolga skoraj toliko, kot vse prejšnje
skupaj. Učeno se temu reče eksponentna rast. :)
Uporabili smo funkcijo pairwise
, ki jo prijazno
ponuja modul itertools
. Funkcija je stara dve leti (Python
3.10). Poprej bi namesto pairwise(pot)
pisali
zip(pot, pot[1:])
.
Spremenljivko, v katero seštevamo čas, smo poimenovali
skupni_cas
. Lahko bi jo tudi cas
, vendar je
tako ime že funkciji, ki jo ravnokar pišemo, zato se temu - čeprav tule
sicer ne bi povzročalo nobenih sitnosti - raje izognemo. V prejšnji
funkciji smo mirno uporabili ime cas
, pa tudi v naslednji
ga bomo; kako orodje za preverjanje "lepote" programov (pylint) bi ob
tem pogodrnjalo.
V potu svojega obraza napišemo takšno funkcijo.
def povezava_spotike(pribitki):
= naj_cas = None
naj_povezava for povezava in zemljevid:
= cas_za_povezavo(povezava, pribitki)
cas if naj_povezava is None or cas > naj_cas or cas == naj_cas and povezava > naj_povezava:
= povezava
naj_povezava = cas
naj_cas return naj_povezava
"Garanje" je pogoj: povezavo si zapomnimo kot povezavo spotike, če
doslej ni bilo še nobene (naj_povezava is None
) ali pa je
čas za povezavo, ki jo trenutno opazujemo, večji od najdaljšega doslej
(cas > naj_cas
) ali pa je enak (tega dela pogoja ne
smemo pozabiti!) in je ta povezava po abecedi za najhujšo doslej
(cas == naj_cas and povezava > naj_povezava
).
Za začetek dva komentarja, potem izboljšave.
for povezava in zemljevid:
in ne
for povezava in zemljevid.keys():
ali celo
povezave = list(zemljevid)
in potem
for povezava in povezave:
. S kratkimi programi je manj dela
pri pisanju, branju, popravljanju in vzdrževanju.
Pogoj deluje zato, ker and
veže močneje kot
or
. Vseeno bi tule zaradi preglednosti veljalo postaviti
oklepaje - da je vsakemu, ki bere, hitreje jasno, kako je sestavljen
pogoj:
naj_povezava is None or cas > naj_cas or (cas == naj_cas and povezava > naj_povezava)
.
Še lepše je pogoj razbiti v tri vrstice; na konec vrstic postavimo
\
, da Python ve, da se vrstica nadaljuje.
def povezava_spotike(pribitki):
= naj_cas = None
naj_povezava for povezava in zemljevid:
= cas_za_povezavo(povezava, pribitki)
cas if naj_povezava is None \
or cas > naj_cas \
or cas == naj_cas and povezava > naj_povezava:
= povezava
naj_povezava = cas
naj_cas return naj_povezava
Nalogo lahko rešimo tudi brez nepotrebnega švicanja, če znamo
uporabiti max
z key
in če znamo napisati
lambdo.
def povezava_spotike(pribitki):
return max(zemljevid, key=lambda povezava: (cas_za_povezavo(povezava, pribitki), povezava))
Če funkciji max
z argumentom key
podamo
funkcijo, elementov (torej ključev slovarja zemljevid
) ne
bo primerjala po njihovih vrednostih, temveč po vrednostih, ki jih zanje
vrne podana funkcija. max
torej ne bo vrnil največjega
elementa temveč element, za katerega podana funkcija vrne največjo
vrednost. Na prvi pogled bi potrebovali
key=lambda povezavа: cas_za_povezavo(povezava, pribitki)
,
vendar bo to primerjalo le čase, ne pa tudi povezav po abecedi, če so
časi enaki. Zato naša lambda vrača terko z dvema stvarema: časom in
povezavo. Tako bo max
funkcije z enakim časom primerjal še
po drugem elementu terke, povezavi. Ker naloga zahteva, da vrnemo
povezavo, ki je zadnja po abecedi, bo max
izbral pravo.
Če si želimo poenostaviti lambdo, pa lahko max
-u podamo
povezave, ki so urejene padajoče po abecedi. max
v primeru,
da je največjih več elementov, vrne tistega, na katerega naleti
prej.
def povezava_spotike(pribitki):
return max(sorted(zemljevid, reverse=True), key=lambda povezava: cas_za_povezavo(povezava, pribitki))
Ta rešitev je sicer počasnejša, ker mora urejati zemljevid. Če ni velik, nam je za to vseeno. Po drugi strani pa program zaradi tega tudi ni nič krajši (nasprotno: celo podaljšal se je!), torej je bila prejšnja rešitev pravzaprav boljša.
urnik(pot, pribitki)
vrne slovar, katerega ključi so
točke, ki jih kolesar obišče, pripadajoče vrednosti pa časi (od začetka
poti), ko je kolesar prvič v tej točki.
skupinski_sport(pot, pribitkii)
za razliko od
ostalih funkcij ne prejme slovarja pribitki temveč seznam takšnih
slovarjev (seznam vsebuje vsaj en element). Gre namreč za to, da gre na
pot cela skupina kolesarjev. Ker so uvidevni, se na vsakem križišču
počakajo. Funkcija mora vrniti čas, ki ga bo skupina potrebovala za
podano pot.
tekma(pot, pribitkii)
prav tako dobi seznam
slovarjev, vrniti pa mora indeks kolesarja (od 0
do,
vključno, len(pribitkii) - 1
)), ki bo prvi končal pot. Če
ima enak najhitejši čas več kolesarjev, mora funkcija vrniti
None
.
urnik
V slovar postavimo začetno točko in čas do nje je 0
.
Nato simuliramo korake: gremo po poti, za vsako povezavo prišetejemo čas
in v slovar dodamo ciljno točko povezave in skupni čas do nje - vendar
le, če te točke še ni v slovarju in je torej še ni obiskal.
def urnik(pot, pribitki):
= {pot[0]: 0}
prvic = 0
cas for od, do in pairwise(pot):
+= cas_za_povezavo((od, do), pribitki)
cas if do not in prvic:
= cas
prvic[do] return prvic
Program nam malo skrajša metoda setdefault
, ki doda
ključ in vrednost, če ga še ni, sicer pa ga pusti pri miru. Funkcija
tudi vrne staro vrednost (če je ključ že obstajal) oziroma novo (če ga
še ni bilo). Vendar nas rezultat ne zanima, zato se z njim ne
ukvarjamo.
def urnik(pot, pribitki):
= {pot[0]: 0}
prvic = 0
cas for od, do in pairwise(pot):
+= cas_za_povezavo((od, do), pribitki)
cas
prvic.setdefault(do, cas)return prvic
skupinski_sport
Podobno kot prej moramo tudi zdaj simulirati vožnjo, le da ničesar ne beležimo v slovar. Čas povečamo za največji čas, ki ga potrebuje kateri od kolesarjev.
def skupinski_sport(pot, pribitkii):
= 0
cas for povezava in pairwise(pot):
= 0
naj_cas for pribitki in pribitkii:
= cas_za_povezavo(povezava, pribitki)
ta_cas if ta_cas > naj_cas:
= ta_cas
naj_cas += naj_cas
cas return cas
Za take namene so si v novejših različicah Pythona izmislili mrožji operator (walrus operator). Mnenja o njem so deljena; tudi moje mnenje o njem je deljeno, zato ga na predavanjih ne kažem pogosto. Ampak tule bi ga lahko. :)
def skupinski_sport(pot, pribitkii):
= 0
cas for povezava in pairwise(pot):
= 0
najcas for pribitki in pribitkii:
if (ta_cas := cas_za_povezavo(povezava, pribitki)) > naj_cas:
= ta_cas
naj_cas += naj_cas
cas return cas
Tako ali tako pa se v tej funkciji bolj spodobi uporabi
max
in generatorski izraz.
def skupinski_sport(pot, pribitkii):
= 0
cas for povezava in pairwise(pot):
+= max(cas_za_povezavo(povezava, pribitki) for pribitki in pribitkii)
cas return cas
Ali pa še tole stlačimo kar v sum
.
def skupinski_sport(pot, pribitkii):
return sum(max(cas_za_povezavo(povezava, pribitki) for pribitki in pribitkii)
for povezava in pairwise(pot))
tekma
Čase dobimo s funkcijo cas
, tu ni kaj. Glavna finta
naloge je, kako vrniti None
, če je enako dobrih več
kolesarjev. Takole: naj_cas
bode najboljši čas,
naj_i
pa indeks kolesarja, ki ga je dosegel. Če enak čas
doseže še kdo drug, preprosto nastavimo naj_i
na
None
. Če se kasneje prikaže kdo, ki ima še boljši čas -
prav. Če ne, bomo na koncu pač vrnili None
.
def tekma(pot, pribitkii):
= naj_i = None
naj_cas for i, pribitki in enumerate(pribitkii):
= cas(pot, pribitki)
ta_cas if naj_cas is None or ta_cas < naj_cas:
= ta_cas
naj_cas = i
naj_i elif ta_cas == naj_cas:
= None
naj_i return naj_i
elif
je potreben zato, ker bo tisto, kar je znotraj
if
(morda) nastavilo naj_cas
na
ta_cas
in potem bo drugi pogoj,
ta_cas == naj_cas
že takoj resničen in nastavil
naj_i
na None
.
Alternativa je, da sestavimo seznam časov, poiščemo največjega in
preverimo, kolikokrat se pojavi. Če enkrat, vrnemo indeks, če večkrat,
None
.
def tekma(pot, pribitkii):
= [cas(pot, pribitki) for pribitki in pribitkii]
casi = min(casi)
naj_cas if casi.count(naj_cas) == 1:
return casi.index(naj_cas)
else:
return None
Ker funkcija, ki ne vrne ničesar, vrne None
, bi šlo
tudi
def tekma(pot, pribitkii):
= [cas(pot, pribitki) for pribitki in pribitkii]
casi = min(casi)
naj_cas if casi.count(naj_cas) == 1:
return casi.index(naj_cas)
Vendar se to ne šteje za lepo. Pravilo je, da mora funkcija, ki v
kakem primeru nekaj vrne, nekaj vrniti v vsakem primeru. Z drugimi
besedami, nočemo pisati funkcij, ki imajo v nekaterih scenarijih
return
, v nekaterih pa ga nimajo in za to (brez našega
eksplicitnega return
-a vrnejo None
). V tej
funkciji je stvar očitna, v daljših in bolj razvejanih pa bi kdo
pomislil, da smo v nekaterih scenarijih preprosto pozabili na
return
. Zato je bolj prav, da eksplicitno povemo, da
funkcija v tem in tem primeru vrne None
.
Ta, ki so mu všeč ternarni operatorji (C-jevski ?:
) pa
bo v Pythonu napisal
def tekma(pot, pribitkii):
= [cas(pot, pribitki) for pribitki in pribitkii]
casi = min(casi)
naj_cas return casi.index(naj_cas) if casi.count(naj_cas) == 1 else None
trening(pot, pribitki)
vrne čas, ki ga kolesar
potrebuje za podano pot - podobno kot funkcija cas
. Razlika
je v tem, da se kolesar trenira: vsakič, ko uporabi določeno veščino, se
čas, ki ga bo zanjo potreboval prihodnjič, zmanjša za 5 %. Funkcija mora
vrniti čas in poleg tega tudi dejansko spremeniti slovar
pribitki
: po klicu funkcije morajo biti vrednosti v njem
ustrezno manjše.
zastavice(pot, pribitkii)
simulira igro, v kateri
sodeluje poljubno število kolesarjev. Vsak kolesar ima svoje pribitke,
zato funkcija prejme seznam slovarjev z pribitki. Na vsakem križišču je
zastavica. Kolesar, ki prvi pride v križišče pobere zastavico (in
ostali, ki pridejo v križišče, ne dobijo ničesar). Funkcija naj vrne
seznam, ki ima toliko elementov, kolikor je tekmovalcev: i-ti element
pove, koliko zastavic je pobral i-ti tekmovalec.
Če prideta dva kolesarja v križišče istočasno, dobi zastavico tisti z manjšim indeksom. Tough luck.
Kolesarji poberejo tudi zastavico v prvem križišču. Dobi jo pač ... tisti z najmanjšim indeksom.
trening
Tole je malo kot funkcija cas
, le da še spreminja
vrednosti v slovarju.
def trening(pot, pribitki):
= 0
cas for povezava in pairwise(pot):
for vescina in zemljevid[povezava]:
+= pribitki[vescina]
cas *= 0.95
pribitki[vescina] += 4
cas return cas
Nekoč sem najbrž pridigal o tem, kako vsaka funkcija bodisi nekaj vrne bodisi nekaj naredi (na primer spremeni objekte, ki so ji podani kot argumenti), ne pa oboje. Razen kadar.
No, to je primer funkcije, kjer je to primerno.
zastavice
To se da obrniti na različne načine. Meni se zdi najbolj praktično
iti prek vseh kolesarjev, za vsakega preveriti urnik in v nek slovar
(pobiralci
) za vsako točko beležiti, ob katerem času je
videla najzgodnejšega pobiralca.
Nato sestavimo seznam, ki ga bomo vrnili; dolg je toliko, kolikor je
kolesarjev in ima v začetku same ničle. Gremo čez slovar, v katerem je
za vsako zastavico zapisano, kdo jo je pobral. Ker nas ne zanimajo
zastavice (ključi), gremo le čez values()
; vrednosti so
pari in ker nas tudi časi ne zanimajo več, si zapomnimo le indekse,
for _, i in pobiralci.values()
.
def zastavice(pot, pribitkii):
= {}
pobiralci for i, pribitki in enumerate(pribitkii):
for tocka, cas in urnik(pot, pribitki).items():
if tocka not in pobiralci or cas < pobiralci[tocka][0]:
= (cas, i)
pobiralci[tocka]
= [0] * len(pribitkii)
zastavic for _, i in pobiralci.values():
+= 1
zastavic[i] return zastavic
Alternativni - vzporedno voziti vse kolesarje po poti - se izkaže za daljši.
def zastavice(pot, pribitkii):
= [0] * len(pribitkii)
casi = [0] * len(pribitkii)
zastavic = {pot[0]}
pobrano 0] = 1
zastavic[for povezava in pairwise(pot):
= 0
naj_i for i, pribitki in enumerate(pribitkii):
+= cas_za_povezavo(povezava, pribitki)
casi[i] if casi[i] < casi[naj_i]:
= i
naj_i if povezava[1] not in pobrano:
1])
pobrano.add(povezava[+= 1
zastavic[naj_i] return zastavic
V osnovi je daljši zato, ker smo prej lahko uporabili funkcijo
urnik
, zdaj pa vzdržujemo seznamo časov casi
in jih povečujemo v okviru te funkcije. Namesto slovarja
pobiralci
, katerega ključi so točke, pa imamo tu imamo
množico, ki beleži pobrane zastavice. Torej nismo kaj prida
pridobili.
Če računamo na to, da funkcija urnik
vedno dodaja točke
v slovar v enakem vrstnem redu, lahko funkcijo napišemo tudi tako, da
poberemo urnike vseh kolesarjev in jih zipnemo skupaj. Potem za vsako
točko preverimo, kdo ima v njej najmanjši čas in mu damo zastavico.
def zastavice(pot, pribitkii):
= [urnik(pot, pribitki).values() for pribitki in pribitkii]
urniki = [0] * len(pribitkii)
zastavice for casi in zip(*urniki):
= float("inf")
naj_cas for i, cas in enumerate(casi):
if cas < naj_cas:
= i
naj_i = cas
naj_cas += 1
zastavice[naj_i] return zastavice
Tule je zanimiv zip
. Podati mu moramo vse urnike, kot
argumente, torej nekaj v slogu
zip(urniki[0], urniki[1], urniki[2])
. To bi šlo, če bi bili
trije. Ker pa števila urnikov ne poznamo vnaprej, to ne gre. Pač pa
lahko z zip(*urniki)
povemo, naj elemente seznama
urniki
uporabi kot argumente za funkcijo
zip
.
V bistvu isto dela spodnja funkcija. Če je komu v zabavo brati take stvari, naj se kar poglobi. :)
def zastavice(pot, pribitkii):
return list(map([min(range(len(pribitkii)), key=casi.__getitem__)
for casi in zip(*[urnik(pot, pribitki).values()
for pribitki in pribitkii])].count, range(len(pribitkii))
))
Lenuh vozi po Ljubljani tako, da se v vsakem koraku preprosto odloči za povezavo, ki mu bo vzela najmanj časa. Če je takšnih povezav več, gre v točko, ki je prej po abecedi. Edini pravili sta, da nikoli ne gre po povezavi, po kateri je ravnokar prišel in da nikoli ne gre v slepo ulico (torej v točko, ki ima samo eno povezavo, saj bi to pomenilo, da bi kršil prejšnje pravilo in se vračal po isti povezavi). Seveda se bo izkazalo, da se bo prej ko slej zaciklal. :)
Za potrebe te naloge smeš predpostaviti, da na zemljevidu ni slepih ulic (začasno sta odstranjeni točki E in O.)
cikel(zacetna_tocka, pribitki)
vrne dolžino cikla. Če
se kolesar zacikla tako, da v nedogled ponavlja RDFGIRDFGIRDFGI, je
dolžina cikla 5. (V dolžino cikla seveda niso vštete točke, ki jih je
prevozil, preden se je zaciklal.)Pazi: ko se kolesar prvič znajde v točki, v kateri je že bil, to še ne pomeni, da se je zaciklal.
Ko pride kolesar tretjič na isto povezavo, se je gotovo zaciklal. Prvič in drugič je šel morda v različnih smereh, vtretje pa je konec. Zato bomo funkcijo napisali tako, da bo kolesar najprej naredil dvakrat toliko korakov, kolikor je povezav. Nato si bomo zapomnili, katero povezavo je pravkar prevozil. Potem nadaljujemo simulacijo in štejemo korake do takrat, ko ponovno prevozi to isto povezavo.
from itertools import count
def cikel(tocka, pribitki):
def najugodnejsa(tocka, prejsnja):
return min(((t, nasl) for (t, nasl), vescine in zemljevid.items()
if t == tocka and nasl != prejsnja),
=lambda povezava: cas_za_povezavo(povezava, pribitki))[1]
key
= None
prejsnja for _ in range(2 * len(zemljevid)): # dovolj bi bilo 3 * število točk (se mi zdi)
= najugodnejsa(tocka, prejsnja), tocka
tocka, prejsnja
= (prejsnja, tocka)
zacetek for korakov in count(1):
= najugodnejsa(tocka, prejsnja), tocka
tocka, prejsnja if (prejsnja, tocka) == zacetek:
return korakov
V drugi zanki smo uporabili funkcijo count
. Podobna je
funkciji range
, le da šteje od 0
oziroma od
vrednosti, ki jo podamo kot argument, pa do neskončno.
Za računanje najugodnejše povezave smo si pripravili ločeno funkcijo
najugodnejsa
, saj jo potrebujemo na dveh mestih. V njej smo
uporabili min
in lambdo
in generatorske
izraze. Šlo bi seveda tudi brez - ampak zdaj smo pri oceni 9 in tole bi
moral biti že najmanjši problem. Lahko pa bi jo seveda sprogramirali na
daljši način - ta funkcija ni bistvo te naloge.
Šlo bi tudi z eno zanko: po 2 * len(zemljevid)
korakih
si zapomnimo povezavo in ko nanjo naletimo naslednjič vrnemo število
korakov, ki smo jih naredili po 2 * len(zemljevid)
korakih.
def cikel(tocka, pribitki):
def najugodnejsa(tocka, prejsnja):
return min(((t, nasl) for (t, nasl), vescine in zemljevid.items()
if t == tocka and nasl != prejsnja),
=lambda povezava: cas_za_povezavo(povezava, pribitki))[1]
key
= None
prejsnja = None
zacetek for korak in count(1):
if korak == 2 * len(zemljevid):
= (prejsnja, tocka)
zacetek = najugodnejsa(tocka, prejsnja), tocka
tocka, prejsnja if (prejsnja, tocka) == zacetek:
return korak - 2 * len(zemljevid) + 1
Kakorkoli. Meni je bolj všeč prejšnja različica, iz katere je bolj jasno, kako teče program.
Tekmovanje, ki ga simulira zastavice, je tako zapleteno, da smo izgleda narobe razumeli navodila. Tekmovanje v resnici deluje na izpadanje. Na vsakem križišču je zastavica. Vsak kolesar ima svojo pot in svoje pribitke. Ko kolesar pride na križišče, vzame zastavico. (To velja tudi za križišče, v katerem začne pot.) Če zastavice na križišču ni več, pa izpade - ne nadaljuje poti, ne pobira novih zastavic. Če istočasno pride v križišče več kolesarjev, pobere zastavico kolesar z najmanjšim indeksom; ostali so izločeni
izpadanje(poti, pribitkii)
prejme seznam poti in seznam
pribitkov. Vrniti mora seznam indeksov izpadlih kolesarjev, urejenih po
vrstnem redu izpadanja. Če istočasno izpadeta dva kolesarja, mora biti
manjši indeks zapisan pred večjim.Kolesar, ki prevozi svojo predvideno pot, ne da bi izpadel, ni izpadel. Ostanejo lahko torej vsi kolesarji. Lahko pa se zgodi tudi, da vsi izpadejo.
Pripravili si bomo seznam, v katerem bomo beležili vse kolesarje, ki
so še aktivni. Seznam bo sestavljan iz trojk
(cas, indeks, korak)
. Trojka pove, da bo ob času
cas
kolesar z indeksom indeks
končal svoj
korak z zaporedno številko korak
. Za vsakega kolesarja bomo
imeli v vsakem koraku simulacije v seznamu en element, ki bo
predstavljal to, kar kolesar počne trenutno.
Funkcija je takšna.
def izpadanje(poti, pribitkii):
= [(0, i, 0) for i, pot in enumerate(poti)]
cas_ind_kor = set()
pobrano = []
izpadli while cas_ind_kor:
= min(cas_ind_kor)
cas, ind, korak
cas_ind_kor.remove((cas, ind, korak))= poti[ind]
pot = pot[korak]
tocka if tocka in pobrano:
izpadli.append(ind)else:
pobrano.add(tocka)+= 1
korak if korak < len(pot):
+ cas_za_povezavo((tocka, pot[korak]), pribitkii[ind]), ind, korak))
cas_ind_kor.append((cas return izpadli
V začetku so vsi kolesarji ob času 0 na ničtem koraku. Množica
pobranih zastavic, pobrano
je prazna, izpadel ni nihče.
Nato pride zanka, ki teče, dokler imamo še kakega aktivnega kolesarja. V njej poberemo minimalni element - to je, trojko z najmanjšim prvim elementom, najmanjšim časom, skratka, trojko, ki ustreza kolesarju, ki bo prvi končal "potezo". Če ima enak čas več kolesarjev, bomo dobili tistega z nižjim indeksom. To trojko odstranimo iz seznama.
Nato si v pot
preberemo pot, ki jo opravlja trenutni
kolesar in v tocka
njegovo pravkar doseženo točko. Če je ta
točka med tistimi, ki nimajo več zastavice, je izpadel. Sicer pa dodamo
zastavico med pobrane. Povečamo število korakov tega kolesarja in če
njegova pot s tem ni končana, ga vrnemo v množico aktivnih kolesarjev,
vendar s povečanim časom in korakom.
To je to.
Pri Algoritmih in podatkovnih strukturah boste izvedeli, da je za
takšen seznam kolesarjev primernejša podatkovna struktura z imenom
kopica (heap). Njeni osnovni operaciji sta
push
(dodajanje novega elementa) in pop
("iskanje" in odstranjevanje najmanjšega). Iskanje smo dali pod
narekovaje, ker je kopica tako imenitna podatkovna struktura, da je
najmanjši element vedno na začetku; ko ga odstranimo, pa ga zna hitro
zamenjati z drugim najmanjšim, pa tudi dodajanje na ustrezno mesto je
hitro.
Rešitev z uporabo kopice je praktično enaka gornji, le da v začetku
spremenimo seznam v kopico (heapify
), vrstici, v kateri
poiščemo in pobrišemo najmanjši element zamenjamo s
heappop
, dodajanje pa s heappush
.
from heapq import heappop, heappush, heapify
def izpadanje(poti, pribitkii):
= [(0, i, 0) for i, pot in enumerate(poti)]
cas_ind_kor
heapify(cas_ind_kor)= set()
pobrano = []
izpadli while cas_ind_kor:
= heappop(cas_ind_kor)
cas, ind, korak = poti[ind]
pot = pot[korak]
tocka if tocka in pobrano:
izpadli.append(ind)else:
pobrano.add(tocka)+= 1
korak if korak < len(pot):
+ cas_za_povezavo((tocka, pot[korak]), pribitkii[ind]), ind, korak))
heappush(cas_ind_kor, (cas return izpadli