Day 15: Rambunctious Recitation

(Povezava na nalogo)

Naloga ni nek programerski presežek, zahteva pa, da se spomnimo, česa ne smemo početi s seznamei, temveč zahteva slovarje.

Zaporedje se začne s številkami

initial = 0, 8, 15, 2, 12, 1, 4

Vsak naslednji člen dobimo iz prejšnjega:

Prvi del naloge sprašuje po 2020-tem členu, drugi pa po 30-milijontem.

Rešitev

Nevarna skušnjava, ki pa ji lahko podležejo le manj izkušeni, je shranjevati zaporedje in takrat, ko nas zanima, koliko časa je minilo od zadnje pojavitve števila, le-to v resnici iskati po zaporedju.

Zaporedja v resnici ni potrebno shranjevati, pač pa si moramo za vsako število zapomniti, kdaj se je zadnjič pojavilo.

Vsa stvar je nekoliko zavozlana: prejšnje število smemo dodati šele po tem, ko že izračunamo naslednje. Ko razvozlamo, pa je rešitev kar kratka.

last_spoken = {}

next = None
for turn in range(2021):
    number = next
    next = initial[turn] if turn < len(initial) else turn - last_spoken.get(number, turn)
    if number is not None:
        last_spoken[number] = turn
        
number
289

V drugem delu nadaljujemo odtod naprej.

for turn in range(2021, 30000001):
    number = next
    next = turn - last_spoken.get(number, turn)
    last_spoken[number] = turn
    
number
1505722

Trik je, očitno, da nam v drugem delu ni več potrebno preverjati, ali vzeti naslednji člen iz začetnega zaporedja. Zaradi tega je program za kako tretjino hitrejši.

Seveda bi lahko že začetni del razdelili v dve zanki, vendar ... vse skupaj je potem še bolj sitno zavozlano. Tako je bilo lažje.