Day 10: Pipe Maze

So the algorithmic part of this problem is easy "just breadth/depth first search" but the real problem is figuring out what we're actually searching.

In order to not drown in switch statements, we're going to need to establish some sort of systematic way of saying "Can the animal go from this location to this other location?"

My thought for this was to describe each pipe by its openings. For example, the | pipe is open at the north and south, and the 7 pipe is open at the west and south.

This then gives us a strategy for DFS/BFS: For each node, try every opening in that pipe, and if the pipe next in that direction has an opening in the opposite direction, then the animal can move to that pipe. There's a bit of jank with the starting location S which could theoretically be open at any location, but if you keep everything as a bitset (or, in my implementation, abused int as a bitset) then you can just set S to be open everywhere.

We now have a clear path forward for BFS, but DFS also offers a simple solution: Upon finding the loop, divide the distance by 2 (adding 1 if necessary).

Note for part 2: It turns out that depth first search makes part 2 way easier by making it much faster to figure out what's in the loop, but that's an implementation story for another time.

This is even more "intuitive but computers don't get it".

Fortunately for us one relatively computer-friendly way to determine whether a point is on a curve is to count the number of times it crosses that curve (better known as the Ray casting algorithm).

So this at least gives us a strategy to figure out which points are in the curve. Going from left to right, count how many times we cross the loop and only count points that have crossed an odd number of times. You've probably already spotted an issue with this strategy, though, which is "what if we're literally exactly on the loop, like if we enter a horizontal section?"

The answer is, naturally, to stretch our 2D analogy just enough to avoid having to actually answer the question. In particular, imagine that all the loops make their turns at exactly the midpoint of each section. Then, we imagine that our ray in the ray casting algorithm goes just beneath the midpoint, so that we can not-answer the question by saying that horizontal sections don't count as crossings (because the ray is always hovering just below the horizontal pipe and never touches/crosses it). This also gives us neat solution to the turns in pipes. J and L pipes don't count as crossings (they stay above the ray the whole time) but 7 and F pipes do (the downwards going part does cross the ray). Problem successfully dodged!

Well we're not quite out of the woods yet. One funny thing is determining which pipes are in the loop. With DFS this is easy, since you can just detect the last pipe in the search and go backwards to get the entire loop. With BFS, you have the fun problem of storing the pipes leading to the most distant loop and then inferring the loop in two (almost equal) halves, which is not nearly as nice.

One other problem is that we need to know what the starting pipe S actually is. This is a very tiny edge case but you have to look at the adjacent pipes fitting it and in the loop rather than just adjacent pipes fitting it.

Once we have that sorted out, we can use the ray casting algorithm on all the points not on the loop to figure out whether they're inside or outside.

Cleaning this code up fully will take forever, so feel free to gaze upon the janky implementation details and weird hacks used to make this solution barely work. But as a bonus it outputs the loop and the inside/outside points!

#include <bits/stdc++.h>
using namespace std;
// E N W S
const int dr[4] = {0,-1,0,1};
const int dc[4] = {1,0,-1,0};
int main() {
	vector<vector<int>> g;
	vector<vector<int>> dist;
	string s;
	vector<string> string_grid;
	pair<int,int> start_node;
	while(cin >> s) {
		string_grid.push_back(s);
		g.emplace_back();
		auto& w = g.back();
		for(const auto& c: s) {
			int nx = 0;
			if(c == 'J') {
				nx = (2|4);
			} else if(c == 'L') {
				nx = (1|2);
			} else if(c == 'F') {
				nx = (1|8);
			} else if(c == '7') {
				nx = (4|8);
			} else if(c == '|') {
				nx = (8|2);
			} else if(c == '-') {
				nx = (4|1);
			} else if(c == 'S') {
				start_node = pair<int,int>(g.size(),w.size());
				nx = 1|2|4|8;
			}
			w.push_back(nx);
		}
	}
	start_node.first--;
	dist.assign(g.size(),vector<int>(g[0].size(),-1));
	queue<pair<int,int>> q;
	q.push(start_node);
	dist[start_node.first][start_node.second] = 0;
	int max_dist = 0;
	vector<vector<pair<int,int>>> pa(g.size(),vector<pair<int,int>>(g.back().size()));
	pair<int,int> max_dist_node;
	while(!q.empty()) {
		pair<int,int> co = q.front();q.pop();
		int r = co.first;
		int c = co.second;
		if(dist[r][c] > max_dist) {
			max_dist_node = co;
		}
		max_dist = max(max_dist,dist[r][c]);
		for(int i=0;i<4;i++) {
			if(!(g[r][c]&(1<<i))) {continue;}
			int u = r+dr[i];
			int v = c+dc[i];
			if(u < 0 || u >= g.size()) {continue;}
			if(v < 0 || v >= g[u].size()) {continue;}
			if(g[u][v]&(1<<(i^2))) {
				if(dist[u][v] == -1) {
					dist[u][v] = dist[r][c]+1;
					q.emplace(u,v);
					pa[u][v] = co;
				}
			}
		}
	}
	vector<vector<int>> in_loop(g.size(),vector<int>(g.back().size()));
	{
		int r = max_dist_node.first;
		int c = max_dist_node.second;
		int mad = -1;
		vector<pair<int,int>> oks;
		for(int i=0;i<4;i++) {
			int u = r+dr[i];
			int v = c+dc[i];
			if(u < 0 || u >= g.size()) {continue;}
			if(v < 0 || v >= g[u].size()) {continue;}
			if(dist[u][v] > mad) {
				oks.clear();
				mad = dist[u][v];
			}
			if(dist[u][v] == mad) {
				oks.emplace_back(u,v);
			}
		}
		oks.push_back(max_dist_node);
		for(const auto& co: oks) {
			pair<int,int> ok = co;
			in_loop[ok.first][ok.second] = 1;
			while(ok != start_node) {
				ok = pa[ok.first][ok.second];
				in_loop[ok.first][ok.second] = 1;
			}
		}
	}
	{
		int r = start_node.first;
		int c = start_node.second;
		g[r][c] = 0;
		for(int i=0;i<4;i++) {
			int u = r+dr[i];
			int v = c+dc[i];
			if(u < 0 || u >= g.size()) {continue;}
			if(v < 0 || v >= g[u].size()) {continue;}
			if((g[u][v]&(1<<(i^2))) && in_loop[u][v]) {
				g[r][c] |= 1<<i;
			}
		}
		if(g[r][c]&8) {
			string_grid[r][c] = '|';
		}
	}
	int count_in_loop = 0;
	for(int i=0;i<g.size();i++) {
		int inside = 0;
		for(int j=0;j<g[i].size();j++) {
			if(in_loop[i][j] == 1) {
				if(string_grid[i][j] == '|' || string_grid[i][j] == '7' || string_grid[i][j] == 'F') {
					inside ^= 1;
				}
				cout << string_grid[i][j];
			} else {
				count_in_loop += inside;
				cout << (inside?'I':'O');
			}
		}
		cout << '\n';
	}
	cout << count_in_loop << '\n';
	cout << max_dist << '\n';
}

Not too bad for a part one. Walk the graph from S all the way back to itself,
keeping track of steps travelled. Then it works out that the farthest piece
in the loop from S is half that total loop length.

#!/usr/bin/env python3

from collections import defaultdict 

DIRECTIONS = (-1 + 0j, 1 + 0j, 0 - 1j, 0 + 1j)
CONNECTIONS = {'|': (-1 + 0j, 1 + 0j),
               '-': (0 - 1j, 0 + 1j),
               'L': (-1 + 0j, 0 + 1j),
               'J': (-1 + 0j, 0 - 1j),
               '7': (0 - 1j, 1 + 0j),
               'F': (0 + 1j, 1 + 0j),
               '.': (),
               ' ': ()}

# now that we know the coordinates of 'S', replace it with the pipe that fits
def normalize_start(g, start):
    v = tuple(d for d in DIRECTIONS if any(start + d + conn == start
                                           for conn in CONNECTIONS[g[start + d]]))
    pipe = next(k for k in CONNECTIONS if set(CONNECTIONS[k]) == set(v))
    g[start] = pipe

# walk around the main loop, return number of steps to make it all the way around
def walk_loop(g, start):
    steps = 2
    visited = set([start])
    start_conns = tuple(start + conn for conn in CONNECTIONS[g[start]])
    here = start_conns[0]
    while here != start_conns[1]:
        visited.add(here)
        here = next(filter(lambda pos: pos not in visited,
                           (here + conn for conn in CONNECTIONS[g[here]])))
        steps += 1
    return steps

G = defaultdict(lambda: '.')
for r, line in enumerate(open(0)):
    for c, char in enumerate(line.strip()):
        G[complex(r, c)] = char
start = next(pos for pos, char in G.items() if char == 'S')
normalize_start(G, start)
steps_around = walk_loop(G, start)
print(steps_around // 2)

The trickiest part in part two was the notion that tiles could squeeze between
pipes to be considered non-enclosed. My idea to attack this is to "zoom in" on
the graph, effectively putting empty spaces between every tile in the original
graph. Because I used complex coordinates, this was as easy as multiplying
coordinates by 2 and then filling in vertical and horizontal pipe pieces that
belonged in the newly created empty spaces. I also turned all non-mainloop pipes
into ground pipes (dots) to make things easier. Then I used flood fill on the
new zoomed graph on the exterior of the loop found the difference between all
ground tiles and these exterior ground tiles to end up with the final answer.

#!/usr/bin/env python3

from collections import defaultdict, deque

DIRECTIONS = (-1 + 0j, 1 + 0j, 0 - 1j, 0 + 1j)
CONNECTIONS = {'|': (-1 + 0j, 1 + 0j),
               '-': (0 - 1j, 0 + 1j),
               'L': (-1 + 0j, 0 + 1j),
               'J': (-1 + 0j, 0 - 1j),
               '7': (0 - 1j, 1 + 0j),
               'F': (0 + 1j, 1 + 0j),
               '.': (),
               ' ': ()}

# now that we know the coordinates of 'S', replace it with the pipe that fits
def normalize_start(g, start):
    v = tuple(d for d in DIRECTIONS if any(start + d + conn == start
                                           for conn in CONNECTIONS[g[start + d]]))
    pipe = next(k for k in CONNECTIONS if set(CONNECTIONS[k]) == set(v))
    g[start] = pipe

# walk around the main loop, return a set containing the coords of all its pieces
def walk_loop(g, start):
    visited = set([start])
    start_conns = tuple(start + conn for conn in CONNECTIONS[g[start]])
    here = start_conns[0]
    while here != start_conns[1]:
        visited.add(here)
        here = next(filter(lambda pos: pos not in visited,
                           (here + conn for conn in CONNECTIONS[g[here]])))
    visited.add(here)
    return visited

# returns a "zoomed in" graph with empty space between the original's tiles
def zoom(g, loop, factor=2):
    zg = defaultdict(lambda: ' ')
    for pos, char in g.items():
        zg[pos * factor] = char
    zloop = {pos * factor for pos in loop}
    for pos, char in zg.items():
        if char in ('|-LJ7F') and pos not in zloop:
            zg[pos] = '.'    # set all extra pipes to ground tiles
    max_r = int(max(zg, key=lambda pos: pos.real).real)
    max_c = int(max(zg, key=lambda pos: pos.imag).imag)
    for r in range(0, max_r + 1):
        for c in range(0, max_c + 1):
            pos = complex(r, c)
            if zg[pos] == ' ':
                up, down, left, right = (pos + d for d in DIRECTIONS)
                if zg[up] in ('|7F') or zg[down] in ('|JL'):
                    zg[pos] = '|'    # fill in vertical pipe gaps
                elif zg[left] in ('-LF') or zg[right] in ('-J7'):
                    zg[pos] = '-'    # fill in horizontal pipe gaps
    return zg

# starting from outside of the main loop, flood tiles around the loop
# return a set containing the coords of all outside tiles
def flood(g):
    min_pos = complex(min(g, key=lambda pos: pos.real).real - 1,
                      min(g, key=lambda pos: pos.imag).imag - 1)
    max_pos = complex(max(g, key=lambda pos: pos.real).real + 1,
                      max(g, key=lambda pos: pos.imag).imag + 1)
    start = min_pos
    outside = set()
    todo = deque([start])
    while todo:
        here = todo.popleft()
        if here in outside:
            continue
        outside.add(here)
        for d in DIRECTIONS:
            pos = here + d
            if ((min_pos.real <= pos.real <= max_pos.real)
                and (min_pos.imag <= pos.imag <= max_pos.imag)
                and g[pos] in ('.', ' ')):
                todo.append(pos)
    return outside

G = defaultdict(lambda: '.')
for r, line in enumerate(open(0)):
    for c, char in enumerate(line.strip()):
        G[complex(r, c)] = char
start = next(pos for pos, char in G.items() if char == 'S')
normalize_start(G, start)
loop = walk_loop(G, start)
ZG = zoom(G, loop)
outside = flood(ZG)
num_enclosed = sum(pos not in outside and char == '.' for pos, char in ZG.items())
print(num_enclosed)

using System.Diagnostics;

var _grid = new List<char[]>();

using (var input = new StreamReader(args[0]))
{
    while (!input.EndOfStream)
    {
        _grid.Add(input.ReadLine()!.ToCharArray());
    }
}

var grid = new char[_grid.Count, _grid[0].Length];
for (int row = 0; row < _grid.Count; row++)
{
    for (int col = 0; col < _grid[row].Length; col++)
    {
        grid[row, col] = _grid[row][col];
    }
}

// row, col
(int, int) GetStartingPos()
{
    for (int row = 0; row < grid.GetLength(0); row++)
    {
        for (int col = 0; col < grid.GetLength(1); col++)
        {
            if (grid[row, col] == 'S')
            {
                return (row, col);
            }
        }
    }

    throw new UnreachableException("no starting point found");
}
var startingPos = GetStartingPos();
var distanceGrid = MakeDistanceGrid();

int[,] MakeDistanceGrid()
{
    int[,] dg = new int[grid.GetLength(0), grid.GetLength(1)];

    for (int i = 0; i < dg.GetLength(0); i++)
    {
        for (int j = 0; j < dg.GetLength(1); j++)
        {
            dg[i,j] = Int32.MaxValue;
        } 
    }

    // XXX: Starting position value is 1 NOT 0 as indicated in problem statement
    dg[startingPos.Item1, startingPos.Item2] = 1;
    return dg;
}

void PrintGrid(char[,] g)
{
    for (int i = 0; i < g.GetLength(0); i++)
    {
        for (int j = 0; j < g.GetLength(1); j++)
        {
            Console.Write(g[i, j]);
        } 
        Console.WriteLine();
    }
}

void PrintDistanceGrid(int[,] g)
{
    for (int i = 0; i < g.GetLength(0); i++)
    {
        for (int j = 0; j < g.GetLength(1); j++)
        {
            var val = g[i, j];
            if (val == int.MaxValue)
            {
                Console.Write(" " + grid[i, j]);   
            }
            else
            {
                Console.Write(string.Format("{0:00}", g[i,j]-1));
            }
            Console.Write(" ");
        } 
        Console.WriteLine();
    }
}

int GridMax(int[,] grid)
{
    int max = 0;
    for (int i = 0; i < grid.GetLength(0); i++)
    {
        for (int j = 0; j < grid.GetLength(1); j++)
        {
            var val = grid[i, j];
            if (val == int.MaxValue)
            {
                continue;
            }

            max = Math.Max(max, val);
        } 
    }

    return max;
}


void BFS((int, int) position)
{
    var fillValue = distanceGrid[position.Item1, position.Item2] + 1;
    var currentCell = grid[position.Item1, position.Item2];
    var queue = new List<(int, int)>();
    // Pipes: |-LJ7FS
    // Check north
    if (position.Item1 - 1 >= 0)
    {
        var cell = (position.Item1 - 1, position.Item2);
        if (distanceGrid[cell.Item1, cell.Item2] > fillValue && "|7F".Contains(grid[cell.Item1, cell.Item2]) && "S|LJ".Contains(currentCell))
        {
            distanceGrid[cell.Item1, cell.Item2] = fillValue;
            queue.Add(cell);
        }
    }
    // Check west
    if (position.Item2 - 1 >= 0)
    {
        var cell = (position.Item1, position.Item2 - 1);
        if (distanceGrid[cell.Item1, cell.Item2] > fillValue && "-LF".Contains(grid[cell.Item1, cell.Item2]) && "S-J7".Contains(currentCell))
        {
            distanceGrid[cell.Item1, cell.Item2] = fillValue;
            queue.Add(cell);
        }
    }
    // Check south
    if (position.Item1 + 1 < grid.GetLength(0))
    {
        var cell = (position.Item1 + 1, position.Item2);
        if (distanceGrid[cell.Item1, cell.Item2] > fillValue && "|LJ".Contains(grid[cell.Item1, cell.Item2]) && "S|7F".Contains(currentCell))
        {
            distanceGrid[cell.Item1, cell.Item2] = fillValue;
            queue.Add(cell);
        }
    }
    // Check east
    if (position.Item2 + 1 < grid.GetLength(1))
    {
        var cell = (position.Item1, position.Item2 + 1);
        if (distanceGrid[cell.Item1, cell.Item2] > fillValue && "-J7".Contains(grid[cell.Item1, cell.Item2]) && "S-LF".Contains(currentCell))
        {
            distanceGrid[cell.Item1, cell.Item2] = fillValue;
            queue.Add(cell);
        }
    }
    
    // BFS
    foreach(var q in queue)
    {
        BFS(q);
    }
}

// Part 1
// BFS(startingPos);
// PrintDistanceGrid(distanceGrid);
// Console.WriteLine(gridMax(distanceGrid) - 1);

char[,] DoubleGrid()
{
    // Double the grid resolution
    var newGrid = new char[grid.GetLength(0) * 2, grid.GetLength(1) * 2];
    for (int row = 0; row < grid.GetLength(0); row++)
    {
        for (int col = 0; col < grid.GetLength(1); col++)
        {
            var mappedRow = row * 2;
            var mappedCol = col * 2;
            newGrid[mappedRow, mappedCol] = grid[row, col];
            newGrid[mappedRow+1, mappedCol+1] = '.';
            switch (grid[row, col])
            {
                case '|':
                    // |.
                    // |.
                    newGrid[mappedRow, mappedCol+1] = '.';
                    newGrid[mappedRow+1, mappedCol] = '|';
                    break;
                case '-':
                    // --
                    // ..
                    newGrid[mappedRow, mappedCol+1] = '-';
                    newGrid[mappedRow+1, mappedCol] = '.';
                    break;
                case 'L':
                    // L-
                    // ..
                    newGrid[mappedRow, mappedCol+1] = '-';
                    newGrid[mappedRow+1, mappedCol] = '.';
                    break;
                case 'J':
                    // J.
                    // ..
                    newGrid[mappedRow, mappedCol+1] = '.';
                    newGrid[mappedRow+1, mappedCol] = '.';
                    break;
                case '7':
                    // 7.
                    // |.
                    newGrid[mappedRow, mappedCol+1] = '.';
                    newGrid[mappedRow+1, mappedCol] = '|';
                    break;
                case 'F':
                    // F-
                    // |.
                    newGrid[mappedRow, mappedCol+1] = '-';
                    newGrid[mappedRow+1, mappedCol] = '|';
                    break;
                case '.':
                    // ..
                    // ..
                    newGrid[mappedRow, mappedCol+1] = '.';
                    newGrid[mappedRow+1, mappedCol] = '.';
                    break;
                case 'S':
                    // S-
                    // |.
                    newGrid[mappedRow, mappedCol+1] = '-';
                    newGrid[mappedRow+1, mappedCol] = '|';
                    break;
            }
        }
    }

    return newGrid;
}

grid = DoubleGrid();
startingPos = GetStartingPos();
distanceGrid = MakeDistanceGrid();

BFS(startingPos);

// Remove irrelevant grid positions
for (int row = 0; row < distanceGrid.GetLength(0); row++)
{
    for (int col = 0; col < distanceGrid.GetLength(1); col++)
    {
        if (distanceGrid[row, col] == int.MaxValue)
        {
            grid[row, col] = '.';
        }
    }
}

PrintDistanceGrid(distanceGrid);

void FloodFill((int, int) position)
{
    if (grid[position.Item1, position.Item2] != '.')
    {
        return;
    }

    grid[position.Item1, position.Item2] = 'O';
    // top
    if (position.Item1 - 1 >= 0)
    {
        FloodFill((position.Item1-1, position.Item2));
    }
    // left
    if (position.Item2 - 1 >= 0)
    {
        FloodFill((position.Item1, position.Item2-1));
    }
    // south
    if (position.Item1 + 1 < grid.GetLength(0))
    {
        FloodFill((position.Item1+1, position.Item2));
    }
    // right
    if (position.Item2 + 1 < grid.GetLength(1))
    {
        FloodFill((position.Item1, position.Item2+1));
    }
}

// Flood fill the edges with O
for (int i = 0; i < grid.GetLength(0); i++)
{
    // Fill left edge
    FloodFill((i, 0));
    // Fill right edge
    FloodFill((i, grid.GetLength(1) - 1));
}

for (int i = 0; i < grid.GetLength(1); i++)
{
    // Fill top edge
    FloodFill((0, i));
    // Fill bottom edge
    FloodFill((grid.GetLength(0)-1, i));
}
PrintGrid(grid);

int CountHalfDots()
{
    int accum = 0;
    for (int row = 0; row < grid.GetLength(0); row += 2)
    {
        for (int col = 0; col < grid.GetLength(1); col += 2)
        {
            if (grid[row, col] == '.')
            {
                accum++;
            }
        }
    }

    return accum;
}

Console.WriteLine(CountHalfDots());

Part 1 seemed pretty straightforward -- look at the adjacent tiles in the directions the current tile points and see if they point back at you. It would have been a lot more searching if there were T's or four way pipes, because then you'd have to branch more finding the path.

I also found I had a wrong assumption but got lucky on my input. I'm curious if anyone's input had more than two pipes pointing at the S tile, which was not the case in my input or any of the test inputs. This means there's no branching search needed.

This was easily solved using the raycasting algorithm that @Hvv wrote about in more detail, but
I did the handling of the crossings a little differently. Vertical pipes count as a crossing. For the places where the pipe runs horizontally, I looked at whether the end pieces were opposite or the same. That is, F---J and L---7 count as crossing, but F---7 and L---J don't. The number of horizontal pipes is doesn't matter.

And then.....I ended up just making a grid with both edges & vertices showing aka a 3n x 3n grid.

My final solution isn't shown in code because I solved it by ctrl+F - in the output and then dividing # of occurrences by 9, that felt faster than writing a loop. Although given I had to check my test input that probably wasn't true.

# Advent of Code 2023
# Day 10: Pipe Maze

with open("inputs/day_10.txt") as file:
    sketch = [list(line[:-1]) for line in file.readlines()]

for y, row in enumerate(sketch):
    for x, tile in enumerate(row):
        if tile == "S":
            start_x = x
            start_y = y

width = len(sketch[0])
height = len(sketch)

current_x = start_x
current_y = start_y

if current_x < len(sketch[0]) and sketch[current_y][current_x + 1] in "-J7":
    current_x += 1
    current_dir = "right"
elif current_y < height and sketch[current_y + 1][current_x] in "|LJ":
    current_y += 1
    current_dir = "down"
elif current_x > 0 and sketch[current_y][current_x - 1] in "-LF":
    current_x -= 1
    current_dir = "left"
else:
    current_y -= 1
    current_dir = "up"

start_dir = current_dir
loop = [(current_x, current_y)]

while current_x != start_x or current_y != start_y:
    tile = sketch[current_y][current_x]

    if tile == "|":
        if current_dir == "down":
            current_y += 1
        elif current_dir == "up":
            current_y -= 1
    elif tile == "-":
        if current_dir == "right":
            current_x += 1
        elif current_dir == "left":
            current_x -= 1
    elif tile == "L":
        if current_dir == "down":
            current_x += 1
            current_dir = "right"
        elif current_dir == "left":
            current_y -= 1
            current_dir = "up"
    elif tile == "J":
        if current_dir == "right":
            current_y -= 1
            current_dir = "up"
        elif current_dir == "down":
            current_x -= 1
            current_dir = "left"
    elif tile == "7":
        if current_dir == "right":
            current_y += 1
            current_dir = "down"
        elif current_dir == "up":
            current_x -= 1
            current_dir = "left"
    elif tile == "F":
        if current_dir == "left":
            current_y += 1
            current_dir = "down"
        elif current_dir == "up":
            current_x += 1
            current_dir = "right"

    loop.append((current_x, current_y))

print(f"Part 1: {len(loop) // 2}")

if current_dir == "right":
    if start_dir == "right":
        sketch[start_y][start_x] = "-"
    elif start_dir == "down":
        sketch[start_y][start_x] = "7"
    elif start_dir == "up":
        sketch[start_y][start_x] = "J"
elif current_dir == "down":
    if start_dir == "right":
        sketch[start_y][start_x] = "L"
    elif start_dir == "down":
        sketch[start_y][start_x] = "|"
    elif start_dir == "left":
        sketch[start_y][start_x] = "J"
elif current_dir == "left":
    if start_dir == "down":
        sketch[start_y][start_x] = "F"
    elif start_dir == "left":
        sketch[start_y][start_x] = "-"
    elif start_dir == "up":
        sketch[start_y][start_x] = "L"
elif start_dir == "right":
    sketch[start_y][start_x] = "F"
elif start_dir == "left":
    sketch[start_y][start_x] = "7"
else:
    sketch[start_y][start_x] = "|"

detailed = [[False for _ in range(width * 3)] for _ in range(height * 3)]

for y, row in enumerate(sketch):
    for x, tile in enumerate(row):
        if (x, y) in loop:
            if tile == "|":
                detailed[y * 3][x * 3:x * 3 + 3] = False, True, False
                detailed[y * 3 + 1][x * 3:x * 3 + 3] = False, True, False
                detailed[y * 3 + 2][x * 3:x * 3 + 3] = False, True, False
            elif tile == "-":
                detailed[y * 3][x * 3:x * 3 + 3] = False, False, False
                detailed[y * 3 + 1][x * 3:x * 3 + 3] = True, True, True
                detailed[y * 3 + 2][x * 3:x * 3 + 3] = False, False, False
            elif tile == "L":
                detailed[y * 3][x * 3:x * 3 + 3] = False, True, False
                detailed[y * 3 + 1][x * 3:x * 3 + 3] = False, True, True
                detailed[y * 3 + 2][x * 3:x * 3 + 3] = False, False, False
            elif tile == "J":
                detailed[y * 3][x * 3:x * 3 + 3] = False, True, False
                detailed[y * 3 + 1][x * 3:x * 3 + 3] = True, True, False
                detailed[y * 3 + 2][x * 3:x * 3 + 3] = False, False, False
            elif tile == "7":
                detailed[y * 3][x * 3:x * 3 + 3] = False, False, False
                detailed[y * 3 + 1][x * 3:x * 3 + 3] = True, True, False
                detailed[y * 3 + 2][x * 3:x * 3 + 3] = False, True, False
            elif tile == "F":
                detailed[y * 3][x * 3:x * 3 + 3] = False, False, False
                detailed[y * 3 + 1][x * 3:x * 3 + 3] = False, True, True
                detailed[y * 3 + 2][x * 3:x * 3 + 3] = False, True, False

queue = []

for y, row in enumerate(detailed):
    if y in (0, height * 3 - 1):
        search = range(width * 3)
    else:
        search = (0, width * 3 - 1)

    for x in search:
        if not row[x]:
            queue.append((x, y))

visited = set()

while queue:
    pos = queue.pop(0)

    for new_pos in (
        (pos[0] + 1, pos[1]),
        (pos[0], pos[1] + 1),
        (pos[0] - 1, pos[1]),
        (pos[0], pos[1] - 1)
    ):
        try:
            if not detailed[new_pos[1]][new_pos[0]] and new_pos not in visited:
                queue.append(new_pos)
                visited.add(new_pos)
        except IndexError:
            pass

inside = 0

for y in range(height):
    for x in range(width):
        if (
            (x * 3 + 1, y * 3 + 1) not in visited
            and not detailed[y * 3 + 1][x * 3 + 1]
        ):
            inside += 1

print(f"Part 2: {inside}")

My code ended up being very messy, so I'll just post my general approach. I suspect my approach to this problem was highly suboptimal again, but I couldn't think of a better way to do this.

For Part 1, following both pipes at once was simple using a bog-standard Breadth-First Search.

Part 2 seemed like it would be easy until I understood the "squeezing betwen pipes" part...

My idea to solve that was simple, though tedious: I wrote code that 'zoomed' the map in 5x by defining templates manually on a piece of paper. Each normal pipe symbol, such as 'J' would turn into a 5x5 block that had ground tiles in the right places so that the "squeezing through" part was possible.

Then I ran a connected-component analysis using a Disjoint-set datastructure (which I implemented following that Wikipedia article) to find all the connected components.
I suspect a correctly-wielded floodfill algorithm would probably have been better here, but I like fancy data structures, so...

The connected component indices were collected into a new grid, and I zoomed that grid out again so that it had the original size.
The grid could be filtered for components that were either in the loop itself or adjacent to the edge of the map.
Components in the loop all have the same component number, so it sufficed to just pick the start tile and remove all tiles with that component id.
Filtering out tiles adjacent to the edge of the map was simpler: I just enlarged the grid by a one-wide border of ground tiles before calculating the components.

Jeez. Even my description of this is a jumbled mess...

Anyway. What remains after filtering should theoretically be components that are enclosed by the loop.

For reasons that I've not found out yet, my code yielded a few, small, spurious components when applied to the actual puzzle input, which I chose to manually filter out using trial and error (i.e. submit the result without them to the site and see if they yield a gold star), which took three tries.

So, not a very satisfying conclusion, but I spent too long on this already. Maybe I'll revisit it later.

I don't think BFS type searches were necessary for this. It's a closed loop, so you just start at S and follow it all the way around, and the furthest point is just half the total distance of that loop.

use std::env;
use std::io::{self, prelude::*, BufReader};
use std::fs::File;
use std::collections::{HashSet,HashMap};

use point2d::point2d::Point2D;

#[derive(Clone)]
struct Pipe {
    dirs: [Direction; 2]
}
impl Pipe {
    pub fn goes(&self, dir: &Direction) -> bool {
        self.dirs.iter().any(|d| d == dir)
    }
}

#[derive(Debug,PartialEq,Copy,Clone)]
enum Direction {
    North,
    South,
    East,
    West,
    Start,
    Nowhere,
}

fn opposite(dir: Direction) -> Direction {
    use Direction::*;
    match dir {
        North => South,
        South => North,
        East  => West,
        West  => East,
        _ => panic!(),
    }
}

fn pipe_kind(ch: char) -> Pipe {
    use Direction::*;
    match ch {
        '|' => Pipe { dirs: [North,South] },
        '-' => Pipe { dirs: [East,West] },
        'L' => Pipe { dirs: [North,East] },
        'J' => Pipe { dirs: [North,West] },
        '7' => Pipe { dirs: [South,West] },
        'F' => Pipe { dirs: [South,East] },
        '.' => Pipe { dirs: [Nowhere,Nowhere] },
        'S' => Pipe { dirs: [Start,Start] },
        _ => panic!("Unexpected pipe map character: {ch}"),
    }
}

fn move_to(from: &Point2D, dir: &Direction) -> Point2D {
    use Direction::*;
    match dir {
        North => Point2D { x: from.x,     y: from.y - 1 },
        South => Point2D { x: from.x,     y: from.y + 1 },
        East  => Point2D { x: from.x + 1, y: from.y     },
        West  => Point2D { x: from.x - 1, y: from.y     },
        _ => panic!(),
    }
}

fn new_dir(dir: Direction, pipe: &Pipe) -> Direction {
    let from = opposite(dir);
    if pipe.dirs[0] == from { pipe.dirs[1] } else { pipe.dirs[0] }
}

fn solve(input: &str) -> io::Result<()> {
    let file = File::open(input).expect("Input file not found.");
    let reader = BufReader::new(file);

    // The pipe configuration at S is not determined programmatically.
    // Must be specified per input file.
    let start_pipe = match input {
        "input.txt"   => Pipe { dirs: [Direction::South,Direction::East] },
        "sample.txt"  => Pipe { dirs: [Direction::South,Direction::East] },
        "sample2.txt" => Pipe { dirs: [Direction::South,Direction::East] },
        "sample3.txt" => Pipe { dirs: [Direction::South,Direction::East] },
        "sample4.txt" => Pipe { dirs: [Direction::South,Direction::West] },
        _ => panic!("Must specify pipe type at S for each input file."),
    };

    // Input
    let input: Vec<String> = match reader.lines().collect() {
        Err(err) => panic!("Unknown error reading input: {}", err),
        Ok(result) => result,
    };

    // Build map
    let mut start: Point2D = Point2D { x: -1, y: -1 };
    let mut pipes: HashMap<Point2D,Pipe> = HashMap::new();
    for (y,line) in input.iter().enumerate() {
        for (x,ch) in line.chars().enumerate() {
            let pt = Point2D { x: x as i64, y: y as i64 };
            if ch == 'S' {
                start = pt;
                pipes.insert(pt,start_pipe.clone());
            } else {
                pipes.insert(pt,pipe_kind(ch));
            }
        }
    }

    // Trace path and calculate part 1
    let mut steps = 0;
    let mut current = start;
    let mut direction = Direction::East;
    let mut path_map: HashMap<Point2D,Pipe> = HashMap::new();
    path_map.insert(start,start_pipe.clone());
    loop {
        let next_pt = move_to(&current,&direction);
        let pipe_next = pipes.get(&next_pt).unwrap();
        path_map.insert(next_pt,pipe_next.clone());
        direction = new_dir(direction, pipe_next);
        current = next_pt;
        steps += 1;
        if current == start { break }
    }
    println!("Part 1: {}",steps/2); // 6864

    // Calculate part 2
    let xmax = pipes.keys().map(|pt| pt.x).max().unwrap();
    let ymax = pipes.keys().map(|pt| pt.y).max().unwrap();
    let yinf = ymax + 1;

    // Part 2
    let mut enclosed_points: HashSet<Point2D> = HashSet::new();
    for x in 0..=xmax {
        'y_lp: for y in 0..=ymax {
            // Skip points that are on the path
            if path_map.contains_key(&Point2D { x: x, y: y }) { continue 'y_lp }

            // Even-Odd Rule (https://en.wikipedia.org/wiki/Even%E2%80%93odd_rule)
            // Draw vector directly South to infinity (ymax+1) from every point not
            // already part of the path. Count the number of times this vector
            // crosses pipes that go east and pipes that go west.
            // If the minimum of these two counts is odd, point is enclosed.
            let mut crosses_east = 0;
            let mut crosses_west = 0;
            for ynew in y..=yinf {
                let pt_test = Point2D { x: x, y: ynew };
                if let Some(pt) = path_map.get(&pt_test) {
                    if pt.goes(&Direction::East) { crosses_east += 1 }
                    if pt.goes(&Direction::West) { crosses_west += 1 }
                }
            }
            // Check for odd number of crosses
            if std::cmp::min(crosses_west,crosses_east) % 2 != 0 {
                enclosed_points.insert(Point2D { x: x, y: y });
            }
        }
    }
    let part2 = enclosed_points.len();
    println!("Part 2: {part2}"); // 349

    Ok(())
}

fn main() {
    let args: Vec<String> = env::args().collect();
    let filename = &args[1];
    solve(&filename).unwrap();
}

I implemented it using a map indexed by Position structs, rather than a 2-dimensional array. I find this a bit more ergonomic, and it also allows for memory-efficient "sparse" maps where very few cells within the grid are occupied, which can be useful in some cases.

I copied the semantics of the stdlib's map interface where the getter functions return a value, bool tuple indicating if the item was present or not.

there are Visit functions that simplify the frequent need to "do something with each cell in row such-and-such".

VisitNeighbors is particularly useful for a lot of AoC problems. it supports both "fall off the edge of the world" and "wrap-around" semantics at the edges of the grid.

package grid

import (
    "github.com/rs/zerolog/log"
)

type Position struct {
    Row int
    Col int
}

type Grid[T any] struct {
    Items      map[Position]T
    Height     int
    Width      int
    Wraparound bool
    Diagonal   bool
}

type CellVisitor[T any] func(pos Position, value T, ok bool)

func NewGrid[T any](height int, width int) *Grid[T] {
    g := Grid[T]{
        Items:  make(map[Position]T),
        Height: height,
        Width:  width,
    }

    return &g
}

func (g *Grid[T]) GetAt(pos Position) (T, bool) {
    g.boundsCheck(pos)
    value, ok := g.Items[pos]
    return value, ok
}

func (g *Grid[T]) Get(rowIdx int, colIdx int) (T, bool) {
    pos := Position{rowIdx, colIdx}
    return g.GetAt(pos)
}

func (g *Grid[T]) SetAt(pos Position, value T) {
    g.boundsCheck(pos)
    g.Items[pos] = value
}

func (g *Grid[T]) Set(rowIdx int, colIdx int, value T) {
    pos := Position{rowIdx, colIdx}
    g.SetAt(pos, value)
}

func (g *Grid[T]) VisitCells(visitor CellVisitor[T]) {
    for rowIdx := 0; rowIdx < g.Height; rowIdx++ {
        for colIdx := 0; colIdx < g.Width; colIdx++ {
            pos := Position{rowIdx, colIdx}
            value, ok := g.GetAt(pos)
            visitor(pos, value, ok)
        }
    }
}

func (g *Grid[T]) VisitRow(rowIdx int, visitor CellVisitor[T]) {
    for colIdx := 0; colIdx < g.Width; colIdx++ {
        pos := Position{rowIdx, colIdx}
        value, ok := g.GetAt(pos)
        visitor(pos, value, ok)
    }
}

func (g *Grid[T]) VisitCol(colIdx int, visitor CellVisitor[T]) {
    for rowIdx := 0; rowIdx < g.Height; rowIdx++ {
        pos := Position{rowIdx, colIdx}
        value, ok := g.GetAt(pos)
        visitor(pos, value, ok)
    }
}

func (g *Grid[T]) VisitNeighbors(rowIdx int, colIdx int, visitor CellVisitor[T]) {
    for rowDelta := -1; rowDelta <= 1; rowDelta++ {
        for colDelta := -1; colDelta <= 1; colDelta++ {
            if rowDelta == 0 && colDelta == 0 {
                continue
            }

            if !g.Diagonal && (rowDelta != 0 && colDelta != 0) {
                continue
            }

            nRowIdx := rowIdx + rowDelta
            nColIdx := colIdx + colDelta

            neighbor := Position{nRowIdx, nColIdx}
            g.visitNeighbor(neighbor, visitor)
        }
    }
}

func (g *Grid[T]) visitNeighbor(neighbor Position, visitor CellVisitor[T]) {
    neighbor, wrapped := g.computeWraparound(neighbor)
    if wrapped && !g.Wraparound {
        return
    }

    value, ok := g.GetAt(neighbor)
    visitor(neighbor, value, ok)
}

func (g *Grid[T]) computeWraparound(orig Position) (Position, bool) {
    real := orig

    if orig.Row < 0 {
        real.Row = g.Height + orig.Row
    } else {
        real.Row = orig.Row % g.Width
    }

    if orig.Col < 0 {
        real.Col = g.Width + orig.Col
    } else {
        real.Col = orig.Col % g.Width
    }

    wrapped := orig != real
    return real, wrapped
}

func (g *Grid[T]) boundsCheck(pos Position) {
    if pos.Row < 0 || pos.Row >= g.Height {
        log.Panic().Msgf("failed bounds check at %v", pos)
    }

    if pos.Col < 0 || pos.Col >= g.Width {
        log.Panic().Msgf("failed bounds check at %v", pos)
    }
}

package grid

import (
    "testing"

    "github.com/stretchr/testify/assert"
)

func TestGridBounds(t *testing.T) {
    g := NewGrid[int](10, 12)

    assert := assert.New(t)

    assert.Equal(g.Height, 10)
    assert.Equal(g.Width, 12)

    value, ok := g.Get(0, 0)
    assert.Equal(value, 0)
    assert.False(ok)

    g.Set(0, 0, 1)
    value, ok = g.Get(0, 0)
    assert.Equal(value, 1)
    assert.True(ok)

    assert.Panics(func() {
        g.Get(100, 100)
    })

    assert.Panics(func() {
        g.Set(100, 100, 1)
    })
}

func TestVisitors(t *testing.T) {
    assert := assert.New(t)

    g := NewGrid[int](10, 10)

    g.VisitCells(func(pos Position, value int, ok bool) {
        assert.False(ok)
        g.SetAt(pos, 1)
    })

    expectedColIdx := 0
    g.VisitRow(5, func(pos Position, value int, ok bool) {
        assert.Equal(value, 1)
        assert.Equal(pos.Row, 5)
        assert.Equal(pos.Col, expectedColIdx)
        expectedColIdx++
    })

    expectedRowIdx := 0
    g.VisitCol(5, func(pos Position, value int, ok bool) {
        assert.Equal(value, 1)
        assert.Equal(pos.Col, 5)
        assert.Equal(pos.Row, expectedRowIdx)
        expectedRowIdx++
    })
}

func TestNeighbors(t *testing.T) {
    assert := assert.New(t)

    g := NewGrid[int](10, 10)

    var neighbors []Position

    g.VisitNeighbors(3, 4, func(pos Position, value int, ok bool) {
        neighbors = append(neighbors, pos)
    })
    assert.Equal(len(neighbors), 4)
    assert.Equal(neighbors[0], Position{2, 4})
    assert.Equal(neighbors[1], Position{3, 3})
    assert.Equal(neighbors[2], Position{3, 5})
    assert.Equal(neighbors[3], Position{4, 4})

    neighbors = nil
    g.VisitNeighbors(0, 0, func(pos Position, value int, ok bool) {
        neighbors = append(neighbors, pos)
    })
    assert.Equal(len(neighbors), 2)
    assert.Equal(neighbors[0], Position{0, 1})
    assert.Equal(neighbors[1], Position{1, 0})
}

func TestNeighborsDiagonal(t *testing.T) {
    assert := assert.New(t)

    g := NewGrid[int](10, 10)
    g.Diagonal = true

    var neighbors []Position

    g.VisitNeighbors(3, 4, func(pos Position, value int, ok bool) {
        neighbors = append(neighbors, pos)
    })
    assert.Equal(len(neighbors), 8)
    assert.Equal(neighbors[0], Position{2, 3})
    assert.Equal(neighbors[1], Position{2, 4})
    assert.Equal(neighbors[2], Position{2, 5})
    assert.Equal(neighbors[3], Position{3, 3})
    assert.Equal(neighbors[4], Position{3, 5})
    assert.Equal(neighbors[5], Position{4, 3})
    assert.Equal(neighbors[6], Position{4, 4})
    assert.Equal(neighbors[7], Position{4, 5})

    neighbors = nil
    g.VisitNeighbors(0, 0, func(pos Position, value int, ok bool) {
        neighbors = append(neighbors, pos)
    })
    assert.Equal(len(neighbors), 3)
    assert.Equal(neighbors[0], Position{0, 1})
    assert.Equal(neighbors[1], Position{1, 0})
    assert.Equal(neighbors[2], Position{1, 1})
}

func TestNeighborsWithWraparound(t *testing.T) {
    assert := assert.New(t)

    g := NewGrid[int](10, 10)
    g.Diagonal = true
    g.Wraparound = true

    var neighbors []Position

    g.VisitNeighbors(9, 9, func(pos Position, value int, ok bool) {
        neighbors = append(neighbors, pos)
    })
    assert.Equal(len(neighbors), 8)
    assert.Equal(neighbors[0], Position{8, 8})
    assert.Equal(neighbors[1], Position{8, 9})
    assert.Equal(neighbors[2], Position{8, 0})
    assert.Equal(neighbors[3], Position{9, 8})
    assert.Equal(neighbors[4], Position{9, 0})
    assert.Equal(neighbors[5], Position{0, 8})
    assert.Equal(neighbors[6], Position{0, 9})
    assert.Equal(neighbors[7], Position{0, 0})

    neighbors = nil
    g.VisitNeighbors(0, 0, func(pos Position, value int, ok bool) {
        neighbors = append(neighbors, pos)
    })
    assert.Equal(len(neighbors), 8)
    assert.Equal(neighbors[0], Position{9, 9})
    assert.Equal(neighbors[1], Position{9, 0})
    assert.Equal(neighbors[2], Position{9, 1})
    assert.Equal(neighbors[3], Position{0, 9})
    assert.Equal(neighbors[4], Position{0, 1})
    assert.Equal(neighbors[5], Position{1, 9})
    assert.Equal(neighbors[6], Position{1, 0})
    assert.Equal(neighbors[7], Position{1, 1})
}