Advent of Code Day 10 was a funny one where many folks, including me, found the answer for part 2 before part 1. Lets find out how!

---

The below is a guest post by the amazing Shraddha Agrawal.

---

Part 1

The input is a 2D grid, representing a topographic map of an area, where each cell has a digit value. The value defines the height of the area at the cell’s coordinates.

We need to find hiking trails that start from the lowest height, and gradually increases height and is the longest. This means each hiking trail should start at 0 and end at 9 and should be of length 10. The map is such that, a starting position, ie a cell with value 0 can lead to several different hiking trails.

For part 1, for each cell with value 0, we need to find the distinct number of cells with value 9 that can be reached. The final answer should be the sum of this value for all 0 valued cells.

Not to be confused with distinct paths. A starting cell can reach the same 9 from many different hiking trails.

Consider the first example above, the ending cell can be reached by various different paths as shown below:

For part 1, we only want to count the number of distinct reachable ending cells, ie cells valued 9. For the above example, only 1 ending cells can be reached from the 0 at (0,0).

Solution

The crux of the problem is finding the number of distinct paths from each 0 valued cell. This is easily solved using a recursive function.

Before we write the recursive function, lets write a function that returns the next cells to traverse from the current position. The key point here is that only those cells should be traversed next which have the value that is 1 greater than the current cell’s value.

func findNext(input [][]int, current point) []point {
	validNextSteps := []point{}
	// can check left
	if current.x > 0 && input[current.y][current.x-1] == input[current.y][current.x]+1 {
		validNextSteps = append(validNextSteps, point{current.x - 1, current.y})
	}

	// can check right
	if current.x < len(input[0])-1 && input[current.y][current.x+1] == input[current.y][current.x]+1 {
		validNextSteps = append(validNextSteps, point{current.x + 1, current.y})
	}

	// can check up
	if current.y > 0 && input[current.y-1][current.x] == input[current.y][current.x]+1 {
		validNextSteps = append(validNextSteps, point{current.x, current.y - 1})
	}

	// can check down
	if current.y < len(input)-1 && input[current.y+1][current.x] == input[current.y][current.x]+1 {
		validNextSteps = append(validNextSteps, point{current.x, current.y + 1})
	}
	return validNextSteps
}

Now, lets write our recursive function. A few things:

1. The success condition is if the current cell is 9. This means we have reached the end of the trail. Since we need count of distinct end cells, we need to check if we have reached this 9 before. We can easily do this using a map. If this cell has not been reached before, we can increase the count.
2. The exit condition is if the current cell does not have any next possible cells to traverse.
3. We call this function recursively on all possible next steps to final all distinct end points.

Writing this out, we have:

func findScore(input [][]int, start point, trailHeads map[point]struct{}, count int) (map[point]struct{}, int) {
	if input[start.y][start.x] == 9 {
		if _, ok := trailHeads[start]; !ok {
			trailHeads[start] = struct{}{}
			count += 1
		}
		return trailHeads, count
	}
	nextSteps := findNext(input, start)
	if len(nextSteps) == 0 {
		return trailHeads, count
	}

	for _, step := range nextSteps {
		trailHeads, count = findScore(input, step, trailHeads, count)
	}
	return trailHeads, count
}

And finally, we can traverse the input map and call the above function for each cell with value 0 to get the final answer!

Part 2

This time, instead of distinct end points, we need to find distinct paths to all possible end points. That is the above example, where a single 9 can be reached in many different ways from the same 0 is what we’re supposed to count now.

Solution

This one is extremely simple. Now, in our recursive function, we do NOT need to be careful about distinct 9s can should increment count every single time we reach an end cell. That is, we just need to move the count increment outside of the map check.

func findScore(input [][]int, start point, trailHeads map[point]struct{}, count int) (map[point]struct{}, int) {
	if input[start.y][start.x] == 9 {
		if _, ok := trailHeads[start]; !ok {
			trailHeads[start] = struct{}{}
		}
		return trailHeads, count + 1
	}
	nextSteps := findNext(input, start)
	if len(nextSteps) == 0 {
		return trailHeads, count
	}

	for _, step := range nextSteps {
		trailHeads, count = findScore(input, step, trailHeads, count)
	}
	return trailHeads, count
}

And with this one line change, we have the answer for part 2, how neat was that! You can find the final code here.

While solving this problem, I had initially not bee careful to find distinct end points in part 1, ie, hadn’t added the visited map, and accidentally found the answer to part 2 first. On reading the second part’s description, I was elated! After a tough Day 9, this felt good :)

Did you also find the answer to part 2 before part 1 for Day 9? I would love to compare notes and checkout your solution. Reach out to me on Twitter, Bluesky or on e-mail at contact[at]shraddhaag[dot]dev.