[Day 10] Pipe Maze // Advent of Code 2023 (Python)
Part One
You use the hang glider to ride the hot air from Desert Island all the way up to the floating metal island. This island is surprisingly cold and there definitely aren’t any thermals to glide on, so you leave your hang glider behind.
You wander around for a while, but you don’t find any people or animals. However, you do occasionally find signposts labeled “Hot Springs” pointing in a seemingly consistent direction; maybe you can find someone at the hot springs and ask them where the desert-machine parts are made.
The landscape here is alien; even the flowers and trees are made of metal. As you stop to admire some metal grass, you notice something metallic scurry away in your peripheral vision and jump into a big pipe! It didn’t look like any animal you’ve ever seen; if you want a better look, you’ll need to get ahead of it.
Scanning the area, you discover that the entire field you’re standing on is densely packed with pipes; it was hard to tell at first because they’re the same metallic silver color as the “ground”. You make a quick sketch of all of the surface pipes you can see (your puzzle input).
The pipes are arranged in a two-dimensional grid of tiles:
|is a vertical pipe connecting north and south.
-is a horizontal pipe connecting east and west.
Lis a 90-degree bend connecting north and east.
Jis a 90-degree bend connecting north and west.
7is a 90-degree bend connecting south and west.
Fis a 90-degree bend connecting south and east.
.is ground; there is no pipe in this tile.
Sis the starting position of the animal; there is a pipe on this tile, but your sketch doesn't show what shape the pipe has.Based on the acoustics of the animal’s scurrying, you’re confident the pipe that contains the animal is one large, continuous loop.
For example, here is a square loop of pipe:
.....
.F-7.
.|.|.
.L-J.
.....If the animal had entered this loop in the northwest corner, the sketch would instead look like this:
.....
.S-7.
.|.|.
.L-J.
.....In the above diagram, the
Stile is still a 90-degreeFbend: you can tell because of how the adjacent pipes connect to it.Unfortunately, there are also many pipes that aren’t connected to the loop! This sketch shows the same loop as above:
-L|F7
7S-7|
L|7||
-L-J|
L|-JFIn the above diagram, you can still figure out which pipes form the main loop: they’re the ones connected to
S, pipes those pipes connect to, pipes those pipes connect to, and so on. Every pipe in the main loop connects to its two neighbors (includingS, which will have exactly two pipes connecting to it, and which is assumed to connect back to those two pipes).Here is a sketch that contains a slightly more complex main loop:
..F7.
.FJ|.
SJ.L7
|F--J
LJ...Here’s the same example sketch with the extra, non-main-loop pipe tiles also shown:
7-F7-
.FJ|7
SJLL7
|F--J
LJ.LJIf you want to get out ahead of the animal, you should find the tile in the loop that is farthest from the starting position. Because the animal is in the pipe, it doesn’t make sense to measure this by direct distance. Instead, you need to find the tile that would take the longest number of steps along the loop to reach from the starting point — regardless of which way around the loop the animal went.
In the first example with the square loop:
.....
.S-7.
.|.|.
.L-J.
.....You can count the distance each tile in the loop is from the starting point like this:
.....
.012.
.1.3.
.234.
.....In this example, the farthest point from the start is
4steps away.Here’s the more complex loop again:
..F7.
.FJ|.
SJ.L7
|F--J
LJ...Here are the distances for each tile on that loop:
..45.
.236.
01.78
14567
23...Find the single giant loop starting at
S. How many steps along the loop does it take to get from the starting position to the point farthest from the starting position?
A maze question! I was waiting for this one. Let’s understand some basic rules of the given data first.
The pipes are arranged in a two-dimensional grid of tiles:
| is a vertical pipe connecting north and south.
- is a horizontal pipe connecting east and west.
L is a 90-degree bend connecting north and east.
J is a 90-degree bend connecting north and west.
7 is a 90-degree bend connecting south and west.
F is a 90-degree bend connecting south and east.
. is ground; there is no pipe in this tile.
S is the starting position of the animal; there is a pipe on this tile, but your sketch doesn't show what shape the pipe has.Looking at the example, in essence we have to transform the input data from this — to — > this!
-L|F7 --> .....
7S-7| --> .S-7.
L|7|| --> .|.|.
-L-J| --> .L-J.
L|-JF --> .....💭 My first thought is to start from S and then go in all 4 directions (North, East, West and South) and do a DFS (depth first search) to find the complete loop/cycle and then ignore everything else! And then calculate the farthest distance using slow/fast pointer approach.
Let’s write our base test case first:
Let’s now try to work our way through the maze. Our algorithm should start at the point ‘S’ and explore the neighbor nodes at the present depth prior to moving on to nodes at the next depth level.
But first, we need to parse our maze and best way to get started is to whip out our cli with REPL:
Now, we just need to write a function to find our starting point from where animal entered the maze: S
Now, lets define our directions — North, South, East & West and also our Pipe Shapes as per the question so we can begin to write our maze exploration logic!
Directions can just be an Enum, where each direction is associated with a tuple of two integers. These tuples are used to represent movement in a 2D grid. The first integer in the tuple represents movement along the x-axis (horizontal), and the second integer represents movement along the y-axis (vertical).
We can keep a track of PIPE_SHAPES as a dict, where we can map the {pipe_shape:directions_they_allow_movement_in} as per the problem statement:
|: allows movement in[Direction.NORTH, Direction.SOUTH].-: allows movement in[Direction.EAST, Direction.WEST].L: allows movement in[Direction.NORTH, Direction.EAST].J: allows movement in[Direction.NORTH, Direction.WEST].7: allows movement in[Direction.SOUTH, Direction.WEST].F: allows movement in[Direction.SOUTH, Direction.EAST].S: This is the starting point and allows movement in all four directions[Direction.NORTH, Direction.SOUTH, Direction.EAST, Direction.WEST].
The idea is, when the code navigates through the maze, it can look up the current pipe shape in PIPE_SHAPES to find out which directions it can move in next.
Ah! Found a bug My PIPE_SHAPES was incorrect. 😅
Also, we can modify our code to only go in Direction allowed by my PIPE_SHAPE
Now, to find the farthest_point from S we know that it should be somewhere in the middle of the loop, so we can just find the middle index and return that?
So, let’s run the code and validate our base test case?
[Running] python3 "/Users/jmalik/github/advent-of-code-2023/day_10/pipe_maze.py"
Cycle: [(1, 1), (1, 2), (1, 3), (2, 3), (3, 3), (3, 2), (3, 1), (2, 1)]
✅ Simple maze test passedNow, let’s see if our code works well for other cases where the input is not as clean.
And….
[Running] python3 "/Users/jmalik/github/advent-of-code-2023/day_10/pipe_maze.py"
Cycle: [(1, 1), (1, 2), (1, 3), (2, 3), (3, 3), (3, 2), (3, 1), (2, 1)]
✅ Simple maze test passed
Cycle: [(1, 1), (2, 1), (3, 1), (3, 2), (3, 3), (2, 3), (1, 3), (1, 2), (0, 2), (0, 1)]
Traceback (most recent call last):
File "/Users/jmalik/github/advent-of-code-2023/day_10/pipe_maze.py", line 96, in <module>
test_complex_maze()
File "/Users/jmalik/github/advent-of-code-2023/day_10/pipe_maze.py", line 91, in test_complex_maze
assert farthest_point == 4, f"Expected 6, got {farthest_point}"
AssertionError: Expected 6, got 5As expected, our code fails as we are not allowing the code to backtrack, and also we are not checking if the pipe shape we are reaching to is via an allowed direction!
Example: In the following maze:
[['-', 'L', '|', 'F', '7'],
['7', 'S', '-', '7', '|'],
['L', '|', '7', '|', '|'],
['-', 'L', '-', 'J', '|'],
['L', '|', '-', 'J', 'F']]If we start from S | 1,1 and if we go NORTH we can reach L | 0,1 which while is a valid PIPE_SHAPE but is an illegal move as we can only get to L from [Direction.NORTH, Direction.EAST]
Let’s update our code to track that and ignore any such moves.\
Let’s take even more complex cases, because we still haven’t solved the backtracking issue and my intution says that our break statement will come back to haunt us.
Adding 3 more cases from problem:
Let’s run them and …. what….the…hell???!
❯ /Users/jmalik/.pyenv/versions/3.10.7/bin/python /Users/jmalik/github/advent-of-code-2023/day_10/pipe_maze.py
Cycle: [(1, 1), (1, 2), (1, 3), (2, 3), (3, 3), (3, 2), (3, 1), (2, 1)]
✅ Simple maze test passed
Cycle: [(1, 1), (1, 2), (1, 3), (2, 3), (3, 3), (3, 2), (3, 1), (2, 1)]
✅ Complex maze test passed
Cycle: [(2, 0), (2, 1), (1, 1), (1, 2), (0, 2), (0, 3), (1, 3), (2, 3), (2, 4), (3, 4), (3, 3), (3, 2), (3, 1), (4, 1), (4, 0), (3, 0)]
✅ More complex maze test passed
Cycle: [(2, 0), (2, 1), (1, 1), (1, 2), (0, 2), (0, 3), (1, 3), (2, 3), (2, 4), (3, 4), (3, 3), (3, 2), (3, 1), (4, 1), (4, 0), (3, 0)]
✅ Most complex maze test passedSo….looks like our GREEDY approach works as the questions promises us exactly 1 loop (atleast for the part 1). This may change later but let’s execute our code for puzzle input and see how it works?
Let’s run this!
❯ /Users/jmalik/.pyenv/versions/3.10.7/bin/python /Users/jmalik/github/advent-of-code-2023/day_10/pipe_maze.py
Steps to the farthest point: xxxxAnd let’s input this in our answer box? 🤞
Here’s our fully-pythonic* code till now, I loved this code so much that I used by Github Copilot to document it completely! ❤️
*missing backtracking
# -- Day 10: Pipe Maze ---
from enum import Enum
class Direction(Enum):
"""
Enum representing cardinal directions with their grid movements.
"""
NORTH = (-1, 0)
SOUTH = (1, 0)
EAST = (0, 1)
WEST = (0, -1)
REVERSE_DIRECTION_MAP = {
Direction.NORTH: Direction.SOUTH,
Direction.SOUTH: Direction.NORTH,
Direction.EAST: Direction.WEST,
Direction.WEST: Direction.EAST,
}
PIPE_MOVEMENT_OPTIONS = {
"|": [Direction.NORTH, Direction.SOUTH],
"-": [Direction.EAST, Direction.WEST],
"L": [Direction.NORTH, Direction.EAST],
"J": [Direction.NORTH, Direction.WEST],
"7": [Direction.SOUTH, Direction.WEST],
"F": [Direction.SOUTH, Direction.EAST],
"S": [Direction.NORTH, Direction.SOUTH, Direction.EAST, Direction.WEST],
}
class Maze:
def __init__(self, input_string):
"""
Initialize the Maze with a string representation.
:param input_string: Multiline string representing the maze.
"""
self.maze = [list(line) for line in input_string.splitlines()]
def find_animal_start(self):
"""
Find the starting position of the animal marked by 'S' in the maze.
:return: Tuple (x, y) as the starting position.
"""
for i, row in enumerate(self.maze):
for j, cell in enumerate(row):
if cell == "S":
return (i, j)
class MazeSolver:
def __init__(self, maze):
"""
Initialize the MazeSolver with the maze.
:param maze: 2D list representing the maze.
"""
self.maze = maze
def find_cycle(self, start):
"""
Find the cycle in the maze starting from the given position.
:param start: Tuple (x, y) as the starting position.
:return: List of tuples representing the cycle path.
"""
stack = [start]
visited = {start}
path_tracker = {start: None}
while stack:
x, y = stack.pop()
for direction in PIPE_MOVEMENT_OPTIONS[self.maze[x][y]]:
nx, ny = x + direction.value[0], y + direction.value[1]
if self.can_move(x, y, nx, ny, direction):
if (nx, ny) not in visited:
self.update_stack_and_visited(
stack, visited, path_tracker, x, y, nx, ny
)
break
elif path_tracker[(x, y)] != (nx, ny):
return self.construct_cycle(path_tracker, x, y, nx, ny)
raise ValueError("No cycle found")
def can_move(self, x, y, nx, ny, direction):
"""
Check if movement is possible in the maze from (x, y) to (nx, ny).
:param x, y: Current position coordinates.
:param nx, ny: Next position coordinates.
:param direction: Direction of movement.
:return: Boolean indicating if movement is possible.
"""
return (
0 <= nx < len(self.maze)
and 0 <= ny < len(self.maze[0])
and self.maze[nx][ny] in PIPE_MOVEMENT_OPTIONS
and REVERSE_DIRECTION_MAP[direction]
in PIPE_MOVEMENT_OPTIONS[self.maze[nx][ny]]
)
def update_stack_and_visited(self, stack, visited, path_tracker, x, y, nx, ny):
"""
Update the stack, visited set, and path tracker for the next move.
:param stack: List representing the stack of positions to explore.
:param visited: Set of visited positions.
:param path_tracker: Dictionary tracking the path taken.
:param x, y: Current position coordinates.
:param nx, ny: Next position coordinates.
"""
stack.append((nx, ny))
visited.add((nx, ny))
path_tracker[(nx, ny)] = (x, y)
def construct_cycle(self, path_tracker, x, y, nx, ny):
"""
Construct the cycle path when a cycle is detected.
:param path_tracker: Dictionary tracking the path taken.
:param x, y: Current position coordinates.
:param nx, ny: Detected cycle starting position coordinates.
:return: List of tuples representing the cycle path.
"""
cycle = [(nx, ny)]
while (x, y) != (nx, ny):
cycle.append((x, y))
x, y = path_tracker[(x, y)]
return cycle
@staticmethod
def get_steps_to_the_farthest_point(cycle):
"""
Calculate the number of steps to the farthest point in the cycle.
:param cycle: List of tuples representing the cycle path.
:return: Integer representing the number of steps.
"""
return len(cycle) // 2
def part_one():
# Read the maze input from a file
with open("day_10/input.txt") as f:
maze_input = f.read()
# Initialize the Maze and MazeSolver
maze = Maze(maze_input)
solver = MazeSolver(maze.maze)
# Find the starting position and solve the maze
start = maze.find_animal_start()
cycle = solver.find_cycle(start)
farthest_point = solver.get_steps_to_the_farthest_point(cycle)
# Print the result
print(f"❗️ Steps to the farthest point: {farthest_point}")
def test_simple_maze():
maze_input = """.....
.S-7.
.|.|.
.L-J.
....."""
maze = Maze(maze_input)
solver = MazeSolver(maze.maze)
start = maze.find_animal_start()
cycle = solver.find_cycle(start)
farthest_point = solver.get_steps_to_the_farthest_point(cycle)
assert farthest_point == 4, f"Expected 4, got {farthest_point}"
print("✅ Simple maze test passed")
def test_complex_maze():
maze_input = """-L|F7
7S-7|
L|7||
-L-J|
L|-JF"""
maze = Maze(maze_input)
solver = MazeSolver(maze.maze)
start = maze.find_animal_start()
cycle = solver.find_cycle(start)
farthest_point = solver.get_steps_to_the_farthest_point(cycle)
assert farthest_point == 4, f"Expected 4, got {farthest_point}"
print("✅ Complex maze test passed")
def test_more_complex_maze():
maze_input = """..F7.
.FJ|.
SJ.L7
|F--J
LJ..."""
maze = Maze(maze_input)
solver = MazeSolver(maze.maze)
start = maze.find_animal_start()
cycle = solver.find_cycle(start)
farthest_point = solver.get_steps_to_the_farthest_point(cycle)
assert farthest_point == 8, f"Expected 8, got {farthest_point}"
print("✅ More complex maze test passed")
def test_most_complex_maze():
maze_input = """7-F7-
.FJ|7
SJLL7
|F--J
LJ.LJ"""
maze = Maze(maze_input)
solver = MazeSolver(maze.maze)
start = maze.find_animal_start()
cycle = solver.find_cycle(start)
farthest_point = solver.get_steps_to_the_farthest_point(cycle)
assert farthest_point == 8, f"Expected 8, got {farthest_point}"
print("✅ Most complex maze test passed")
if __name__ == "__main__":
test_simple_maze()
test_complex_maze()
test_more_complex_maze()
test_most_complex_maze()
part_one()Sidetrack
I wrote a simple loop to visualize the maze acc to puzzle input and I removed everything in maze except our pipe shapes in the cycle
def visualize_maze(maze, cycle):
for i, row in enumerate(maze):
for j, cell in enumerate(row):
if (i, j) not in cycle:
maze[i][j] = "·"
for row in maze:
print("".join(row))Here’s how it looks like on my vertical monitor:
Part Two
You quickly reach the farthest point of the loop, but the animal never emerges. Maybe its nest is within the area enclosed by the loop?
To determine whether it’s even worth taking the time to search for such a nest, you should calculate how many tiles are contained within the loop. For example:
...........
.S-------7.
.|F-----7|.
.||.....||.
.||.....||.
.|L-7.F-J|.
.|..|.|..|.
.L--J.L--J.
...........The above loop encloses merely four tiles — the two pairs of
.in the southwest and southeast (markedIbelow). The middle.tiles (markedObelow) are not in the loop. Here is the same loop again with those regions marked:...........
.S-------7.
.|F-----7|.
.||OOOOO||.
.||OOOOO||.
.|L-7OF-J|.
.|II|O|II|.
.L--JOL--J.
.....O.....In fact, there doesn’t even need to be a full tile path to the outside for tiles to count as outside the loop — squeezing between pipes is also allowed! Here,
Iis still within the loop andOis still outside the loop:..........
.S------7.
.|F----7|.
.||OOOO||.
.||OOOO||.
.|L-7F-J|.
.|II||II|.
.L--JL--J.
..........In both of the above examples,
4tiles are enclosed by the loop.Here’s a larger example:
.F----7F7F7F7F-7....
.|F--7||||||||FJ....
.||.FJ||||||||L7....
FJL7L7LJLJ||LJ.L-7..
L--J.L7...LJS7F-7L7.
....F-J..F7FJ|L7L7L7
....L7.F7||L7|.L7L7|
.....|FJLJ|FJ|F7|.LJ
....FJL-7.||.||||...
....L---J.LJ.LJLJ...The above sketch has many random bits of ground, some of which are in the loop (
I) and some of which are outside it (O):OF----7F7F7F7F-7OOOO
O|F--7||||||||FJOOOO
O||OFJ||||||||L7OOOO
FJL7L7LJLJ||LJIL-7OO
L--JOL7IIILJS7F-7L7O
OOOOF-JIIF7FJ|L7L7L7
OOOOL7IF7||L7|IL7L7|
OOOOO|FJLJ|FJ|F7|OLJ
OOOOFJL-7O||O||||OOO
OOOOL---JOLJOLJLJOOOIn this larger example,
8tiles are enclosed by the loop.Any tile that isn’t part of the main loop can count as being enclosed by the loop. Here’s another example with many bits of junk pipe lying around that aren’t connected to the main loop at all:
FF7FSF7F7F7F7F7F---7
L|LJ||||||||||||F--J
FL-7LJLJ||||||LJL-77
F--JF--7||LJLJ7F7FJ-
L---JF-JLJ.||-FJLJJ7
|F|F-JF---7F7-L7L|7|
|FFJF7L7F-JF7|JL---7
7-L-JL7||F7|L7F-7F7|
L.L7LFJ|||||FJL7||LJ
L7JLJL-JLJLJL--JLJ.LHere are just the tiles that are enclosed by the loop marked with
I:FF7FSF7F7F7F7F7F---7
L|LJ||||||||||||F--J
FL-7LJLJ||||||LJL-77
F--JF--7||LJLJIF7FJ-
L---JF-JLJIIIIFJLJJ7
|F|F-JF---7IIIL7L|7|
|FFJF7L7F-JF7IIL---7
7-L-JL7||F7|L7F-7F7|
L.L7LFJ|||||FJL7||LJ
L7JLJL-JLJLJL--JLJ.LIn this last example,
10tiles are enclosed by the loop.Figure out whether you have time to search for the nest by calculating the area within the loop. How many tiles are enclosed by the loop?
💭 This is interesting! On first glance, it does look like a flood fill problem, where I have to just do a convert everything except PIPE_SHAPES in cycle to ground . and then just do a BFS from any . and mark them as flooded.
And then, I can just visit each element and pick . that were not flooded.
But, while building this, it’s clear that I will need to “flood” from all the edges as my flooded part might not be connected universally, which makes it difficult to differentiate between tiles in or out of the loop!
💭 Another approach I can think to solve this is to just write a method is_in_loop(tile, cycle, maze) bool and just use some good’ol geometry to check of the location of the point is within bounds. I will need to google how to do it, because it’s been over a decade since I left high school maths!
💡Fascinating, I found a computational geometry technique called the “ray casting” algorithm.
The basic idea is to extend a “ray” from the tile in question to the outside of the grid and count how many times it intersects the loop. If the number of intersections is odd, the tile is inside the loop; if it’s even, the tile is outside.
Just an elegant solution! I think this should solve our problem here as we can just loop through each tile and then cast it towards the nearest boundary of grid and return!
❗️Ah, but wait! It assumes the loop is properly formed and continuous. However, it assumes that the loop does not have any gaps and that it fully encloses an area. In our case, the “pipe” can go around multiple times making a series of loops. 🤦♂
.
thinking
.
🧠 What if we can use a combination of both?
Basically, we can do a flood fill from all the outside edges not part of the loop to mark all tiles outside the loop. Then, any unmarked ‘.’ tiles inside the maze boundaries would be considered inside the loop.
Let’s try for another example with an edge case…?
Well, that’s fails our test case!
Traceback (most recent call last):
File "/Users/jmalik/github/advent-of-code-2023/day_10/pipe_maze.py", line 295, in <module>
test_enclosed_tiles_in_tighter_maze()
File "/Users/jmalik/github/advent-of-code-2023/day_10/pipe_maze.py", line 282, in test_enclosed_tiles_in_tighter_maze
assert enclosed_tiles == 4, f"Expected 4, got {enclosed_tiles}"
AssertionError: Expected 4, got 12We just need to handle our flood fill algo to squeeze through the pipes. I have a very naive idea on how we can enhance the gaps in b/w pipes so our standard flood fill algorithm should give a correct answer!
💡We can just expand our grid by doubling the size of our board and connect pipes accordingly to still maintain our loop/cycle correctly. This will lead to a singluar connected region for everything outside the loop and we can just do standard floodfill to get our answers.
…
Well that didn’t work! I have wasted over 2 days on this! I think it’s time I take a peak for a hint! :(
…
💡Oh! Got to learn about a mathematical algorithm to determine the area of a simple polygon whose vertices are described by their Cartesian coordinates in the plane.
💡Using this, we should be able to simply calculate tiled inside the polygon formed by our loop. This brings our code to be simplified to:
Let’s write our base testcases from the example:
Let’s see if our Shoelace formula works:
❯ /Users/jmalik/.pyenv/versions/3.10.7/bin/python /Users/jmalik/github/advent-of-code-2023/day_10/pipe_maze.py
✅ Enclosed tiles in maze test passed
✅ Enclosed tiles in tighter maze test passed
✅ Enclosed tiles in tightest maze test passedYes! Now let’s run this through our puzzle input?
Executing and yes! We get a number:
❯ /Users/jmalik/.pyenv/versions/3.10.7/bin/python /Users/jmalik/github/advent-of-code-2023/day_10/pipe_maze.py
✅ Enclosed tiles in maze test passed
✅ Enclosed tiles in tighter maze test passed
✅ Enclosed tiles in tightest maze test passed
❗️ Enclosed tiles: XXXLet’s input this in our answer’s page:
Here’s our final pythonic code till now:
# -- Day 10: Pipe Maze ---
from enum import Enum
class Direction(Enum):
"""
Enum representing cardinal directions with their grid movements.
"""
NORTH = (-1, 0)
SOUTH = (1, 0)
EAST = (0, 1)
WEST = (0, -1)
REVERSE_DIRECTION_MAP = {
Direction.NORTH: Direction.SOUTH,
Direction.SOUTH: Direction.NORTH,
Direction.EAST: Direction.WEST,
Direction.WEST: Direction.EAST,
}
PIPE_MOVEMENT_OPTIONS = {
"|": [Direction.NORTH, Direction.SOUTH],
"-": [Direction.EAST, Direction.WEST],
"L": [Direction.NORTH, Direction.EAST],
"J": [Direction.NORTH, Direction.WEST],
"7": [Direction.SOUTH, Direction.WEST],
"F": [Direction.SOUTH, Direction.EAST],
"S": [Direction.NORTH, Direction.SOUTH, Direction.EAST, Direction.WEST],
}
class Maze:
def __init__(self, input_string):
"""
Initialize the Maze with a string representation.
:param input_string: Multiline string representing the maze.
"""
self.maze = [list(line) for line in input_string.splitlines()]
def find_animal_start(self):
"""
Find the starting position of the animal marked by 'S' in the maze.
:return: Tuple (x, y) as the starting position.
"""
for i, row in enumerate(self.maze):
for j, cell in enumerate(row):
if cell == "S":
return (i, j)
class MazeSolver:
def __init__(self, maze):
"""
Initialize the MazeSolver with the maze.
:param maze: 2D list representing the maze.
"""
self.maze = maze
def find_loop(self, start):
"""
Find the loop in the maze starting from the given position.
:param start: Tuple (x, y) as the starting position.
:return: List of tuples representing the loop path.
"""
stack = [start]
visited = {start}
path_tracker = {start: None}
while stack:
x, y = stack.pop()
for direction in PIPE_MOVEMENT_OPTIONS[self.maze[x][y]]:
nx, ny = x + direction.value[0], y + direction.value[1]
if self.can_move(x, y, nx, ny, direction):
if (nx, ny) not in visited:
self.update_stack_and_visited(
stack, visited, path_tracker, x, y, nx, ny
)
break
elif path_tracker[(x, y)] != (nx, ny):
return self.construct_loop(path_tracker, x, y, nx, ny)
raise ValueError("No loop found")
def can_move(self, x, y, nx, ny, direction):
"""
Check if movement is possible in the maze from (x, y) to (nx, ny).
:param x, y: Current position coordinates.
:param nx, ny: Next position coordinates.
:param direction: Direction of movement.
:return: Boolean indicating if movement is possible.
"""
return (
0 <= nx < len(self.maze)
and 0 <= ny < len(self.maze[0])
and self.maze[nx][ny] in PIPE_MOVEMENT_OPTIONS
and REVERSE_DIRECTION_MAP[direction]
in PIPE_MOVEMENT_OPTIONS[self.maze[nx][ny]]
)
def update_stack_and_visited(self, stack, visited, path_tracker, x, y, nx, ny):
"""
Update the stack, visited set, and path tracker for the next move.
:param stack: List representing the stack of positions to explore.
:param visited: Set of visited positions.
:param path_tracker: Dictionary tracking the path taken.
:param x, y: Current position coordinates.
:param nx, ny: Next position coordinates.
"""
stack.append((nx, ny))
visited.add((nx, ny))
path_tracker[(nx, ny)] = (x, y)
def construct_loop(self, path_tracker, x, y, nx, ny):
"""
Construct the loop path when a loop is detected.
:param path_tracker: Dictionary tracking the path taken.
:param x, y: Current position coordinates.
:param nx, ny: Detected loop starting position coordinates.
:return: List of tuples representing the loop path.
"""
loop = [(nx, ny)]
while (x, y) != (nx, ny):
loop.append((x, y))
x, y = path_tracker[(x, y)]
return loop
@staticmethod
def get_steps_to_the_farthest_point(loop):
"""
Calculate the number of steps to the farthest point in the loop.
:param loop: List of tuples representing the loop path.
:return: Integer representing the number of steps.
"""
return len(loop) // 2
def num_of_tiles_enclosed_by_loop(self, loop):
"""
Calculate the area enclosed by the loop.
:param perimeter_points: List of tuples representing the loop perimeter.
:return: Integer representing the enclosed area.
"""
area = 0
n = len(loop)
for i in range(n):
j = (i + 1) % n
area += loop[i][0] * loop[j][1]
area -= loop[j][0] * loop[i][1]
area = abs(area) // 2
return area - n // 2 + 1
def part_one():
# Read the maze input from a file
with open("day_10/input.txt") as f:
maze_input = f.read()
# Initialize the Maze and MazeSolver
maze = Maze(maze_input)
solver = MazeSolver(maze.maze)
# Find the starting position and solve the maze
start = maze.find_animal_start()
loop = solver.find_loop(start)
farthest_point = solver.get_steps_to_the_farthest_point(loop)
# Print the result
print(f"❗️ Steps to the farthest point: {farthest_point}")
def part_two():
# Read the maze input from a file
with open("day_10/input.txt") as f:
maze_input = f.read()
# Initialize the Maze and MazeSolver
maze = Maze(maze_input)
solver = MazeSolver(maze.maze)
# Find the starting position and solve the maze
start = maze.find_animal_start()
loop = solver.find_loop(start)
enclosed_tiles = solver.num_of_tiles_enclosed_by_loop(loop)
# Print the result
print(f"❗️ Enclosed tiles: {enclosed_tiles}")
def test_simple_maze():
maze_input = """.....
.S-7.
.|.|.
.L-J.
....."""
maze = Maze(maze_input)
solver = MazeSolver(maze.maze)
start = maze.find_animal_start()
loop = solver.find_loop(start)
farthest_point = solver.get_steps_to_the_farthest_point(loop)
assert farthest_point == 4, f"Expected 4, got {farthest_point}"
print("✅ Simple maze test passed")
def test_complex_maze():
maze_input = """-L|F7
7S-7|
L|7||
-L-J|
L|-JF"""
maze = Maze(maze_input)
solver = MazeSolver(maze.maze)
start = maze.find_animal_start()
loop = solver.find_loop(start)
farthest_point = solver.get_steps_to_the_farthest_point(loop)
assert farthest_point == 4, f"Expected 4, got {farthest_point}"
print("✅ Complex maze test passed")
def test_more_complex_maze():
maze_input = """..F7.
.FJ|.
SJ.L7
|F--J
LJ..."""
maze = Maze(maze_input)
solver = MazeSolver(maze.maze)
start = maze.find_animal_start()
loop = solver.find_loop(start)
farthest_point = solver.get_steps_to_the_farthest_point(loop)
assert farthest_point == 8, f"Expected 8, got {farthest_point}"
print("✅ More complex maze test passed")
def test_most_complex_maze():
maze_input = """7-F7-
.FJ|7
SJLL7
|F--J
LJ.LJ"""
maze = Maze(maze_input)
solver = MazeSolver(maze.maze)
start = maze.find_animal_start()
loop = solver.find_loop(start)
farthest_point = solver.get_steps_to_the_farthest_point(loop)
assert farthest_point == 8, f"Expected 8, got {farthest_point}"
print("✅ Most complex maze test passed")
def test_enclosed_tiles_in_maze():
maze_input = """...........
.S-------7.
.|F-----7|.
.||.....||.
.||.....||.
.|L-7.F-J|.
.|..|.|..|.
.L--J.L--J.
..........."""
maze = Maze(maze_input)
solver = MazeSolver(maze.maze)
start = maze.find_animal_start()
loop = solver.find_loop(start)
enclosed_tiles = solver.num_of_tiles_enclosed_by_loop(loop)
assert enclosed_tiles == 4, f"Expected 4, got {enclosed_tiles}"
print("✅ Enclosed tiles in maze test passed")
def test_enclosed_tiles_in_tighter_maze():
maze_input = """..........
.S------7.
.|F----7|.
.||....||.
.||....||.
.|L-7F-J|.
.|..||..|.
.L--JL--J.
.........."""
maze = Maze(maze_input)
solver = MazeSolver(maze.maze)
start = maze.find_animal_start()
loop = solver.find_loop(start)
enclosed_tiles = solver.num_of_tiles_enclosed_by_loop(loop)
assert enclosed_tiles == 4, f"Expected 4, got {enclosed_tiles}"
print("✅ Enclosed tiles in tighter maze test passed")
def test_enclosed_tiles_in_tightest_maze():
maze_input = """FF7FSF7F7F7F7F7F---7
L|LJ||||||||||||F--J
FL-7LJLJ||||||LJL-77
F--JF--7||LJLJ7F7FJ-
L---JF-JLJ.||-FJLJJ7
|F|F-JF---7F7-L7L|7|
|FFJF7L7F-JF7|JL---7
7-L-JL7||F7|L7F-7F7|
L.L7LFJ|||||FJL7||LJ
L7JLJL-JLJLJL--JLJ.L"""
maze = Maze(maze_input)
solver = MazeSolver(maze.maze)
start = maze.find_animal_start()
loop = solver.find_loop(start)
enclosed_tiles = solver.num_of_tiles_enclosed_by_loop(loop)
assert enclosed_tiles == 10, f"Expected 10, got {enclosed_tiles}"
print("✅ Enclosed tiles in tightest maze test passed")
if __name__ == "__main__":
# --- Part One ---
test_simple_maze()
test_complex_maze()
test_more_complex_maze()
test_most_complex_maze()
part_one()
# --- Part Two ---
test_enclosed_tiles_in_maze()
test_enclosed_tiles_in_tighter_maze()
test_enclosed_tiles_in_tightest_maze()
part_two()Phew! This one really took a lot of my energy, especially considering I haven’t been able to spend focus time on the problem due to my cousin’s wedding!
I need to catch up to next few problems as I am running behind!
p.s: I am deliberating not adding answers here so you can actually spend some time trying to understand how we solved the problem!
Feel free to checkout code on my Github repo and try to set it up and run on your machine 👇
