So many solver solutions that day, either Z3 or Gauss-Jordan lol. I got a little obsessed about doing it without solvers or (god forbid) manually solving the system and eventually found a relatively simple way to find the intersection with just lines and planes:
Translate all hailstones and their velocities to a reference frame in which one stone is stationary at 0,0,0 (origin).
Take another arbitrary hailstone (A) and cross its (rereferenced) velocity and position vectors. This gives the normal vector of a plane containing the origin and the trajectory of A, both of which the thrown stone must intersect. So, the trajectory of the thrown stone lies in that plane somewhere.
Take two more arbitrary hailstones B and C and find the points and times that they intersect the plane. The thrown stone must strike B and C at those points, so those points are coordinates on the line representing the thrown stone. The velocity of the thrown stone is calculated by dividing the displacement between the two points by the difference of the time points of the intersections.
Use the velocity of the thrown stone and the time and position info the intersection of B or C to determine the position of the thrown stone at t = 0
Translate that position and velocity back to the original reference frame.
It’s a suboptimal solution in that it uses 4 hailstones instead of the theoretical minimum of 3, but was a lot easier to wrap my head around. Incidentally, it is not too hard to adapt the above algorithm to not need C (i.e., to use only 3 hailstones) by using line intersections. Such a solution is not much more complicated than what I gave and still has a simple geometric interpretation, but I’ll leave that as an exercise for the reader :)
Advent of code 2023 day 24 part 2. Z3 solver saved the day on that one.
Now I have PTSD every time I see an hailstorm.
So many solver solutions that day, either Z3 or Gauss-Jordan lol. I got a little obsessed about doing it without solvers or (god forbid) manually solving the system and eventually found a relatively simple way to find the intersection with just lines and planes:
It’s a suboptimal solution in that it uses 4 hailstones instead of the theoretical minimum of 3, but was a lot easier to wrap my head around. Incidentally, it is not too hard to adapt the above algorithm to not need C (i.e., to use only 3 hailstones) by using line intersections. Such a solution is not much more complicated than what I gave and still has a simple geometric interpretation, but I’ll leave that as an exercise for the reader :)
That is a great explanation of how you solved it, thanks! I should go back to it and conquer that puzzle properly without a solver. Or at least try.