Not only can the elf historians teleport, they can travel through time as well. I wonder if Santa has a TARDIS - that would explain how he can deliver all the presents to all the kids in the world.
Today ramped up the difficulty for me significantly. For the first time this year, I had to grab a pen and piece of paper and do some drawings.
Read input
I started with a couple of helper data structures:
from collections import namedtuple
Coordinate = namedtuple("Coordinate", ["x", "y"])
class Token:
EMPTY = "."
GUARD = "^"
OBSTACLE = "#"
OUTSIDE = NoneCoordinate is a well named namedtuple, so we don’t have to remember if the first coordinate is x or y, and instead we can refer to them by name.
Token helps give things more semantic and readable names when navigating the code base. It also helps us avoid magic numbers which in turn helps avoid bugs. I find it nicer to deal with EMPTY, OBSTACLE and OUTSIDE instead of ., # and None in the code.
Like in Day 04, we are dealing with a grid. And again, I’m using a grid dictionary to represent the map. When I run into the cell containing ^, I create a Guard object and mark the spot back to empty so we can later pass through it.
def make_grid(inputs):
grid = {}
for y, row in enumerate(inputs):
for x, cell in enumerate(row):
if cell == Token.GUARD:
guard = Guard(Coordinate(x, y))
cell = Token.EMPTY
grid[Coordinate(x, y)] = cell
return grid, guard
inputs = read_input(6, list)
grid, guard = make_grid(inputs)I decided to model the Guard as a class that knows its own location and direction and has a method to figure out the next location. I also encoded the directions into a helper class to avoid typos.
class Direction:
UP = "up"
DOWN = "down"
LEFT = "left"
RIGHT = "right"
class Guard:
def __init__(self, start):
self.position = start
self.direction = Direction.UP
self.direction_order = deque(
[Direction.RIGHT, Direction.DOWN, Direction.LEFT, Direction.UP]
)
def next(self, grid):
new_coord = None
match self.direction:
case Direction.UP:
new_coord = Coordinate(self.position.x, self.position.y - 1)
case Direction.DOWN:
new_coord = Coordinate(self.position.x, self.position.y + 1)
case Direction.LEFT:
new_coord = Coordinate(self.position.x - 1, self.position.y)
case Direction.RIGHT:
new_coord = Coordinate(self.position.x + 1, self.position.y)
next_location = grid.get(new_coord)
if next_location == Token.EMPTY:
self.position = new_coord
return True
if next_location == Token.OBSTACLE:
self.direction = self.direction_order[0]
self.direction_order.rotate(-1)
return True
if next_location == Token.OUTSIDE:
return FalseIn this puzzle, the guard always starts pointing up so I hard-coded that in. If this would be for a more general approach, I’d pass the starting direction in as an argument.
For directions, I used a collections.deque that I’ve previously used for implementing a rotating turn order. Since the guard always turns 90 degrees right, we can store the turns in a deque and after every turn, rotate it so the previously used turn moves to the end. An alternative (and my initial solution) was to use a four branch if clause but I find this cleaner.
When moving to a next location, we start by calculating the new coordinate. Since we move on a cardinal grid, we either add or subtract 1 from either the x or y coordinate.
We then take a look at what is in the next location. If it’s empty, the guard moves there without changing their direction. If it’s an obstacle, the guard turns 90 degrees but doesn’t move. If it’s outside the grid, we return False to tell our main logic that we’ve ran out of the grid.
When modelling the data like this, a part of the puzzle logic gets implemented into the object. I didn’t write these first and then the rest of the code but the actual process was much more back and forth and iterative and involved multiple rounds of refactoring once I got the right results.
Part 1
In the first part of the puzzle we’re given a grid:
....#.....
.........#
..........
..#.......
.......#..
..........
.#..^.....
........#.
#.........
......#...and we need to find out how many spots does the guard visit when it starts moving from its starting position.
def part_1():
inputs = read_input(6, list)
grid, guard = make_grid(inputs)
visited = set([guard.position])
while guard.next(grid):
visited.add(guard.position)
result = len(visited)
print(f"Part 1: {result}")First we read the data in and create our grid as I explained in the previous section.
Then we need to keep track of all the visited locations, starting with the start position. A Set is a great choice for this one because it will get rid of duplicate locations for us.
We then let the guard move and keep track of visited spots. Since our guard.next() method returns False once it steps outside, we can use that as our while condition.
Finally, to get the result, we count how many unique visited spots there were.
Part 2
And then there was the second part. This was the first time for me this year that I started to struggle.
In this part, we needed to find out how many empty spots (not including the starting location) we can turn into an obstacle where this change would cause the guard to end up in a loop.
In my input, there were 16900 locations in the grid and in the first part, the guard visited 5086 of them. So there’s quite a lot to check.
I tried to approach this from many directions. First I thought I could just check if any turn would lead me to a trajectory that would cross a previously visited spot but that didn’t work because the guard only turns if there are obstacles.
My first proper attempt that led somewhere was to check if the guard had been in the current spot but turned 90 degrees to right before. This would mean adding an obstacle to the next spot would help out.
I then ran that against the example, only to discover it found 3 out of 6 spots.
(alt text for the image above: Hand drawing of a 10x10 grid with a lots of dots and few hashtag symbols. Next to it, text “An obstacle # creates a loop if the guard (^) has been in the previous spot, in 90 degrees to right position before. 6,7 / 6,6 / 4,6 visit exact spot. Missing: spots where following along would hit spot that ends up in a loop.)
Once I drew the grid on an index note and started following along, I discovered that it was missing the spots that had not been visited before but would lead into a loop if followed along.
I’ve often said that my favourite programming tool is pen & paper. It helps me so much to step away from the keyboard and code and work on the problem at hand with text, flow charts, drawings and just writing down my assumptions and ideas.
loop detection is a stable in Advent of Code puzzles and experience in Advent of Code puzzles over the years helps to know how to find the loop but also when to recognise if a loop detection is required when it’s not stated exactly like in today’s puzzle.
So I added that and got the correct result for the example input. But it’s quite different running a code for 10x10 grid with 41 visited spots compared to a 130x130 grid. It took forever to calculate the result with my first naive solution.
My first better solution isn’t very efficient either. It takes tens of seconds to finish but it does get there and so far, I couldn’t yet figure out a more efficient one.
I start by returning the visited path from the part 1 and pass it to the second part as a starting point:
visited = part_1()
part_2(visited)This time, I also keep track of the directions for each visit:
visited = set([(guard.position, Direction.UP)])because that’s crucial knowledge for knowing if I’ve entered a loop or not.
I then brute force the heck out of this grid:
loop_locations = 0
for coordinate in guard_path:
n_guard = Guard(start)
n_grid = grid.copy()
n_visited = visited.copy()
if coordinate == start:
continue
if n_grid.get(coordinate) == Token.EMPTY:
n_grid[coordinate] = Token.OBSTACLE
while n_guard.next(n_grid):
spot = (n_guard.position, n_guard.direction)
if spot in n_visited:
loop_locations += 1
break
n_visited.add(spot)
print(f"Part 2: {loop_locations}")I keep track of locations where a loop would occur.
And for each visited spot in the original path, I create temporary copies of the grid and visited spots and on their turn, change each spot into an obstacle and make the guard walk the grid so many times, keeping track of when they enter a loop.
It’s like that scene from Infinity War where Doctor Strange looks through all potential futures. Poor little guard.
And it works but it takes a while to run. Eric Wastl has said that one way he tries to balance the differences between programming languages is through the complexity of the solutions. This solution is very slow and would be so with any language. That’s a sign to me that this is not an “intended” solution and that there are way quicker ways to figure this out.
Once I’ve written and published this note, I’m gonna take a look and have discussions with people to figure out what tricks I’ve missed. Until then, my brute force doesn’t take half a day and I’m happy I’m a proud owner of 12 stars - still no sign of the Chief Historian though. That’s a shame.