Pipe Maze

Part 1

Here it is: the first grid puzzle I’d ever encountered in Advent of Code! I had fun coming up with my initial solution, which had a neat approach to Part 2;¹ instead of that, however, I’ll be explaining a different approach.

But first, I want to talk about how I handle AoC grid puzzles, using a grids module I wrote (which I modified from David Brownman’s graphs module from his solution repo). Basically, grids are parsed into dicts that map (row, column) location tuples to grid items. This doesn’t involve a lot of code; in fact, here is the entire parse_grid function:

from collections.abc import Callable, Iterable

# NOTE This type-alias syntax was added in Python 3.12.
type GridPoint = tuple[int, int]
type Grid[Item] = dict[GridPoint, Item]

# NOTE This generic-function syntax was also added in Python 3.12.
def parse_grid[Item](
        raw_grid: list[str],
        item_factory: Callable[[str], Item] = str,
        *,
        ignore_chars: Iterable[str] = "",
) -> Grid[Item]:
    result: Grid[Item] = {}
    ignore = set(ignore_chars)
    for row, line in enumerate(raw_grid):
        for col, char in enumerate(line):
            if char in ignore:
                continue
            result[row, col] = item_factory(char)
    return result

This function can be used to quickly parse a grid in certain useful ways:

• parse_grid(self.input): grid with string characters at each grid point
• parse_grid(self.input, int): grid with ints at each grid point (each character is passed to int)
• parse_grid(self.input, str, ignore_chars=".#"): grid with string characters at each grid point, without any . or # characters

My grids module also defines other common grid-related functions, which I’ll explain as they come up.

We’re looking for a loop of pipe tiles in a grid. First, let’s parse the grid, ignoring any non-pipe tiles; we can easily use next with a generator expression to find the starting point.

class Solution(StrSplitSolution):
    def part_1(self) -> int:
        grid = parse_grid(self.input, ignore_chars=".")
        start = next(k for k, v in grid.items() if v == "S")
        ...

To traverse the loop, we’ll need to know which directions the pipes connect to. My grids module includes a Direction class that makes some direction-related operations easier:

from enum import IntEnum

class Direction(IntEnum):
    UP = 0
    RIGHT = 1
    DOWN = 2
    LEFT = 3

    @property
    def offset(self) -> GridPoint:
        return _ROW_COLUMN_OFFSETS[self]

_ROW_COLUMN_OFFSETS: dict[Direction, GridPoint] = {
    Direction.UP: (-1, 0),
    Direction.RIGHT: (0, 1),
    Direction.DOWN: (1, 0),
    Direction.LEFT: (0, -1),
}

As I’ve defined it, each direction has an offset property, which is what you’d need to add to the row/column of a grid point to move it in that direction. I also define a function to do this addition:

def add_points(a: GridPoint, b: GridPoint) -> GridPoint:
    return a[0] + b[0], a[1] + b[1]

This can be used to write a function that gets both possible moves that can be made from any pipe tile. We will get the directions you can travel from a pipe tile from a lookup table.

PIPES = {
    "|": (Direction.UP, Direction.DOWN),
    "-": (Direction.RIGHT, Direction.LEFT),
    "L": (Direction.UP, Direction.RIGHT),
    "J": (Direction.UP, Direction.LEFT),
    "7": (Direction.DOWN, Direction.LEFT),
    "F": (Direction.RIGHT, Direction.DOWN),
}

def possible_moves(current: GridPoint, ch: str) -> tuple[GridPoint, GridPoint]:
    result = tuple(add_points(current, d.offset) for d in PIPES[ch])
    assert len(result) == 2
    return result

There’s just one problem: how do we know which ways the S tile connects? According to the prompt, it (like every other pipe tile) has two pipes connected to it, and it connects back to those two pipes. So we can look at each of the tiles that neighbor the S, and check whether they connect back to the S.

My grids module has a neighbors function for looping through the neighbors of a grid point. I won’t paste it here because it’s somewhat long; all you need to know is that neighbors(start, num_directions=4) yields the neighbors of start going up, down, left, and right.

def get_moves_from_start(grid: Grid[str], start: GridPoint) -> list[GridPoint]:
    moves: list[GridPoint] = []
    for neighbor in neighbors(start, num_directions=4):
        if neighbor not in grid:
            continue
        if start in possible_moves(neighbor, grid[neighbor]):
            moves.append(neighbor)
    assert len(moves) == 2, "didn't find two moves possible from start"
    return moves

Now that all of that’s out of the way, we can solve Part 1.

We need the number of steps to the farthest point from the starting position; that’s going to be at the exact halfway point, since that’s as far as we can go without getting closer to the start again. We’ll walk along the pipe loop until we get back to the start, collecting the points we visit into a list as we go. Each time, the next tile we visit will simply be the one we didn’t just visit.

...

class Solution(StrSplitSolution):
    def part_1(self) -> int:
        grid = parse_grid(self.input, ignore_chars=".")
        start = next(k for k, v in grid.items() if v == "S")

        points = [start]
        current = get_moves_from_start(grid, start)[0]
        while current != start:
            last = points[-1]
            points.append(current)
            a, b = possible_moves(current, grid[current])
            current = a if b == last else b

        # The farthest point from the start is the halfway point of the
        # loop
        return len(points) // 2

Part 2

How many tiles are enclosed by the pipe loop? Well, the pipe loop is basically a polygon, and we know the coordinates of its vertices. From this information, we can use the shoelace formula to calculate the area of the polygon. How convenient!

If $(x_n, y_n)$ are the coordinates of the $n$th vertex of a polygon (going clockwise or counterclockwise), then the area $A$ is given by:

(Note that the list of vertices are treated as circular; after the last vertex ($i = n$), the next vertex is the first one ($i + 1 = 1$).)

We can easily write a function that uses this formula, which I also put in my grids module.

from itertools import pairwise

def interior_area(points: list[GridPoint]) -> float:
    # NOTE The "shoelace formula" requires a circular list of vertices.
    padded_points = [*points, points[0]]
    return abs(sum(
        row1 * col2 - row2 * col1
        for (row1, col1), (row2, col2) in pairwise(padded_points)
    )) / 2

But we must be careful! Strictly speaking, we don’t want the area within the pipe loop; we want the number of grid points within the pipe loop. Luckily, there’s a formula that relates the area of a polygon to the number of grid points inside of it, given by Pick’s theorem. Again, how convenient!

If $i$ is the number of grid points inside of a polygon, and $b$ is the number of grid points on its boundary, then its area $A$ is given by:

Solving for $i$ gives us $i = A - \frac{b}{2} + 1$. We know the area of the pipe loop, and we know the number of boundary points (the number of points along the loop), so we can simply plug these numbers in!

...

class Solution(StrSplitSolution):
    def solve(self) -> tuple[int, int]:
        grid = parse_grid(self.input, ignore_chars=".")
        start = next(k for k, v in grid.items() if v == "S")

        points = [start]
        current = get_moves_from_start(grid, start)[0]
        while current != start:
            last = points[-1]
            points.append(current)
            a, b = possible_moves(current, grid[current])
            current = a if b == last else b

        # The farthest point from the start is the halfway point of the
        # loop
        farthest_loop_distance = len(points) // 2

        area = interior_area(points)
        # NOTE Pick's theorem relates the area, number of interior grid
        # points, and number of boundary grid points of a simple lattice
        # polygon. This formula follows from simple algebra.
        num_interior_points = int(area - len(points) / 2 + 1)

        return farthest_loop_distance, num_interior_points

I spent quite a bit of time here writing that grids helper module. But it was worth it for two reasons:

1. It shortened my solution quite a bit, and it’ll also shorten my solutions to the other AoC grid puzzles. (And there are a lot of them!)
2. Now that I’ve written it, I’ll never have to write it again.