AOC Day 24 Part 2

I liked this puzzle! I re-learned some geometry and linear algebra!

There are lots of good solutions on Reddit. For my part, I used the sympy library to do some Algebra, and used a fun property of skew lines.

As a reminder of the puzzle: we have multiple hailstone rays, defined by initial position (x,y,z) and velocity (dx, dy, dz), and we are seeking to throw a rock that will collide with all of our existing rays. The collision is not just intersection: we're thinking of these as rocks travelling over time.

Reading data & parsing

Nothing to see here; boring parsing.

import re

SAMPLE = """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"""

def parse(s):
    return [ [int(x) for x in re.split("[^0-9-]+", line) ] for line in s.splitlines() ]

ray_tuples = parse(SAMPLE)
# Could be done ofr the "real" inputas well.
# ray_tuples = list(parse(open("24-input.txt").read()))
ray_tuples

[[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]]

Establish symbolic lines

We can use sympy to create Line/Ray objects and we can visualize them. It's not useful, but it's pretty.

from sympy import Point, Line, Ray, symbols, matrices, plotting, Eq, solve

t = symbols('t')
rays = [ Ray(Point(x, y, z), Point(x+dx, y+dy, z+dz)) for x,y,z,dx,dy,dz in ray_tuples ]
WINDOW = 1000000000000

plotting.plot3d_parametric_line( *[ (r.arbitrary_point(t).x, r.arbitrary_point(t).y, r.arbitrary_point(t).z, (t, 0, WINDOW)) for r in rays ])

<sympy.plotting.plot.Plot at 0x1099e4bd0>

We can, with only a little bit of loss of generality, define our target ray as one that intersects with the first line at t₀ and the second line at t₁.

t0, t1 = symbols("t0 t1")
p0, p1 = rays[0].arbitrary_point(t0), rays[1].arbitrary_point(t1)
rockline = Line(p0, p1)

Geometry ❤️ Linear Algebra

By construction, we know that our rockline intersects rays 0 and 1. We know that it must intersect ray 2 as well from the puzzle.

Since the lines intersect, we know that they must share a plane. They are not skew. (Two lines are skew lines if they do not intersect and are not parallel.)

If A and B are points on one line, and C and D are points on the other line, and those lines are coplanar, then the determinant of (A-B, C-D, and A-C) must be zero. So we're going to set it to zero, and try to solve for t0 and t1.

The intuition in wikipedia for this is that two skew lines are the non-intersecting edges of a tetrahedron, and this is roughly the formula for the volume of the tetrahedron. My intuition is a little simpler: let's rotate the two lines so that they're on the xy plane, and translate so that the intersection is at the origin. We can further skew things so that one line is on the x axis and the other line is on the y axis. The "A-C" line is going to be also in the xy plane. So, these three vectors can't possibly describe a 3-dimensional vector space, since nothing goes into the z axis... In other words, the vectors AB, CD, and AC are all coplanar and therefore not the basis of a 3-dimensional vector space, and, that means the determinant must be zero.

We compute these determinants for the next two vectors, which gives us to equations in two variables:

t = symbols('t')
eqns = []
for idx in [2, 3]:
    ray = rays[idx]
    AB = rockline.arbitrary_point(t).subs({t:1}) - rockline.arbitrary_point(t).subs({t:0})
    CD = ray.arbitrary_point(t).subs({t:1}) - ray.arbitrary_point(t).subs({t:0})
    AC = rockline.arbitrary_point(t).subs({t:0}) - ray.arbitrary_point(t).subs({t:0})
    m = Eq(matrices.Matrix([AB, CD, AC]).det(), 0)
    eqns.append(m)
eqns[0]

$\displaystyle 32 t_{0} - 160 = 0$

eqns[1]

$\displaystyle 5 t_{0} t_{1} + 60 t_{0} - 37 t_{1} - 264 = 0$

At this point, we have two equations and two unknowns, so we should be able to solve it quite nicely! The API here returns a list of solutions.

solutions = solve(eqns)
solutions

[{t0: 5, t1: 3}]

Excellent. We're so close! We need to pick one that satisfies our constraints, which is that the times are positive integer. (In the sample data, this doesn't show up, but it does show up in my puzzle input.)

valid_solutions = [ x for x in solutions if all([ y >= 0 and y.is_integer for _, y in x.items()]) ]
assert len(valid_solutions) > 0
s = valid_solutions[0]
s

{t0: 5, t1: 3}

Now we have the line and we know some timestamps; we need to back out our starting position and velocity.

rockline2 = rockline.subs(s)
rockline2

$\displaystyle \operatorname{Line3D}\left(\operatorname{Point3D}\left(9, 18, 20\right), \operatorname{Point3D}\left(15, 16, 16\right)\right)$

rockline2.p1, rockline2.p2

(Point3D(9, 18, 20), Point3D(15, 16, 16))

velocity = (rockline2.p2 - rockline2.p1)/(s[t1] - s[t0])
velocity

$\displaystyle \operatorname{Point3D}\left(-3, 1, 2\right)$

start = rockline2.p1 - s[t0]*velocity
start

$\displaystyle \operatorname{Point3D}\left(24, 13, 10\right)$

start, velocity

(Point3D(24, 13, 10), Point3D(-3, 1, 2))

Success! That's our answer. Let's double check that everything intersects nicely and also plot everything...

rays2 = rays + [Ray(start, start + velocity)]
plotting.plot3d_parametric_line( *[ (r.arbitrary_point(t).x, r.arbitrary_point(t).y, r.arbitrary_point(t).z, (t, 0, 10)) for r in rays2 ])

<sympy.plotting.plot.Plot at 0x11fbda490>

rockray = Ray(start, velocity + start)
for ray in rays:
    intersection = rockray.intersect(ray)
    time = solve([ Eq(a, b) for a, b in zip(list(rays[0].arbitrary_point(t)), list(rockray.arbitrary_point(t))) ])[t]
    print(intersection, "at", time)

{Point3D(9, 18, 20)} at 5
{Point3D(15, 16, 16)} at 5
{Point3D(12, 17, 18)} at 5
{Point3D(6, 19, 22)} at 5
{Point3D(21, 14, 12)} at 5

QED