Solving Advent Of Code 2024
Posted on
What is Advent of Code
Advent of Code is a yearly set of 25 problems, each divided in two parts, with one being released every day since the 1st of December all the way until Christmas day. Quite literally an advent calendar for coding. As we approach Christmas, the problems become harder and harder.
This year, I decided to take part. I had a three day workshop on using Python for Data Science at the beginning of the month, so it felt fitting to stick with Python for the rest of the month as well. Turns out that by the time I got to the last few problems, I was taking well over 6 hours to complete some of them. Here's some of my favorite problems:
Day 13
This problem involved trying to find the minimum amount of tokens to spend on a bunch of claw machines. A claw machine looks like this:
Pressing the A button costs 3 tokens, and pressing the B button costs 1 token. We start at (0,0).
At first, I thought this would end up being a Linear Programming problem, in which we had to minimize the objective function . Turns out, none of that was necessary, because there was only ever one possible solution to each claw machine problem (basically the intersection of two lines in ). All there was to be done was to solve a bunch of systems of equations.
In order to solve this particular example, I started out by rewriting the data in this system of equations:
By rewritting the problem this way, we can now use Cramer's Rule to solve for and . Since the matrix of the system of equations is 2x2, calculating determinants is straightforward. Here's the three determinants I had to calculate in the present example:
Now, the value of is simply and the value of b is . If these values are integers, we have the only combination of A button presses and B button presses that solves this problem. For this specific claw machine, the solution is and .
Now all we have to do is just rinse and repeat for all the different claw machines that are in the input. Then, we can add to a "token" variable to figure out how many tokens we need. Here's how I did it in code:
Python Code
I liked this problem because of the simplicity of the solution. It's all very basic Linear Algebra. You can read the full problem statement here.
Day 19
Day 19's problem was about arranging "towel" patterns into some desired designs. Here's an example of what the input looks like:
The first line represents each of the towel patterns to be used. I'll call these "towels". We have unlimited access to each of them. The remaining lines represent the desired patterns we're trying to achieve. I'll call these our "goals". For example the first one, brwrr
, can be built by using br
+ wr
+ r
, all towels that we have access to.
The task is to figure out all the different ways we can produce the goals. In the present example, we can achieve brwrr
like br
+ wr
+ r
but we can also achieve it using b
+ r
+ wr
+ r
. On the other hand, the goal ubwu
is actually impossible to achieve with the given towels.
To solve this problem, I used depth first search. The dfs
function takes the following inputs:
- A
towels
array (e.g.,["r", "wr", "b", "g", "bwu", "rb", "gb", "br"]
), - A
target
string (e.g.,brwrr
), - An
index
indicating the current position in thetarget
.
The base case happens if the index is the length of our target goal: in this scenario we've reached the end of the word and we return 1.
Then, for each towel in the towels
array, if the substring of the target
starting at index
matches the towel, we recursively call dfs
with the updated index (index + len(towel)
). This process allows us to explore all possible ways to build the target
using the towels.
There is one issue though: if our input is too large, with a lot of different towels, the program takes a long time to run. For context, the input that I had to use had:
- 447 different towels
- 400 goals, each averaging around 50 characters
With this large of an input, the number of recursive calls grows exponentially. This happens because the function repeatedly solves the same subproblems (e.g., starting at the same index in the target) in different branches of the recursion.
The solution is surprisingly simple: by adding three lines of code and a memo
dictionary input to the dfs
function, we enable memoization. This allows the reuse of previously computed results, drastically reducing recursive calls and making the code run almost instantly.
Full dfs function with memoization
Now we just call dfs on all goals present in the input:
If you're curious, the answer to my specific (very large) input was 691316989225259 (computed instantly).
I loved this problem for its elegant solution (a recurring theme for me). Memoization transformed the DFS from overwhelming my computer to running instantly. It was fascinating. You can read the full problem statement here.
Day 23
For day 23, the input looked something like this:
Each line of text represents a non-directional connection in a graph. The task is to find the largest set of nodes that are all connected to each other. In other words, the task is to find the largest clique (new term I learned). Here's the wikipedia definition:
In graph theory, a clique is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent.
This is a visualization of the graph from the example shown above:
If you look closely, you can see that the nodes co
, de
, ka
, ta
form a clique: they are all connected pair by pair. There are more cliques in this graph, but this group of four is actually the largest one and is, therefore, the answer to the problem at hand.
Now for this small of an example, it's reasonable enough to solve the problem just by looking at the graph. But what if the input is much larger? For comparison, the input that I received had 3380 different edges. Here's an attempt at visualizing the resulting graph:
Clearly, we need a better approach. For that, I found the Bron-Kerbosch Algorithm: an algorithm precisely to find maximal cliques in graphs.
A maximal clique is a set of nodes where adding any other node from the graph would break the clique property. The largest clique in our graph has to be a maximal clique.
The Bron-Kerbosch Algorithm uses three sets to look for maximal cliques:
- : the set of nodes of a maximal clique.
- : the set of possible nodes in a maximal clique.
- : the set of nodes that are excluded.
We start by initializing the algorithm with and empty, and with all the nodes in the graph. Our base case is if . In this scenario, is a maximal clique.
Then, for every node in , we recursively call the bron_kerbosch
function with new sets: becomes , becomes and we also add to our potential clique : .
After the recursive call but still within the for loop, we update our sets again: becomes - and we add to our set of processed nodes : . And that's it: about 10 lines of code for the whole function.
Here's the whole code with an optimization to make it run a bit faster (called the Bron-Kerbosch with pivot), where instead of iterating over all nodes in we instead iterate over where is the node with the most neighbors in .
Bron-Kerbosch with pivot function
For the curious, the algorithm takes 0.3836s without pivot and 0.0159s with pivot (on the large graph).
It's always really nice when you find these concise algorithms that solve exactly the problem you're facing: that's why I thoroughly enjoyed day 23's problem. You can read the full problem statement here. Also, here's the video that I used to properly understand the algorithm step by step.
Honorable Mentions
Day 11
Part 1 of Day 11 was easily solved by brute force as it only involved doing a bunch of calculations on a loop with 25 iterations. For part 2, the rules didn't change as they usually did every other day. Instead, we simply had to do a bigger loop: 75 iterations.
My part 1 solution used a list and my computer really struggled to run the code (which I never even let it end). The solution was clear: by switching from a list to a dictionary, the code ran instantly without significantly increasing complexity.
Day 11 Part 2 solution
By recognizing a pattern, all of the computational overhead of the problem disappears. Isn't that neat?
Day 14
I wanted to mention Day 14 because it was such a curveball compared to all other problems.
In these kind of programming "puzzles", from both Advent of Code or Leetcode, I've learnt to expect writting code that outputs the response, and then maybe optimize it if I want to have it run faster.
But there are some areas, and some times, in which that isn't necessarily the case: sometimes we need to do more investigative work: Data Science is a good example of this: we just need to find any insight in the middle of all that we have access to. Day 14 part 2 was just like that: we were given a 2d grid in which "robots" moved at constant speeds and wrapped around the grid, and were told to find when they arrange themselves into a picture of a Christmas tree.
I spent a lot of time trying to come up with an algorithm, but nothing clicked. Eventually, I started reviewing individual frames of the grid manually. When I got tired of that, I decided to use a metric from part 1 of the problem: the safety factor, which is calculated by multiplying the number of robots in each of the four quadrants, ignoring the central rows and columns. Take this example from a smaller grid:
Here, the safety factor is . By calculating this for the first 10,000 frames and sorting them, I found the first frame with the lowest safety factor. Here's what I saw:
Spoiler
Found it! Since the safety factor calculation ignores robots in the central columns and rows, the frame with the minimum value for the safety factor should have a bunch more robots in the center. If the picture is centered, maybe the minimum safety factor happens when the robots arrange themselves into a Christmas tree! It almost feels like some sort of measure of entropy.
After staring at random dots scattered across a 2D grid, seeing this result was incredibly satisfying, especially since it came from a hunch I didn't have much faith in. I thoroughly enjoyed the concept behind this exercise. Here's a video I saw of someone being a much better detective than me.
Parsing Strings
Every day, the input of the problem was a very large string. It quickly became a habit to write a parse_input
function at the start of each problem. As surprising as it sounds, it actually became one of my favorite parts of solving each problem. Here's some examples:
For day 3, the input looked something like this:
Here's how I parsed it (using Python's regular expressions library):
From the input above, the result of the parsing becomes [[2,4], [8,5]]
. The rest of the exercise is basically solved.
For day 16 and day 20, the input looked something like this:
Day 16 and 20 input
And here's how I parsed it:
This year, there were a lot of 2D grids in Advent Of Code. I ended up with a bunch of parsings of different inputs that look like this.
For day 18, the input looks like:
Day 18 example input
Which can be parsed in one line:
And become something like this:
Final Remarks
Of course, there were also some exercises that truly stumped me. Without checking out Advent of Code's reddit, I doubt I would have managed to finish all exercises before the end of the year. Parts 2 from both day 16 and day 24 were the ones that eluded me the most.
I also want to mention that solving the problems each day was made considerably easier simply because my friend Afonso was doing them alongside me. He finished all exercises before me, and I couldn't not complete the 25 days with him having finished them all too.
Finally, here's the Github repository with my solutions. I structured the folders like 2024 > Day 2 > solution.py
because I'm sure I'll come back for next year, and who knows, also come back for the problems of previous years. I think next time I give Advent of Code a shot, I'll try to do it in Rust.
I highly recommend trying out Advent of Code!