Skip to main content

Day 10: Hoof It

by @SethTisue

Puzzle description​

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

Summary​

Like many Advent of Code puzzles, this is a graph search problem. Such problems are highly amenable to recursive solutions.

In large graphs, it may be necessary to memoize intermediate results in order to get good performance. But here, it turns out that the graphs are small enough that recursion alone does the job just fine.

Shared code​

Let's start by representing coordinate pairs:

  type Pos = (Int, Int)
  extension (pos: Pos)
    def +(other: Pos): Pos =
      (pos(0) + other(0), pos(1) + other(1))

and the input grid:

  type Topo = Vector[Vector[Int]]
  extension (topo: Topo)
    def apply(pos: Pos): Int =
      topo(pos(0))(pos(1))
    def inBounds(pos: Pos): Boolean =
      pos(0) >= 0 && pos(0) < topo.size &&
      pos(1) >= 0 && pos(1) < topo.head.size
    def positions =
      for row <- topo.indices
          column <- topo.head.indices
      yield (row, column)

So far this is all quite typical code that is usable in many Advent of Code puzzles.

Reading the input is typical as well:

  def getInput(name: String): Topo =
    io.Source.fromResource(name)
    .getLines
    .map(_.map(_.asDigit).toVector)
    .toVector

In order to avoid doing coordinate math all the time, let's turn the grid into a graph by analyzing which cells are actually connected to each other. Each cell can only have a small number of "reachable" neighbors -- those neighbors that are exactly 1 higher than us.

  type Graph = Map[Pos, Set[Pos]]

  def computeGraph(topo: Topo): Graph =
    def reachableNeighbors(pos: Pos): Set[Pos] =
      Set((-1, 0), (1, 0), (0, -1), (0, 1))
      .flatMap: offsets =>
        Some(pos + offsets)
        .filter: nextPos =>
          topo.inBounds(nextPos) && topo(nextPos) == topo(pos) + 1
    topo.positions
    .map(pos => pos -> reachableNeighbors(pos))
    .toMap

with this graph structure in hand, we can forget about the grid and solve the problem at a higher level of abstraction.

Part 1​

Part 1 is actually more difficult than part 2, in my opinion. In fact, in my first attempt to solve part 1, I accidentally solved part 2! Once I saw part 2, I had to go back and reconstruct what I had done earlier.

From a given trailhead, the same summit may be reachable by multiple routes. Therefore, we can't just count routes; we must remember what the destinations are. Hence, the type of the recursive method is Set[Pos] -- the set of summits that are reachable from the current position.

  def solve1(topo: Topo): Int =
    val graph = computeGraph(topo)
    def reachableSummits(pos: Pos): Set[Pos] =
      if topo(pos) == 9
      then Set(pos)
      else graph(pos).flatMap(reachableSummits)
    topo.positions
    .filter(pos => topo(pos) == 0)
    .map(pos => reachableSummits(pos).size)
    .sum

  def part1(name: String): Int =
    solve1(getInput(name))

As mentioned earlier, note that we don't bother memoizing. That means we're doing some redundant computation (when paths branch and then rejoin), but the code runs plenty fast anyway on the size of input that we have.

Part 2​

The code for part 2 is nearly identical. We no longer need to de-duplicate routes that have the same destination, so it's now sufficient for the recursion to return Int.

It would certainly be possible to refactor this to share more code with part 1, but I've chosen to leave it this way.

  def solve2(topo: Topo): Int =
    val graph = computeGraph(topo)
    def routes(pos: Pos): Int =
      if topo(pos) == 9
      then 1
      else graph(pos).toSeq.map(routes).sum
    topo.positions
    .filter(pos => topo(pos) == 0)
    .map(routes)
    .sum

  def part2(name: String): Int =
    solve2(getInput(name))

One tricky bit here is the necessity to include toSeq when recursing. That's because we have a Set[Pos], but if we .map(...) on a Set, the result will also be a Set. But we don't want to throw away duplicate counts.

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