Advent of Code 2023, Day 24
❄️ Back to Advent of Code 2023 solutions homepage ❄️
# Imports
from aoc23.utils import read_input
from dataclasses import dataclass, field
from itertools import combinations
import numpy as np
input_24 = read_input(24)
Part 1
In the Christmas Eve puzzle, we are given the initial positions and velocities of a collection of hailstones which are flying through the air. The trajectories of the hailstones are linear - i.e. there is no acceleraton due to gravity. Let’s create a class which can represent a hailstone:
@dataclass
class Hailstone:
position: list = field(default_factory=list)
velocity: list = field(default_factory=list)
Using this convenience dataclass, we can process the provided test hailstones to get lists of Hailstone objects:
def process_input(input_lines):
stones = []
for line in input_lines:
pos, vel = line.split(' @ ')
stones.append(Hailstone(position=[int(x) for x in pos.split(', ')],
velocity=[int(x) for x in vel.split(', ')]))
return stones
test_input = [
'19, 13, 30 @ -2, 1, -2',
'18, 19, 22 @ -1, -1, -2',
'20, 25, 34 @ -2, -2, -4',
'12, 31, 28 @ -1, -2, -1',
'20, 19, 15 @ 1, -5, -3',
]
test_stones = process_input(test_input)
test_stones
[Hailstone(position=[19, 13, 30], velocity=[-2, 1, -2]),
Hailstone(position=[18, 19, 22], velocity=[-1, -1, -2]),
Hailstone(position=[20, 25, 34], velocity=[-2, -2, -4]),
Hailstone(position=[12, 31, 28], velocity=[-1, -2, -1]),
Hailstone(position=[20, 19, 15], velocity=[1, -5, -3])]
The first part of the puzzle asks to identify pairs of hailstones which have intersecting trajectories. For the purpose of the puzzle, the hailstones are not required to actually collide at this point (so they can reach the intersection point at different times), and the $z$-coordinates of the trajectories need not match (so the trajectories are projected down onto the 2-dimensional $x$-$y$ plane). Also, we are only considering intersection points lying in the cubic region defined by upper and lower coordinate bounds - in the test example, these are $[7, 27]$ for all coordinates.
Consider a pair of hailstones $H_1$ and $H_2$, with positions $\mathbf{p}^{(1)}, \mathbf{p}^{(2)}$ and $\mathbf{v}^{(1)}, \mathbf{v}^{(2)}$ respectively - for now, ignore the $z$ component of these and treat them as 2D vectors. The projected trajectories will intersect if and only if $\mathbf{v}^{(1)}$ and $\mathbf{v}^{(2)}$ are parallel - in other words, they are linearly dependent. It can be shown that this is equivalent to the determinant of the $2\times 2$ matrix formed from these two vectors being zero:
\[\begin{vmatrix} v^{(1)}_x & v^{(2)}_x\\ v^{(1)}_y & v^{(2)}_y \end{vmatrix} = v^{(1)}_x v^{(2)}_y - v^{(2)}_x v^{(1)}_y = 0\]When this condition is true, we know that the vectors are parallel are the trajectories do not intersect anywhere; if not true, they will definitely intersect at some point. The time $t_1$ at which the first hailstone reaches the intersection point is given by the formula:
\[t_1 = \frac{\left(p^{(2)}_x - p^{(1)}_x\right)v^{(2)}_y - \left(p^{(2)}_y - p^{(1)}_y\right)v^{(2)}_x} {v^{(1)}_x v^{(2)}_y - v^{(1)}_y v^{(2)}_x},\]and there is an equivalent formula for $t_2$, the time for the second hailstone to reach the intersection point, obtained by switching all the superscript $(1)$ and $(2)$ variables. The intersection point $x$ is then given by:
\[\mathbf{x}=\mathbf{p}^{(1)}+t_1 \mathbf{v}^{(1)}=\mathbf{p}^{(2)}+t_2 \mathbf{v}^{(2)}.\]Once the intersection point is found, all that needs to be checked is:
- The intersection times $t_1, t_2$ are both positive, i.e. the intersection is not in the past for either hailstone
- The coordinates of the intersection point lie inside the required bounds.
def count_2d_intersections(stones, bounds):
intersections = 0
# Loop over all pairs of intersections
for stone1, stone2 in combinations(stones, 2):
p1x, p1y = stone1.position[0], stone1.position[1]
p2x, p2y = stone2.position[0], stone2.position[1]
v1x, v1y = stone1.velocity[0], stone1.velocity[1]
v2x, v2y = stone2.velocity[0], stone2.velocity[1]
# Check if velocities are parallel
det = (v1x*v2y - v1y*v2x)
if det == 0:
continue
# Times of intersection
t1 = ((p2x - p1x)*v2y - (p2y - p1y)*v2x)/(v1x*v2y - v1y*v2x)
t2 = ((p1x - p2x)*v1y - (p1y - p2y)*v1x)/(v2x*v1y - v2y*v1x)
# Remove past intersections
if t1<0 or t2<0:
continue
# Check in bounds
p = [p1x + t1*v1x, p1y + t1*v1y]
if not bounds[0]<=p[0]<=bounds[1]:
continue
if not bounds[0]<=p[1]<=bounds[1]:
continue
intersections += 1
return intersections
We expect the example input to have only 2 intersection points satisfying the criteria:
assert count_2d_intersections(test_stones, [7, 27]) == 2
print('Success!')
Success!
And so applying the same function to the full input:
stones = process_input(input_24)
count_2d_intersections(stones, [200000000000000, 400000000000000])
11246
This means that the answer to part 1 is: 11246.
Part 2
In the second part, we are now considering all three coordinates of the positions and velocities. We are told that for each set of hailstones (the test set and the full puzzle input), there exists an initial position $\mathbf{p}$ and velocity $\mathbf{v}$ from which a rock is thrown, which will collide with all the hailstones in the set. Collision in theis context means that the rock and each specific hailstone $H_i$ occupy the same coordinates at time $t_i>0$.
It is not necessary to consider all of the hailstones when trying to solve for $p$ and $v$, as this is a highly overdetermined system. There will not in general be a way to throw the rock and hit all of the hailstones, for arbitrarily chosen initial hailstone positions and velocities - for this puzzle, the provided initial conditions are specifically chosen so that this is the case. Lets consider each hailstone one by one, determining how many equations we have in total, and involving how many variables.
Hailstone 1
Suppose the rock has initial position $p$, velocity $v$, and intesects with hailstone 1 at time $t_1$. Then we have the equation:
\[\mathbf{p} + t_1 \mathbf{v} = \mathbf{p}^{(1)} + t_1 \mathbf{v}^{(1)}\]which when rearranged, tells that:
\[\mathbf{p} - \mathbf{p}^{(1)} = t_1\left(\mathbf{v}^{(1)} - \mathbf{v}\right).\]In other words, the vectors $\mathbf{p} - \mathbf{p}^{(1)}$ and $\mathbf{v} - \mathbf{v}^{(1)}$ are proportional; this is equivalent to the statement that:
\[\left(\mathbf{p} - \mathbf{p}^{(1)}\right)\times\left(\mathbf{v} - \mathbf{v}^{(1)}\right)=0\]where $\times$ is the usual 3-vector cross product. This is a vector equation, which when expanded (using the distributive properties of the cross product) gives the following vector equation:
\[\mathbf{p}\times\mathbf{v} - \mathbf{p}\times\mathbf{v}^{(1)} - \mathbf{p}^{(1)}\times\mathbf{v} + \mathbf{p}^{(1)}\times\mathbf{v}^{(1)} = 0.\]The quantities $\mathbf{p}^{(1)}$ and $\mathbf{v}^{(1)}$ are provided, so this is a quadratic equation in the components of the vectors $\mathbf{p}$ and $\mathbf{v}$. However, it would be preferable to have a linear system, which can be solved using the tools of linear algebra; thankfully, we can introduce a further variable to reduce the order the equation to linear:
\[\mathbf{c} \equiv \mathbf{p}\times\mathbf{v}\]This then reduces the vector equation into a system of 3 linear equations in the 9 variables $(\mathbf{p}, \mathbf{v}, \mathbf{c})$. The definition of $\mathbf{c}$ itself still remains quadratic, and so the order of the system remains quadratic - however, we do not need to enforce this quadratic definition as a constraint, as the system is highly overdetermined already. By treating $\mathbf{c}$ as an variable to solve for, independent of the other variables, we can treat the system as linear; if we can find a unique solution to the linear system, we need only check that the quadratic constraint is satisfied by the found solution to ensure that it is a true solution of the full problem.
At the moment, 3 linear equations for 9 variables is not sufficient to solve for a unique solution; this is expected, as there are many initial points/velocities to throw the stone from/with in order to hit the first hailstone. Therefore, further hailstones must be added to further constrain this system. Before doing this, let’s also define the following fixed quantities for convenience:
\[\mathbf{c}^{(i)} \equiv \mathbf{p}^{(i)}\times\mathbf{v}^{(i)},\]meaning the first set of linear equations in $(\mathbf{p}, \mathbf{v}, \mathbf{c})$ can be written:
\[\mathbf{c} - \mathbf{p}\times\mathbf{v}^{(1)} - \mathbf{p}^{(1)}\times\mathbf{v} + \mathbf{c}^{(1)} = 0.\]Hailstone 2
As the rock also hits the second hailstone at some time $t_2$, we have the familiar equation:
\[\mathbf{p} + t_2 \mathbf{v} = \mathbf{p}^{(2)} + t_2 \mathbf{v}^{(2)}\]and by repeating the analysis, we obtain a similar set of linear equations for $(\mathbf{p}, \mathbf{v}, \mathbf{c})$:
\[\mathbf{c} - \mathbf{p}\times\mathbf{v}^{(2)} - \mathbf{p}^{(2)}\times\mathbf{v} + \mathbf{c}^{(2)} = 0.\]This adds an additional 3 linear equations to the system, giving a cumulative total of 6 equations for 9 variables. This is still not sufficient to yield a unique solution, so more hailstones are necessary. Again, this makes sense: even if we know that we will hit the first hailstone, this could be anywhere along the hailstone’s trajectory, and with any velocity. This leaves a large number of options for ways in which the trajectory of the second hailstone can be intersected, ensuring multiple solutions.
Hailstone 3
Adding a third hailstone with the defining relationship
\[\mathbf{p} + t_3 \mathbf{v} = \mathbf{p}^{(3)} + t_3 \mathbf{v}^{(3)}\]and repeating the analysis one more time gives 3 further linear equations to add to the system:
\[\mathbf{c} - \mathbf{p}\times\mathbf{v}^{(3)} - \mathbf{p}^{(3)}\times\mathbf{v} + \mathbf{c}^{(3)} = 0.\]This now gives 9 equations for 9 unknowns, which in general if necessary to ensure a unique solution. The 3 sets of 3-vector equations can be combined into a single, $9$-dimensional linear equation, which when written out in full looks like this:
\[\begin{pmatrix} 0 & v^{(1)}_3 & -v^{(1)}_2 & 0 & -p^{(1)}_3 & p^{(1)}_2 & -1 & 0 & 0 \\ -v^{(1)}_3 & 0 & v^{(1)}_1 & p^{(1)}_3 & 0 & -p^{(1)}_1 & 0 & -1 & 0\\ v^{(1)}_2 & -v^{(1)}_1 & 0 & -p^{(1)}_2 & p^{(1)}_1 & 0 & 0 & 0 & -1\\ 0 & v^{(2)}_3 & -v^{(2)}_2 & 0 & -p^{(2)}_3 & p^{(2)}_2 & -1 & 0 & 0 \\ -v^{(2)}_3 & 0 & v^{(2)}_1 & p^{(2)}_3 & 0 & -p^{(2)}_1 & 0 & -1 & 0\\ v^{(2)}_2 & -v^{(2)}_1 & 0 & -p^{(2)}_2 & p^{(2)}_1 & 0 & 0 & 0 & -1\\ 0 & v^{(3)}_3 & -v^{(3)}_2 & 0 & -p^{(3)}_3 & p^{(3)}_2 & -1 & 0 & 0 \\ -v^{(3)}_3 & 0 & v^{(3)}_1 & p^{(3)}_3 & 0 & -p^{(3)}_1 & 0 & -1 & 0\\ v^{(3)}_2 & -v^{(2)}_1 & 0 & -p^{(3)}_2 & p^{(3)}_1 & 0 & 0 & 0 & -1\\ \end{pmatrix} \begin{pmatrix} p_0^{\phantom{(}} \\ p_1^{\phantom{(}} \\ p_2^{\phantom{(}} \\ v_1^{\phantom{(}} \\ v_2^{\phantom{(}} \\ v_3^{\phantom{(}} \\ c_1^{\phantom{(}} \\ c_2^{\phantom{(}} \\ c_3^{\phantom{(}} \end{pmatrix} =\begin{pmatrix} c^{(1)}_1\\ c^{(1)}_2\\ c^{(1)}_3\\ c^{(2)}_1\\ c^{(2)}_2\\ c^{(2)}_3\\ c^{(3)}_1\\ c^{(3)}_2\\ c^{(3)}_3 \end{pmatrix}\]Let’s write this in the simpler format:
\[M\mathbf{x} = \mathbf{y},\]identifying the respective quantities from the two equations. As the matrix $M$ is square, it has an inverse if the determinant is non-zero. If the matrix is not invertible, then either there are infinitely many solutions (i.e. infinitely many places to throw the rock from to hit the 3 hailstones), or no solution. As we expect the puzzle setter to have provided a problem dataset with a unique solution, we should expect the matrix to be invertible. A caveat is that there may be a degeneracy in the first set of 3 hailstones chosen - for example, if two of the hailstones and the rock all meet at the same point simultaneously. However, it should be possible for a general, well-defined problem set to find three hailstones that do not suffer from this degeneracy.
If the matrix $M$ is found to have an inverse, the solution vector $\mathbf{x}$ can be found by simply inverting the matrix equation
\[\mathbf{x} = M^{-1}\mathbf{y}.\]from which the solution 3-vectors $\mathbf{p}, \mathbf{v}$ and $\mathbf{c}$ can be read. The last check that the relationship $\mathbf{c}=\mathbf{p}\times\mathbf{v}$ holds will verify that the obtained solution is indeed a solution to the original problem.
Let’s code this up:
def compute_throw_intersection(stones):
# Convenient helper quantities
# Using the first three stones as the default
X = np.cross(stones[0].position, stones[0].velocity)
Y = np.cross(stones[1].position, stones[1].velocity)
Z = np.cross(stones[2].position, stones[2].velocity)
a = stones[0].position
b = stones[0].velocity
m = stones[1].position
n = stones[1].velocity
p = stones[2].position
q = stones[2].velocity
# Matrix to invert
M = [
[0, b[2], -b[1], 0, -a[2], a[1], -1, 0, 0],
[-b[2], 0, b[0], a[2], 0, -a[0], 0, -1, 0],
[b[1], -b[0], 0, -a[1], a[0], 0, 0, 0, -1],
[0, n[2], -n[1], 0, -m[2], m[1], -1, 0, 0],
[-n[2], 0, n[0], m[2], 0, -m[0], 0, -1, 0],
[n[1], -n[0], 0, -m[1], m[0], 0, 0, 0, -1],
[0, q[2], -q[1], 0, -p[2], p[1], -1, 0, 0],
[-q[2], 0, q[0], p[2], 0, -p[0], 0, -1, 0],
[q[1], -q[0], 0, -p[1], p[0], 0, 0, 0, -1],
]
# Target vector
v = [X[0], X[1], X[2], Y[0], Y[1], Y[2], Z[0], Z[1], Z[2]]
# Solve and
sol = np.matmul(np.linalg.inv(M), v)
p, v, c = sol[:3], sol[3:6], sol[6:]
# Check that c = p x v
assert np.allclose(np.cross(p, v), c)
return p, v
Let’s check this method first on the provided test hailstones:
test_pos, test_vel = compute_throw_intersection(test_stones)
assert np.allclose(test_pos, [24, 13, 10])
assert np.allclose(test_vel, [-3, 1, 2])
print('Success!')
Success!
And so all that remains is to repeat on the full set of hailstones:
pos, vel = compute_throw_intersection(stones)
print(f'Initial position: {pos}')
print(f'Velocity: {vel}')
Initial position: [1.16689374e+14 3.48350725e+14 2.51559839e+14]
Velocity: [330. -94. 53.]
Thankfully, the matrix inverted successfully and we have found a unique solution; the sum of the position coordinates for this solution is:
int(sum(pos))
716599937560103
And so the solution to part 2 is: 716599937560103.
Comments