Skip to main content

Day 24: Never Tell Me The Odds

by @merlinorg

Puzzle description​

https://adventofcode.com/2023/day/24

Summary​

Day 24 involves calculating the intersections of the lines that some hailstones trace in 2D, and then determining the linear trajectory for a rock in 3D that will intersect the trajectories of all the hailstones in the model.

Model​

Hail​

A hailstone has an initial location and velocity in 3D space.

final case class Hail(x: Long, y: Long, z: Long, vx: Long, vy: Long, vz: Long)

2D Hail​

The first part of this problem asks us to consider just the two-dimensional XY trajectory of the hailstone, so we add a model for this:

final case class Hail2D(x: Long, y: Long, vx: Long, vy: Long)

and then add a method xyProjection method to Hail to get a 2D projection:

// Inside class Hail:
  def xyProjection: Hail2D = Hail2D(x, y, vx, vy)

Parsing​

To parse the input we just pattern match each line. The sample input has some extra whitespace so we need to trim the numbers.

def parseAll(input: String): Vector[Hail] =
  input.linesIterator.toVector.map:
    case s"$x, $y, $z @ $dx, $dy, $dz" =>
      Hail(x.trim.toLong, y.trim.toLong, z.trim.toLong,
            dx.trim.toLong, dy.trim.toLong, dz.trim.toLong)

2D Line Intersection​

2D line intersection is simple geometry. Two infinite lines will always intersect at some point unless they are parallel.

Point of Intersection​

To help solve the problem, you can represent the trajectory of the hail as a general polynomial ax + by + c = 0 and use an equation for the intersection. If the denominator is zero then the lines are parallel and there is no solution.

Add intersect to Hail2D as follows:

// inside class Hail2D
  private val a: BigDecimal = BigDecimal(vy)
  private val b: BigDecimal = BigDecimal(-vx)
  private val c: BigDecimal = BigDecimal(vx * y - vy * x)

  def intersect(hail: Hail2D): Option[(BigDecimal, BigDecimal)] =
    val denominator = a * hail.b - hail.a * b
    Option.when(denominator != 0):
      ((b * hail.c - hail.b * c) / denominator,
       (c * hail.a - hail.c * a) / denominator)

Time of Intersection​

In addition to knowing where the hailstone trajectories intersect, we need to know when the hailstones arrive at this point. This lets us know whether the intersection occurs in the hailstone's future or past.

Add timeTo to Hail2D as follows:

// inside class Hail2D
  def timeTo(posX: BigDecimal, posY: BigDecimal): BigDecimal =
    if vx == 0 then (posY - y) / vy else (posX - x) / vx

Part 1 Solution​

Part 1 asks us to count how many pairs of hailstone have a trajectory that intersects in the 2D XY projection, within a given area, in the hailstone's future, but not necessarily simultaneously.

We iterate through all pairs of hailstones, determining whether their trajectories intersect, and if so if it satisfies the spatial and temporal constraints.

def intersections(
  hails: Vector[Hail2D],
  min: Long,
  max: Long
): Vector[(Hail2D, Hail2D)] =
  for
    (hail0, hail1) <- hails.allPairs
    (x, y)         <- hail0.intersect(hail1)
    if x >= min && x <= max && y >= min && y <= max &&
       hail0.timeTo(x, y) >= 0 && hail1.timeTo(x, y) >= 0
  yield (hail0, hail1)

This takes advantage of an extension method for determining all the pairs:

extension [A](self: Vector[A])
  def allPairs: Vector[(A, A)] = self.tails.toVector.tail.flatMap(self.zip)

Our solution is then to just parse the hailstones, project them onto the XY plane and then count the intersections.

def part1(input: String): Long =
  val hails = parseAll(input)
  val hailsXY = hails.map(_.xyProjection)
  intersections(hailsXY, 200000000000000L, 400000000000000L).size

Part 2​

Part 2 is, at first blush, much more complex. It asks us to determine the location and velocity of a rock that will strike every one of the hailstones, meeting each one at some location in time and space.

Mathing It​

The mathematician in us just wants to solve this directly. Considering a rock at x, y, z with velocity vx, vy, vz and a hailstone x1, y1, z1, vx1, vy1, vz1, the collision will occur at time t1 resulting in three equations in seven variables.

x + vx.t1 = x1 + vx1.t1, y + vy.t1 = y1 + vy1.t1, z + vy.t1 = z1 + vz1.t1

Considering hailstones 2 and 3, we add six more equations and two more variables, giving us nine equations and nine variables.

x + vx.t2 = x2 + vx2.t2, y + vy.t2 = y2 + vy2.t2, z + vy.t2 = z2 + vz2.t2

x + vx.t3 = x3 + vx3.t3, y + vy.t3 = y3 + vy3.t3, z + vy.t3 = z3 + vz3.t3

These are not linear equations, but any non-unique solution requires a contrived hailstone configuration that we don't really need to consider. Plugging these into Z3 or Mathematica gives us an exact solution with no more effort. And, indeed, ScalaZ3 wraps Z3 and gives us a convenient scala API, as demonstrated by @beneyal's solution.

Working It​

For the purpose of this exercise, I did not use Z3. I instead used the observation that from the perspective of the rock (which, from its own perspective, is stationary), all the hailstones will appear to be on a direct collision path with it, and all will intersect with that singular location at some point in time. If we are some observer traveling separately from, but at the same velocity as the rock, all the hailstones will intersect with some single point in space, the location of the rock. So, if we can guess the velocity of the rock, we can then determine its location by finding that point where the trajectories intersect. Moreover, we can solve in X and Y alone, by considering these intersections in just 2D space. And this looks an awful lot like part 1.

The question that this then raises is, how can we know the velocity of the rock. Looking at the sample data, all the hailstones have absolute velocity components less than 1,000. So what we can do is just guess. If we assume the rock velocity is of the same order of magnitude as the hailstones, we can just try every X, Y velocity from -1,000 to 1,000 until we find one where intersections occur.

Shifting Perspective​

We add a method to shift the velocity of a hailstone to a moving observer's frame of reference.

// Inside class Hail2D
  def deltaV(dvx: Long, dvy: Long): Hail2D =
    copy(vx = vx - dvx, vy = vy - dvy)

Determining the Origin of the Rock​

Then we will take three hailstones and compute their intersection from the moving observer's perspective. We compute where the first hailstone will intersect the second, and where it will intersect the third. If these locations are the same in space, then we have a solution and, given the time of one of the intersections, we can trace back to locate the origin of the rock.

def findRockOrigin(
  hails: Vector[Hail2D],
  vx: Long,
  vy: Long
): Option[(Long, Long)] =
  val hail0 +: hail1 +: hail2 +: _ = hails.map(_.deltaV(vx, vy)): @unchecked
  for
    (x0, y0) <- hail0.intersect(hail1)
    (x1, y1) <- hail0.intersect(hail2)
    if x0 == x1 && y0 == y1
    time      = hail0.timeTo(x0, y0)
  yield (hail0.x + hail0.vx * time.longValue,
         hail0.y + hail0.vy * time.longValue)

Pedantically, there exists the possibility of a false positive, where the first three hailstones intersect for some velocity other than the ultimate solution, but not the rest. We could extend our test to include all hailstones, not just the third, but this is fairly improbable given the constraints that positions and velocities are all integers.

Optimizing Our Search Space​

A simple search would just search for vx <- -1000 to 1000 and vy <- -1000 to 1000, but if we assume the rock velocity is closer to zero then this will be inefficient. Instead, we will generate a spiral of initial velocities, starting at (0,0), then (1,0), (1,1), (0,1), (-1, 1), (-1, 0), etc, so we can test locations closer to zero first.

For this, we define a spiral generator FSM that can be used with Iterator.iterate. The code here is longer than it need be because it uses no supporting libraries:

final case class Spiral(
  x: Long, y: Long,
  dx: Long, dy: Long,
  count: Long, limit: Long,
):
  def next: Spiral =
    if count > 0 then
      copy(x = x + dx, y = y + dy, count = count - 1)
    else if dy == 0 then
      copy(x = x + dx, y = y + dy, dy = dx, dx = -dy, count = limit)
    else
      copy(x = x + dx, y = y + dy, dy = dx, dx = -dy,
           count = limit + 1, limit = limit + 1)
  end next
end Spiral

object Spiral:
  final val Start = Spiral(0, 0, 1, 0, 0, 0)

Part 2 Solution​

Our part 2 solution is to then just use the spiral generator to produce candidate rock velocities for which we attempt to find a rock origin. Once we find a solution we know the X and Y location and velocity of the rock. We can then just repeat exactly the same search for an XZ projection of the hailstones to find the Z origin of the rock. This search could be optimized since the x velocity is already known, so we only need to test z candidates, but this is less effort.

First add a method xzProjection method to Hail to get a 2D projection:

// Inside class Hail:
  def xzProjection: Hail2D = Hail2D(x, z, vx, vz)

Next, add a helper method to find a value in an iterator:

// An unruly and lawless find-map-get
extension [A](self: Iterator[A])
  def findMap[B](f: A => Option[B]): B = self.flatMap(f).next()

Finally solve part 2

def part2(input: String): Long =
  val hails = parseAll(input)

  val hailsXY = hails.map(_.xyProjection)
  val (x, y)  = Iterator
    .iterate(Spiral.Start)(_.next)
    .findMap: spiral =>
      findRockOrigin(hailsXY, spiral.x, spiral.y)

  val hailsXZ = hails.map(_.xzProjection)
  val (_, z)  = Iterator
    .iterate(Spiral.Start)(_.next)
    .findMap: spiral =>
      findRockOrigin(hailsXZ, spiral.x, spiral.y)

  x + y + z
end part2

Final Code​

The complete solution follows:

final case class Hail(x: Long, y: Long, z: Long, vx: Long, vy: Long, vz: Long):
  def xyProjection: Hail2D = Hail2D(x, y, vx, vy)
  def xzProjection: Hail2D = Hail2D(x, z, vx, vz)

def parseAll(input: String): Vector[Hail] =
  input.linesIterator.toVector.map:
    case s"$x, $y, $z @ $dx, $dy, $dz" =>
      Hail(x.trim.toLong, y.trim.toLong, z.trim.toLong,
            dx.trim.toLong, dy.trim.toLong, dz.trim.toLong)

final case class Hail2D(x: Long, y: Long, vx: Long, vy: Long):
  private val a: BigDecimal = BigDecimal(vy)
  private val b: BigDecimal = BigDecimal(-vx)
  private val c: BigDecimal = BigDecimal(vx * y - vy * x)

  def deltaV(dvx: Long, dvy: Long): Hail2D = copy(vx = vx - dvx, vy = vy - dvy)

  // If the paths of these hailstones intersect, return the intersection
  def intersect(hail: Hail2D): Option[(BigDecimal, BigDecimal)] =
    val denominator = a * hail.b - hail.a * b
    Option.when(denominator != 0):
      ((b * hail.c - hail.b * c) / denominator,
       (c * hail.a - hail.c * a) / denominator)

  // Return the time at which this hail will intersect the given point
  def timeTo(posX: BigDecimal, posY: BigDecimal): BigDecimal =
    if vx == 0 then (posY - y) / vy else (posX - x) / vx
end Hail2D

extension [A](self: Vector[A])
  // all non-self element pairs
  def allPairs: Vector[(A, A)] = self.tails.toVector.tail.flatMap(self.zip)

extension [A](self: Iterator[A])
  // An unruly and lawless find-map-get
  def findMap[B](f: A => Option[B]): B = self.flatMap(f).next()

def intersections(
  hails: Vector[Hail2D],
  min: Long,
  max: Long
): Vector[(Hail2D, Hail2D)] =
  for
    (hail0, hail1) <- hails.allPairs
    (x, y)         <- hail0.intersect(hail1)
    if x >= min && x <= max && y >= min && y <= max &&
       hail0.timeTo(x, y) >= 0 && hail1.timeTo(x, y) >= 0
  yield (hail0, hail1)
end intersections

def part1(input: String): Long =
  val hails = Hail.parseAll(input)
  val hailsXY = hails.map(_.xyProjection)
  intersections(hailsXY, 200000000000000L, 400000000000000L).size
end part1

def findRockOrigin(
  hails: Vector[Hail2D],
  vx: Long,
  vy: Long
): Option[(Long, Long)] =
  val hail0 +: hail1 +: hail2 +: _ = hails.map(_.deltaV(vx, vy)): @unchecked
  for
    (x0, y0) <- hail0.intersect(hail1)
    (x1, y1) <- hail0.intersect(hail2)
    if x0 == x1 && y0 == y1
    time      = hail0.timeTo(x0, y0)
  yield (hail0.x + hail0.vx * time.longValue,
         hail0.y + hail0.vy * time.longValue)
end findRockOrigin

final case class Spiral(
  x: Long, y: Long,
  dx: Long, dy: Long,
  count: Long, limit: Long,
):
  def next: Spiral =
    if count > 0 then
      copy(x = x + dx, y = y + dy, count = count - 1)
    else if dy == 0 then
      copy(x = x + dx, y = y + dy, dy = dx, dx = -dy, count = limit)
    else
      copy(x = x + dx, y = y + dy, dy = dx, dx = -dy,
           count = limit + 1, limit = limit + 1)
  end next
end Spiral

object Spiral:
  final val Start = Spiral(0, 0, 1, 0, 0, 0)

def part2(input: String): Long =
  val hails = Hail.parseAll(input)

  val hailsXY = hails.map(_.xyProjection)
  val (x, y)  = Iterator
    .iterate(Spiral.Start)(_.next)
    .findMap: spiral =>
      findRockOrigin(hailsXY, spiral.x, spiral.y)

  val hailsXZ = hails.map(_.xzProjection)
  val (_, z)  = Iterator
    .iterate(Spiral.Start)(_.next)
    .findMap: spiral =>
      findRockOrigin(hailsXZ, spiral.x, spiral.y)

  x + y + z
end part2

Solutions from the community​

Share your solution to the Scala community by editing this page. You can even write the whole article! See here for the expected format