◂ 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
import numpy as np
NB_TIMES_NEW_VALUE = 2000
with open("input.txt", 'r', encoding='utf-8') as f:
lines = [int(line[:-1]) for line in f.readlines()]
def get_transform_matrix():
tabs = list(np.identity(24, int))
tabs = [ [tabs[i][k]^tabs[i+6][k] for k in range(24)] for i in range(18)] + tabs[18:]
tabs = tabs[:5] + [ [tabs[i][k]^tabs[i+5][k] for k in range(24)] for i in range(19)]
tabs = [ [tabs[i][k]^tabs[i+11][k] for k in range(24)] for i in range(13)] + tabs[13:]
return tabs
transform_matrix = get_transform_matrix()
multiple_trans_matrix = np.linalg.matrix_power(transform_matrix, NB_TIMES_NEW_VALUE) % 2
POWERS_OF_2 = 1 << np.arange(23, -1, -1)
bits_sums = 24 * [0]
for initial_number in lines:
bits = [int(c) for c in np.binary_repr(initial_number, 24)]
bits_sums += multiple_trans_matrix @ bits % 2
print("Réponse partie 1:", bits_sums @ POWERS_OF_2)