How to solve Advent of Code 2024 - Day 6 with Python
This seems to be the first day where checking all possible options is only barely feasible... 🤏
But before we get right into the day and my solution for this day's puzzle, here is the info on how I approach this whole event (where my code is, what editor I use, etc):
Sarah Glasmacher
🎄❄️💻
Day 6 Puzzle
On my blog here, I will go through the puzzle and my way of solving it. If you want, you can jump directly to the code solution here:
GitHub .py script
Here is the challenge, if you want to read the full puzzle:
Advent of Code 2024 - Day 6
Today we are going to the North Pole prototype suit manufacturing lab 🧪 - but in the year 1518, because not only are our friends historians, apparently they are also time travelers. The suit manufacturing lab previously starred in the puzzle of Advent of Code 2018, Day 5. The local elves give us the task of avoiding a single guard patrolling, because if literature agrees on one fact in time traveling, it's this: You should never be seen in the past, to avoid disrupting the present (which is technically the future of the past... or... something like that 🤔).
Part 1
Day 6 gives us a grid again. Thankfully we already have methods for reading a grid from Day 4
# Example input
....#.....
.........#
..........
..#.......
.......#..
..........
.#..^.....
........#.
#.........
......#...
Solution Approach:
- read the grid as an np.array (one of my few exceptions to not using libraries in Advent of Code, see Day 4)
- keep track of the current position
(i, j), and the current directionv/>/... - implement a method to move in a straight line until the obstacle, then turn 90 degrees
- do that again and again, until the current position is off-the-grid
- either mark visited squares in the grid with
Xor keep a list of visited squares (for Part 1 the first is enough, but I adjusted the method for Part 2) - count the
Xs to get the number of visited squares
Key Code Snippets:
Help-functions for moving/turning/checking boundaries:
def turn_right(direction: str) -%3E str:
direction_map = {"^": ">", "v": "<", "<": "^", ">": "v"}
return direction_map[direction]
def move_one_step(position: tuple[int, int], direction: str) -> tuple[int, int]:
if direction == "^":
new_position = (position[0] - 1, position[1])
elif direction == "v":
new_position = (position[0] + 1, position[1])
elif direction == "<":
new_position = (position[0], position[1] - 1)
elif direction == ">":
new_position = (position[0], position[1] + 1)
return new_position
def check_if_position_still_on_grid(
grid: np.ndarray, position: tuple[int, int]
) -> bool:
return (
position[0] >= 0
and position[0] < grid.shape[0]
and position[1] >= 0
and position[1] < grid.shape[1]
)
Finding the starting spot:
def find_start_position(grid: np.ndarray) -> tuple[tuple[int, int], str]:
for i in range(grid.shape[0]):
for j in range(grid.shape[1]):
if grid[i, j] in ["^", "v", "<", ">"]:
return (i, j), grid[i, j]
moving in a straight line until hitting an obstacle or moving off the map:
def move_until_obstacle_or_loop(
grid: np.ndarray,
position: tuple[int, int],
direction: str,
visited_positions: list[tuple[tuple[int, int], str]],
) -> tuple[tuple[int, int], str, list[tuple[tuple[int, int], str]]]:
while check_if_position_still_on_grid(grid, position):
# check if we looped (visited the same position with the same direction)
if (position, direction) in visited_positions:
return position, direction, visited_positions
visited_positions.append((position, direction))
grid[position[0], position[1]] = direction
new_position = move_one_step(position, direction)
# Note: the 'O' obstacle marker is used only in Part 2.
if check_if_position_still_on_grid(grid, new_position) and grid[
new_position
] in ["#", "O"]:
break
position = new_position
new_direction = turn_right(direction)
return position, new_direction, visited_positions
Counting visits:
def count_distinct_visited_positions(
visited_positions: list[tuple[tuple[int, int], str]]
) -> int:
# ignore directions and transform coordinates into set to get rid of duplicates
distinct_positions = set(position for position, _ in visited_positions)
return len(distinct_positions)
Full Solution for Part 1:
def solve_part_1(mode: str = "example"):
file_lines = read_input_file(day=6, mode=mode)
grid = read_letter_grid_from_lines(file_lines)
position, direction = find_start_position(grid)
visited_positions = []
while check_if_position_still_on_grid(grid, position):
position, direction, visited_positions = move_until_obstacle_or_loop(
grid, position, direction, visited_positions
)
return count_distinct_visited_positions(visited_positions)
Part 2
You already saw a little bit of code for part 2 in the code for part 1 since most methods can be reused this time with very little modifications.
The only new thing is setting a new obstacle on the grid somewhere and keeping track of which obstacles loop. The loop logic is already present in move_until_obstacle_or_loop - technically you could have skipped this line in Part 1.
🚨 Disclaimer: For now, I opted for a somewhat brute-force approach. My solution took 50 minutes to run on my MacBook Pro M2 Pro (without parallelization). I did a naive approach of simply trying every single possible location for the new obstacle - like every field on the grid, which means I need to try 130x130 options. I think it's possible to narrow this down by only setting obstacles on the fields where the guard actually walks. I'm short on time today, so I will leave this as an exercise for reader 😉 (that's a math joke, math professors are cruel people 😩).
Here's the slow solution, don't be surprised if you run this. It works though, sooo 🤷♀️
Create an obstacle:
def create_obstacle_on_grid(grid: np.ndarray, position: tuple[int, int]) -> np.ndarray:
new_grid = grid.copy()
new_grid[position[0], position[1]] = "O"
return new_grid
Full Solution for Part 2:
def solve_part_2(mode: str = "example"):
file_lines = read_input_file(day=6, mode=mode)
grid = read_letter_grid_from_lines(file_lines)
start_position, start_direction = find_start_position(grid)
loop_count = 0
for i in tqdm(range(grid.shape[0]), desc="Rows"):
for j in tqdm(range(grid.shape[1]), desc="Columns", leave=False):
if grid[i, j] not in ["^", "v", "<", ">", "#"]:
new_grid = create_obstacle_on_grid(grid, (i, j))
position = start_position
direction = start_direction
visited_positions = []
while check_if_position_still_on_grid(new_grid, position):
new_position, new_direction, visited_positions = (
move_until_obstacle_or_loop(
new_grid, position, direction, visited_positions
)
)
if new_position == position and new_direction == direction:
loop_count += 1
break
position = new_position
direction = new_direction
return loop_count
Basically I exit immediately in the move_until_obstacle_or_loop if the location has already been visited, so if position and direction remain unchanged I know that I looped in the solve_part_2 method
You need to install tqdm and numpy for this. tqdm is just there to see progress during the long runtime of Part 2, it has no effect on the solution.
Conclusion/Methods for improvement
I feel like I cheated. If I ever have time left over, I will fix this. I think if I only put obstacles on the grid-positions of Part 1, the runtime would be 1/4. That would still be about 10 minutes on my device, so there probably is an even better way to do this... 🤔
You can probably exclude any positions that are on "empty" lines ... or next to empty lines. Basically you need to ensure that the guard can "hit" another obstacle after the artificial one - if he would walk right off the map after hitting the artificial obstacle, it would of course be useless.
These are all speculations on my part, but feel free to play around with these ideas. 😊