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:
12345.....
.F-7.
.|.|.
.L-J.
.....If the animal had entered this loop in the northwest corner, the sketch would instead look like this:
12345.....
.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:
12345-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 (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:
12345..F7.
.FJ|.
SJ.L7
|F--J
LJ...Here's the same example sketch with the extra, non-main-loop pipe tiles also shown:
123457-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:
12345.....
.S-7.
.|.|.
.L-J.
.....You can count the distance each tile in the loop is from the starting point like this:
12345.....
.012.
.1.3.
.234.
.....In this example, the farthest point from the start is 4 steps away.
Here's the more complex loop again:
12345..F7.
.FJ|.
SJ.L7
|F--J
LJ...Here are the distances for each tile on that loop:
12345..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?
- Find the start position
- Find connected pipe to the start position
- Follow the pipe until we get back to the start position, counting the number of tiles in the pipe as we go
- This makes heavy usage of the
OFFSET_MAP
- This makes heavy usage of the
- Return the
length of the pipe / 2
"Why length of the pipe / 2?"
Because the pipe always connects back to the start position, it must always have an even number of segments.
Don't believe me? Try to draw a continuous pipe with an odd number of segments.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119from dataclasses import dataclass
from pathlib import Path
import pytest
@dataclass
class Position:
x: int
y: int
# (character, x-offset, y-offset) -> (x-offset, y-offset)
OFFSET_MAP: dict[tuple[str, int, int], Position] = {
("|", 0, 1): Position(x=0, y=1),
("|", 0, -1): Position(x=0, y=-1),
("-", 1, 0): Position(x=1, y=0),
("-", -1, 0): Position(x=-1, y=0),
("L", 0, 1): Position(x=1, y=0),
("L", -1, 0): Position(x=0, y=-1),
("J", 1, 0): Position(x=0, y=-1),
("J", 0, 1): Position(x=-1, y=0),
("7", 1, 0): Position(x=0, y=1),
("7", 0, -1): Position(x=-1, y=0),
("F", -1, 0): Position(x=0, y=1),
("F", 0, -1): Position(x=1, y=0),
}
@dataclass
class Map:
start: Position
current: Position
positions: list[Position]
characters: list[list[str]]
def get_character(self, x: int, y: int) -> str | None:
if 0 <= x < len(self.characters[0]) and 0 <= y <= len(self.characters):
return self.characters[y][x]
return None
def run(self) -> int:
steps = 0
# Move one position manually
next_offset: Position | None = None
for x_offset, y_offset in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
next_character = self.get_character(
x=self.current.x + x_offset,
y=self.current.y + y_offset,
)
if OFFSET_MAP.get((next_character, x_offset, y_offset)):
next_offset = OFFSET_MAP[(next_character, x_offset, y_offset)]
self.current = Position(
x=self.current.x + x_offset, y=self.current.y + y_offset
)
steps += 1
break
while self.current != self.start:
# Get the character at the next position
next_character = self.get_character(
x=self.current.x + next_offset.x,
y=self.current.y + next_offset.y,
)
self.positions.append(self.current)
self.current = Position(
x=self.current.x + next_offset.x, y=self.current.y + next_offset.y
)
steps += 1
next_offset = OFFSET_MAP.get((next_character, next_offset.x, next_offset.y))
return steps // 2
def runner(document: list[str]) -> int:
character_map: list[list[str]] = []
position = Position(x=0, y=0)
for y_index, line in enumerate(document):
character_map.append(list(line))
for x_index, character in enumerate(line):
if character == "S":
position = Position(x=x_index, y=y_index)
pipe_map = Map(
start=position,
current=position,
positions=[position],
characters=character_map,
)
return pipe_map.run()
@pytest.mark.parametrize(
"filename,output",
[
("example-1.txt", 8),
("example-5.txt", 6968), # Very slow
],
)
def test_runner(filename: str, output: int) -> None:
with open(Path(__file__).with_name(filename)) as file:
result = runner(file.read().splitlines())
assert result == output
Answer: 6,968
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:
123456789...........
.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:
123456789...........
.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:
123456789..........
.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:
12345678910.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):
12345678910OF----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, 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:
12345678910FF7FSF7F7F7F7F7F---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:
12345678910FF7FSF7F7F7F7F7F---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, 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?
There are two ways I could think of solving this.
My solution below uses flood fill, but I initially solved this problem with a (slow) point in polygon implementation.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293from dataclasses import dataclass, field
from pathlib import Path
import pytest
# Doesn't matter what these characters are...
# As long as they don't conflict with existing characters in the map.
# These choices print with nice colors for debugging.
OPEN_CHARACTER = "\033[94m█\033[0m"
ENCLOSED_CHARACTER = "\033[31m█\033[0m"
@dataclass
class Position:
x: int
y: int
# (character, x-offset, y-offset) -> (x-offset, y-offset)
OFFSET_MAP: dict[tuple[str, int, int], Position] = {
("|", 0, 1): Position(x=0, y=1),
("|", 0, -1): Position(x=0, y=-1),
("-", 1, 0): Position(x=1, y=0),
("-", -1, 0): Position(x=-1, y=0),
("L", 0, 1): Position(x=1, y=0),
("L", -1, 0): Position(x=0, y=-1),
("J", 1, 0): Position(x=0, y=-1),
("J", 0, 1): Position(x=-1, y=0),
("7", 1, 0): Position(x=0, y=1),
("7", 0, -1): Position(x=-1, y=0),
("F", -1, 0): Position(x=0, y=1),
("F", 0, -1): Position(x=1, y=0),
}
EXPAND_MAP: dict[str, tuple[list[str], list[str], list[str]]] = {
OPEN_CHARACTER: (
[OPEN_CHARACTER, OPEN_CHARACTER, OPEN_CHARACTER],
[OPEN_CHARACTER, OPEN_CHARACTER, OPEN_CHARACTER],
[OPEN_CHARACTER, OPEN_CHARACTER, OPEN_CHARACTER],
),
ENCLOSED_CHARACTER: (
[ENCLOSED_CHARACTER, ENCLOSED_CHARACTER, ENCLOSED_CHARACTER],
[ENCLOSED_CHARACTER, ENCLOSED_CHARACTER, ENCLOSED_CHARACTER],
[ENCLOSED_CHARACTER, ENCLOSED_CHARACTER, ENCLOSED_CHARACTER],
),
"S": (
["S", "S", "S"],
["S", "S", "S"],
["S", "S", "S"],
),
"|": (
[ENCLOSED_CHARACTER, "|", ENCLOSED_CHARACTER],
[ENCLOSED_CHARACTER, "|", ENCLOSED_CHARACTER],
[ENCLOSED_CHARACTER, "|", ENCLOSED_CHARACTER],
),
"-": (
[ENCLOSED_CHARACTER, ENCLOSED_CHARACTER, ENCLOSED_CHARACTER],
["-", "-", "-"],
[ENCLOSED_CHARACTER, ENCLOSED_CHARACTER, ENCLOSED_CHARACTER],
),
"L": (
[ENCLOSED_CHARACTER, "|", ENCLOSED_CHARACTER],
[ENCLOSED_CHARACTER, "L", "-"],
[ENCLOSED_CHARACTER, ENCLOSED_CHARACTER, ENCLOSED_CHARACTER],
),
"J": (
[ENCLOSED_CHARACTER, "|", ENCLOSED_CHARACTER],
["-", "J", ENCLOSED_CHARACTER],
[ENCLOSED_CHARACTER, ENCLOSED_CHARACTER, ENCLOSED_CHARACTER],
),
"7": (
[ENCLOSED_CHARACTER, ENCLOSED_CHARACTER, ENCLOSED_CHARACTER],
["-", "7", ENCLOSED_CHARACTER],
[ENCLOSED_CHARACTER, "|", ENCLOSED_CHARACTER],
),
"F": (
[ENCLOSED_CHARACTER, ENCLOSED_CHARACTER, ENCLOSED_CHARACTER],
[ENCLOSED_CHARACTER, "F", "-"],
[ENCLOSED_CHARACTER, "|", ENCLOSED_CHARACTER],
),
}
@dataclass
class Map:
start: Position
current: Position
positions: list[Position]
characters: list[list[str]]
expanded_characters: list[list[str]] = field(default_factory=list)
def get_character(self, x: int, y: int) -> str | None:
if 0 <= x < len(self.characters[0]) and 0 <= y <= len(self.characters):
return self.characters[y][x]
return None
def run(self) -> int:
steps = 0
# Move one position manually
next_offset: Position | None = None
for x_offset, y_offset in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
next_character = self.get_character(
x=self.current.x + x_offset,
y=self.current.y + y_offset,
)
if OFFSET_MAP.get((next_character, x_offset, y_offset)):
next_offset = OFFSET_MAP[(next_character, x_offset, y_offset)]
self.current = Position(
x=self.current.x + x_offset, y=self.current.y + y_offset
)
steps += 1
break
while self.current != self.start:
# Get the character at the next position
next_character = self.get_character(
x=self.current.x + next_offset.x,
y=self.current.y + next_offset.y,
)
self.positions.append(self.current)
self.current = Position(
x=self.current.x + next_offset.x, y=self.current.y + next_offset.y
)
steps += 1
next_offset = OFFSET_MAP.get((next_character, next_offset.x, next_offset.y))
return steps // 2
def is_in_loop(self, x: int, y: int) -> bool:
return any(position.x == x and position.y == y for position in self.positions)
def get_enclosed_positions(self) -> int:
enclosed = 0
for y_index in range(len(self.characters)):
for x_index in range(len(self.characters[0])):
if not self.is_in_loop(x_index, y_index):
crosses = 0
# Offset by 0.5 to account for corners, points, etc.
y_position = y_index + 0.5
# For each point pair in the loop, see if we intersect it
for p_index in range(len(self.positions) - 1):
a = self.positions[p_index]
b = self.positions[p_index + 1]
if a.y == b.y:
continue
if (
(a.y > y_position > b.y or a.y < y_position < b.y)
and a.x > x_index
and b.x > x_index
):
crosses += 1
if crosses % 2 == 1:
self.characters[y_index][x_index] = ENCLOSED_CHARACTER
enclosed += 1
return enclosed
def cleanup(self) -> None:
for y_index in range(len(self.characters)):
for x_index in range(len(self.characters[0])):
if not self.is_in_loop(x_index, y_index):
if (
y_index == 0
or y_index == len(self.characters) - 1
or (x_index == 0 or x_index == len(self.characters[0]) - 1)
):
self.characters[y_index][x_index] = OPEN_CHARACTER
else:
self.characters[y_index][x_index] = ENCLOSED_CHARACTER
def expand(self) -> None:
# 3x the height of characters
self.expanded_characters = [[] for _ in range(len(self.characters) * 3)]
for y_index in range(len(self.characters)):
for x_index in range(len(self.characters[0])):
character = self.characters[y_index][x_index]
first_line, second_line, third_line = EXPAND_MAP[character]
self.expanded_characters[y_index * 3] += first_line
self.expanded_characters[y_index * 3 + 1] += second_line
self.expanded_characters[y_index * 3 + 2] += third_line
def flood_fill(self) -> None:
# {(x, y)}
positions_to_check: set[tuple[int, int]] = set()
# Fill positions to check with initial data of all Os
for y_index in range(len(self.expanded_characters)):
for x_index in range(len(self.expanded_characters[0])):
character = self.expanded_characters[y_index][x_index]
if character == OPEN_CHARACTER:
positions_to_check.add((x_index, y_index))
while positions_to_check:
x_index, y_index = positions_to_check.pop()
# Check in cardinal directions
for x_offset, y_offset in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
try:
character = self.expanded_characters[y_index + y_offset][
x_index + x_offset
]
if character == ENCLOSED_CHARACTER:
self.expanded_characters[y_index + y_offset][
x_index + x_offset
] = OPEN_CHARACTER
positions_to_check.add((x_index + x_offset, y_index + y_offset))
except IndexError:
pass
def shrink(self) -> None:
for y_index in range(0, len(self.expanded_characters), 3):
for x_index in range(0, len(self.expanded_characters[0]), 3):
# Get the center of each 3x3 grid
character = self.expanded_characters[y_index - 2][x_index - 2]
self.characters[y_index // 3 - 1][x_index // 3 - 1] = character
def count(self, character: str) -> int:
total = 0
for y_index in range(len(self.characters)):
for x_index in range(len(self.characters[0])):
if self.characters[y_index][x_index] == character:
total += 1
return total
def runner(document: list[str]) -> int:
character_map: list[list[str]] = []
position = Position(x=0, y=0)
for y_index, line in enumerate(document):
character_map.append(list(line))
for x_index, character in enumerate(line):
if character == "S":
position = Position(x=x_index, y=y_index)
pipe_map = Map(
start=position,
current=position,
positions=[position],
characters=character_map,
)
pipe_map.run()
pipe_map.cleanup()
pipe_map.expand()
pipe_map.flood_fill()
pipe_map.shrink()
return pipe_map.count(ENCLOSED_CHARACTER)
@pytest.mark.parametrize(
"filename,output",
[
("example-2.txt", 4),
("example-3.txt", 4),
("example-4.txt", 2),
("example-5.txt", 413), # Very slow
],
)
def test_runner(filename: str, output: int) -> None:
with open(Path(__file__).with_name(filename)) as file:
result = runner(file.read().splitlines())
assert result == output
Answer: 413
| Day | Part 1 Time | Part 1 Rank | Part 2 Time | Part 2 Rank |
|---|---|---|---|---|
| 10 | 01:13:29 | 5,227 | 02:53:15 | 3,953 |
Red rectangles represent the enclosed characters within the map.
Green rectangles represent the characters within the map that appear to be enclosed but actually aren't.
Large - Enclosed
Pipe Maze Empty
Large - Enclosed + Escaped
Pipe Maze Filled