Advent of Code Day 20 was easy to solve if you spot the hint in the problem description. Let’s dive in!

---

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

---

Part 1

Input is a 2D grid, consisting of tracks ., a start and end track depicted by S and E and walls #.

First, we need to find the least number of tiles in which we can reach from the start tile to the end tile. Number of tiles walked is equal to the number of picoseconds it takes to walk the track.

Now, we need to find ways to finish the race faster when we are allowed “cheat” for 2 picoseconds only once. The rules for “cheat” are as follows:

1. At the time of the cheat, we can pass through walls.
2. At the end of the cheat, we should be back on a the track, ie on a . tile.
3. We can only cheat atmost once during the entire race.
4. The cheat should only last for 2 picoseconds, ie 2 tiles.
5. Each cheat is identified by a start tile and and an end tile.

Consider the following input grid where the best path without ant cheat is 84 tiles long. With one of the cheats visualised below, the number of tile reduces to 72 tiles, 12 tiles lesser than the path without any cheat.

The answer for part 1 is the number of distinct cheats that save atleast 100 picoseconds ie steps to reach from start to end.

Solution

First of all, lets start with finding the best path without any cheats. This is simply using Dijkstra’s algorithm, very similar to how it is implemented here. We need the path traversed as that is needed for finding cheats. I am using a map to store the path where the key is the coordinates of the tile and the value is int, the number of step in the path when this coordinate is traversed.

Now, lets figure out how to find cheats.

Since, the rules specify that we can cheat can only be 2 tiles long and it should always end on the original path, it mean we can only step on a single wall. This makes the problem fairly simple to solve:

1. We only need to check the tiles that are part of the best path as taking a short cut from there can only decrease the length of the path.
2. For each tile on the best path, we need to check all four directions and check if any of them lead to the original path back. If yes and if the number of steps saved is greater than 100, we can add it to the result set.
3. The result set should be a map to avoid overcounting.
4. The number of steps can be found by: (count of steps in original best path for end of cheat coordinates - count of steps in original best path for the tile we are currently checking all four directions in - 2)

Implementing it is now fairly simple:

func ans1(path map[aoc.Coordinates]int, grid [][]string, leastGain int) int {
	dirs := []aoc.Coordinates{aoc.Up, aoc.Down, aoc.Right, aoc.Left}
	uniqueCheats := make(map[cheat]int)
	count := 0

	for current, currentPathCount := range path {
		for _, dir1 := range dirs {
			cheat1 := aoc.Coordinates{current.X + dir1.X, current.Y + dir1.Y}
			if !isValidStep(cheat1, grid) {
				continue
			}
			if grid[cheat1.Y][cheat1.X] != "#" {
				continue
			}

			for _, dir2 := range dirs {
				cheat2 := aoc.Coordinates{cheat1.X + dir2.X, cheat1.Y + dir2.Y}
				if !isValidStep(cheat2, grid) {
					continue
				}
				if val2, ok := path[cheat2]; ok && val2-currentPathCount-2 > 0 {
					uniqueCheats[cheat{s: cheat1, e: cheat2}] = val2 - currentPathCount - 2
					if val2-currentPathCount-2 >= leastGain {
						count++
					}
				}
			}
		}
	}
	return count
}

The value of count is the answer for part 1.

Part 2

Now, instead of cheats of length 2, we can go as high as length 20. We again need to find how many cheat save atleast 100 tiles.

Solution

I initially didn’t understand how to solve this. I tried implementing a recursive, brute force solution but that would run for too long for 20 steps and obviously did not work out. So, time to think of something more optimised.

While trying out different solutions, it occurred to me, that the problem statement clearly mentions that a cheat is unique with its start and end coordinates, the path traversed is not important. So for each coordinates on the path, if the manhattan distance is less than or equal to 20 from another coordinate on the path, that means we have found a cheat!

Manhattan distance between two points can be found as follows:

func ManhattanDistance(p1, p2 Coordinates) int {
	return Abs(p2.Y-p1.Y) + Abs(p1.X-p2.X)
}

Now, we can check for cheats calling the above function between every two points on the path. This can be done using a nested loop.

func ans2(path map[aoc.Coordinates]int, grid [][]string, leastGain int) int {
	uniqueCheats := make(map[cheat]int)
	count := 0

	for p1, d1 := range path {
		for p2, d2 := range path {
			if d2-d1-aoc.ManhattanDistance(p1, p2) >= leastGain && aoc.ManhattanDistance(p1, p2) <= 20 {
				uniqueCheats[cheat{s: p1, e: p2}] = d2 - d1
				count++
			}
		}
	}
	return count
}

And thats it! This gives us the answer to part 2, you can find the final code here.

This was a small easy little problem. I think I most struggled with understanding the problem statement about how cheats work. The hint for part 2 was also clearly mentioned in the problem statement. Once that was clear, the problem became significantly easier to solve. This is yet another reminder to focus on understanding the problem clearly first before jumping to write a solution. Advent of Code is good at reminding me about such simple yet useful techniques for problem solving.

How did you solve Day 20? 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.