Advent of code

◂ 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).
  1. code.py
  2. code_part1_optim.py
  3. code_part1_optim_numpy.py
  4. code_part1_optim_tabs.py
  5. diff_bitShift.diffy
from math import sumprod

with open("input.txt", 'r', encoding='utf-8') as f:
    lines = [int(line[:-1]) for line in f.readlines()]

def next_pseudorandom_tabs(tabs):
    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

NB_TIMES_NEW_VALUE = 2000

# Précalculons le mélange de bits après 2000 opérations
tabs = [ [1 if (k == i) else 0 for k in range(24)] for i in range(24)]   # matrice diag ! numpy à la rescousse ?
for i in range(NB_TIMES_NEW_VALUE):
    tabs = next_pseudorandom_tabs(tabs)

numbers_sum = 0
for initial_number in lines:
    #bits = [(initial_number >> bit) & 1 for bit in range(23, -1, -1)]   # conversion en tableau de bits façon matheuse
    bits = [int(c) for c in bin(initial_number)[2:].rjust(24, '0')]      # mais même temps qu'avec fonction bin()
    last_val_bits = [ sumprod(bits, tab) % 2  
                      for tab in tabs ]
    numbers_sum += int("".join(str(b) for b in last_val_bits), 2)       # conversion en décimal
print()

print("Réponse partie 1:", numbers_sum)