Advent of Code 2023: Day 10

Code for solutions available on GitHub.

More covid-programming and -writing. Will be brief, especially because this day was pretty messy for me both in terms of health and code quality (They might be correlated).

Pipe Maze

The input today represents a bunch of pipes or ground. Each pipe connects in exactly two of the cardinal directions, north, west, east, or south. No T-junctions here.

The first example given is a simple loop of pipes:

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

Where . represents ground and the other characters are pipes. Given a starting point on the pipe, how many steps are needed to reach the point farthest from the start (in number of pipes travelled, not absolute distance)? The answer is obviously just the length of the loop divided by 2. The challenge in this day is designing good data structures and parsing to make it pretty simple. I did not do a very good job of that, as can be seen in the repo, but hey it works.

Part 2

In this part, the challenge is to figure out how many tiles are enclosed by the loop. In the example above, it is just one ground tile. The real input of course has many, many more ground tiles and random pipes that are not part of the loop. These should also be accounted for.

Determining whether a point is on the inside of a closed curve is a solved problem from computer graphics. The solution is given by the non-zero winding number. Basically, we need to keep track of the direction of the curve we’re interested in (the pipe loop) and if we draw a line out to infinity from a point, we can determine if the point is on the inside or outside by counting the number of crossings and their direction. If the pipe loop crosses this infinite ray in a leftward direction, we subtract one from our count. If it crosses it in a rightward direction, we add one. The final number we get from this process is called the winding number, and if it is anything other than zero, the point is on the inside of the loop.

It’s pretty intuitive why, as if the winding number is zero, every leftward crossing has been matched by a rightward crossing and this can only happen when the point is on the outside of the loop.

It’s pretty simple to explain, but a whole lot of bookkeeping if you choose suboptimal data structures and/or have a fever when coding it. Don’t be like me.

Anyway, the winding number can be calculated looking backwards for each tile in each row of the input. No need to do any 2D-array operations or anything fancy for this puzzle.