Advent of Code Day 6 was all about path finding and loops detection. Let’s dive in!

---

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

---

Part 1

Input is the map we need to find the “guard’s” path on. For each point on the input grid:

• . - is a valid block to walk on.
• # - signifies an obstacle.
• ^ - signifies the guard’s starting position.

The rules for traversal are defined as below:

• Guard will keep walking in the same direction till an obstacle is encountered.
• When an obstacle is encountered, the guard should turn right by 90 degrees.

For part 1, we need to find the distinct blocks that are on the guard’s path before they exits the map (that is goes out of bounds).

Solution

Part 1 is fairly straightforward. We just need to traverse the path according to the rules till the guard gets out of the map boundary. We start from the coordinates of ^ in the sample input. Main crux of the problem is how do we determine the next step.

Before we tackle what should be the next step, lets first implement a helper function to turn right as per the rules defined above.

func turn90(input [][]string, current point) point {
	switch current.direction {
	case up:
		current.direction = right
	case down:
		current.direction = left
	case right:
		current.direction = down
	case left:
		current.direction = up
	}
	return current
}

Now that we have this, lets implement a function to determine the next step. For each new step, we continue in the same direction and check:

1. Has the guard walked out of bounds? If true, this is our success state and we can exit the function.
2. Has the guard walked into a hurdle? If yes, then we turn and step.
3. Otherwise, the guard has taken a valid step and we continue.

Implementing this would look like:

func findNextStep(input [][]string, current point) (bool, point) {
	valid, possibleNext := getNextStepWithDirectionPreserved(input, current)
	if !valid {
		return false, possibleNext
	}

	switch input[possibleNext.y][possibleNext.x] {
	case "#":
		return getNextStepWithDirectionPreserved(input, turn90(input, current))
	case ".":
		return true, possibleNext
	case "^":
		return true, possibleNext
	}
	return false, possibleNext
}

Now, all we need to do is store in a data structure all distinct coordinates the guard has walked on for the final count. For this I used a map. Putting it all together:

 func findPath(input [][]string, start point) (int, map[coordinates]int) {
	path := make(map[coordinates]int)
	count := 0
	current := start
	for {
		if _, ok := path[coordinates{current.x, current.y}]; !ok {
			count++
			path[coordinates{current.x, current.y}] = current.direction
		}

		isValid, newCurrent := findNextStep2(input, current)
		if !isValid {
			return count, path
		}

		current = newCurrent
	}
	return count, path
}

The count is the answer for the part one. But, the function to calculate the next step does not handle a corner case which becomes important for part two. Let’s figure it out!

Part 2

This is where things got interesting. Now, we want to trap the guard in a loop. We can do this by introducing an obstacle. Some rules are laid down for the same:

1. Only a single obstacle can be placed on the map at a time. This addition of a single obstacle should result in the guard getting trapped in a loop.
2. The obstacle can not be placed on the guard’s starting position.

We need to figure out the total count of unique positions where adding an obstacle will lead to the guard traversing a loop endlessly.

Solution

The most brute force way of solving this would be try placing an obstacle at each . block on the map and see if the guard gets stuck on a loop. While this would work, lets improve upon this!

1. Loop Detection

Let’s start off with loop detection. Since the way the guard can move is so controlled, we can determine if the guard is walking on a loop without traversing the same loop a couple times. If the guard is repeating the same coordinates with the same direction, it means we have encountered a loop.

This can be detected quite trivially with Golang’s map. Implementing it would look like this:

func isLoop(input [][]string, start point) bool {
	path := make(map[point]struct{})
	current := start
	for {
		if _, ok := path[current]; !ok {
			path[current] = struct{}{}
		} else {
			return true
		}

		valid, newCurrent := findNextStep(input, current)
		if !valid {
			return false
		}

		current = newCurrent
	}
	return false
}

2. Where to try adding an obstacle?

Again, how the guard can traverse the map is pretty limited. So putting obstacles where the guard can’t go isn’t going to affect the path at all. So we should only attempt to add an obstacle in the guard’s existing path.

We already have all the distinct locations where the guard is going to walk from part 1. All we need to do is for each of those coordinates, replace . with # ie add an obstacle and see if we can detect a loop. This can be implemented like so:

func findNewObstacleCount(input [][]string, start point, path map[coordinates]int) int {
	count := 0
	obstanceMap := make(map[coordinates]struct{})
	for step, _ := range path {
	  // obstacle can not be placed on the guard's starying point 
		if step.x == start.x && step.y == start.y {
			continue
		}
		if input[step.y][step.x] == "." {

			input[step.y][step.x] = "#"
			if isLoop(input, start) {
				if _, ok := obstanceMap[step]; !ok {
					count++
					obstanceMap[step] = struct{}{}
				}
			}
			input[step.y][step.x] = "."
		}
	}
	return count
}

All the above sounds good, right? When I tried running the above against my sample input, I got the expected answer. Empowered, I ran the above against my actual input and that didn’t work. What gives? Let’s figure it out.

Gotchas in Input

Consider the below input map. In this case, when an obstacle is encountered and we turn right, there is another obstacle. This is a valid case and we need to turn right again, effectively retracing our steps. Here, instead of turning 90 degrees, we are essentially turning 180 degrees.

This was one of those nasty bugs that I wasted many an hour trying to figure out why exactly my code wasn’t working as this case wasn’t present in the sample input.

If two of such cases are placed inline, that would result in a loop. This is visualised brilliantly here.

Accounting for this, we can now fix the issues in our function to calculate the next step:

func findNextStep(input [][]string, current point) (bool, point) {
	valid, possibleNext := getNextStepWithDirectionPreserved(input, current)
	if !valid {
		return false, possibleNext
	}

	switch input[possibleNext.y][possibleNext.x] {
	case "#":
		// this is really subtle, consider the below case
		// where > represents your current position + direction:
		// ....#.....
		// ........>#
		// ........#.
		// When you turn right and step, you again encounter
		// an obstacle (a '#'). This is a valid case and you
		// can not exit the loop at this point.
		// Instead, you turn right once MORE, an effective turn of
		// 180 degrees this time, and then continue forward.
		return findNextStep(input, turn90(input, current))
	case ".":
		return true, possibleNext
	case "^":
		return true, possibleNext
	}
	return false, possibleNext
}

And with that, we can get the count for part two. Final code is available here.

This day was the toughest day of the challenge for me so far. The problem wasn’t inherently difficult to solve, it was the edge case that got me. Figuring it out felt so good though after hours of banging my head against the wall!

Did you find solving Day 6 tough?  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.