◂ 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.
- code.py
- code_detZero.py
- diff_detZero.diffy
- code_numpy.py
- diff_numpy.diffy
- code_naif_sansEquations.py
import re import re
> import numpy
with open("input.txt", 'r', encoding='utf-8') as f: with open("input.txt", 'r', encoding='utf-8') as f:
lines = [line[:-1] for line in f.readlines()] lines = [line[:-1] for line in f.readlines()]
def parse_ints(line: str) -> list[int]: def parse_ints(line: str) -> list[int]:
return [ int(token) for token in re.split('[^-0-9]+', lin return [ int(token) for token in re.split('[^-0-9]+', lin
PRICE_A = 3 PRICE_A = 3
PRICE_B = 1 PRICE_B = 1
DELTA_PART2 = 10_000_000_000_000 DELTA_PART2 = 10_000_000_000_000
tokens = {'part1':0, 'part2':0} tokens = {'part1':0, 'part2':0}
for i in range(0, len(lines), 4): for i in range(0, len(lines), 4):
xA, yA = parse_ints(lines[i]) xA, yA = parse_ints(lines[i])
xB, yB = parse_ints(lines[i+1]) xB, yB = parse_ints(lines[i+1])
x_prize, y_prize = parse_ints(lines[i+2]) x_prize, y_prize = parse_ints(lines[i+2])
# simple système d'équations # simple système d'équations
> matrix = numpy.array(((xA, xB),(yA, yB)))
determinant = xA * yB - xB * yA | determinant = numpy.linalg.det(matrix) # det(((1,2),(4,5)) retourne -2.9999999999999996, je fais pas trop confiance
if determinant == 0: if determinant == 0:
print("Oh myyyy, that's another algorithm altogether, print("Oh myyyy, that's another algorithm altogether,
exit() exit()
> inverse = numpy.linalg.inv(matrix)
for id_partie, x, y in ( for id_partie, x, y in (
('part1', x_prize, y_prize), ('part1', x_prize, y_prize),
('part2', x_prize + DELTA_PART2, y_prize + ('part2', x_prize + DELTA_PART2, y_prize + DELTA_PART2) ):
nbA_times_det = yB * x - xB * y | nb_pushAB = inverse @ (x, y) # @ est la multiplication matricielle
nbB_times_det = -yA * x + xA * y | nbA, nbB = (round(v) for v in nb_pushAB)
if (nbA_times_det % determinant == 0) and (nbB_times_ | if numpy.array_equal(matrix @ (nbA, nbB), (x,y)) and ( # vérifier si les arrondis entiers sont bien la solution
# and nbA_times_det >= 0 and nbB_times_det >=0 | all(nb_pushAB > 0) ):
nbA = nbA_times_det // determinant <
nbB = nbB_times_det // determinant <
tokens[id_partie] += PRICE_A * nbA + PRICE_B * nb | tokens[id_partie] += PRICE_A * nbA + PRICE_B * nbB
print("Réponse partie 1:", tokens['part1']) print("Réponse partie 1:", tokens['part1'])
print("Réponse partie 2:", tokens['part2']) print("Réponse partie 2:", tokens['part2'])