Advent of code

◂ 13 décembre 2024 ▸

  Claw Contraption : Trouver une combinaison de mouvements pour aller à des coordonnées (résolution de combinaison linéaire).
Button A: X+79, Y+87
   
Button B: X+44, Y+14
   
Prize: X=7384, Y=4824
   
  
   
Button A: X+28, Y+94
   
Button B: X+79, Y+69
   
Prize: X=7377, Y=13189
   
           ⋮
J'avais oublié de regarder si les solutions étaient positives ou nulles.
Heureusement, il n'y avait pas de cas comme celui-là, mais je pense que j'aurais perdu du temps à voir le problème.

Version detZero : prend en charge le cas de déplacements boutons A et B parallèles (déterminant = 0).
Mais ça n'arrive pas avec les inputs AOC.

Version avec numpy : on ne teste pas si les solutions sont entières (trops peu précis), on teste si les réponses arrondies aux entiers sont bien la solution !

code_naif_sansEquations.py : Une façon assez rapide (juste 5 fois plus lent que le code de base) de trouver le bon nombre de boutons à presser, sans résoudre d'équation !
Tout se trouve dans la fonction calc_nb_pushes.
  1. code.py
  2. code_detZero.py
  3. diff_detZero.diffy
  4. code_numpy.py
  5. diff_numpy.diffy
  6. code_naif_sansEquations.py
import re, math
with open("input2.txt", 'r', encoding='utf-8') as f:
    lines = [line[:-1] for line in f.readlines()]

def parse_ints(line: str) -> list[int]:
    return [ int(token) for token in re.split('[^-0-9]+', line) if token ]

PRICE_A = 3
PRICE_B = 1

DELTA_PART2 = 10_000_000_000_000

tokens = {'part1':0, 'part2':0}

for i in range(0, len(lines), 4):
    xA, yA = parse_ints(lines[i])
    xB, yB = parse_ints(lines[i+1])
    x_prize, y_prize = parse_ints(lines[i+2])

    # simple système d'équations
    determinant = xA * yB - xB * yA
    for id_partie, x, y in (
                 ('part1',  x_prize,  y_prize), 
                 ('part2',  x_prize + DELTA_PART2,  y_prize + DELTA_PART2) ):
        if determinant == 0:
            if xA * y == x * yA:   # prize is in the same direction as A and B buttons.
                gcd = math.gcd(xA, xB)
                if x % gcd == 0:  # condition to have integer answers, but could be negative
                    a, b = xA // gcd, xB // gcd
                    ta = [a,1,0]
                    tb = [b,0,1]
                    while tb[0] != 1:
                        factor = ta[0] // tb[0]
                        ta,tb = tb, [ta[i] - factor * tb[i] for i in range(3)]
                    na, nb = tb[1] * x // gcd, tb[2] * x // gcd
                    print("milieu", na, nb)
                    if b * PRICE_A > a * PRICE_B:
                        na,nb = na % b, nb + na//b * a 
                    else:
                        na,nb = na + nb//a * b, nb % a
                    print("best", na, nb)
                    if na*nb >= 0:
                        tokens[id_partie] += na * PRICE_A + nb * PRICE_B
        else:
            nbA_times_det =   yB * x  -  xB * y 
            nbB_times_det =  -yA * x  +  xA * y 
            if (nbA_times_det % determinant == 0) and (nbB_times_det % determinant == 0):
                # and nbA_times_det >= 0  and nbB_times_det >=0    # oublié de tester ça, mais ça n'arrive pas. Ouf !
                nbA = nbA_times_det // determinant
                nbB = nbB_times_det // determinant
                tokens[id_partie] += PRICE_A * nbA + PRICE_B * nbB

print("Réponse partie 1:", tokens['part1'])
print("Réponse partie 2:", tokens['part2'])