10 votes

Day 10: Pipe Maze

Today's problem description: https://adventofcode.com/2023/day/10

Please post your solutions in your own top-level comment. Here's a template you can copy-paste into your comment to format it nicely, with the code collapsed by default inside an expandable section with syntax highlighting (you can replace python with any of the "short names" listed in this page of supported languages):

<details>
<summary>Part 1</summary>

```python
Your code here.
```

</details>

14 comments

  1. [5]
    Hvv
    Link
    Alright we're getting to those Advent of code problems that go "yeah it's intuitive but now make a computer understand it" which are the best/worst type of problems. Part 1 Solution So the...

    Alright we're getting to those Advent of code problems that go "yeah it's intuitive but now make a computer understand it" which are the best/worst type of problems.

    Part 1 Solution

    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.

    Part 2 Solution

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

    Ray casting algorithm bonus

    Of course someone had to prove that this method works, and the proof is one of the ultimate "intuitive but mathematically hairy" theorems out there. Enter the Jordan Curve Theorem, which states that closed loops in 2D space have an inside and an outside. Very simple, as long as you have absolutely no followup questions.

    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.

    Part 1/2 Code

    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';
    }
    
    4 votes
    1. [2]
      first-must-burn
      Link Parent
      Comment on your Part 2 discussion This made me realize I have a (potential) bug in my part 1 solution. I was thinking that because you couldn't have more than two pipes connected to the start,...
      Comment on your Part 2 discussion

      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.

      This made me realize I have a (potential) bug in my part 1 solution. I was thinking that because you couldn't have more than two
      pipes connected to the start, then the other two adjacent tiles must not be connected -- that's true, but it doesn't mean that they can't be pointing at the start.

      However, in all the test inputs and my puzzle input, the other adjacent tiles do not point to the start tile. Which makes me wonder if I was just lucky, or if all the test inputs are that way. If they are not all that way, then whatever fraction of people get a problem more than two adjacent tiles pointing at the start tile have a more complicated problem to solve. Since it's not covered by any of the given test cases, that doesn't seem fair.

      2 votes
      1. tjf
        Link Parent
        I can confirm my input had this property too, and I am thankful for it.

        I can confirm my input had this property too, and I am thankful for it.

        2 votes
    2. RheingoldRiver
      Link Parent
      Part 2 comments Ahhhhhhhh I hadn't heard of "ray casting" but when drawing this out I stumbled upon the even-odd thing...but then I ran into a wall (pun 100% intended) with the corners, I saw you...
      Part 2 comments

      Ahhhhhhhh I hadn't heard of "ray casting" but when drawing this out I stumbled upon the even-odd thing...but then I ran into a wall (pun 100% intended) with the corners, I saw you could have an even number of corners on each side & then thought maybe I was wrong about this property in the first place, so I didn't pursue any further. Feeling a bit sad now.

      One funny thing is determining which pipes are in the loop.

      As for this, I updated my part 1 to clone the pipe as it got solved, and "saved" the one that didn't error while trying to close the loop, no cleverness in part 2 needed!

      1 vote
    3. tape
      Link Parent
      This is an annoying edge case you just helped me find for part 1, full input data. I couldn't get the right answer to save my life but it was because I checked each side of my S and it was messing...

      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.

      This is an annoying edge case you just helped me find for part 1, full input data. I couldn't get the right answer to save my life but it was because I checked each side of my S and it was messing up my traversing. Thank you!

      1 vote
  2. tjf
    Link
    Nice ramp up in difficulty from part one to two, which I always appreciate. Seems like there were a couple different ways to solve this, and I'm not convinced mine is a great one. But it works!...

    Nice ramp up in difficulty from part one to two, which I always appreciate.
    Seems like there were a couple different ways to solve this, and I'm not
    convinced mine is a great one. But it works! And it's fast enough to not care
    too much.

    Here are my Python solutions, albeit messy ones:

    Part 1

    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)
    
    Part 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)
    

    All in all I liked today's problem, as I often do with graph-type problems.
    Also this is my first day this year that I chose to use complex numbers for
    coordinates, which I think worked out well.

    2 votes
  3. whs
    Link
    Initially I didn't have C# on the "language I've written" list, but I realize I wrote a Unity game back in first year university. I remember that C# now has top level statement. Oh well, this is...

    Initially I didn't have C# on the "language I've written" list, but I realize I wrote a Unity game back in first year university. I remember that C# now has top level statement. Oh well, this is easily the messiest code I've wrote so far. I couldn't even split part 2 into a new file because only one file can have top level statements.

    Finally today's problem is now proper programming problem and not math problem. Part 2 took a while to figure out. I thought of increasing grid resolution but I didn't think it would work until I saw some redditors does it. With increased grid resolution, I run into C# recursion limit that is solved by building in release mode.

    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());
    
    1 vote
  4. first-must-burn
    Link
    Golang solution Pretty happy with how this one came out. I got to use my Grid class that I wrote on spec a few days ago. It already has notions of north/south/east/west, so that made traversal...

    Golang solution

    Pretty happy with how this one came out. I got to use my Grid class that I wrote on spec a few days ago. It already has notions of north/south/east/west, so that made traversal much simpler.

    Part 1 Discussion

    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.

    Part 2 Discussion

    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.

    1 vote
  5. RheingoldRiver
    Link
    Python solutions Part 1 comments Nothing clever about this one really Part 2 comments At first I was like "okay, so this needs to be represented as a grid with both edges & vertices showing in the...

    Python solutions

    Part 1 comments Nothing clever about this one really
    Part 2 comments At first I was like "okay, so this needs to be represented as a grid with both edges & vertices showing in the grid." And then I was like "omg no that's too much work" so I proceeded to spend about an hour trying to figure out another way to do it. Finally I was like "okay let me just do it as a grid but only kind of, I'll make each cell a 3x3 grid and have the same dimensions on the original grid."

    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.

    1 vote
  6. lily
    Link
    I was a complete idiot solving this one. I spent multiple hours trying to solve part 2 without increasing the resolution of the grid and without raycasting like @Hvv (I was basically special...

    I was a complete idiot solving this one. I spent multiple hours trying to solve part 2 without increasing the resolution of the grid and without raycasting like @Hvv (I was basically special casing the individual combinations of characters that could be "squeezed" through; it was horrible), and ended up writing an insanely long and complicated program that didn't actually work. I eventually figured out that I could increase the resolution, and once I did I solved part 2 in about 10 minutes. If I'd figured that out earlier I might've been able to snag a leaderboard spot. But oh well. At least I got top 300 for part 1. I'm not very happy with my solution (it's slow and inelegant), but it works and I don't think I have the energy to improve it any further, haha.

    Solution
    # 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}")
    
    1 vote
  7. DataWraith
    Link
    Algorithm 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...
    Algorithm

    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.

    1 vote
  8. wycy
    (edited )
    Link
    Rust Discussion (Spoilers) I didn't implement an automatic way of determining what kind of pipe the `S` point is. I just eyeballed it for each input and hard-coded it in my code based on the...

    Rust

    Discussion (Spoilers) I didn't implement an automatic way of determining what kind of pipe the `S` point is. I just eyeballed it for each input and hard-coded it in my code based on the filename of the input file.

    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.

    Day 10
    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();
    }
    
    1 vote
  9. spit-evil-olive-tips
    Link
    I wrote a Grid library a couple days ago, anticipating based on previous years there'd be at least one or two problems where it'd be useful. grid design I implemented it using a map indexed by...

    I wrote a Grid library a couple days ago, anticipating based on previous years there'd be at least one or two problems where it'd be useful.

    grid design

    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.

    grid.go
    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)
        }
    }
    
    grid_test.go
    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})
    }
    
    part 1 discussion

    I implemented this by walking the whole way around the loop, and then taking half the length.

    the starting point is recorded as part of the parsing process, and from there I try to walk in each of the four directions (but only if there's a compatible pipe in that direction).

    part 1
    package day10
    
    import (
        "github.com/rs/zerolog/log"
        "github.com/spf13/cobra"
        
        "spit-evil-olive.tips/aoc2023/common"
        "spit-evil-olive.tips/aoc2023/grid"
    )
    
    func parseInput(path string) (*grid.Grid[rune], grid.Position, error) {
        var start grid.Position
    
        lines, err := common.ReadFileLines(path)
        if err != nil {
            return nil, start, err
        }
    
        height := len(lines)
        width := len(lines[0])
    
        g := grid.NewGrid[rune](height, width)
    
        for rowIdx, line := range lines {
            for colIdx, value := range line {
                g.Set(rowIdx, colIdx, value)
                if value == 'S' {
                    start = grid.Position{rowIdx, colIdx}
                }
            }
        }
    
        return g, start, nil
    }
    
    func getNeighbors(g *grid.Grid[rune], current grid.Position) []grid.Position {
        value, _ := g.GetAt(current)
        north, east, south, west := false, false, false, false
        switch value {
        case '|':
            north, south = true, true
        case '-':
            east, west = true, true
        case 'L':
            north, east = true, true
        case 'J':
            north, west = true, true
        case '7':
            west, south = true, true
        case 'F':
            east, south = true, true
        }
    
        var neighbors []grid.Position
    
        if north {
            neighbors = append(neighbors, grid.Position{current.Row-1, current.Col})
        }
    
        if south {
            neighbors = append(neighbors, grid.Position{current.Row+1, current.Col})
        }
    
        if east {
            neighbors = append(neighbors, grid.Position{current.Row, current.Col+1})
        }
    
        if west {
            neighbors = append(neighbors, grid.Position{current.Row, current.Col-1})
        }
    
        return neighbors
    }
    
    func walk(g *grid.Grid[rune], start grid.Position, current grid.Position) int {
        steps := 1
        previous := start
    
        for {
            if current == start {
                return steps
            }
    
            neighbors := getNeighbors(g, current)
    
            for _, neighbor := range neighbors {
                if neighbor != current && neighbor != previous {
                    previous = current
                    current = neighbor
                    steps += 1
                    break
                }
            }
        }
    
        return steps
    }
    
    func walkLoop(g *grid.Grid[rune], start grid.Position) int {
        north := grid.Position{start.Row-1, start.Col}
        south := grid.Position{start.Row+1, start.Col}
        east := grid.Position{start.Row, start.Col+1}
        west := grid.Position{start.Row, start.Col-1}
        
        northCell, _ := g.GetAt(north)
        southCell, _ := g.GetAt(south)
        eastCell, _ := g.GetAt(east)
        westCell, _ := g.GetAt(west)
    
        switch northCell {
        case '|', '7', 'F':
            log.Printf("walking north")
            return walk(g, start, north)
        }
    
        switch southCell {
        case '|', 'L', 'J':
            log.Printf("walking south")
            return walk(g, start, south)
        }
    
        switch eastCell {
        case '-', 'J', '7':
            log.Printf("walking east")
            return walk(g, start, east)
        }
    
        switch westCell {
        case '-', 'L', 'F':
            log.Printf("walking west")
            return walk(g, start, west)
        }
    
        panic("unreachable")
    
    }
    
    var CommandA = &cobra.Command{
        Use:  "10a",
        Args: cobra.ExactArgs(1),
        RunE: func(cmd *cobra.Command, args []string) error {
            g, start, err := parseInput(args[0])
            if err != nil {
                return err
            }
    
            length := walkLoop(g, start)
            log.Printf("%v", length / 2)
    
            return nil
        },
    }
    
    part 2 discussion

    bleh. I hate topology problems.

    I even know the trick to this, counting an even or odd number of edges to cross - but bleh.

    the "even zero-width gaps are permitted" requirement means you can't do edge-detection directly on the map of pipes, you'd need to transform it into a slightly different map-of-gaps.

    performance
    > env BENCHMARK=100 go run main.go 10a day10/10.txt
    {"level":"info","time":"2023-12-10T20:42:47.125499868-08:00","message":"mean: 4.066732ms"}
    {"level":"info","time":"2023-12-10T20:42:47.125555672-08:00","message":"stddev: 241.019┬Ás"}
    
    1 vote
  10. infinitesimal
    Link
    I thought part 1 was straightforward but tedious (BFS, but every pipe shape has a different neighbor), and then I tapped out on part 2 and probably the rest of AoC2023. I tried to walk around the...

    I thought part 1 was straightforward but tedious (BFS, but every pipe shape has a different neighbor), and then I tapped out on part 2 and probably the rest of AoC2023. I tried to walk around the loop and look to my right until I hit another loop tile, which worked for the simplest examples. A small issue was that the loop could be oriented the opposite way (I'd just toggle looking left instead of right), but a bigger issue is that I don't think my code worked for corner pipes in some/many situations, and I didn't know how to fix it.

    1 vote