Imamo oštevilčene kozarce, postavljene v krog. Razpored števil in kozarec, pri katerem začnemo, sta v podatkih. V primeru na sliki je določeno, da začnemo pri kozarcu 3.
V vsakem koraku naredimo tole.
Gornji recept ponovimo stokrat. Kakšen je vrstni red kozarcev od 1 naprej?
Da se ne hecamo brez potrebe s tem, ali se trije kozarci, ki sledijo trenutnemu, že ovijajo okrog, bomo vrteli seznam: trenutni element bo vedno ničti. Ko gremo na naslednji element, bomo v resnici dali trenutni element na konec.
Dobimo takšen program.
= "389125467"
initial = list(map(int, initial))
state
for round in range(100):
= state[0], state[1:4], state[4:]
current, removed, state = current - 1 or 9
place while place in removed:
= place - 1 or 9
place = state.index(place) + 1
pi = removed
state[pi:pi]
state.append(current)
= state.index(1)
pos = state[pos + 1:] + state[:pos]
state print("".join(map(str, state)))
67384529
V state
prepišemo števila, pretvorjena v
int
-e. Nato v zanki vzamemo prvo število, naslednja tri in
ostala. Poiščemo mesto za vstavljanje; place
bo trenutni -
1, oziroma 9
, če bi trenutni s tem postal 0. V zanki nato
poskrbimo za primer, ko je place
eden od odstranjenih
kozarcev.
Nato odkrijemo, kjer v seznamu je kozarec, za katerim morajo biti
trije kozarci, ki jih premikamo (pi
). V mesto med
pi
in pi
- torej točno za pi
,
damo odstranjene kozarce, na konec pa še trenutnega. Ne spreglejmo, da
state
pred temu prirejani vsebuje samo preostale kozarce,
brez prvega (trenutnega) in tistih treh, ki mu sledijo.
Po stotih potezah poiščemo kozarec 1. Seznam prevrtimo tako, da imamo najprej kozarca 1 do konca in nato kozarce od začetka do tega kozarce. Števila pretvorimo v števke, združimo v niz in izpišemo.
Slaba novica: kozarcu 9 sledijo še kozarci od 10 do milijon. Poleg tega ne naredimo sto korakov temveč deset milijonov korakov.
Gornji program nima šans. Lahko ga prepišemo v numpy, pa se bo izvajal uro ali dve. Dodamo trik ali dva, pa bo morda dvakrat ali trikrat hitrejši.
Tu je potrebno uporabiti drugačen pristop. Sprogramirali ga bomo na tem, krajšem primeru, potem pa ga dopolnili do milijonov.
Osnovni problem gornjega programa je, da kopira sezname v nov seznam. Tudi če se temu izognemo in premikamo števila znotraj nekega seznama, jih je še vedno potrebno premikati. In s premikanjem milijona števil je veliko dela. Tudi če ne vrtimo seznama, tako da je trenutni element vedno na začetku, ne bomo nič na boljšem, saj je treba premikati elemente seznama, ko odstranjujemo in vstavljamo te tri elemente.
Potrebujemo nekaj, kar Python, kolikor vem, ni vdelano v Python: seznam. :) Pythonovi seznami so bolj tabele, array-i. Potrebujemo povezan seznam. Za vsak kozarec moramo vedeti, kateri kozarec mu sledi.
Devet kozarcev bomo predstavili s seznamom dolžine 10; prvi element bo za okras. No, za praktičnost. Element 3, recimo, vsebuje 8, ker kozarcu 3 sledi kozarec 8.
To nam poenostavi prestavljanje kozarcev, saj je potrebno, kot bomo videli, spremeniti le štiri številke, ne pa prestavljati milijona elementov.
Najprej sestavimo tabelico, kot je gornja. Sestavimo tabelo
None
-ov. Nato se zapeljemo čez vse pare
(ta, potem)
in zabeležimo, da za ta
pride
potem
. zip
sestavimo tako, da za
potem
prestavimo prvi element ("seznam, ki vsebuje samo
prvi element") na konec seznama.
= "389125467"
initial = list(map(int, initial))
state
= [None] * (len(state) + 1)
circle for ta, potem in zip(state, state[1:] + state[:1]):
= potem circle[ta]
Dobimo, kar je treba.
circle
[None, 2, 5, 8, 6, 4, 7, 3, 9, 1]
Zdaj pa pripravimo funkcijo, ki kot argument dobi gornjo strukturo in število korakov.
def run(circle, rounds):
= len(circle) - 1
last_cup = state[0]
current for round in range(rounds):
= circle[current]
a = circle[a]
b = circle[b]
c
= (a, b, c)
next3 = current - 1 or last_cup
where while where in next3:
= where - 1 or last_cup
where
= circle[c]
circle[current] = circle[where]
circle[c] = a
circle[where]
= circle[current] current
Kar iz seznama razberemo številko zadnjega kozarca, ki ga potrebujemo takrat, ko iščemo kozarec s številko, nižjo od trenutnega.
Prvi začetni kozarec je state[0]
. Nato v zanki najprej
poberemo številke naslednjih treh kozarcev (a
,
b
. c
).
V where
izračunamo številko kozarca, za katerega je
potrebno postaviti a
, b
in c
. To
gre podobno kot prej, le da namesto 9
uporabljamo
last_cup
.
Sledijo prevezave.
a
, b
in
c
, ki sledijo kozarcu current
, mora kozarcu
current
po nove, slediti tisto, kar je prej sledilo
c
-ju.a
, b
inc
je potrebno vriniti med where
in kozarec,
ki sledi where
.To postorimo v treh vrsticah:
current
po novem sledi kozarec, ki trenutno
sledi kozarcu c
(circle[c]
);c
sledi kozarec, ki je prej sledil kozarcu
where
;where
pa kozarec a
.Na koncu še premaknemo current
na kozarec, ki mu
sledi.
Za prvi del pokličemo gornjo funkcijo, začnemo pri kozarcu, ki sledi
1
, gremo po krogu in si beležimo številke.
100)
run(circle,
= circle[1]
i = ""
res for _ in range(8):
+= str(i)
res = circle[i]
i
res
'67384529'
Najprej pripravimo krog. Najprej desetkrat None
, potem
pa na mesta od 10 do last_cup
postavimo številke od 11 do
last_cup + 1
, tako da vsaka številka kaže na naslednjo.
Temu sledi enaka zanka, kot zgoraj. Na koncu še povežemo seznama: zadnji
element začetnega zaporedja mora kazati na 10
(začetek
dodatnih elementov), zadnji dodatni element pa kaže na prvi element
začetnega zaporedja.
= 1000000
last_cup = [None] * 10 + list(range(11, last_cup + 1))
circle for ta, potem in zip(state, state[1:] + state[:1]):
= potem
circle[ta]
-1]] = 10
circle[state[0]) circle.append(state[
Zdaj poženemo zahtevan milijon ciklov. Poberemo številko kozarca, ki
sledi 1
in številko kozarca, ki sledi temu kozarcu, ter ju,
kot zahteva naloga, zmnožimo.
10000000)
run(circle,
= circle[1]
a = circle[a]
b
* b a
149245887792