Pas de Z3, mais au moins Z^3 neurones grillés

C'est celui qui m'a le plus gonflé sur téléphone.
Pas la partie 1 bien sûr, encore expédiée assez vite dès que je m'y suis mis (c'est à dire une fois le jour précédent terminé).

La partie 2.
Où les données de test laissent entrevoir plein de simplifications qui ne fonctionnent pas avec le vrai problème.
Et une résolution finale qui ne fonctionne pas sur les données de test !

J'ai assez modélisé mes trajectoires de grêlon, pour faire des opérations en masse, je cherchais des simplifications, des translations, pivots, etc, mais je n'ai jamais réussi à résoudre autre chose que les données de test comme ça : à chaque fois il fallait tester au moins un paramètre final, et le plus complexe à tester a au final une valeur de 57 milliard et quelques au minimum, donc on ne va pas l'atteindre comme ça, en cherchant...
C'est le temps nécessaire à notre caillou pour atteindre un élément.
On tombe pas dessus par hasard.
Dans les données de test, c'est 1, ça simplifie grandement le problème.

En fait, il faut comprendre le problème.
On choisit un point d'origine et une trajectoire : Traj(x=393358484426865.0, y=319768494554521.0, z=158856878271783.0, dx=-242, dy=-49, dz=209)
À partir de là on choisit des entiers, grands, ça va de quelques dizaines de milliards à probablement mille milliards (j'ai un 943 538 374 225 pour un grêlon), ça définit des points de départ sur notre trajectoire.
De chacun de ces points on choisit une direction, et on fait reculer notre grêlon du temps nécessaire à atteindre le point en question.
Voilà, on a notre problème posé, on oublie la trajectoire initiale, il faut la retrouver.
Facile à construire, pas simple à démêler...

Et franchement, il faut trouver des simplifications.
Et là on les trouve avec une première constatation : ce qui se passe en x, y et z est presque entièrement décorrélé, pour trouver dx, dy ou dz, on n'a besoin de se concentrer que sur la coordonnée en question. Après on fera une corrélation sur l'écart en temps entre deux grêlons, qu'on peut connaître pour dx, dy ou dz, et qui sera donc égale pour les autres, et permet de faire une triangulation.
Et une seconde constatation, sur un axe on a des grêlons parallèles, c'est à dire qui ont le même dx, le même dy ou le même dz.
Et ça va nous aider.
C'est même la seule simplification que j'ai trouvé pour réussir à résoudre ce problème.

Parce que si entre deux grêlons on a un dx identique, ça veut dire que l'écart en x entre ces deux grêlon est une constante.
Et donc qu'on parcourt cette écart avec un nombre entier d'étapes, chacune d'un nombre entier de décalages.
Donc pour deux grêlons a et b parallèles en x, donc a.dx==b.dx, on a que l'écart en x (a.x - b.x) est divisible par r.dx-a.dx ou r est notre trajectoire résultat à trouver. On cherche r.dx.
Et ben on va chercher les diviseurs de a.x - b.x, sans connaître le sens on va tous les prendre en positif ou négatif, on ajoute a.dx, et on a des valeurs possibles de r.dx.
Et on cherche les valeurs communes entre tous les éléments parallèles en x, on aura réduit drastiquement nos possibilités de r.dx.

En pratique, si on n'oublie pas de considérer les diviseurs en négatif ou positif (parce qu'on ne sait pas dans quel sens on va, on a juste deux grêlons au pif), on va trouver une seul valeur pour dx, dy et dz.
On a la direction parfaite de notre caillou !
Ça aurait pu rater, on aurait pu avoir des choix et devoir tester parmi ces choix lesquels seraient les bons, mais on sent que même si on en avait eu plusieurs, ça n'aurait pas été trop explosif, et si l'algo pour finir le boulot est pas trop pourri on pouvait tout tester.

Là, suite à une erreur de ma part, j'ai aussi pondu un algorithme capable de calculer dy si on connaît dx et dz !
Sauf que ça foirait, à cause de mon erreur, mais j'ai corrigé et poursuivi, en pratique je calcule la solution pour tous les grêlons parallèles deux à deux en x, et je valide cette solution en montrant qu'ils donnent tous le même résultat. Ça m'a permis de débugger et d'être absolument certain d'avoir le bon résultat au bout du compte.

En pratique, quand on a dx, dy, et dz, il suffit de prendre deux grêlons parallèles selon n'importe quel axe, et on va avoir la solution.
On calcule le nombre d'étapes (microsecondes) pour que notre caillou passe de l'un à l'autre, ce qui est facile si on a compris l'algorithme qui a permit de trouver les dx, dy et dz : on divise l'écart en x a.x-b.x par r.dx-a.dx qui sont connus.
Sachant le temps séparant ces deux chocs, on peut calculer l'écart en y ou en z, constaté parce que nos grêlons ne sont pas parallèles en y ou z, et ça va nous permettre de savoir de combien d'étapes dans le temps il faut remonter pour combler cet écart, et faire en sorte de bien percuter les deux grêlons, en x, y et z.

En pratique mon algorithme, que je n'ai pas simplifié, calcule dy à partir de la connaissance de dx et dz sur des grêlons parallèles en z, c'est pas trop compliqué une fois qu'on a le nombre d'étapes à remonter dans le temps, et on valide déjà qu'on trouve pour tous la bonne valeur de dy. Puis on fait remonter effectivement dans le temps notre caillou depuis sa percussion avec a pour trouver un point de départ.
J'ai juste validé que r.x était identique pour tous, mais tant que ce n'était pas le cas c'était que j'avais une erreur dans mes formules.

Les maths sont simples, mais prise de tête et il faut bien se torturer les neurones.

Au final je fais bien trop de calculs, qui me donnent tous le même résultat, heureusement, et ça prend moins d'une seconde malgré tout.

Voici donc le code, avec trop de méthodes inutilisées dans mes Trajectoires, et des noms de variable bien trop peu lisibles.
Heureusement le code n'est pas trop complexe, et reste a peu près lisible.
Il y a un hack au milieu pour les données de test, puisqu'on n'a pas assez de parallèles pour trouver dx, dy et dz, je force les valeurs, connues, pour valider la seconde partie de l'algorithme.
Mais ça aurait pu faire l'objet d'un développement intéressant pour valider sur un ensemble de valeurs possible, si on n'avait pas eu un dx, dy et dz unique à l'issue de la première partie.
Rendant nécessaire de tester plusieurs cas et de vérifier qu'on ait bien un même résultat. Ça aurait été immonde à débugger par contre...
J'ai tout de même utilisé sympy pour les diviseurs, pour le coup c'était quand même plus simple que de coder une fonction moi-même.

from sys import stdin
from dataclasses import dataclass
from functools import total_ordering
from sympy import divisors
test = False
data = stdin.read().strip().splitlines()
ex1 = ex2 = 0
m0, m1 = (7, 27) if test else (200000000000000, 400000000000000)
@total_ordering
@dataclass(frozen=True)
class Traj:
 x: int = 0
 y: int = 0
 z: int = 0
 dx: int = 0
 dy: int = 0
 dz: int = 0
 @property
 def a(self):
 return self.dy / self.dx
 @property
 def b(self):
 return self.y - self.x * self.dy / self.dx
 def __mul__(self, other):
 # t = (x-x0)/dx
 # y = y0+dy*(x-x0)/dx = a*x+b
 # b = y0-x0*dy/dx
 # a = dy/dx
 # x = (B-b)/(a-A)
 if self.a == other.a:
 return 0, 0, -1, -1
 x = (other.b - self.b) / (self.a - other.a)
 y = self.a * x + self.b
 return x, y, (x - self.x) / self.dx, (x - other.x) / other.dx
 def __lt__(self, other):
 return self.tzero < other.tzero
 def __add__(self, n):
 return Traj(
 self.x + self.dx * n,
 self.y + self.dy * n,
 self.z + self.dz * n,
 self.dx, self.dy, self.dz)
 def __sub__(self, other):
 return Traj(
 self.x - other.x,
 self.y - other.y,
 self.z - other.z,
 self.dx, self.dy, self.dz)
 def __truediv__(self, other):
 return Traj(
 self.x, self.y, self.z,
 self.dx - other.dx,
 self.dy - other.dy,
 self.dz - other.dz)
 def __neg__(self):
 return Traj(-self.x, -self.y, -self.z, -self.dx, -self.dy, -self.dz)
 @property
 def tzero(self):
 return -self.z / self.dz if self.dz else 0
# data
D = [
 Traj(*(int(x) for x in line.replace(" ", "").replace("@", ",").split(",")))
 for line in data
]
# ex1
for i, d in enumerate(D):
 for f in D[i + 1:]:
 x, y, t, tt = d * f
 if x >= m0 and x <= m1 and y >= m0 and y <= m1 and t > 0 and tt > 0:
 ex1 += 1
# ex2
def correlate(trucs):
 dds = [d[0] for d in trucs]
 dds = {d for d in dds if dds.count(d) > 1}
 X = {
 d: sorted(x for dx, x in trucs if d == dx)
 for d in dds
 }
 Z = {
 dx: {
 s * di + dx
 for x1 in x
 for di in divisors(x0 - x1)
 for s in [1, -1]
 }
 for dx, (*x, x0) in X.items()
 }
 return set.intersection(*Z.values())
def recorrelate(trucs, dx, dy, dz):
 dds = [d.dz for d in trucs]
 dds = {d for d in dds if dds.count(d) > 1}
 X = {
 d: sorted(
 (_ for _ in trucs if _.dz == d),
 key=lambda f: f.z
 )
 for d in dds
 }
 Y = [
 {
 "dy": (x0.y - x1.y - step0 * (x0.dy - x1.dy)) / step + x0.dy,
 "x0": x0,
 "x1": x1,
 "step": step,
 "xp": xp,
 "step0": step0,
 "src": Traj(
 x1.x - x1.dx * step0,
 x1.y - x1.dy * step0,
 x1.z - x1.dz * step0,
 dx, dy, dz) + step0,
 }
 for _, (*x, x0) in X.items()
 for x1 in x
 for step in [(x0.z - x1.z) / (dz - x0.dz)]
 if step
 for xp in [(x0.x - x1.x) - (dx - x0.dx) * step]
 for step0 in [xp / (x0.dx - x1.dx)]
 ]
 return Y, {h["dy"] for h in Y}, {h["src"].x for h in Y}
PDX = correlate([(d.dx, d.x) for d in D])
PDY = correlate([(d.dy, d.y) for d in D])
PDZ = correlate([(d.dz, d.z) for d in D])
print(PDX, PDY, PDZ)
PDX, PDY, PDZ = (-3, 1, 2) if test else (PDX.pop(), PDY.pop(), PDZ.pop())
Y, dys, xs = recorrelate(D, PDX, PDY, PDZ)
print(Y)
print(dys)
print(xs)
print(sorted(-h["step0"] for h in Y))
# This searches for a hailstone going parallel to our rock in one axis.
# Turns out that won't be useful, but it could lead to an easy way for initial position
# for d in D:
# if d.dx == PDX or d.dy == PDY or d.dz == PDZ:
# print(d)
T = Y[0]["x1"]
R = Y[0]["src"]
print(R)
ex2 = R.x + R.y + R.z
r1, r2 = (2, 47) if test else (16779, 871983857253169)
print(f"{'ok' if ex1 == r1 else 'nok'}: {ex1}")
print(f"{'ok' if ex2 == r2 else 'nok'}: {ex2}")

J'ai pas trop nettoyé le code hein.
Et dans la version téléphone, j'utilise s et o au lieu de self et other dans la classe Traj (qui ne va quand même pas s'appeler Trajectory non plus, trop long...), tout pour écrire le moins possible !

• Yth.