Skip to main content

Day 8: Resonant Collinearity

by @merlinorg

Puzzle description​

https://adventofcode.com/2024/day/8

Solution summary​

  1. Parse the map to identify the locations of all the antennae, grouped by their frequency.
  2. Find all the antinode locations within the map boundary.
  3. Count the number of distinct antinodes.

Data model​

First, we'll define some case classes to represent the antenna map. We could use tuples, but the named classes help readability.

Antenna map​

An antenna map contains the width and height of the map, along with a sequence of sequences of antenna locations. Each sequence of antenna locations corresponds to a particular frequency (i.e. a particular letter or digit on the map.)

case class AntennaMap(
  width: Int,
  height: Int,
  antennaGroups: Iterable[Seq[Location]],
)

Location​

A location is an x, y pair along with some helpers for location arithmetic and range checking.

case class Location(x: Int, y: Int):
  def -(other: Location): Vec          = Vec(x - other.x, y - other.y)
  def +(vec: Vec): Location            = Location(x + vec.dx, y + vec.dy)
  def within(map: AntennaMap): Boolean = x >= 0 && x < map.width && y >= 0 && y < map.height
end Location

case class Vec(dx: Int, dy: Int)

Parsing​

To parse the map, we iterate through each line of the input and each character of each line, emitting an antenna tuple (the character and location) if the character is alphanumeric. We then return a board containing the map dimensions and the antennae, grouped by their frequency (the character).

def parse(input: String): AntennaMap =
  val lines = input.linesIterator.toSeq

  val antennae: Seq[(Char, Location)] = for
    (line, y) <- lines.zipWithIndex
    (char, x) <- line.zipWithIndex
    if Character.isLetterOrDigit(char)
  yield char -> Location(x, y)

  AntennaMap(
    lines.head.length,
    lines.size,
    antennae.groupMap(_._1)(_._2).values
  )
end parse

Part 1​

For part 1, we take each pair of antennae of a given frequency and locate their antinodes. We then count the number of distinct locations within the map area.

According to the puzzle, the antinodes are collinear with each pair of same-frequency antennae, but located at twice the distance from one antenna as the other. Vector algebra tells us that the two antinodes of antennae A and B lie at A + B→A and B + A→B, where B→A is the vector from B to A, because |A → (B + A→B)| = |A→B| + |A→B| = 2|A→B|.

The code thus loops through each antenna group, loops through each combination of two antennae of a given frequency, computes the two antinodes, tests that they are within the map, and then counts the distinct results.

def part1(input: String): String =
  val map = parse(input)

  val antinodes: Iterable[Location] = for
    antennaGroup     <- map.antennaGroups
    case a +: b +: _ <- antennaGroup.combinations(2)
    antinode         <- Seq(a + (a - b), b + (b - a))
    if antinode.within(map)
  yield antinode

  antinodes.toSet.size.toString
end part1

Part 2​

Part 2 is very similar to part 1, but instead of there being only two antinodes, the antinodes occur at any location that is a whole multiple of the distance between the antennae. That is, the antinodes lie at A + n(B→A). We can use Iterator.iterate to generate the infinite series of these locations and then just take while the location is within the map.

def part2(input: String): String =
  val map = parse(input)

  val antinodes: Iterable[Location] = for
    antennaGroup     <- map.antennaGroups
    case a +: b +: _ <- antennaGroup.combinations(2)
    antinode         <- Iterator.iterate(a)(_ + (a - b)).takeWhile(_.within(map)) ++
                          Iterator.iterate(b)(_ + (b - a)).takeWhile(_.within(map))
  yield antinode

  antinodes.toSet.size.toString
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