◂ 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 math
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]+', line) if token ]
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])
determinant = xA * yB - xB * yA determinant = xA * yB - xB * yA
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) ):
> if determinant == 0:
> if xA * y == x * yA: # prize is in the same dir
> gcd = math.gcd(xA, xB)
> if x % gcd == 0: # condition to have integer
> 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] f
> na, nb = tb[1] * x // gcd, tb[2] * x // g
> 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 + n
> else:
nbA_times_det = yB * x - xB * y nbA_times_det = yB * x - xB * y
nbB_times_det = -yA * x + xA * y nbB_times_det = -yA * x + xA * y
if (nbA_times_det % determinant == 0) and (nbB_times_ if (nbA_times_det % determinant == 0) and (nbB_times_det % determinant == 0):
# and nbA_times_det >= 0 and nbB_times_det >=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 nbA = nbA_times_det // determinant
nbB = nbB_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
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'])