Day 8, part 2

Introduction

Welcome to the par two of day 8 puzzle. First part is described in Day 8, part 1. Please get familiar with the part 1 before jumping into this article. This part of the challenge is available only when you successfully finished the part 1. The second part of the challenge is described under section here.

What's the new problem?

From now on the rules changed. We don't have one starting and one ending point, thus there is more than one path. Now every node which name ends with is a start node and every node which name ends with is an end node. We have to go through every path starting at every starting node and finish when all the paths end simultaneously on a node. Once again, the answer we have to give is how many steps it took.

Solution

To solve this problem we will mostly reuse the code we have, we just have to make some adjustments.

Update the crawl function to take the initial node as a parameter

Now when we have to crawl multiple paths from many different starting points, it might be useful to pass to our function the initial node. But first let's update the test data with the one from this part of the puzzle.

We also have to change the rules of what means that the node is last. Now we only need our node to end up with .

Now if we take the node as a staring node and look at its path it goes like this:

This means we had to take 2 steps to get to the node which ends with . Now lets update the function to take the parameter.

And if we run the code we can see:

This means our code works fine. We can save this and move forward.

Finding the starting nodes

This is as simple as finding all the nodes which name ends with .

This gives us the following list of nodes:

If you look now at the test data, you can see that this is the correct answer. We can commit the changes.

Finding the number of steps for each path

Now We can use our upgraded function to find how many steps we need to make to

As you can see this is almost the same function as the , but we changed the condition to check if all the are the ending nodes and in general we update multiple nodes instead of just one. Now if we run our little program we can see:

If you take a look into the puzzle description, you will see that this is the correct answer. Once again we can save our progress.

Finding the LCM

Instead of looping until we get the result where all the nodes ended up on node, we can find the least common multiple for all the steps we had to take in each path. To do this we can use this set of functions:

We can run this and see if the result is as we expected. But what do we expect? Lets take a look at the test data.

1. We start at and .
2. We move both nodes to the left, leading to and .
3. Next we move both nodes to the right, leading to and .
4. Once again, we move both nodes to the left, leading to and .
5. Then, we move both nodes to the right, leading to and .
6. Once more, we move both nodes to the left, leading to and .
7. And finally we move both nodes to the right, leading to and .

So, in this example, you end up entirely on nodes that end in after steps.

So that's it! Let's save the result of our work before we feed our code with the real data.

Final result

Now if we replace the test data with the one coming from the input file and run our program we get:

We can feed this number to the form on the AoC website and as soon as we submit it we can see that our hard work was a big success. Congratulations to all of you who made it. The final step is to save our progress.

Now it's time for me to invite you to the Day 9, part 1 where we will try to crack the code once again!