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 collections import Counter

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 mix(a,b):
    return (a ^ b) % (2**24)

def next_pseudorandom_number(n):
    n = mix(n, n * 64)
    n = mix(n, n // 32)
    n = mix(n, n * 2048)
    return n


# Part 1 : sum last pseudorandom numbers after NB_TIMES_NEW_VALUE
numbers_sum = 0

# Part 2 : count bananas provided for each 4-changes sequence
bananas_counter = Counter()


for initial_number in lines:
    print('.', end='', flush=True)      # slow down things, but better for the user (https://en.wikipedia.org/wiki/Perceived_performance)

    this_seller_counter = Counter()     # we need it to spot the *first* time we encounter a specific 4-changes sequence.
    rand_num = initial_number
    bananas = initial_number % 10
    differences = []

    for i in range(NB_TIMES_NEW_VALUE):
        old_rand, rand_num = rand_num, next_pseudorandom_number(rand_num)
        old_bananas, bananas = bananas, rand_num % 10
        differences.append(bananas - old_bananas)

        if len(differences) >= 4 :
            four_last_changes = tuple(differences[-4:])
            if four_last_changes not in this_seller_counter:
                this_seller_counter[four_last_changes] += bananas

    numbers_sum += rand_num
    bananas_counter.update(this_seller_counter)
print()

    
print("Réponse partie 1:", numbers_sum)
print("Réponse partie 2:", max(bananas_counter.values()))