Throwing rocks at the problem

Advent of Code, day 24, part 2 gives you several hailstones, traveling in a straight line over time. It asks you to find the trajectory of a rock, which intersects with every hailstone.

Every hailstone is a line segment, described with a starting position, and a velocity, each given as X, Y, and Z coordinates.

Shift in perspective

Choose a reference hailstone, and subtract its position and velocity from every other hailstone and rock.

The result is that every line is offset, except our reference hailstone, which collapsed into a singular point at the origin. Since the rock has to intersect with the reference hailstone, it must also intersect with the origin.

The diagram still shows our rock as well as all the hailstones. However, we don't actually know our rock's trajectory yet, and we only need 3 hailstones in total to solve the problem, so the diagram below hides everything except those:

A plane of intersection

As the rock has to intersect with all of these hailstones, it must intersect with their trajectories. We just don't know where exactly it will intersect. Using two points along the cyan hailstone's trajectory, and the origin, we get a plane:

The rock must travel along this plane, otherwise it could never hit both our reference and cyan hailstones. The intersection of the purple hailstone and the plane, is therefore also its intersection with the rock, and we calculate the time of intersection.

We can then do the same calculation, this time forming a plane between the purple and reference hailstones to find the intersection time of the rock and the cyan hailstone.

Constructing the rock's trajectory

With the time of intersection between the rock and both of those hailstones in hand, we can calculate where the rock should be at those points.

let rock_pos_at_time_a = a.pos + a.vel * time_a;
let rock_pos_at_time_b = b.pos + b.vel * time_b;

let delta_time =             time_b -             time_a;
let delta_pos  = rock_pos_at_time_b - rock_pos_at_time_a;

let rock_velocity = delta_pos / delta_time;
let rock_position = rock_pos_at_time_a - rock_velocity * time_a;

Finally, showing both planes and the rock's trajectory combined, you can see the rock traveling along the intersection of the planes:

Mathematics and implementation notes

The planes we define all pass through the origin (due to our shift), therefore, they are uniquely defined by just a normal vector. To calculate the normal vector, we can use the cross product between any two points on the reference line. I chose a.position and a.position + a.velocity as points, and then normalizing the vector. The formula for calculating the line-plane intersection is relatively straightforward, taking two dot products and dividing them.

Normalizing a vector just scales it, and since the dot product with the plane normal is done in both the numerator and denominator, this scalar factor cancels out, and we can skip normalizing the vector. This allows us to stay within integers, which prevents having to worry about rounding errors.

Another issue arises in the form of overflow. The actual inputs are large numbers, up 49 bits for my input, multiplying two of them, resulting in numbers that are potentially up to 98 bits in size. Multiplication is required by both the cross and dot products. You can either use a big integer library, or in my case, use Rust's built-in 128-bit integer types to prevent overflow.

After doing some algebra, we conclude that given hailstone A, and B, relative to the reference hailstone, we can calculate the intersection time between the rock and B, using:

$N=A_{position}\times(A_{position}+A_{velocity})\T_{ime}={-B_{position}\cdot N\over{B_{velocity}\cdot N}}$

Finally, a lot of detail, and edge case handling has been omitted. For example, if a hailstone had the same velocity as the reference hailstone, it would collapse into a point instead of a line, preventing us from forming a plane. Similarly, the other hailstone could fully line within the plane, leaving us with no intersection point, the reason to omit this detail, is because the given inputs don't cause these situations, and even if they did, it's so overspecified that you could just arbitrarily pick different hailstones.

You can find the full source code on my GitHub.