Last modified: 2023-12-11 @ a185fa7

# Advent of Code 2023: Day 10

*This post is part of a series: Advent of Code 2023*

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.