I Completed All 8 Advents of Code in One Go: Here Are the Lessons I Learned.

Context

Last December, I completed my first Advent Of Code: 2022. Before that, I had a total of something like six stars for the past seven years. But this year, we created a private leaderboard at Docker, and it motivated me to go as far as possible.

For those unfamiliar with the Advent Of Code, one small word: it’s an advent calendar of programming puzzles. Every year since 2015, Eric Wastl released in December a new puzzle each day until day 25. In general, the puzzles get more difficult over time.

Because I had so much fun last December, beginning of 2023, I decided to challenge myself: try to complete all the previous years and reach all the possible stars. After 34,281 lines of code written (tests not included), I wanted to write a post describing all the lessons I learned throughout this genuinely amazing experience 🚀.

NOTE: I completed the Advents Of Code mainly in Go and a bit in Rust but I’ll keep this post as much as possible language-agnostic.

Graphs, Graphs, And Graphs

I never had to use fancy data structures to complete an Advent Of Code. Yet, we need to be familiar with the most common ones: arrays, linked lists, stacks, queues, heaps, trees, and… graphs.

Being comfortable with graphs is an absolute necessity: how to represent a graph and the most common algorithms. For me, the two algorithms I used the most, and by far, were:

• Breadth-First Search (BFS): allows computing the shortest path in an unweighted graph
• Topological sorting: allows to sort vertices

Let’s delve a bit into the latter as it may be the one most people are the less comfortable with. Imagine the following scenario where we need to handle four different tasks. Yet, some tasks need to be completed before others:

If there’s an edge from U to V, then U ≤ V

In this example, an arrow represents an happens-before relationship. For example, to complete D, we need to complete C first. But to complete C, we have to complete both A and B. Using topological sort, we could flatten the graph based on the edges representing the dependencies:

A, B, C, D

Why is this algorithm important? Let’s take 2019 day 14 as an example. We are given a list of chemical reactions:

10 ORE => 10 A
1 ORE => 1 B
7 A, 1 B => 1 C
7 A, 1 C => 1 D
7 A, 1 D => 1 E
7 A, 1 E => 1 FUEL

We need to calculate what’s the minimum number of ORE required to produce one FUEL. To solve this problem, my solution relied first on using topological sorting to model the transformation dependencies. Once modeled, I just had to start from a FUEL and then delve into the dependencies to get the final result.

All in all, completing the Advents Of Code allowed me to get way more comfortable working with graphs, and I discovered algorithms I wasn’t aware of (e.g., using Floyd–Warshall to calculate the length of shortest paths between all pairs of vertices which I used for 2022 day 16 here). Doing an Advent Of Code is a great way to learn and practice algorithmics.

Coding != Software Engineering

As a software engineer, be it at Docker or in previous companies, most lines of code are written while keeping many factors in mind, such as maintainability, readability, expressiveness, etc. Different characteristics that do matter in the context of long-term projects with plenty of engineers working on the same codebase.

Yet, writing some code for the Advent Of Code or similar challenges is a complete different context. We don’t really care whether our solution is maintainable: we’re the only one to work on it, and once we get the two stars, we move to something else. We may face many challenges that aren’t necessarily the same as in our day-to-day job.

In the (great) Software Engineering at Google book, there’s one quote that perfectly summarizes my point:

“Software engineering is programming integrated over time”.

The Advent Of Code made me realize again how much coding activity can sometimes be different from the job of a software engineer. As software engineers, we face the time dimension, which does impact our activity immensely. Sometimes for the best, sometimes for the worst.

If a Result Is Random, It’s a Great Trail To Follow

On some occasions, our code may produce a non-deterministic result; put another way, a result that varies from one execution to another. In this case, it’s actually not that bad. Facing such a scenario means tracking the parts in our code that lead to this non-deterministic result.

One case I faced pretty frequently was a non-deterministic result with my Go solution when using a map iteration. Indeed, in Go, iterating on a map is unspecified; it produces a (somewhat) random ordering. When I noticed such a behavior, it meant that the code inside the map iteration was necessarily wrong, and I needed to review that part carefully. And in many occasions, it was the issue preventing me from having a successful solution.

So if you face a non-deterministic result, try understanding what part of your code leads to such behavior. You may not have found the unique problem of your code, but it’s a trail you must follow.

How to Rely on Algorithm Invariants

Regardless of the language we use, we all have some ways to check assertions; said differently, verifying predicates in the code that should always be true. I found out that, sometimes, using assertions in my code was particularly useful.

For example, 2016 day 11, I implemented a solution that handled different cases based on a variable value. At first, my code was written in a way that I wasn’t even handling one specific case. Indeed, this case was invalid, and I should never face it.

Yet, when I realized that my solution wasn’t correct, I added an assertion into my code to make sure that I was never facing this case, and surprise: I was. The problem wasn’t that this was a wrong invariant; it was because my code was, on some occasions, producing this incorrect value. It helped me find out what was the source of the problem.

NOTE: In Go, we can, for example, use panic to semantically express: “this is not an error per se; it’s an actual fault, and this case should never ever occur”.

So using assertions to model your algorithm invariants can sometimes be particularly useful, especially in the process of debugging why a solution doesn’t work.

Beyond Big O

The Big O notation is a great way to model how an algorithm will scale. Yet, it’s far from being the only part to consider. For example, we may develop a solution with a quadratic complexity: O(n²). However, from which value of n will our solution becomes too slow to execute?

That made me realize that I was far from having a precise understanding of how many instructions can be run in a decent amount of time. For example, and the question is in Go, but the order or magnitude is probably similar for most programming languages: how long does it take to get 100 million random entries from a map containing a thousand values (I purposely designed an experiment not to leverage CPU caches)?

• 1 millisecond?
• 1 second?
• 10 seconds?
• 1 minute?
• 10 minutes?

The answer is roughly one second. So, it takes one second to retrieve 100 million random entries from a map with a length of a thousand values.

Once you start understanding what’s feasible in a decent amount of time, you will also be able to confront your big O analysis against your possible solution. Sure, in 2017 day 15 we needed to repeat an operation 40 million times, but my solution runs in less than 20 milliseconds.

The more you practice, the more you’ll be able to have some sense of how long your solution should run, and this is invaluable knowledge.

NOTE: A great addition to this very point is the page created by Julia Evans and Kamal Marhubi: Do you know how much your computer can do in a second? It gives a list of examples showing what a program can tackle within a second.

Mutability Can Be a Source Of Mistakes

During 2018 day 22, we were given a way to generate a map (the map itself isn’t an input), and we needed to find the shortest path from one point (M) to another (T). One challenge was also the fact that the map wasn’t bounded, and perhaps, the shortest path was going through rows below the actual target (the Xs represent the shortest path):

M=.|=.|.|=.|=|=.
XXXXX|||..|.=...
.==|X...||=..|==
=.|.X..|.==.|==.
=|..X=...=.|==..
=||.X.=||=|=..|=
|.=.X==|||..=..|
|..=X||=.|==|===
.=..XX=..=|.|||.
.====X=|||=|=.|=
.===|X|===T===||
=|||.XX|==X.|=.|
=.=|=.XXXXX||==| <-- Passing through this row
||=|=...|==.=|==
|=.=||===.|||===
||.|==.|.|.||=|| 

In my solution, I updated two parameter variables by adding an extra length:

func toCave(depth, targetCol, targetRow int) *Cave {
   const (
      extraRow = 100
      extraCol = 100
   )

   targetCol += extraCol // Mutate parameter variable
   targetRow += extraRow // Mutate parameter variable
   // ...
} 

This code is 100% valid: variables in Go are mutable. Yet, it caused me a lot of pain to understand why my solution wasn’t passing. Indeed, throughout this function, I was using targetCol and targetRow in two different ways:

• To represent the max size of the 2D array
• But also to indicate the coordinates of the target

In both cases, that was stupid. For the former, it was a semantic issue; I was using a variable called targetXXX for something that wasn’t really a target. And for the latter, that was a pure bug because the target I was searching for (T) wasn’t anymore the actual target because of this extra delta I was adding.

In my case, I should have created two new variables:

func toCave(depth, targetCol, targetRow int) *Cave {
   const (
      deltaRow = 100
      deltaCol = 100
   )

   totalCol := targetCol+ deltaCol // New variable
   totalRow := targetRow + deltaRow // New variable
   // ...
}

So bear in mind that mutability, even if allowed, can sometimes be a source of mistakes. At the very least, keep a consistent semantic meaning for a variable throughout your function.

What if a Solution Solves the Example but Not the Puzzle Input

I’m pretty sure that it happens to all of us. We implement a solution, we run it against the small example given during the day description, and the test passes. Then, we run our solution against our puzzle input and click on submit confidently, but we get this:

Sadness.

The first thing I do in this case (I mean apart from suspecting a bug in the Advent Of Code solutions which is never the case) is to run a successful test using the code coverage feature of my IDE:

On the left-hand side, the red part represents the code path not covered.

Why do this? If your solution works for one example and not another, there is a significant probability that the issue lies in the code not covered. It might not be 100% true (for example, a bug might be present only if a line of code is executed twice), but it saved me on many occasions.

When You’re Stuck 1/3: Try Visualizing Your Data

If you’re stuck on a problem, one of the possible approaches is trying to visualize your data.

It happened to me on 2018 day 23. In a nutshell, we’re given a list of robots having a position and a range, and we need to calculate the coordinate in the range of the largest number of robots. One small problem, the coordinates, and ranges are gigantic:

pos=<-34870395,34498817,-2843154>, r=96244937
pos=<-52741579,9875242,37136273>, r=89509114
pos=<23303891,41664349,2510522>, r=63042453
pos=<10573027,54782809,49932958>, r=97928881
pos=<30268215,-1711562,83940876>, r=91888282
...

Because of the scale, a brute-force solution should complete in a few million years. For some time, I was completely stuck. Then, I tried visualizing the input data. So dividing all the coordinates by five million and then checking where the clusters were. By doing that, I was able to notice that the most interesting coordinates were inside one little square:

A 1 represents an interesting coordinate.

Thanks to that, I came up with an algorithm that:

• Divides all the coordinates by one million, selects the most interesting area, and delves into it.
• Then it divides the coordinates by 100 thousand, selects the most interesting area, and delves into it.
• Etc.

Finally, the range I’m iterating over is small enough to make my code run in a reasonable time.

So, sometimes when you’re stuck, try visualizing your data. Humans work well when they have a mental picture of the problem.

When You’re Stuck 2/3: Try Another Approach

It looks like a dumb advice: if you’re stuck on an approach, you should find another one. Or perhaps it’s because I’m dumb enough, but I really struggled sometimes to apply this advice. On some occasions, it took me hours to realize that my solution was a dead end. I can’t emphasize enough how important it is sometimes to take a step back on your solution and try to understand why it won’t work.

For example, 2015 day 19 part 2 (a problem involving some string transformations), I spent way too much time trying to solve the problem from the start to the target, whereas it took me only a few minutes to solve the other way around, from the target to the start.

So you need to be able sometimes to realize yourself that a solution is a dead end. For that, the following point is sometimes mandatory.

When You’re Stuck 3/3: Go Do Something Else, or Go Get Some Sleep!

It might sound like a joke, but it’s not. Sometimes, when you’re stuck on an issue, the best option for us is to stop. Go get a shower, watch a movie, read a book, get some sleep, etc. In other words, give your brain some rest.

I hadn’t counted the number of times when I was stuck on a problem, and I started doing something else, I came up with ideas. It wasn’t necessarily the actual solution, but some food for thought, some test cases to check, etc. Even if sometimes it’s far from being easy, force yourself to do something else to improve your chances of success.

NOTE: I struggled with this piece of advice for myself. On some occasions, I worked until being mentally exhausted. Sometimes it’s easy to give advice that you don’t follow yourself!

The Advent Of Code Made Me Love Algorithms and Data Structures Again

I don’t know about you, but personally, the moment I have to use data structures the most (I mean outside just arrays and maps) is when I prepare coding interviews. And because of this context, I tend to associate those topics with something constraining: I don’t do it because I enjoy it; I do it because I have to.

Thanks to the Advent Of Code, it made me love working again on algorithmics. I started reading Advanced Algorithms and Data Structures by Marcello La Rocca because I want to extend my knowledge beyond the basic data structures we have to know during coding interviews, such as K-d trees, clustering, d-way heaps, gradient descent, etc. There are so many things to learn in this domain. It’s truly fascinating.

Conclusion

A massive thank you to Eric Wastl and all the people working on the Advent Of Code ❤️. I can’t praise enough how great my experience was, and if you’re not familiar with the Advent Of Code or a bit reluctant, you should definitely try it!

In the meantime, here’s my GitHub repository:

GitHub - teivah/advent-of-code: 🎄 My solutions to the Advent Of Code, from 2015 to 2022.

Bonus

• Is that normal to struggle that much to implement a doubly linked list in Rust? Because such website exists, I feel like the answer is yes.
• 3D is hard! At least for me. I have never been good at visualizing data in a 3D space. I struggled immensely with days such as 2021 day 21 or 2022 day 22 part 2 (no, not a 3D cube! 😱).
• The people competing for the global leaderboard are really great. Among them, betaveros is genuinely remarkable. This guy is almost consistently ranked in the top 10 every day. Having people like him forces you to stay humble.
• If you want to start an Advent Of Code, I would recommend you either to start building your own library or reusing an existing one. For example, the activity of parsing the puzzle inputs should be as fast as possible. Even if you don’t compete for a leaderboard, what matters is to focus on the actual problem. Hence, relying on a library for common utilities is important. If you use Go, you can take a look at the one I built here. I also made a small script to generate a new project and automatically import the puzzle input.