Advent of Code 2023 - Day 24Never Tell Me The Odds

| Problem statement | Source code | Tags: GeometryMathematics

Part 1

Each hailstone is a parametric equation. If we are given x1, y1, z1 @ vx1, vy1, vz1, then the position of the hailstone at time t is given by:

where $\mathbf{p}_1(0) = (x_1, y_1, z_1)^\top$ and $\mathbf{v}_1 = (vx_1, vy_1, vz_1)^\top$.

In part 1 we only care about 2D, so instead $\mathbf{p}_1(0) = (x_1, y_1)^\top$ and $\mathbf{v}_1 = (vx_1, vy_1)^\top$. To find the intersection of two hailstone paths (perhaps at different times) is to find the solution to:

This linear system can be directly solved in R gmp with solve.bigz. The system may not have a solution if the two paths are parallel; we additionally require $t_1, t_2 \geq 0$ for the solution to be valid. The intersection point can be found by plugging $t_1$ into $\mathbf{p}_1(t)$.

intersection2d <- function(l1, l2) {
  v_mat <- matrix(c(l1[4], l1[5], -l2[4], -l2[5]), nrow = 2)
  b_vec <- c(l2[1] - l1[1], l2[2] - l1[2])
  sol <- tryCatch(solve.bigz(v_mat, b_vec), error = function(e) NULL)
  if (is.null(sol) || any(sol < 0)) {
    return(NULL)
  }
  c(l1[1], l1[2]) + sol[1] * c(l1[4], l1[5])
}

After obtaining the intersection point, we can easily test if it's in the test area.

Part 2

Now coordinates are 3D. We need some $\mathbf{p}(0)$ and $\mathbf{v}$, such that for every $i$,

If we take two trails, $i$ and $j$, we can eliminate $\mathbf{p}(0)$:

This means that $\mathbf{p}_j(0) - \mathbf{p}_i(0)$ can be expressed as a linear combination of $\mathbf{v}_i - \mathbf{v}$ and $\mathbf{v}_j - \mathbf{v}$, i.e., $\mathbf{p}_j(0) - \mathbf{p}_i(0)$ is in the plane spanned by $\{\mathbf{v}_i - \mathbf{v}, \mathbf{v}_j - \mathbf{v}\}$. Note that $\mathbf{v}_j - \mathbf{v}_i$ is also in this plane, so we can express this in terms of the scalar triple product:

(because $\times$ gives a normal vector to the plane, and $\cdot$ returns 0 if the two vectors are perpendicular).

Now this can be separated into an equation in $\mathbf{v}$:

This is a single linear equation. Because $\mathbf{v}$ has three components, we need at least three equations in this form, which means taking three trails.

num_eq <- 3
A <- matrix(as.bigz(0), nrow = num_eq, ncol = 3)
b <- matrix(as.bigz(0), nrow = num_eq, ncol = 1)
for (i in 1:num_eq) {
  j <- i %% num_eq + 1
  v_diff <- hails[[j]][4:6] - hails[[i]][4:6]
  p_diff <- hails[[j]][1:3] - hails[[i]][1:3]
  cross_prod <- cross(v_diff, p_diff)
  A[i, ] <- cross_prod
  b[i] <- sum(cross_prod * hails[[i]][4:6])
}
v <- tryCatch(solve.bigz(A, b), error = function(e) NULL)

I didn't really verify that this solution works on the remaining hail paths, because they'd better be (otherwise there's no answer). After solving for $\mathbf{v}$, we can plug it into two lines to solve for $t$ on 2D (it's guaranteed that the z-coordinate must match as well, otherwise it wouldn't be a solution). This can take advantage of the existing intersection2d function.

p1 <- as.bigz(hails[[1]][1:3])
p2 <- as.bigz(hails[[2]][1:3])
v1 <- as.bigz(hails[[1]][4:6])
v2 <- as.bigz(hails[[2]][4:6])
pxy <- intersection2d(c(p1, v1 - v), c(p2, v2 - v))

Finally, we can deduce the z-coordinate.

t1 <- (pxy[1] - p1[1]) / (v1[1] - v[1])
pz <- p1[3] + t1 * (v1[3] - v[3])