python, on oublie toute dignité

Je suis tombé dans le piège de la solution qui ne scale pas en deuxième partie. Pas grave, on s'adapte.

Pour les deux parties, pour éviter un parsing laborieux, j'ai transformé l'input en code. Car à bien y regarder, c'est du code :)

La solution naïve ne scale pas car passé une certaine taille (32bit je crois) l'arithmétique des grands entiers sort du processeur, doit repasser par la mémoire et devient très très lente.

Chez moi c'était très net : les 500 premiers rounds sont fulgurants, moins de 1s, puis chaque round prends presque une seconde. Pour faire les 100000, en admettant avoir assez de RAM, il faudrait donc une grosse heure à 100% de CPU. Je n'ai pas cette patience.

L'astuce pour passer à l'échelle est de limiter la taille des nombres manipulés en appliquant l'arithmétique modulaire. Chaque singe à son diviseur (un nombre premier mais je crois pas que ça joue). Donc au lieu d'avoir l'item sous forme de nombre, on le transforme en une liste de restes de division, un pour chaque singe.

part 1

Je vous épargne le code complet de la première partie qui est en gros celui de la deuxième partie en un peu plus simple.

input

from collections import deque
M = [
(
 deque([ 84, 72, 58, 51])
 , lambda old: old * 3
 , lambda x: 7 if divmod(x,13)[1] else 1
)
# ...
# same for all monkeys
# ...
]

part 2

input

from collections import deque
PRIMES = (13,2,7,17,5,11,3,19)
def mods(x):
 return [x%i for i in PRIMES]
M = [
[
 deque(mods(x) for x in [ 84, 72, 58, 51])
 , lambda old: [((o%i)*(3%i))%i for (o,i) in zip(old,PRIMES)]
 , lambda x: 7 if x[0] else 1
 ,0
],[
 deque(mods(x) for x in [ 88, 58, 58 ])
 , lambda old: [((o%i)+(8%i))%i for (o,i) in zip(old,PRIMES)]
 , lambda x: 5 if x[1] else 7
 ,0
]# ...
# same for all monkeys
# ...
]

main loop

import sys
mod = __import__(sys.argv[1])
M = mod.M
for r in range(10*1000):
 print(f"\rround {r+1}",end='')
 for m in M:
 items = m[0]
 m[3] += len(items)
 for _ in range(len(items)):
 i = items.popleft()
 ni = m[1](i) #// 3
 nm = m[2](ni)
 M[nm][0].append(ni)
print()
L=list(sorted(m[3] for m in M))
print(L[-1]*L[-2])