Notebook

Visions of Mario Bros¶

https://adventofcode.com/2023/day/10

It's a pipe dream! Some things to realise:

You can map out, for any given symbol, what symbols to expect in any of the 4 compass directions. A vertical pipe can only connect to another vertical pipe on either side, or to a 7 or F to the north, for example. Any point that connects to just one other symbol this way is a dead end and not part of the loop.
We just have to follow the pipes leading from the four sides of the starting point (if there is a pipe that connects to the starting point), and keep track of the position for each and the distance travelled. Discard the pipe positions that are dead ends. Once you reach a pipe that connects to a spot you have been before, you know you have found the furthest point.

In [1]:

# pyright: strict
from __future__ import annotations

import typing as t
from enum import Enum
from itertools import count

type PipeChar = t.Literal["S", "|", "-", "L", "J", "7", "F"]
type MapChar = t.Literal["."] | PipeChar
type Connections = tuple[()] | tuple[PipeChar, PipeChar, PipeChar]
type PosAndChar = tuple[complex, MapChar]
_impassible = ()
_n_conn = ("|", "7", "F", "S")
_s_conn = ("|", "L", "J", "S")
_w_conn = ("-", "L", "F", "S")
_e_conn = ("-", "J", "7", "S")


class PipePiece(Enum):
    # name = (character, north, east, south, west)
    ns_pipe = ("|", _n_conn, _impassible, _s_conn, _impassible)
    ew_pipe = ("-", _impassible, _e_conn, _impassible, _w_conn)
    ne_bend = ("L", _n_conn, _e_conn, _impassible, _impassible)
    nw_bend = ("J", _n_conn, _impassible, _impassible, _w_conn)
    sw_bend = ("7", _impassible, _impassible, _s_conn, _w_conn)
    se_bend = ("F", _impassible, _e_conn, _s_conn, _impassible)
    start = ("S", _n_conn, _e_conn, _s_conn, _w_conn)

    if t.TYPE_CHECKING:
        connected_to: tuple[Connections, Connections, Connections, Connections]

    else:
        # hide the extended new method from pyright, it'll otherwise
        # be confused about PipePiece(...) calls later on.

        def __new__(
            cls,
            char: PipeChar,
            n: Connections,
            e: Connections,
            s: Connections,
            w: Connections,
        ) -> PipePiece:
            obj = object.__new__(cls)
            obj._value_ = char
            obj.connected_to = (n, e, s, w)
            return obj

    def connects_to(self, *surrounded: PosAndChar) -> list[complex]:
        return [
            p for (p, char), conn in zip(surrounded, self.connected_to) if char in conn
        ]


def _nesw(pos: complex) -> t.Iterator[complex]:
    for dxy in (-1j, 1, 1j, -1):
        yield pos + dxy


class PipeMap:
    def __init__(self, mapdescr: str) -> None:
        self.map = mapdescr.splitlines()
        self.start = next(
            x + y * 1j
            for y, line in enumerate(self.map)
            for x, c in enumerate(line)
            if c == "S"
        )
        self.shape = len(self.map[0]), len(self.map)

    def __getitem__(self, pos: complex) -> MapChar:
        x, y = map(int, (pos.real, pos.imag))
        if not (0 <= x < self.shape[0] and 0 <= y < self.shape[1]):
            return "."
        return t.cast(MapChar, self.map[y][x])

    def longest_path(self) -> int:
        positions = PipePiece.start.connects_to(
            *((p, self[p]) for p in _nesw(self.start))
        )
        seen: set[complex] = {self.start, *positions}
        # follow the pipes
        for distance in count(1):
            new_positions: list[complex] = []
            for pos in positions:
                piece = PipePiece(self[pos])
                connected_to = piece.connects_to(*((p, self[p]) for p in _nesw(pos)))
                if len(connected_to) == 1:
                    # dead end, drop this position
                    continue
                new_pos = next((p for p in connected_to if p not in seen), None)
                if new_pos is None:
                    # we found the furthest point, as both ends have been visited now
                    return distance
                new_positions.append(new_pos)
            positions = new_positions
            seen.update(positions)

        raise AssertionError("All pipes were dead ends")


test_maps = {
    """\
-L|F7
7S-7|
L|7||
-L-J|
L|-JF
""": 4,
    """\
7-F7-
.FJ|7
SJLL7
|F--J
LJ.LJ
""": 8,
}

for test_map, expected in test_maps.items():
    assert PipeMap(test_map).longest_path() == expected

In [2]:

import aocd

maptext = aocd.get_data(day=10, year=2023)
print("Part 1:", PipeMap(maptext).longest_path())

Part 1: 7063

Let's just flood the pipes¶

To start with, we need to get a set of all positions that are part of the pipe loop. We do so by keeping the positions of each pipe we follow, separately, and discard the sets of positions for the dead ends.

Next, we need to flood fill each area of connected empty positions, and determine for each such area if it is inside or outside the pipe. You can do this with a Point in polygon algorithm. Simply follow a straight line from the starting point and count how many times you cross a pipe; if it is an odd number of crossings you are inside the pipe loop, otherwise you are outside of it.

Counting the number of times you cross is straightforward for any straight pipe sections that are orthogonal to the direction of the line, and only slightly more complicated when you encounter a bend in the pipe or a straight section in the same direction as your line. For the latter, you'll only ever encounter two bends and the straight section between them. If the two bends at the ends point in the same direction, you are not crossing the pipe there, only following along the same edge. If the two bends point in opposite directions, you are crossing the pipe. Just imagine the ends not connected to the straigt part as a single pipe section that's orthogonal to your crossing line.

E.g. when scanning from the test position (marked by T) to the right edge, you could encounter this:

T |F--JL--J|

There are 3 pipe sections there, two | orthogonal pipe sections, and the F--J and L--J sections. The first ends in bends that go off in oppossite directions, and the second with bends that both go up. So the first section you are crossing a pipe (equivalent to a | section) and the second one you are not.

In the implementation below, I just took a substring from the map line corresponding to the remainder past the test position, replacing all characters on it that are not part of the pipe with ., removing all - sections (they are always flanked by bends), replacing each pair of oposite bends with a single |, and then just counting the number of | sections. To avoid having to figure out what kind of pipe section the S starting position obscures, I just take the section before the test position if the S starting position is directly to the right.

In [3]:

from collections import deque
from itertools import product


class FloodedPipeMap(PipeMap):
    def loop_positions(self) -> set[complex]:
        positions = PipePiece.start.connects_to(
            *((p, self[p]) for p in _nesw(self.start))
        )
        seen: set[complex] = {self.start, *positions}
        pipes: list[tuple[complex, set[complex]]] = [(pos, {pos}) for pos in positions]

        # follow the pipes
        while pipes:
            new_pipes: list[tuple[complex, set[complex]]] = []
            for pos, pipe in pipes:
                piece = PipePiece(self[pos])
                connected_to = piece.connects_to(*((p, self[p]) for p in _nesw(pos)))
                if len(connected_to) == 1:
                    # dead end, drop this position, remove their pipe positions from
                    # the seen set.
                    seen -= pipe
                    continue
                new_pos = next((p for p in connected_to if p not in seen), None)
                if new_pos is not None:
                    new_pipes.append((new_pos, pipe | {new_pos}))
                    seen.add(new_pos)
            pipes = new_pipes

        return seen

    def _inside(self, loop: set[complex], pos: complex) -> bool:
        px, py = map(int, (pos.real, pos.imag))
        sx, sy = map(int, (self.start.real, self.start.imag))
        # take the section of map line to the east of the position, unless that crosses
        # the start position, in which case we take the section before it.
        mapline = (
            enumerate(self.map[py][:px])
            if py == sy and px < sx
            else enumerate(self.map[py][px + 1 :], px + 1)
        )
        # only take sections of pipe that are part of the loop, skipping
        # east-west pipe sections and empty spaces.
        line = "".join([c for x, c in mapline if x + py * 1j in loop and c not in "-."])
        # remove parallel pipes and sections that are just bend ends, and replace zig-zags
        # with straight orthogonal pipes
        line = (
            line.replace("F7", "")
            .replace("LJ", "")
            .replace("FJ", "|")
            .replace("L7", "|")
        )
        return line.count("|") % 2 == 1

    def enclosed_area(self) -> int:
        loop = self.loop_positions()
        width, height = self.shape
        empty: set[complex] = {
            p
            for x, y in product(range(width), range(height))
            if (p := complex(x, y)) not in loop
        }
        total_area = 0
        while empty:
            pos = empty.pop()
            area: set[complex] = set()
            todo = deque([pos])
            while todo:
                pos = todo.popleft()
                if pos in area:
                    continue
                area.add(pos)
                todo.extend(p for p in _nesw(pos) if p in empty)
            if self._inside(loop, pos):
                total_area += len(area)
            empty -= area

        return total_area


test_maps = {
    """\
...........
.S-------7.
.|F-----7|.
.||.....||.
.||.....||.
.|L-7.F-J|.
.|..|.|..|.
.L--J.L--J.
...........
""": 4,
    """\
..........
.S------7.
.|F----7|.
.||OOOO||.
.||OOOO||.
.|L-7F-J|.
.|II||II|.
.L--JL--J.
..........
""": 4,
    """\
.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...
""": 8,
    """\
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
""": 10,
}

for test_map, expected in test_maps.items():
    assert FloodedPipeMap(test_map).enclosed_area() == expected

In [4]:

print("Part 2:", FloodedPipeMap(maptext).enclosed_area())

Part 2: 589