Hoof It | Tommaso Gragnato

You all arrive at a Lava Production Facility on a floating island in the sky. As the others begin to search the massive industrial complex, you feel a small nose boop your leg and look down to discover a reindeer wearing a hard hat.

The reindeer is holding a book titled “Lava Island Hiking Guide”. However, when you open the book, you discover that most of it seems to have been scorched by lava! As you’re about to ask how you can help, the reindeer brings you a blank topographic map of the surrounding area (your puzzle input) and looks up at you excitedly.

Perhaps you can help fill in the missing hiking trails?

The topographic map indicates the height at each position using a scale from 0 (lowest) to 9 (highest). For example:

Based on un-scorched scraps of the book, you determine that a good hiking trail is as long as possible and has an even, gradual, uphill slope. For all practical purposes, this means that a hiking trail is any path that starts at height 0, ends at height 9, and always increases by a height of exactly 1 at each step. Hiking trails never include diagonal steps - only up, down, left, or right (from the perspective of the map).

You look up from the map and notice that the reindeer has helpfully begun to construct a small pile of pencils, markers, rulers, compasses, stickers, and other equipment you might need to update the map with hiking trails.

A trailhead is any position that starts one or more hiking trails - here, these positions will always have height 0. Assembling more fragments of pages, you establish that a trailhead’s score is the number of 9-height positions reachable from that trailhead via a hiking trail. In the above example, the single trailhead in the top left corner has a score of 1 because it can reach a single 9 (the one in the bottom left).

This trailhead has a score of 2:

...0...
...1...
...2...
6543456
7.....7
8.....8
9.....9

(The positions marked . are impassable tiles to simplify these examples; they do not appear on your actual topographic map.)

This trailhead has a score of 4 because every 9 is reachable via a hiking trail except the one immediately to the left of the trailhead:

..90..9
...1.98
...2..7
6543456
765.987
876....
987....

This topographic map contains two trailheads; the trailhead at the top has a score of 1, while the trailhead at the bottom has a score of 2:

10..9..
2...8..
3...7..
4567654
...8..3
...9..2
.....01

Here’s a larger example:

This larger example has 9 trailheads. Considering the trailheads in reading order, they have scores of 5, 6, 5, 3, 1, 3, 5, 3, and 5. Adding these scores together, the sum of the scores of all trailheads is 36.

The reindeer gleefully carries over a protractor and adds it to the pile. What is the sum of the scores of all trailheads on your topographic map?

function findTrails(grid: number[][], startX: number, startY: number): Set<string> {
  const reached9s = new Set<string>();
  const directions = [[-1, 0], [0, 1], [1, 0], [0, -1]];
  const rows = grid.length;
  const cols = grid[0].length;
  
  function dfs(x: number, y: number, visited: Set<string>) {
    if (grid[x][y] === 9) {
      reached9s.add(`${x},${y}`);
      return;
    }

    for (const [dx, dy] of directions) {
      const newX = x + dx;
      const newY = y + dy;
      const key = `${newX},${newY}`;

      if (
        newX >= 0 && newX < rows &&
        newY >= 0 && newY < cols && 
        !visited.has(key) && 
        grid[newX][newY] === grid[x][y] + 1
      ) {
        visited.add(key);
        dfs(newX, newY, visited);
        visited.delete(key);
      }
    }
  }

  dfs(startX, startY, new Set([`${startX},${startY}`]));
  return reached9s;
}

async function main() {
  const input = await Deno.readTextFile("input.txt");
  const grid = input.trim().split('\n').map(line => 
    line.split('').map(Number)
  );
  const rows = grid.length;
  const cols = grid[0].length;
  

  let totalScore = 0;
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (grid[i][j] === 0) {
        const reachable9s = findTrails(grid, i, j);
        totalScore += reachable9s.size;
      }
    }
  }

  console.log(`Sum of trailhead scores: ${totalScore}`);
}

main().catch((err) => console.error(err));

The reindeer spends a few minutes reviewing your hiking trail map before realizing something, disappearing for a few minutes, and finally returning with yet another slightly-charred piece of paper.

The paper describes a second way to measure a trailhead called its rating. A trailhead’s rating is the number of distinct hiking trails which begin at that trailhead. For example:

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

The above map has a single trailhead; its rating is 3 because there are exactly three distinct hiking trails which begin at that position:

.....0.   .....0.   .....0.
..4321.   .....1.   .....1.
..5....   .....2.   .....2.
..6....   ..6543.   .....3.
..7....   ..7....   .....4.
..8....   ..8....   ..8765.
..9....   ..9....   ..9....

Here is a map containing a single trailhead with rating 13:

..90..9
...1.98
...2..7
6543456
765.987
876....
987....

This map contains a single trailhead with rating 227 (because there are 121 distinct hiking trails that lead to the 9 on the right edge and 106 that lead to the 9 on the bottom edge):

Here’s the larger example from before:

Considering its trailheads in reading order, they have ratings of 20, 24, 10, 4, 1, 4, 5, 8, and 5. The sum of all trailhead ratings in this larger example topographic map is 81.

You’re not sure how, but the reindeer seems to have crafted some tiny flags out of toothpicks and bits of paper and is using them to mark trailheads on your topographic map. What is the sum of the ratings of all trailheads?

function countTrails(grid: number[][], startX: number, startY: number): number {
  const dirs = [[-1,0], [0,1], [1,0], [0,-1]];
  const rows = grid.length;
  const cols = grid[0].length;
  let pathCount = 0;
  
  function dfs(x: number, y: number, visited: Set<string>) {
    if (grid[x][y] === 9) {
      pathCount++;
      return;
    }

    for (const [dx, dy] of dirs) {
      const newX = x + dx;
      const newY = y + dy;
      const key = `${newX},${newY}`;

      if (
        newX >= 0 && newX < rows &&
        newY >= 0 && newY < cols && 
        !visited.has(key) && 
        grid[newX][newY] === grid[x][y] + 1
      ) {
        visited.add(key);
        dfs(newX, newY, visited);
        visited.delete(key);
      }
    }
  }

  dfs(startX, startY, new Set([`${startX},${startY}`]));
  return pathCount;
}

async function main() {
  const input = await Deno.readTextFile("input.txt");
  const grid = input.trim().split('\n').map(line => line.split('').map(Number));
  const rows = grid.length;
  const cols = grid[0].length;

  let totalRating = 0;
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (grid[i][j] === 0) {
        const rating = countTrails(grid, i, j);
        totalRating += rating;
      }
    }
  }
  console.log(`Sum of trailhead ratings: ${totalRating}`);
}

main().catch((err) => console.error(err));

Links

Click to show the input

78434565658934341239890154327898789410169567876
89125676543823430123763267016505654321678478965
74034389012710569834354108987419783210501329450
65985293405613478765587017096328798193432010321
54876102564302349323498723165437689087589876501
03123001273211058010567654232126575670670345432
12054320985670769623458912343071464321561210894
23065011234987878543467801056780352143254308743
52176020143010987632966532963091243034165789652
43982176542123676701876547872108389435045630001
04343987233034565899892101543219474326554321100
15458980154901454300765413256978365217893033234
26967898067872343211234322107863210105676128744
37810587120143443205895013278954306018985439653
45721456431234556106786784567805217897851058912
96012367589109667676632397876516986786542367803
87183398676008768985541098923427875987034456934
45698432195419878104323567012434564100124325965
34787563084328769012013432100123473236787619876
23456976176101098743100169981210984345894500761
10067885105432345654221058974303876201903121450
00198793234569854783334567565012565102812034321
87235630321478345698448987545643476983456965410
96544321410145430789567496538753985876589876521
87875401521034521876321323429832104367674307834
76965432690123670965410210018943011278765212985
10126501785434987012124567877654780569890156676
67635652376501456921023498965345698430732347787
58548743210122357830010329453276582521231298898
19989834543218766545689414340189891234560106787
05678129670109658998776504276567760143671015890
14329078786788347643210543183498452087982384321
23010879895690210556987652092354301096543493430
10123965654321987467878941001289212332102584321
89854434365432176307650030110176565443001675610
78765601278300045218941121230145896558903498701
01251012369211234567132430548234787367812345672
14344323054334565478012986699876572210787434987
65689454120423672389873677780125601923896523654
56788763201210981014564578456234892854589018743
45697899854327872103434569327844763765474329012
34307656761056932112363231218903454892365215603
43218947892343341001454120305412178901054508763
52107232103217654012360019456543065016543459454
67800134564308567897871298787832104327872106563
58910129875699430108998345690965432112967654312
67623456766780123234567654321678987003458901203