Advent of Code

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.

import re
import numpy

with open("input.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
    matrix = numpy.array(((xA, xB),(yA, yB)))
    determinant = numpy.linalg.det(matrix)   # det(((1,2),(4,5)) retourne -2.9999999999999996, je fais pas trop confiance
    if determinant == 0:
        print("Oh myyyy, that's another algorithm altogether, then!")
        exit()
    inverse = numpy.linalg.inv(matrix)
    for id_partie, x, y in (
                 ('part1',  x_prize,  y_prize), 
                 ('part2',  x_prize + DELTA_PART2,  y_prize + DELTA_PART2) ):
        nb_pushAB = inverse @ (x, y)   # @ est la multiplication matricielle
        nbA, nbB = (round(v) for v in nb_pushAB)
        if numpy.array_equal(matrix @ (nbA, nbB), (x,y)) and ( # vérifier si les arrondis entiers sont bien la solution
                    all(nb_pushAB > 0) ):
            tokens[id_partie] += PRICE_A * nbA + PRICE_B * nbB

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