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

def next_pseudorandom_sets(sets):
    sets = [sets[i].symmetric_difference(sets[i+6]) for i in range(18)] + sets[18:]
    sets = sets[:5] + [sets[i].symmetric_difference(sets[i+5]) for i in range(19)]
    sets = [sets[i].symmetric_difference(sets[i+11]) for i in range(13)] + sets[13:]
    return sets

NB_TIMES_NEW_VALUE = 2000

# Précalculons le mélange de bits après 2000 opérations
sets = [set([i]) for i in range(24)]
for i in range(NB_TIMES_NEW_VALUE):
    sets = next_pseudorandom_sets(sets)

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 = [ sum(bits[k] for k in the_set)  % 2  
                      for the_set in sets ]
    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)