◂ 22 décembre 2024 ▸
Monkey Market : Des valeurs qui se modifient selon un processus de type génération pseudoaléatoire, on doit repérer des séquences de variations qui donnent la meilleure somme.
2681088
4082700
13359711
14520022
⋮
L'optimisation (assez efficace !) de la partie 1 consiste — après avoir remarqué qu'on ne fait que des XOR entre certains bits — à regarder après 2000 itérations quels bits sont pris en compte où.
Il suffit ensuite de caculer, pour chaque nombre de l'input, les bons bits et trouver sa 2000e valeur du processus, sans avoir eu besoin d'itérer.
J'ai essayé avec des sets, des listes de 0/1, et des listes de booléens ; les sets gagnent d'une très légère avance.
Puis j'ai essayé avec numpy, puisque finalement on peut multiplier la matrice obtenue par elle-même, et c'est un peu plus rapide.
bitShift : Aucune différence, ou légèrement pire, si on remplace les n * 2**k par des shifts n << k, et le % 2**k par & (2**k - 1).
- code.py
- code_part1_optim.py
- code_part1_optim_numpy.py
- code_part1_optim_tabs.py
- diff_bitShift.diffy
# Aucun gain de temps avec du bit shifting, c'est peut-être même très légèrement pire !
def mix(a,b): def mix(a,b):
return (a ^ b) % (2**24) | return (a ^ b) & ((1 << 24) - 1)
def next_pseudorandom_number(n): def next_pseudorandom_number(n):
n = mix(n, n * 64) | n = mix(n, n << 6)
n = mix(n, n // 32) | n = mix(n, n >> 5)
n = mix(n, n * 2048) | n = mix(n, n << 11)
return n return n