Day 22: Crab Cups

(Povezava na nalogo)

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.

Prvi del

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.

initial = "389125467"
state = list(map(int, initial))

for round in range(100):
    current, removed, state = state[0], state[1:4], state[4:]
    place = current - 1 or 9
    while place in removed:
        place = place - 1 or 9
    pi = state.index(place) + 1
    state[pi:pi] = removed
    state.append(current)
    
pos = state.index(1)
state = state[pos + 1:] + state[:pos]
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.

Drugi del

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.

Krožni seznam

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.

initial = "389125467"
state = list(map(int, initial))

circle = [None] * (len(state) + 1)
for ta, potem in zip(state, state[1:] + state[:1]):
    circle[ta] = potem

Dobimo, kar je treba.

circle
[None, 2, 5, 8, 6, 4, 7, 3, 9, 1]

Igra

Zdaj pa pripravimo funkcijo, ki kot argument dobi gornjo strukturo in število korakov.

def run(circle, rounds):
    last_cup = len(circle) - 1
    current = state[0]
    for round in range(rounds):
        a = circle[current]
        b = circle[a]
        c = circle[b]

        next3 = (a, b, c)
        where = current - 1 or last_cup
        while where in next3:
            where = where - 1 or last_cup

        circle[current] = circle[c]
        circle[c] = circle[where]
        circle[where] = a
        
        current = circle[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.

To postorimo v treh vrsticah:

Na koncu še premaknemo current na kozarec, ki mu sledi.

Prvi del

Za prvi del pokličemo gornjo funkcijo, začnemo pri kozarcu, ki sledi 1, gremo po krogu in si beležimo številke.

run(circle, 100)

i = circle[1]
res = ""
for _ in range(8):
    res += str(i)
    i = circle[i]
    
res
'67384529'

Drugi del

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.

last_cup = 1000000
circle = [None] * 10 + list(range(11, last_cup + 1))
for ta, potem in zip(state, state[1:] + state[:1]):
    circle[ta] = potem

circle[state[-1]] = 10
circle.append(state[0])

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.

run(circle, 10000000)

a = circle[1]
b = circle[a]

a * b
149245887792