Reflections on Advent of Code 2022

Now that I've had a couple weeks off from Advent of Code, I wanted to reflect a bit on some of the lessons I learned after my second year of doing all the puzzles. In this article I'll list some of the things that worked really well for me in my preparation so that I could solve a lot of the problems quickly! Hopefully you can learn from these ideas if you're still new to using Haskell for problem solving.

Things that Worked

File Template and Tests

In 2021, my code got very disorganized because I kept reusing the same module, but eventually needed to pick an arbitrary point to start writing a new module. So this year I prepared my project by having a Template File with a lot of boilerplate already in place. Then I prepared separate modules for each day, as well as a test-harness to run the code. This simplified the process so that I could start each problem by just copying and pasting the inputs into pre-existing files and then run the code by running the test command. This helped me get started a lot faster each day.

Megaparsec

It took me a while to get fluent with the Megaparsec library. But once I got used to it, it turned out to be a substantial improvement over the previous year when I did most of the parsing by hand. Some of my favorite perks of using this library included easy handling of alternatives and recursive parsing. I highly recommend it.

Utilities

Throughout this year's contest, I relied a lot on a Utilities file that I wrote based on my experience from 2021. This included refactored code from that year for a lot of common use cases like 2D grid algorithms. It especially included some parsing functions for common cases like numbers and grids. Having these kinds of functions at my disposal meant I could focus a lot more on core algorithms instead of details.

List Library Functions

This year solidified my belief that the Data.List library is one of the most important tools for basic problem solving in Haskell. For many problems, the simplest solution for a certain part of the problem often involved chaining together a bunch of list functions, whether from that library or just list-related functions in Prelude. For just a couple examples, see my code for Day 1 and Day 11

Earlier in 2022 I did several articles on List functions and this was very useful practice for me. Still, there were times when I needed to consult the documentation, so I need more practice to get more fluent! It's best if you can recall these functions from memory so you can apply them quickly!

Data Structures

My series on Data Structures was also great practice. While I rarely had trouble selecting the right data structure back in 2021, I felt a lot more fluent this year applying data structure functions without needing to consult documentation. So I highly recommend reading my series and getting used to Haskell's data structure APIs! In particular, learning how to fold with your data structures will make your code a lot smoother.

Folds and For Loops

Speaking of folds, it's extremely important to become fluent with different ways of using folds in your solutions. In most languages, for-loops will be involved in a lot of complex tasks, and in Haskell folds are the most common replacement for for-loops. So get used to using them, including in a nested fashion!

In fact, the pattern of "loop through each line of input" is so common in Advent of Code that I had some lines in my file template for this solution pattern! (Incidentally, I also had a second solution pattern for "state evolution" which was also useful).

Graph Algorithms

Advent of Code always seems to have graph problems. The Algorithm.Search library helps make these a lot easier to work through. Learn how to use it! I first stumbled it on it while writing about Dijkstra's Algorithm last year.

The Logger Monad

I wrote last year about wanting to use the Logger monad to make it easier to debug my code. This led to almost all of my AoC code this year using it, even when it wasn't necessary. Overall, I think this was worth it! I was able to debug problem much faster this year when I ran into issues. I didn't get stuck needing to go back and add monads into pure code or trying to use the trace library.

Things I Missed

There were still some bumps in the road though! Here are a couple areas where I needed improvement.

Blank Lines in Input

Certain problems, like Day 1, Day 11, Day 13 and Day 19, incorporated blank lines in the input to delineate between different sections.

For whatever reason, it seems like 2021 didn't have this pattern, so I didn't have a utility for dealing with this pattern and spent an inordinate amount of time dealing with it, even though it's not actually too challenging.

Pruning Graph Algorithms

Probably the more important miss in my preparation was how I handled the graph problems. In last year's edition, there were only a couple graph problems, and I was able to get answers reasonably quickly simply by applying Dijkstra's algorithm.

This year, there were three problems (Day 16, Day 19 & Day 24) that relied heavily on graph algorithms. The first two of these were generally considered among the hardest problems this year.

For both of these, it was easy enough to frame them as graph problems and apply an algorithm like Dijkstra's or BFS. However, the scale of the problem proved to be too large to finish in a reasonable amount of time with these algorithms.

The key in all three problems was to apply pruning to the search. That is, you needed to be proactive in limiting the search space to avoid spending a lot of time on search states that can't produce the optimal answer.

Haskell's Algorithm.Search library I mentioned earlier actually provides a great tool for this! The pruning and pruningM functions allow you to modify your normal search function with an additional predicate to avoid unnecessary states.

I also learned more about the A-Star algorithm than I had known before. Previously, I'd vaguely thought of A-Star as "Dijkstra with a heuristic", which is kind of correct but not helpful in describing what the heuristic actually does.

I eventually came to the understanding that Dijkstra is comparable to Breadth-First-Search for a weighted graph. A-Star is closer to a Depth-First-Search on a weighted graph. While a normal DFS blindly goes down a path until it finds an end-state, A-Star uses the heuristic to attempt to make sure the first parts of the graph that we search are the most likely to lead us to the goal.

It was difficult to find a heuristic for Days 16 & 19, but I was able to apply A-Star on Day 24 to get a noticeable speed-up.

Conclusion

For the next few Thursdays I'm still going to be catching up on the video walkthroughs from Advent of Code. And then next Monday I'll have one more AoC-related article exploring how we can build an API to access our question inputs without even using the web browser!

Make sure to subscribe to our mailing list if you haven't already to get access to our Subscriber Resources!