Advent of Code 2023, Day 10
❄️ Back to Advent of Code 2023 solutions homepage ❄️
# Imports
from aoc23.utils import read_input
import math
input_10 = read_input(10)
Part 1
In the day 10 puzzle, we are given an array of tiles, each representing a square on the ground; each character represents a different type of pipe:
|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.
input_10[:5]
['7-LJ7.F-F77FF-77FJ-J-F7FF|777F7--..JJ.F.7.|.F-J7-J777F7FF77F|.|7L-7.F-|7F7FF-J7LF|.7--7J-F.F--7-L--77.|F-J77F7F|-F-F7-J-FFF---F--77|FF7--L7.',
'L7.F--J.L7J7|---FJ-|JLF77L7J7F|-J7|J.FLLJ.FFF7|F7L7-J7LF7.-|L-77-LL7J.|.L-7JFJ7-7J7L-LFJF-7-|7|-|FL--J|L77L-J|7|F|-7J.|LLJJL|.|JF7-|-|||L|-F',
'F|--7.L-7|.-L-|.|7-LL-J|L-|.FJJ7F-..F|.L|FLJL7F7|F.L-|-7LJL|JL77-.|7|7.J.LF-7FJ7JF-J||J|FL77LJJ-7-77||F--7JL-7-LJJF--77LLF7F7-|.JJ|||JFF-|JF',
'FJ|L7-FL-L7J|FL-|LJFL7-F|LJ--J.F-7F-7L7--7.|F7J|F|7.L||F7J-J.FFJ.LLF-7F..-|--JLJF7J.LF.LJ|L-JJ.|.LJ-LFF7|L7-L|-LF7|F|7--7LJF77|7|LF|7FJ|L|F|',
'|LF7L-7J||LF-FJ.|7FF-F--J-J-L-|JJLL.J.||L7-FF7|L-L-7F77L77FJFFLJ7|JL7F-77-L-JL--LJJ7L-77LJJJ|.FF-FJLL|L--L7F|JFLF7FLJ7FJJJFL7JJ77-7|LJL|.J-F']
We are told that the section of pipe containing the S tile is a continuous loop; the first part of the puzzle is to find the length of the continuous loop (actually, it is the number of steps between S and the furthest point along the loop, but this is just $0.5*(\text{loop_length}-1)$).
Start by finding the location of the S tile within the array:
# Array size
n_rows = len(input_10)
n_cols = len(input_10[0])
for row in range(n_rows):
if 'S' in input_10[row]:
col = input_10[row].index('S')
break
# Use start_row, start_col as location of 'S' tile
start_row, start_col = row, col
assert input_10[start_row][start_col] == 'S'
print(f'i={start_row}, j={start_col}')
i=24, j=93
In order to know what kind of pipe tile the S is covering, let’s visualise the tiles in the neighbourhood of the S tile:
S_neighbourhood = [
[input_10[i][j] for j in range(start_col - 1, start_col + 2)]
for i in range(start_row - 1, start_row + 2)
]
for k in S_neighbourhood:
print(''.join(k))
FJF
LSL
7|F
From this, it can be seen that the S is actually a 7 tile, connecting the L tile on the left to the | tile at the bottom.
It will be useful to have a map which, given a pipe tile type and an incoming direction, returns the outgoing direction:
pipe_direction = {}
# L
pipe_direction[('L', 's')] = 'e'
pipe_direction[('L', 'w')] = 'n'
# J
pipe_direction[('J', 's')] = 'w'
pipe_direction[('J', 'e')] = 'n'
# F
pipe_direction[('F', 'n')] = 'e'
pipe_direction[('F', 'w')] = 's'
# 7
pipe_direction[('7', 'n')] = 'w'
pipe_direction[('7', 'e')] = 's'
# |
pipe_direction[('|', 'n')] = 'n'
pipe_direction[('|', 's')] = 's'
# -
pipe_direction[('-', 'e')] = 'e'
pipe_direction[('-', 'w')] = 'w'
Also, this function will convert an index and a direction into a new index, obtained by taking a step in that direction:
def new_index(row: int, col: int, direction: str):
match direction:
case 'n':
return (row-1, col)
case 'e':
return (row, col+1)
case 's':
return (row+1, col)
case 'w':
return (row, col-1)
case '_':
raise ValueError(f'direction {direction} not recognised!')
So, starting at the | tile below the S, having moved south from the S, move from tile to tile until the S tile is reached again, keeping count of the length of the loop so far:
# Start on the `|` tile below the `S` tile
loop_length = 1
row, col = start_row+1, start_col
pipe_type = '|'
direction = 's'
# Keep track of the tiles on the loop for later
loop_index_dict = {(start_row, start_col): 1}
while pipe_type != 'S':
loop_length += 1
# Track loop tiles
loop_index_dict[(row, col)] = 1
# Move a step
direction = pipe_direction[(pipe_type, direction)]
row, col = new_index(row, col, direction)
pipe_type = input_10[row][col]
The furthest point from the S tile is the point halfway around this loop (note that the S tile is excluded from this implementation of loop_length):
loop_length // 2
6956
So the answer to part 1 is: 6956.
Part 2
Now that the loop has been found, we are now asked to find the number of tiles (either ground or unused pipe) inside the loop. To avoid having to handle extra special cases, it is helpful to replace the S tile with a 7 tile, as we know that this is the true value:
corrected_input = [input_10[row].replace('S', '7') for row in range(n_rows)]
Now, the algorithm to compute the number of tiles inside the loop proceeds by looping over all the tiles line by line, and relies on a few key observations:
- The edges of the array always lie outside the loop
- Crossing a
|loop tile will switch from inside to outside, and vice versa. - Crossing a set of loop tiles of the form
F...JorL...7will also switch from inside to outside, or vice versa. - Crossing a set of loop tiles of the form
F...7orL...Jwill not change from the in/outside. - There is no way of crossing loop tiles, other than in the above ways.
So all that needs to be done is to keep a running count of the number of inside tiles seen, along with the types of loop tiles seen when crossed.
def count_inside_loop(input_list: list[str], loop_index_dict: dict[tuple[int], int]) -> int:
# Array size
n_rows = len(input_list)
n_cols = len(input_list[0])
# Keep track of the inside tiles
num_inside_loop = 0
# Iterate over tiles line by line
for i in range(n_rows):
# Always start a row outside the loop
inside_loop = False
# Keep track of the loop tile section when crossing
loop_tile_list = []
for j in range(n_cols):
tile = input_list[i][j]
# Is this a loop tile? Check the loop_index_dict
is_loop_tile = (i, j) in loop_index_dict
if is_loop_tile:
if tile == '|':
# Switch from in <-> out
inside_loop = not inside_loop
loop_tile_list = []
elif tile in ['-', 'F', 'L']:
# Start/middle of loop tile section
loop_tile_list.append(tile)
elif (loop_tile_list[0] == 'F' and tile == '7') or (loop_tile_list[0] == 'L' and tile == 'J'):
# F7 or LJ type - not a true crossing
loop_tile_list = []
elif (loop_tile_list[0] == 'F' and tile == 'J') or (loop_tile_list[0] == 'L' and tile == '7'):
# FJ or L7 type - switch from in <-> out
inside_loop = not inside_loop
loop_tile_list = []
elif inside_loop:
# Add to the counter if inside loop
num_inside_loop += 1
return num_inside_loop
A test array has been provided, which can be used to check if the function is working as expected:
test = [
'.F----7F7F7F7F-7....',
'.|F--7||||||||FJ....',
'.||.FJ||||||||L7....',
'FJL7L7LJLJ||LJ.L-7..',
'L--J.L7...LJF7F-7L7.',
'....F-J..F7FJ|L7L7L7',
'....L7.F7||L7|.L7L7|',
'.....|FJLJ|FJ|F7|.LJ',
'....FJL-7.||.||||...',
'....L---J.LJ.LJLJ...'
]
# Need to find the loop tiles first (as in part 1)
i = 1
row, col = 5, 12
pipe_type = 'J'
direction = 's'
test_loop_index_dict = {(4, 12): 1}
while (row, col) not in test_loop_index_dict:
i += 1
test_loop_index_dict[(row, col)] = 1
direction = pipe_direction[(pipe_type, direction)]
row, col = new_index(row, col, direction)
pipe_type = test[row][col]
assert count_inside_loop(test, test_loop_index_dict) == 8
print('Success!')
Success!
And so the number of tiles inside the loop for the main puzzle input can be computed:
count_inside_loop(corrected_input, loop_index_dict)
455
So the answer to part 2 is: 455.
Comments