You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
There's a bunch of duplicate individual velocity components between the
hailstones:
$\mathbf{v}_x = -1$: $\mathbf{vB}, \mathbf{vD}$
$\mathbf{v}_x = -2$: $\mathbf{vA}, \mathbf{vC}$
$\mathbf{v}_y = -2$: $\mathbf{vC}, \mathbf{vD}$
$\mathbf{v}_z = -2$: $\mathbf{vA}, \mathbf{vB}$
Let's think about the case where two hailstones have a velocity component in
common. For example, in our case both hailstones $B$ and $D$ have
$\mathbf{v}_x = -1$.
At time $t=0$, these two hailstones are some distance $d_x(B,D)$ apart:
Since they're moving at the same speed in the X direction, the distance between
them along the X axis stays constant. We need to hit both hailstones with a rock
we've thrown at some integer velocity. To successfully hit both, its X velocity
relative to those hailstones needs to be such that it covers the distance
$d_x(B,D)$ in an integer amount of time steps. In other words,
$\mathbf{vR}_x - \mathbf{v}_x = \mathbf{vR}_x + 1$ must be a divisor of
$d_x(B,D)$, or the negated value of one. Since $d_x(B,D) = 6$, we therefore
have:
Independent to that, we also have the same situation for $A, C$, where
$\mathbf{vA}_x = \mathbf{vC}_x = -2$. For these two,
$d_x(A,C) = \left|\mathbf{pC}_x - \mathbf{pA}_x\right| = 1$. So we know that:
In the example scenario, we know $\mathbf{vR} = (-3\ 1\ 2)^T$, which is
consistent with this.
For the example, this wasn't sufficient to narrow down the velocity to a single
answer. However, the puzzle input has a lot more data. Running the same steps on
it (with an implicit assumption that the velocity components are "reasonable",
say between -2000 and +2000, to avoid having to find divisors for large numbers)
actually narrows down the sets to single values pretty quickly.
Here's a log for my puzzle input:
for X:
vel 5 pos (252027155370005, 301801136650301)
=> [-1087 -723 ...58 numbers omitted for brevity... 733 1097]
vel 5 pos (252027155370005, 322304061345021)
=> [-99 -47 -21 -8 -3 1 3 4 6 7 9 13 18 31 57 109]
vel 5 pos (301801136650301, 322304061345021)
=> [-99 -47 -21 -8 -3 1 3 4 6 7 9 13 18 31 57 109]
vel -6 pos (313331026360933, 281502442529605)
=> [-99 -8 -3 3 6 18]
vel -49 pos (317912587490765, 325843512544115)
=> [-99]
for Y:
vel -234 pos (417641320056889, 407035805550239)
=> [-584 -409 ...20 numbers omitted for brevity... -59 116]
vel -23 pos (225633601154640, 283130841945486)
=> [-269]
for Z:
vel -140 pos (313407769490726, 454532431171443)
=> [-429 -361 -327 -283 -157 -153 -151 -141 -139 -129 -127 -123 3 47 81 149]
vel -10 pos (266642825749899, 283898755233783)
=> [-283 3 81]
vel -10 pos (266642825749899, 298590923399276)
=> [3 81]
vel -10 pos (283898755233783, 298590923399276)
=> [3 81]
vel -113 pos (431101666985804, 430550575300350)
=> [81]
$\mathbf{vR} = ({-99}\ {-269}\ {81})^T$ is in fact correct for my puzzle input.
Finding the position
Now we know $\mathbf{vR}$, the direction of our line. Could we use that to also
figure out $\mathbf{pR}$, the origin of that line?
Aside: For the argument below, the magnitude of $\mathbf{vR}$ doesn't actually
matter. It's sufficient that it points in the right direction (or the opposite
direction).
Let's consider hailstone $A$, which traces the line
$\mathbf{pA} + t\ \mathbf{vA}$. We know our line intersects it somewhere, but
not exactly where and when. Still, that does narrow the possibilities down to a
single plane, defined by:
The point $\mathbf{pA}$, in that plane.
The direction $\mathbf{vA}$.
The direction $\mathbf{vR}$.
You can visualize this as the plane formed by "sliding" a line pointing at the
direction $\mathbf{vR}$ over all the possible intersection points on the path of
hailstone $A$. (Technically, it would only be a half-plane, as the intersection
must not be in the past. But we can ignore that and assume there's just one
unique solution, and that it's a valid one.)
Let's find a normal vector $\mathbf{nA}$ for that plane. The sign ("up" vs.
"down") and magnitude don't really matter, as long as it's perpendicular to both
$\mathbf{vA}$ and $\mathbf{vR}$. The cross product gives us a vector
perpendicular to two others:
Here $\mathbf{p} = (x\ y\ z)^T$ is an arbitrary point on the plane, but
$\mathbf{pA}$ and $\mathbf{nA}$ are known vectors, and
$\mathbf{pA} \cdot \mathbf{nA}$ therefore also a known scalar.
We still don't know exactly where on that plane the line is, or even where it
intersects the path of hailstone $A$, since we used that to define the plane so
that line is necessarily entirely contained in the plane.
However, there's more hailstones which our target line must intersect. Assuming
their paths are not parallel to the plane, they'll intersect it at exactly one
point.
Let's look at hailstone $B$, and figure out when its line
$\mathbf{pB} + t\ \mathbf{vB}$ intersects our plane. This happens for some value
$t = tB$ when the coordinates satisfy the earlier equation for the plane.
Let's solve for $tB$ by substituting in the line of hailstone $B$ for
$\mathbf{p}$ in our earlier plane equation:
Aside: This step does depend on $\mathbf{vR}$ having the right magnitude.
However, we could always repeat the above for another hailstone $C$ to find
another intersection point with known time $tC$, and use
$\mathbf{vR} = \frac{(\mathbf{pC} + tC\ \mathbf{vC}) - (\mathbf{pB} + tB\ \mathbf{vB})}{tC-tB}$
to figure out the exact $\mathbf{vR}$.
To verify the solution, let's try substituting in the values from the day 24
example. The relevant numbers are:
In other words, we'll hit the second hailstone at time $tB = 3$ and position
$(15\ 16\ 16)^T$, after initially launching the rock from position
$\mathbf{pR} = (24\ 13\ 10)^T$.
Finding the position, but differently
As an alternative solution inside an alternative solution, consider this.
If we did know the complete solution, both the position $\mathbf{pR}$ and
velocity $\mathbf{vR}$, we could translate the entire problem to the reference
frame of the thrown rock, by subtracting $\mathbf{pR}$ from all the initial
hailstone positions, and $\mathbf{vR}$ from all the velocities.
In this formulation, the rock would stay still at position $(0\ 0\ 0)^T$, and
the paths of all the hailstones would intersect at that point, representing
their collision with the rock.
What would happen if we had the rock's velocity right, but the initial position
wrong? For example, let's say the correct initial position was still
$\mathbf{pR}$, but we instead subtracted some other value
$\mathbf{p} = \mathbf{pR} - \mathbf{pO}$ from the hailstones' initial positions?
Well, all the coordinates would be off by $\mathbf{pO}$, but all the lines would
still intersect at a single point, only this time it would be at $\mathbf{pO}$
rather than $(0\ 0\ 0)^T$.
But hey, we of course do know the value $\mathbf{p}$ that we subtracted. So
let's say we didn't change the hailstone initial positions at all:
$\mathbf{p} = (0\ 0\ 0)^T$. In this case,
$\mathbf{0} = \mathbf{pR} - \mathbf{pO}$, or $\mathbf{pR} = \mathbf{pO}$. In
other words, we can find $\mathbf{pR}$ (the correct initial position for the
rock) by just locating the point where all the hailstone paths intersect, once
we change all their velocities to be relative to that of the rock.
Another way of thinking about it: if we subtract $\mathbf{vR}$ from all
velocities, the rock will stand still at its initial position. Since it still
has to hit all the hailstones, all the hailstone lines must intersect at that
initial position.
Unfortunately, the
math for intersecting two lines in three dimensions
isn't really any simpler than the plane-line method above. Here's the answer for
the intersection point, using $\mathbf{vA}' = \mathbf{vA} - \mathbf{vR}$ to
denote the transformed velocity of hailstone $A$ (likewise for $B$):