Day 10 – Pipe Maze

As much I wanted to keep up with this blog, I find my attention wavering. I wish I had a good excuse — there were some things that kept me busy over the summer, but I’ve had plenty of time to write. I just didn’t do it. Mental health is important, but tough to maintain sometimes. But enough of that…

So my apologies for the long delays. However, I still have some more coding problems to cover, especially now that the Advent of Code for 2024 is fast approaching. So let’s get going!

Day 10 gave me something I love — new stuff to learn! Let’s get stuck in.

After dealing with the oasis, you find a hang glider and take it up from the desert to a floating metal island for the Day 10 challenge. (Please check the AoC Day 10 problem for a much better description of the problem)

The floating metal island has a field filled with pipes, some of which connect to one another. You see a large metal animal jump into one of the pipes, and think you might want to study it.

The pipe field is arranged on a 2D grid, and there is a loop in the pipes that starts where the animal jumped in, marked with an ‘S‘. Each pipe in the loop connects to exactly two other pipes in the loop. Pipes can connect up and down, left and right, or any of four corners — again, check the AoC site for a complete description. To study the animal, you need to find the point in the loop furthest from the point where it entered.

Approach

The Advent of Code wouldn’t be complete without at least one mapping problem, where you need to trace your steps through a maze or other representation of physical space.

While it seems simple to start at one point, then walk through the maze of pipes, there is one complication brought up by the description. You need to find the furthest pipe from the starting point. Each pipe in the loop connects to two other pipes, so you can follow both paths until they meet, but how do you know you aren’t backtracking?

For example, assume the start S connects to two other pipes, A and B. The pipe A connects to pipe C, but it still connects to S. The same holds for B — it connects to D and still to S. You move from S to A to start. When you move away from A, you need to make sure you aren’t backtracking to S again. How do you make sure each path is always heading in the proper direction?

You can keep track of where you came from on each path as you progress. However, you may note that this problem looks an awful lot like the Day 8 problem, with each part of the pipe connecting to two others. Maybe if you treat it like a graph, you can use an algorithm you already know.

Graphic Interpretations

You can build a separate graph of the field, but that is unnecessarily complicated. The main problem is that there are a lot of pipe sections in the field, and not all of them are part of the loop you need to trace. Creating another graph means filtering a lot of unnecessary data. Rather than build the graph separately, you can use the field as given.

To do this, you read each line from the input file, then convert each into a Vec<char>. Collect those into another Vec using a helper function:

fn convert_to_char_array(lines: &[String]) -> Vec<Vec<char>>{
    let mut char_array: Vec<Vec<char>> = vec![];

    for line in lines{
        char_array.push(line.chars().into_iter().collect());
    }

    char_array

}

This makes the next challenge easier: how to uniquely identify each part of the loop. In the Day 8 problem, each node had a unique three letter identifier. Here, however, the only thing unique about each part of the pipe is it’s location on the field. By using a Vec<Vec<char>> for the field, you can use the X and Y coordinates of each char as the unique identifier for each section of the pipe. By storing them in a tuple, they act as the key in a variety of other data structures.

Next, you need to find the starting location — this is relatively easy, as it is the only ‘S‘ in the field, and a simple scan finds it quickly:

fn find_start(field: &Vec<Vec<char>>) -> Coord{

    for y in 0..field.len() {
        for x in 0..field[y].len(){
            if field[y][x] == 'S'{
                return Coord(x.try_into().unwrap(), y.try_into().unwrap());
            }
        }
    }
    Coord(0,0)
}

Here you use a struct Coord to hold the X and Y coordinates of each location in the field.

The next challenge is figuring out which way the ‘S‘ section connects to the loop — remember, each section can be straight up and down, straight left to right, or one of four corner pieces. However, in practice, this is actually not difficult — you look in each of the four cardinal directions and see if there is a piece there that connects to the current location. For every other piece with known connections, you only need to check two directions.

Note that you can "cheat" here by inspecting the input file and finding the starting location manually, but that means you can’t test it easily using sample input files.

OK, so now you now where to start, and how to find the next connecting parts of the pipe loop. It’s time to break out the algorithm — the breadth first search.

Breadth First Search Algorithm

The breadth first search algorithm is a great way to search a graph for a node that satisfies a given criteria. In this case, the criteria is that it it the furthest away from the starting node. The algorithm is very well documented and described in just about any source that talks about graphs.

The basic algorithm is as follows:

1. Initialize a queue to hold the list of nodes to check.
2. Mark the starting node as explored, and push it onto the queue.
3. While the queue is not empty:
   a. Pull the next item off the queue
   b. If it’s the goal, stop and return it
   c. Otherwise:
   i. Check everything that connects to that item
   ii. If it’s not already explored, push it onto the queue

There are some extra steps if you need to know the path from the start to the finish, but in this case, we’re only concerned about how many steps it takes to get there.

For this problem, you start with two structures:

// Where is the next thing to try
let mut frontier = VecDeque::<(usize, Coord)>::new();

// Where have we been
let mut visited: HashSet<Coord> = HashSet::new();

The frontier: VecDeque<(usize, Coord)> tracks which sections of the pipe you still need to visit. The usize parameter is how many steps it takes to get here from the start, and Coord is where the section is located in the field. You use a queue here to keep the sections in order as you visit them.

The visited: HashSet<Coord> tracks whether you have explored that section yet. You can do this by changing the char in the field structure as well, but using this HashSet has benefits later.

The first part of algorithm looks like this:

while !frontier.is_empty(){

    // Get the next item to explore
    let current = frontier.pop_front().unwrap();

    // Have we been here already?
    if visited.contains(&current.1){
        continue;
    }

    // Mark this as a visited node
    visited.insert(current.1);
    furthest = usize::max(furthest, current.0);

You use furthest to track how many steps you’ve moved away from the start. If the current section is further that anything else, you want to track that, since that’s the answer to part 1.

Finding the next sections to add to the queue is dependent on the way AoC defined the map, but once you know them (identified as next), you can push them using:

frontier.push_back((current.0+1, next));

Add 1 to the step count for the current node, since each connecting node is one step further away. Once the queue is empty (which means you’ve visited every node in the loop), the value of furthest is the answer you’re looking for.

So how do I know you’re not simply following the loop all the way around and back to the beginning? Because you’re doing a breadth first search, and using a queue structure to hold the frontier. When you add nodes to frontier, you use push_back() and remove them with pop_front(). The queue structure maintains the order of the path, which started with the two nodes connecting the start. Each time through the loop, you check one side, then the other, thanks to the queue structure. You have to meet in the middle.

Part 2

Of course, AoC can’t just leave it like that.

Once you get to the furthest part of the loop, there is no animal there. So, you surmise, it must be nesting somewhere in the middle. You have to figure out how big an area to search by calculating how many tiles are enclosed by your loop.

Part 2 Approach

Here’s where we get to the thing I love — I mean absolutely love — about the Advent of Code contest: I never ever fail to learn something new. The Day 10 challenge was the first one this year to teach me really something brand new — actually two really brand new something’s.

As is the way of these things, I didn’t stumble on this on my own. I have the folks on the Advent of Code subreddit to thank for pointing me in the right direction. While the ideas came from the answers sub-thread, the code is all mine.

The Shoelace Formula

The shoelace formula, also known as Gauss’ area formula, is a way of figuring out the area of any simple polygon, given the coordinates of its vertices on the plane. Invented in the 18th century by Meister, it built on work Gauss and Jacobi had done earlier.

Basically, you start with a simple polygon — that is, any shape with straight sides and known vertices. Pick one vertex to be the start, then follow the path counter-clockwise to find the next vertex. Continue until you have a sequence of vertices $(P_1, P_2, \dots P_n)$. Each vertex $P_i$ has two coordinates, $x_i$ and $y_i$.

Now, starting with $P_1$, calculate $x_1\times\ y_2 – x_2\times\ y_1$. Do this for all your vertices. When you get to the last one, $P_n$, you calculate $x_n\times\ y_1 – x_1\times\ y_n$.

The sum of all these calculations is twice the area enclosed by the polygon, so divide it in half. Why divide this sum in half?

The two vertices are basically the corners of a rectangle, but you don’t need the area of the whole rectangle. The line between them is the edge of the polygon, with part inside the polygon and part outside. The part outside the polygon is useless, so you divide it in half to get rid of that. In essence, you’re dividing the polygon into a bunch of right triangles, calculating the area for each given the locations of two vertices, assuming the vertex of the right angle is at $(0,0)$ relative to those points.

Confused? Check out the Wikipedia article for a full rundown on how it all works. Still confused after that? Sorry, this is a blog post, not a math class.

So how do you make this work in Rust?

Rusty Shoelaces

Just like in Part 1, you find the path, but with a twist — you start looking for the first part of the path by looking down or left first. Why? The shoelace formula needs to start at a corner. You know where the start is, but you don’t know what it represents on the polygon. Is it a corner? Is it not? How can you tell?

For me, I came up with some ideas, but they were all complicated and error prone, So instead, I cheated a little: I looked at my input file, found where my starting point was, identified it as a corner, and made the call to limit the starting directions. You may want to check your input file to make sure that assumption holds for you as well.

The other difference is that, instead of calculating the furthest point as you go, this time you keep track of all the corners in a VecDeque cleverly named corners:

// What are our corners, in order  
let mut corners: VecDeque<Coord> = VecDeque::new();

...

// Is it a corner? Push it onto the queue  
if "7JLF".contains(field[cury][curx]){  
    corners.push_back(current);  
}

Once you have all the corners, calculating the area of the polygon is easy. Pop the first vertex off corners, then start a loop, popping and calculating as you go. When you’re done, add in the final calculation using start, divide by $2$ and Bob’s your uncle:

// Now we can do some calculations  
// Get the area from shoelace  
let mut area = 0;  
let mut c1 = corners.pop_front().unwrap();  

while !corners.is_empty() {  
    // let c1 = corners.pop_front().unwrap();  
    let c2 = corners.pop_front().unwrap();  

    area += (c1.0 * c2.1) - (c2.0 * c1.1);  
    c1 = c2;  
}

area += (c1.0 * start.1) - (start.0 * c1.1);  
area /= 2;

Of course, this gives us the area of the polygon, but that’s not what we need — we need the interior points, and that’s where the second new thing I learned comes in: Pick’s Theorem.

Pick’s Theorem

In the late 19th century, geometrician Georg Pick figured out a brilliant way to calculate the area of a simple polygon. If you know the integral coordinates of the boundary of the polygon, and the number of integral interior points contained in the polygon, you can calculate the area as:
$$A = i + {b\over2} – 1$$
Where $A$ is the area, $i$ is the number of interior points, and $b$ is the number of boundary points.

You already figured out the area $A$ using the shoelace formula above, and you can count all the points on the loop as $b$, either using your answer from Part 1 or visited.len() from the shoelace formula area calculation. Note that $b$ isn’t the number of corners, but the complete number of points on the polygon

This means you can easily calculate $i$ as:
$$i = A – {b\over2} + 1$$
In Rust, this looks like:

let b: isize = visited.len().try_into().unwrap();  

if area < 0 {  
    area *= -1;  
}  

area + 1 - (b/2)

Checking for a negative area is done just in case the shoelace formula went clockwise instead of counter-clockwise. In any case, this is the answer we need for part 2.

Summary

I love it when I learn something new, and Day 10 was my time to do that. I can’t say I got either part done within the 24 hour time period — I think the fact that it was a Sunday, and we were decorating our own house for the holidays had something to do with it.

The code, if you’re interested, can be found here — I know it can be improved, and any suggestions for that are always warmly appreciated.