Link to Advent of Code day 10

Thanks to the hang glider, we are now on the floating metal island. Everything is made of metal, but you saw something metallic jumping in a network of pipes. To know what it is, we'll need to have a better look by anticipating his next exit !

Part 1

Rules

The part one is a 2d grid, with pipes having different shapes, connecting different directions:

| 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.

The input looks like this:

.F7.
.FJ|.
SJ.L7
|F--J
LJ...

And each input contains a loop, in which the starting position S is part of.

The first part of today is to find How many steps along the loop does it take to get from the starting position to the point farthest from the starting position.

For example with the previous input, the distances looks like this:

..45.
.236.
01.78
14567
23...

And the result would be 8.

Code

To handle today's problem, the parsing and data structure will be simple: just convert the input to a 2d array, with the connected tiles as values. We just need to handle the special tile S, and figure it's connections.

from dataclasses import dataclass
from typing import Iterable


@dataclass
class Point:
    y: int
    x: int

    def get_neighbours(self) -> Iterable["Point"]:
        yield Point(self.y - 1, self.x)
        yield Point(self.y, self.x + 1)
        yield Point(self.y + 1, self.x)
        yield Point(self.y, self.x - 1)


def get_input(input_file: str) -> (Point, list[list[Point]]):
    with open(input_file) as f:
        raw_grid = f.read().split("\n")
    grid = []
    start_point = None
    for (y, line) in enumerate(raw_grid):
        grid_line = []
        for (x, value) in enumerate(line):
            if value == "S":
                start_point = Point(y, x)
                grid_line.append([])
            else:
                grid_line.append(get_connections(value, y, x))
        grid.append(grid_line)
    # Since we ignored the value `S`, we need to infer it's connections
    # by looking which nodes are pointing to `S`
    for neighbour in start_point.get_neighbours():
        if start_point in grid[neighbour.y][neighbour.x]:
            grid[start_point.y][start_point.x].append(neighbour)
    return start_point, grid


def get_connections(value: str, y: int, x: int) -> list[Point]:
    """Return the connections for a given value according to the following descriptions:

    | 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.

    Returns an empty array if the value is not part of these values.
    """
    # Each value is the delta in form [(y, x), (y, x)]
    connections_delta = {
        "|": [(-1, 0), (1, 0)],
        "-": [(0, -1), (0, 1)],
        "L": [(-1, 0), (0, 1)],
        "J": [(-1, 0), (0, -1)],
        "7": [(1, 0), (0, -1)],
        "F": [(1, 0), (0, 1)],
    }
    if value not in connections_delta:
        return []
    left_delta, right_delta = connections_delta[value]
    left_point = Point(y + left_delta[0], x + left_delta[1])
    right_point = Point(y + right_delta[0], x + right_delta[1])
    return [left_point, right_point]

With these data, we need to find the distance which is the furthest from the starting point.

For this, we can use a classic BFS: we start from one side of S, and we are looking to join the other side of S.

The trick is to add S in the visited list at the beginning, to break the link between the start and end node:

def bfs(graph: list[list[list[Point]]], s_point: Point) -> dict[Point:Point]:
    starting_point_paths = graph[s_point.y][s_point.x]
    # We are looking to go from one side to the other side of the loop
    left_side, right_side = starting_point_paths[0], starting_point_paths[1]
    # We add `s_point` to `visited` as well,
    # to break the link between `left_side` and `right_side`
    visited = {s_point, left_side}
    queue = deque()
    queue.append(left_side)
    came_from = {left_side: None}

    while queue:
        current_point = queue.popleft()
        if current_point == right_side:
            return came_from

        for neighbor in graph[current_point.y][current_point.x]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
                came_from[neighbor] = current_point
    raise ValueError(f"Path from {left_side} to {right_side} not found")

After that, we need to implement the function to have the len between 2 points:

def get_path_len(came_from: dict[Point:Point], start: Point) -> int:
    path = []
    current = start
    while current is not None:
        path.append(current)
        current = came_from[current]
    return len(path)

With these functions, the part 1 can be simply solved by computing the path, get it's len, and return it's len divided by 2:

def part_one(input_file: str):
    start, grid = get_input(input_file)
    _, right_node = grid[start.y][start.x]
    paths = bfs(grid, start)
    return (get_path_len(paths, right_node) + 1) // 2

And the part one is done !

Part 2

Rules

For the part 2, we need to find the number of points in the area enclosed by the loop.

For example, with the input

..........
.S------7.
.|F----7|.
.||....||.
.||....||.
.|L-7F-J|.
.|..||..|.
.L--JL--J.
..........

There is 4 tiles enclosed by the loop, which are represented by the I:

..........
.S------7.
.|F----7|.
.||OOOO||.
.||OOOO||.
.|L-7F-J|.
.|II||II|.
.L--JL--J.
..........

The tiles O are still counted as outside the loop, since they can squeeze between the pipes at the bottom.

Any tile that isn't part of the main loop can count as being enclosed by the loop.

Code

Sadly I didn't had time to finish this part. I'll come back later and update this post once it's done.

I though about a rather long, and not very efficient solution:

1. discard all the tiles which are not part of the main loop
2. Space all tiles by one empty tile. For example,

F-7
|.|
L-J

Would become

F.-.7
.....
|...|
.....
L.-.J

3. Link all the new empty tiles if they are between 2 pipes which were previously connected to each other.

F.-.7
.....
|...|
.....
L.-.J

will become

F---7
|...|
|...|
|...|
L---J

4. Detect the outside of the map and replace the empty tiles with a flood-fill algorithm.

.......
.F---7.
.|...|.
.|...|.
.|...|.
.L---J.
.......

would become

#######
#F---7#
#|...|#
#|...|#
#|...|#
#L---J#
#######

5. Once it's done, we just have to count the empty remaining tiles.

It should work because by expanding the grid and linking only the previously connected pipe, we are adding some gaps between 2 adjacent pipes which are not connected. The flood-fill algorithm is now possible.

---

All the code is available on github