Advent of Code - 2023
This is a solution to Day 10 of Advent of Code 2023.
Day 10: Pipe Maze
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.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.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 S tile is still a 90-degree F bend: 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|-JF
In 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 (including S, 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.LJ
If 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 4 steps 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?
My first comment today when I read the description: "This smells like recursion. It's gonna be a long day."
But let's take one step at a time and start with creating our data structures and worry about recursion later.
Recursion depth limit
During my solution, I kept running into
RecursionError: maximum recursion depth exceeded in comparison
and to solve this, I needed to give my notebook a bit extra recursions to run through.
import sys
sys.setrecursionlimit(30000)
Read input
I'm using a complex number coordinate system that I learned from Tess Ferrandez a few years ago.
In this system, every coordinate is represented by a single complex number in format of x + yj
where j
denotes imaginary part. I really like this system when there's any kind of traversing happening because movements become clean.
To move up/north, we add 1j and to move down/south, we subtract 1j. To move right/east, +1 and left/west, -1.
The entire grid then is a dictionary with the coordinate number as key and the contents of that cell as value. I also find the start node on this initial creation process.
from utils import read_input
raw_input = read_input(10)
def create_grid(raw_input):
grid = {}
start = None
for y, row in enumerate(raw_input):
for x, value in enumerate(row):
if value == 'S':
start = x + y * -1j
grid[x + y * -1j] = value
return grid, start
grid, start = create_grid(raw_input)
To find out if two coordinates in the grid are connected, I calculate the movement needed to make the move. Because I use the Complex Number system, it's just a subtraction. Beautiful.
I created four sets with pipes based on which directions they are open to. S
tile is always open to connect to anything needed so it's included in all of them.
To check if two shapes are connected, the start shape and end shape need to be in opposite directions.
OPEN_TO_EAST = set(['-', 'L', 'F', 'S'])
OPEN_TO_WEST = set(['-', 'J', '7', 'S'])
OPEN_TO_NORTH = set(['|', 'J', 'L', 'S'])
OPEN_TO_SOUTH = set(['|', 'F', '7', 'S'])
def are_connected(start, end, grid):
start_shape = grid[start]
end_shape = grid[end]
movement = end - start
match movement:
case 1:
return start_shape in OPEN_TO_EAST and end_shape in OPEN_TO_WEST
case -1:
return start_shape in OPEN_TO_WEST and end_shape in OPEN_TO_EAST
case 1j:
return start_shape in OPEN_TO_NORTH and end_shape in OPEN_TO_SOUTH
case -1j:
return start_shape in OPEN_TO_SOUTH and end_shape in OPEN_TO_NORTH
To get adjacent (but not diagonal) neighbors, once again this coordinate system shines because I only need to add or subtract one value.
def get_adjacent(coord):
return [
coord + 1,
coord - 1,
coord - 1j,
coord + 1j
]
The main engine of this solution is the recursive depth-first search inside find_loop
.
I enter it with start position and empty set of already checked
cells.
I then find its neighbors and only consider ones that
- Have not been checked yet
- Are coordinates in the grid
- Are connected to the current cell
I add current cell to the checked list and for each cell that fits the criteria above, I dive into the next layer of recursion. If we end up in a situation where there are no more options to loop through, we return the set of checked items as our loop.
def find_loop(current, grid, checked):
neighbors = get_adjacent(current)
options = [
n
for n
in neighbors
if n not in checked
and n in grid
and are_connected(current, n, grid)
]
checked.add(current)
for nxt in options:
return find_loop(nxt, grid, checked)
return checked
Since we are only interested in the distance to the furthest cell and not which position it is or what kind of pipe is there, we can add one and divide by two and then convert to integer.
loop = find_loop(start, grid, set())
part_1 = int((len(loop) + 1) / 2)
print(f'Solution: {part_1}')
assert part_1 == 6815
Solution: 6815
Part 2
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 (marked I below). The middle . tiles (marked O below) 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, I is still within the loop and O is still outside the loop:
.......... .S------7. .|F----7|. .||OOOO||. .||OOOO||. .|L-7F-J|. .|II||II|. .L--JL--J. ..........
In both of the above examples, 4 tiles 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---JOLJOLJLJOOO
In this larger example, 8 tiles 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.L
Here 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.L
In this last example, 10 tiles 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>>?
I had to get some help with this one to find out which math concept to apply. A friend pointed me towards point in polygon problem. Wikipedia article for it has a section for ray casting algorithm that started with
One simple way of finding
and I stopped reading and decided to use it. A simple way sounded good.
Well, it wasn't that easy or simple.
I tried to implement the algorithm but ran into a problem where there would be a horizontal line on the same line as a cell I wanted to check. It meant the ray would only touch the edge of the polygon without entering it. With the aforementioned friend's help, I decided to rotate my "ray" 45 degrees.
So to check whether a position is inside the loop, I have function is_inside
. It starts with the position up and left (or northwest) from the tested position and continues moving that direction until it runs out of the grid.
Each time, it checks if the position to check is inside the loop and increases the hit counter. There are two special cases, 'L' and '7' curves that have this "touch the edge" problem so I count them twice to effectively ignore them.
Finally, if there were an odd number of hits, return True.
def is_inside(position, loop, grid):
"""
Using crossing number algorithm
to test if we're inside the loop or not
"""
double_crosses = ['L', '7']
hits = 0
northwest = (-1+1j)
# Move up and left along the diagonal
position = position + northwest
# Continue until we go outside the grid
while position in grid:
# If we're crossing something in loop, it's a hit
if position in loop:
hits += 1
# If it's a L or 7 curve, count as double cross
if grid[position] in double_crosses:
hits += 1
position = position + northwest
# If there are an odd number of hits, we're inside
return hits and hits % 2 != 0
My next problem was that all the examples worked well but my actual input didn't.
I realized that I still had the S
cell there and that messed up the calculation.
To convert the start cell into the right pipe, I have get_start_pipe
function that finds the two connections it connects with by permuating through all the cells that it touches (and are part of the loop).
I got to reuse my handy OPEN_TO_
sets from earlier! I calculated the direction between two pipes and gave possible connections. Then I did it with the other pair as well, got the intersection, removed the 'S' node and ended up with a set of single value. Popping that out gave me the right pipe for the start cell.
from itertools import permutations
def connect(s, c, grid):
diff = c - s
match diff:
case 1:
return OPEN_TO_EAST
case -1:
return OPEN_TO_WEST
case 1j:
return OPEN_TO_NORTH
case -1j:
return OPEN_TO_SOUTH
def get_start_pipe(start, loop, grid):
connections = [pos for pos in get_adjacent(start) if pos in loop]
for c1, c2 in permutations(connections, 2):
if are_connected(start, c1, grid) and are_connected(start, c2, grid):
break
connection_to_c1 = connect(start, c1, grid)
connection_to_c2 = connect(start, c2, grid)
return ((connection_to_c1 & connection_to_c2) - { 'S' }).pop()
To calculate the amount of positions within the loop, I first find the loop (it's redundant here, I could have just used the one from part 1 but due to Jupyter Notebook, I like to keep the call here to make sure I'm running this on the right loop).
I then replace the start node. Another Jupyter Notebook trick here: I copy the grid and operate on that copy to avoid issues when running notebook cells in different order.
Finally, I go through all the positions in the grid, skip those that are part of the loop and for others, find if they are inside or note.
loop = find_loop(start, grid, set())
full_grid = grid.copy()
full_grid[start] = get_start_pipe(start, loop, grid)
part_2 = 0
for position in full_grid:
if not position in loop and is_inside(position, loop, full_grid):
part_2 += 1
print(f'Solution: {part_2}')
assert part_2 == 269
Solution: 269
Two stars
20!
Today had two really difficult parts for me. I struggle with recursion so part 1 had me in ropes and I struggle with not knowing the correct algorithms or math concepts for problems so part 2 dependent on a friend nudging me to the right direction - twice.
I did really like using the Complex Number Coordinate System though. It takes a bit to get used to so if you read through the code, some parts might be challenge to grasp but once you've used it a bit, it makes the code really clean in my opinion.
Being able to calculate new positions with adding or subtracting two numbers from each other rather than dealing with two separate coordinates in a tuple is a joy for me.