Another day, another 2D grid! Advent of Code Day 16 was all about Dijkstra’s algorithm, lets dive in.

---

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

---

Part 1

The input is a map of the 2D grid we need to navigate today. There are 4 types of tiles:

1. . - a walkable tile.
2. # - a wall tile.
3. S - the starting tile.
4. E - the destination tile.

The reindeer starts at the tile containing S , facing east. The score is increased by 1 for each step taken. Each turn (ie direction change) incurs an additional 1000 score as well. The reindeer is allowed to turn 90 degrees, clockwise or anticlockwise.

Many paths exist for the reindeer to reach the destination tile. We need to find the path which incurs the lowest score to reach the destination tile. This lowest score is the answer for part 1.

Consider the following input. One of the possible best paths is visualised which incurs the lowest score of 7036 with 36 steps and 7 turns.

Solution

What we need to find is the shortest path from start to destination. That calls for Dijkstra! We will implement the algorithm using a priority queue.

For each node of priority queue, I am storing:

• Coordinates.
• Direction to take.
• Current score.
• Path traversed so far.

For each new step, we check the allowed 3 directions, if any of them is not a wall, ie a # tile, we add that to the queue increasing the score appropriately if its a turn.

func getNextSteps(current step, grid [][]string, visited map[point]struct{}) []step {
	possibleNext := []step{}
	for _, dir := range getAllowedDirections(current.lastDir) {
		newPosition := aoc.Coordinates{current.co.X + dir.X, current.co.Y + dir.Y}

		if !isValidStep(newPosition, grid) {
			continue
		}

		if grid[newPosition.Y][newPosition.X] == "#" {
			continue
		}

		if _, ok := visited[point{newPosition, dir}]; ok {
			continue
		}

		score := current.score + 1
		if dir != current.lastDir {
			score += 1000
		}

		possibleNext = append(possibleNext, step{
			co:      newPosition,
			lastDir: dir,
			score:   score,
			path:    copyMap(current.path),
		})
	}
	return possibleNext
}

To ensure we don’t get stuck in a loop, we will maintain a visited map of coordinates with the direction we have already traversed. We iterate over the queue till we find the destination.

Putting it all together, here is what the implementation looks like:

func dijktras(matrix [][]string) (int, map[aoc.Coordinates]int) {

	priorityQueue := pq.NewWith(func(a, b interface{}) int {
		return a.(step).score - b.(step).score
	})

	priorityQueue.Enqueue(step{aoc.Coordinates{1, len(matrix) - 2}, aoc.Right, 0, make(map[aoc.Coordinates]int)})

	visited := make(map[point]struct{})

	for !priorityQueue.Empty() {
		element, _ := priorityQueue.Dequeue()

		currentNode := element.(step)

		if _, ok := visited[point{currentNode.co, currentNode.lastDir}]; ok {
			continue
		}

		currentNode.path[currentNode.co] = currentNode.score

		if matrix[currentNode.co.Y][currentNode.co.X] == "E" {
			return currentNode.score, currentNode.path
		}

		nextSteps := getNextSteps(currentNode, matrix, visited)
		for _, n := range nextSteps {
			priorityQueue.Enqueue(n)
		}

		visited[point{currentNode.co, currentNode.lastDir}] = struct{}{}
	}
	return -1, make(map[aoc.Coordinates]int)
}

The score returned is the answer for part 1.

Part 2

Now we need to find the count of distinct tiles that lie in atleast one of the best paths.

Consider the previous example, the number of distinct tiles across all best paths is 45 in this case visualised below.

Solution

Now we need to find all best paths and find the number of distinct tiles across them. We already have the path of one of the best paths from part 1.

The key insight I used here was that, any other best path would only have a subsection of the path that is different from the original path. This means, when we return back to the original path and the score also matches, we have discovered a new subsection of a new best path. When a subsection of a new best path is found, we can iterate over it to find distinct coordinates that aren’t already considered in the original best path.

To keep finding sections of new best paths, instead of returning from Dijkstra’s algorithm when we reach the destination tile, we keep iterating over over all the enqueued points.

Implementing this looks like this:

func getUniqueCount(matrix [][]string, path map[aoc.Coordinates]int) int {

	priorityQueue := pq.NewWith(func(a, b interface{}) int {
		return a.(step).score - b.(step).score
	})

	priorityQueue.Enqueue(step{aoc.Coordinates{1, len(matrix) - 2}, aoc.Right, 0, make(map[aoc.Coordinates]int)})

	visited := make(map[point]struct{})
	newSafeCoordinates := make(map[aoc.Coordinates]struct{})

	for !priorityQueue.Empty() {
		element, _ := priorityQueue.Dequeue()

		currentNode := element.(step)

		if score, ok := path[currentNode.co]; ok && score == currentNode.score {
			for point, _ := range currentNode.path {
				if _, ok := path[point]; !ok {
					newSafeCoordinates[point] = struct{}{}
				}
			}
		}

		if _, ok := visited[point{currentNode.co, currentNode.lastDir}]; ok {
			continue
		}

		currentNode.path[currentNode.co] = currentNode.score

		if matrix[currentNode.co.Y][currentNode.co.X] == "E" {
			continue
		}

		nextSteps := getNextSteps(currentNode, matrix, visited)
		for _, n := range nextSteps {
			priorityQueue.Enqueue(n)
		}

		visited[point{currentNode.co, currentNode.lastDir}] = struct{}{}
	}
	return len(path) + len(newSafeCoordinates)
}

The returned count is the answer for part 2. You can find my final code here.

Day 16 was a classic entry for Dijkstra’s in Advent of Code. I always found this algorithm quite daunting to use before, but I finally understood it properly while solving AOC last year. So when I read this year’s Day 16 problem, I was ready! This is one of the reasons I like doing advent of code, you get to learn and relearn things with a fun and interesting problem statement.

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