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

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 itand in the looprather 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!

## 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, then the other two adjacent tiles must not be connected -- that's true, but it doesn't mean that they can't be

pointing atthe 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

notall 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.I can confirm my input had this property too, and I am thankful for it.

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

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!

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!

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

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

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

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.

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.

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

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

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

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

## grid_test.go

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

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

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.