Advent of code

◂ 24 décembre 2023 ▸

  Never Tell Me The Odds : Trouver des intersections de droites paramétriques, puis résolution d'équations non linéaires

233210433951170, 272655040388795, 179982504986147 @ 39, -98, 166

385274025881243, 351578921558552, 375160114124378 @ -71, -36, -9

298962016918939, 322446494312107, 293073189215975 @ 36, 8, 96

1. code1.py
2. code2.py
3. code2_paralleles.py

""" S'il existe des trajectoires de grêlons parallèles, alors on sait que notre caillou doit se déplacer dans le plan formé par ces deux parallèles.
    Il devient alors facile d'intersecter ce plan avec les trajectoires des autres grêlons pour en déterminer la position et le temps du crash. Il suffit
    de deux crashs pour remonter à l'origine du caillou.
    Malheureusement, mon input ne contient pas de parallèles :( """

import re, itertools, functools, math
from collections import defaultdict

if True:
    file = 'input.txt' 
    debug = False
else:
    file = 'input2.txt' 
    debug = True

f = open(file, 'r', encoding='utf-8')
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 ]

Vecteur   = tuple[float,float,float] | list[float]
Position  = tuple[float,float,float] | list[float]
Direction = Vecteur
Plan      = tuple[float, float, float, float]  # a,b,c,d de ax+by+cz+d=0

def normaliser(v: Vecteur) -> Direction:
    if not any(v):
        return v
    g = math.gcd(*v)
    if [c for c in v if c][0] < 0:
        g *= -1
    return tuple([c//g for c in v])
    
pos: list[Position] = []
vit: list[Vecteur] = []
directions: dict[Direction,list[int]] = defaultdict(list)

for i,line in enumerate(lines):
    values = parse_ints(line)
    pos.append(tuple(values[:3]))
    v = tuple(values[3:])
    vit.append(v)
    direction = normaliser(v)
    directions[direction].append(i)
    

def produit_vectoriel(v:Vecteur, w:Vecteur) -> Vecteur:
    return [v[(i+1)%3] * w[(i+2)%3] -  v[(i+2)%3] * w[(i+1)%3] for i in range(3)]

def produit_scalaire(v:Vecteur, w:Vecteur) -> float:
    return sum(a * b for a,b in zip(v,w))


paralleles = [(k,t) for k,t in directions.items() if len(t) > 1]
if len(paralleles) == 0:
    print("Cet input ne contient pas de grêlons aux trajectoires parallèles. Utilisez une autre méthode.")
    exit(1)

dir, indices = paralleles[0]
vecteur_normal = normaliser(produit_vectoriel(dir, [pos[indices[0]][coord]-pos[indices[1]][coord] for coord in range(3)]))
plan: Plan = list(vecteur_normal) + [-produit_scalaire(vecteur_normal, pos[indices[0]])]


positions_caillou: list[tuple[Position,int]]  = [] 
for i,p in enumerate(pos):
    v = vit[i]
    #  a*(p1+t*v1)+b*(p2+t*v2)+c*(p3+t*v3)+d = 0
    den = produit_scalaire(plan[:3], v)
    if den == 0:
        continue
    num = -produit_scalaire(plan, list(p)+[1])
    if num % den == 0:
        t = num // den
    else:
        t = num / den
    positions_caillou.append( ([p[coord]+t*v[coord] for coord in range(3)], t) )
    if len(positions_caillou) > 1:
        break

(p1,t1),(p2,t2),*_ = positions_caillou
# (t2-t1)*orig = p1*t2 -p2*t1

assert not any ((p1[coord]*t2 - p2[coord]*t1)  % (t2-t1) for coord in range(3)), "La position de départ n'est pas formée d'entiers. Erreur de calcul?"
depart_caillou = [(p1[coord]*t2 - p2[coord]*t1) // (t2-t1) for coord in range(3)]
print("Position départ:", depart_caillou)
print("Réponse partie 2:", sum(depart_caillou))