Advent of code 2024 - Day 06 of 25
Table of Contents
The sixth day of Advent of Code was yesterday 06/12/2024! If you’re here for the first time today, don’t forget to read the posts about Day 1, Day 2, Day 3, Day 4, and Day 5.
I classified the sixth problem as medium (part 1) and difficult (part 2).
Tips#
-
Again, a maze problem where each character can be seen as an element in a matrix.
-
Since you’ll constantly need to check maze boundaries, valid positions, and obstacles, I recommend creating a class to represent the maze.
-
In the first part of the answer, you’ll find a class to represent the path and the maze itself. You can use them to visualize the path, as shown in the problem.
-
A class to work with 2D vectors also greatly simplifies the implementation. If you visualize the current position as a vector (y, x), the new position can be calculated by adding another vector with the movement direction (dy, dx)
-
Part 1 of the problem is relatively easy but requires you to traverse the matrix following precise instructions and keeping track of the path.
-
You can implement direction changes (90 degrees) at each obstacle using a list of tuples representing directions. Using modulo properties, you can ensure the position is always valid in the list.
-
Part 2 is more complicated because you must generate obstacles and see how the program behaves. Since the goal is to put the guard in an infinite loop, you need to detect when a cycle is formed (or your program won’t terminate!). In a graph, a cycle can be seen when the path returns to visit a previously visited node. As in our problem we have a maze and each position can be visited in different directions, to detect a cycle, you need to check if the position has been visited before with the same passing direction.
-
To generate obstacles, you must “speculate” that a new obstacle can be generated at each position of the guard’s normal path, as long as it’s not the initial position and isn’t already occupied by an obstacle.
-
You can create a new maze with the new obstacle and check if the path enters a loop.
-
The complexity of part 2 is high, something like O(m x n), taking about 200 seconds to complete on my computer.
How much Python do you need to know?#
The chapters refer to my book Introduction to Programming with Python.
- Modulo properties - Chapter 2
- Lists, Tuples, Sets, and Dictionaries - Chapter 6
- Recursive functions - Chapter 8
- Graphs
Answer#
from aux import string_to_matrix, read_file_without_blank_lines, Vector2d
INPUT = """
....#.....
.........#
..........
..#.......
.......#..
..........
.#..^.....
........#.
#.........
......#...
"""
GUARD = "^"
OBSTACLE = "#"
DIRECTIONS = [Vector2d(*v) for v in [(-1, 0), (0, 1), (1, 0), (0, -1)]]
class Path:
def __init__(self):
self.path = {}
def __len__(self):
return len(self.path)
def visited(self, position: Vector2d, direction: int) -> bool:
if position in self.path and direction in self.path[position]:
return True
return False
def add(self, position: Vector2d, direction: int):
if position in self.path:
self.path[position].add(direction)
else:
self.path[position] = {direction}
class Maze:
def __init__(self, maze):
self.max_y = len(maze)
self.max_x = len(maze[0])
self.orig_maze = maze
self.maze = [list(line) for line in maze]
def copy(self):
return Maze(self.orig_maze)
def find_guard(self) -> Vector2d:
for y, line in enumerate(self.maze):
if "^" in line:
x = line.index(GUARD)
return Vector2d(y, x)
raise ValueError("No guard found in maze")
def valid_position(self, position: Vector2d) -> bool:
return 0 <= position.y < self.max_y and 0 <= position.x < self.max_x
def draw(self, path, character="X"):
for position, directions in path.items():
if directions:
h = {1, 3} & directions
v = {0, 2} & directions
dchar = "+" if h and v else "-" if h else "|"
self.maze[position.y][position.x] = dchar
else:
self.maze[position.y][position.x] = character
def __str__(self):
return "\n".join(["".join(line) for line in self.maze])
def __setitem__(self, yx, value):
self.maze[yx[0]][yx[1]] = value
def __getitem__(self, yx):
return self.maze[yx[0]][yx[1]]
def do_patrol(maze: Maze) -> tuple[Path, bool]:
path_taken = Path()
current_direction = 0
position = maze.find_guard()
while maze.valid_position(new_position := position + DIRECTIONS[current_direction]):
path_taken.add(position, current_direction)
if maze[new_position.y, new_position.x] == OBSTACLE:
current_direction = (current_direction + 1) % 4
else:
position = new_position
if path_taken.visited(position, current_direction):
return path_taken, True
path_taken.add(position, current_direction)
return path_taken, False
def find_possible_obstacles(maze: Maze):
current_direction = 0
possible_obstacles = set()
position = initial_position = maze.find_guard()
while maze.valid_position(new_position := position + DIRECTIONS[current_direction]):
if maze[new_position.y, new_position.x] == OBSTACLE:
current_direction = (current_direction + 1) % 4
else:
position = new_position
if position != initial_position:
new_maze = maze.copy()
new_maze[position.y, position.x] = OBSTACLE
_, cycle_detected = do_patrol(new_maze)
if cycle_detected:
possible_obstacles.add(position)
return possible_obstacles
# Part 1
# Test vector
test_maze = string_to_matrix(INPUT)
path, _ = do_patrol(Maze(test_maze))
print("Unique positions (test):", len(path))
assert len(path) == 41
input_maze = string_to_matrix(read_file_without_blank_lines("06/input.txt"))
path, _ = do_patrol(Maze(input_maze))
print("Unique positions (part 1):", len(path))
assert len(path) == 4696
# Part 2
possible_obstacles = find_possible_obstacles(Maze(test_maze))
print("Possible obstacles (test part 2):", len(possible_obstacles))
assert len(possible_obstacles) == 6
possible_obstacles = find_possible_obstacles(Maze(input_maze))
print("Possible obstacles (part 2):", len(possible_obstacles))
assert len(possible_obstacles) >= 1443
# Output
# Unique positions (test): 41
# Unique positions (part 1): 4696
# Possible obstacles (test part 2): 6
# Possible obstacles (part 2): 1443
Module aux.py#
Partial listing, to be added to other helper functions published in other articles.
class Vector2d:
def __init__(self, y, x):
self.x = x
self.y = y
def copy(self):
return Vector2d(self.y, self.x)
def __add__(self, other):
return Vector2d(self.y + other.y, self.x + other.x)
def __str__(self):
return f"({self.y}, {self.x})"
def __repr__(self):
return f"Vector2d({self.y}, {self.x})"
def __hash__(self):
return hash(f"({self.y}, {self.x})")
def __eq__(self, other):
if isinstance(other, Vector2d):
return self.x == other.x and self.y == other.y
return False