202412100000 Advent of Code 2024 Day 10

Hoof It

Today we're back at the Lava Production Facility from 2023 day 15 helping reindeer find the best hiking routes around their floating island.

The Puzzle

Today we're back at the Lava Production Facility from 2023 day 15 helping reindeer find the best hiking routes around their floating island.

We're given a topographic map of the island and need to search for paths from the bottoms of the hills to the tops. For the first part, we only need to count the number of summits that are reachable from each trailhead. The second part asks for the total number of unique paths from each trailhead to each summit. For example,

.....0.
..4321.
..5..2.
..6543.
..7..4.
..8765.
..9....

Using this topographic map for part 1 would result in an answer of 1 since there is only one unique summit (9) starting from the trailhead (0). For part 2 the answer is 3 since there are 3 paths from the 0 to the 9.

Lastly, we're constrained to only counting paths that are monotonically increasing by one level each step: staying at the same elevation, going down, and going up by more than one level are all prohibited.

Solution

I'll show the glue code for today first.

export const solve = (input, all) => {
  let trailheads = [];
  const grid = input.map((l, y) =>
    chars(l).map((c, x) => {
      const n = +c;
      if (n === 0) trailheads.push([x, y]);
      return n;
    }),
  );

  let sum = 0;
  for (let [x, y] of trailheads) {
    let seen = new Set();
    sum += paths(grid, all ? undefined : seen, y, x);
  }

  return sum;
};

export const solutionOne = (input) => solve(input, false);
export const solutionTwo = (input) => solve(input, true);

We parse the inputs, find the trailheads, loop over them, and count the paths for each part per trailhead. We parameterize the path counting by the uniqueness constraint that separates the two parts using a set of seen points. For the first part, we use the set to deduplicate paths and for the second part, we just don't.

The paths function is a simple depth-first search.

const paths = (grid, seen, y, x) => {
  let sum = 0;
  for (const [v, r, c] of grid.nbrs(y, x, false, false)) {
    if (v - grid[y][x] === 1) {
      if (v === 9) {
        if (seen) {
          const hash = sk(c, r);
          if (seen.has(hash)) continue;
          seen.add(hash);
        }
        sum += 1;
      } else {
        sum += paths(grid, seen, r, c);
      }
    }
  }
  return sum;
};

We get all the neighboring grid locations (without diagonals per the problem definition), loop over them, and explore the path until it's invalid or we find the summit. Invalid states are given by the elevation change, whether we've seen it or not in part 1, and whether or not we're in the grid (which our nbrs function helpfully omits so we never have to check that here).

A straightforward example of DFS today: pretty fun, and not much to rewrite between parts. Looking forward to tomorrow.

You can find the full solutions to today's AoC puzzles in my AoC GitHub repo.