For day 6 of AoC, our input is a grid showing the setup of a room. Most of the space is marked with periods (“.”), but there are some that are marked with a pound sign (“#”) to denote some sort of obstruction. Also within the grid, is the starting location of a guard, whose route you have to map out.
The guard has a simple routine, they walk forward until they either leave the map (and the route is over) or they hit an obstruction. If they hit an obstruction, they turn 90 degrees to their right and then keep walking forward. The first part of the problem requires us to map out the guards complete route, and count the number of unique blocks within the grid that he enters.
To solve this, I built a primary navigate function that passes the guards movement off to a separate function for each direction that the guard could be traveling (north, south, east, west). I can think of a few ways that I could do this all with a single function, but at the time that I was working one this, they didn’t occur to me and so I figured simple (and working) but not particularly sexy was better spending a good chunk of the night trying to make something better work.
The main logic is in my navigate function.
while True:
if dir == "north":
moves, cord, next_dir = move_north(grid, cord)
elif dir == "south":
moves, cord, next_dir = move_south(grid, cord)
elif dir == "east":
moves, cord, next_dir = move_east(grid, cord)
elif dir == "west":
moves, cord, next_dir = move_west(grid, cord)
history[dir] += moves
dir = next_dir
if dir == "finish":
break
Each direction has its own individual function that are almost exactly the same other than than the direction being returned for the next direction, and the way that it searches across the board.
def move_north(grid, cord):
moves = []
x, y = cord
while y >= 0:
if grid[y][x] == "#":
return moves, (x, y + 1), "east"
else:
moves.append((x,y))
y -= 1
return moves, (x, y), "finish"
At the end, I turned the complete list of values that are stored in answer into a set to remove any duplicates, and then get the length of the set to give me the number of spaces that have been touched.
answer = len(set(answer))
Part 2
Part 2 wants us to find the single spot on the board where we can add a new obstruction, that will cause the guard to walk in a never ending loop based on the rules from above. There are actually multiple places that will cause this, and we need to count the number of places that can create the loop.
To start with, we already know that it has to be a spot on the existing path that we mapped out in the first part. That significantly reduces the number of spots on the grid that we have to test against. I started out by looping through each location in the first answer, and introducing an obstruction at it one at a time. After each obstruction is laid, I just run the map and see if we find a loop.
To check for a loop, we need to identify if we not only enter the same grid location twice (we were already doing that in the first part) but travelving in the same direction as the previous time. To do this, I made a small modification to my code for part one, and rather than putting my entire history into a single bucket, I broke the history into each direction.
history = {
"north": [],
"south": [],
"east": [],
"west": []
}
history[dir] += moves
I also created a new function called loop_check that takes the spaces from the last move of the guard, and compares it with spaces that the guard previously interacted with from that same direction. It turns them both into sets, and looks for any overlap. If there’s an overlap, then we have identified the start of a loop and can count it.
def check_loop(history, recent):
thistory = set(history)
trecent = set(recent)
repeat = thistory.intersection(trecent)
return len(repeat) > 0
You can see my complete code on Github.