Overview

This was my first year participating in Advent of Code, a daily programming challenge starting on December 1st and ending on Christmas. I found the first ten or so days to be relatively simple to hack together a solution, but the difficulty quickly ramped up and I found myself needing to rethink my approach often (and check the subreddit for hints). It paid off though as I managed to get all 50 stars by completing both parts of each daily challenge.

I found Day 24 to be an especially fun challenge. The premise of the puzzle was needing to traverse a 2D grid. The grid starts off with spaces occupied by blizzards that move in one of four directions; up, down, left, or right. As you move, each blizzard moves, and you cannot move to a space that is occupied by a blizzard or stay in a space if it will be occupied by a blizzard on the next turn. Blizzards will never change their direction and when they reach the end of the grid, they wrap around to the side opposite of their direction of movement (e.g., hitting the top edge of the grid will cause them to come out the bottom).

Strategy

One of the first things I recognized in this puzzle—thanks largely to lessons learned from previous days—was the cyclical nature of the grid state. Consider a grid with a width of 6 units and a height of 5 units. The blizzards moving across the width of the grid will be back to their original starting space every 6 turns and the blizzards moving across the height of the grid will be back to their original starting space every 5 turns. The least common multiple of 6 and 5 is 30, which means every 30 turns the grid will be back to its original starting state. This means we don’t need to keep track of how the blizzards move every turn, we can just calculate each grid state and use that to determine where we can move each turn.

I started my solution by creating an encapsulation of each grid state. What I really care about with each state is the collection of valid spaces. To accomplish this, I opted to create a function that encodes x-y coordinate pairs into a single string value and use that as the key in a key-value map. When I want to get the collection of all valid spaces, all I need to do is get all of the keys in the map and use a function that turns the encoded string values back into x-y coordinate pairs.

The next thing I needed was a way to keep track of blizzard movement. What I really needed to keep track of for each blizzard was its current location and direction of movement. I also wanted a way to move each blizzard in the appropriate direction. I created a class to encapsulate all of this data and functionality.

With grid states and blizzard movement taken care of, I now needed a class that would keep track of each blizzard, generate the grid based on all blizzard locations, and then move each blizzard to the next location. This seemed like an excellent opportunity to use a factory pattern, so I created a class aptly named GridFactory. The idea was simple; I could use the height and width of the grid to calculate how many grid states I needed to keep track of, calculate each of those grid states, and then use the stored grid states to determine how I can move through the grid at a given time index.

Now it was time to get to the fun part, constructing a graph that connected all the possible movements between valid spaces at time T to neighboring spaces at time T + 1. If I were to create a visual representation, this would be a third axis to represent movement in the grid as the grid state changes. This axis would also be circular such that the final time T would circle back to 0 instead of T + 1, which is a relatively common practice in computer science.

From here, a simple breadth-first search is all that’s needed to find the shortest path to the finish. Since the graph is unweighted, Dijkstra’s algorithm and A* search don’t provide a huge benefit, though you can use the remaining Manhattan Distance as a heuristic in either algorithm. Keeping track of the movement history along the way, we can easily calculate the number of moves required to reach the end.

Part 2

The second part of the puzzle involves traversing to the end, making a round trip back to the start, and then traversing back to the end again. Fortunately, there weren’t too many changes that needed to be made to find the answer. All I needed to do was:

1. Update my function to find the shortest route to take in the start position, ending position, and the time index of where to start (this ensures we look at the correct grid state for each leg of the trip
2. Add a function to clear any nodes that have been marked as visited (for performance reasons, it was vital that we would not recalculate a path from any node that had been visited previously)

Both of these changes were rather trivial, and with them in place, I was able to calculate the shortest path for each leg of the trip. Once I had all three of my paths, I simply added up the total time taken and found my answer.

Full Solution

I wrote my solution in JavaScript using Node as my runtime. I had a handful of test files to help track down a few issues I encountered with ava as my test runner.