Advent of Code 2024 - Write Up

2024 was my first year doing Advent of Code.

I’ve known about it for a long time but I don’t usually enjoy doing leetcode problems so I’ve never given it a fair shot. In this post I’m just going to ramble about it for a bit, showing some stuff I did and sharing some thoughts.

All my solutions for this year are written in Go. You’ll find some links sprinkled throught the post, but you can find all my solutions here. I managed to get 39 stars.

What is Advent of Code?

Advent of Code is a yearly challenge that runs from 1st Dec to 25th Dec. Every day a single challenge is released and there are leaderboards depending on how fast you managed to complete it. The global leaderboard is very though and practically unachivable for must of us, but you can create private leaderboards to have a more relax competition with friends or teammates.

The challanges follow a chrismas narrative. While it does make some exercise quite verbose at times, I eventually started to appreciate the extra effort to make them feel different than leetcode.

Challenge Structure

All challenges are structured in a mostly consistent manner. A short story introduces the problem, the exact rules are given and then a small example input is provided with its respective solution.

Then there’s a link to a text file containing the actual input for the problem, and a text box where you write the solution once you get it.

After submitting a correct answer, a second part of the challenge is unlocked. The second part often modifies or adds to the rules given for the first part. It then follows the previously provided example input and gives the new solution. You use the same input given for part 1 and again submit the answer in the text box at the bottom of the page.

That’s it. There’s no web-embeded IDE, remote runtime environments or any such thing. You download the input, write your solution locally, run it locally and submit the output.

2024 - Some interesting challenges

Bruteforcing and recursion

The challenges usually get gradually harder, with some dips and peaks along the way. This means that to start off, and sometimes through the middle, it’s possible to use bruteforcing techniques to solve challenges. I decided this was fair thing to do for me.

It being the first year I do AoC I’m not going to bother optimizing all the solutions, I just want to have fun and practice things I find useful. Finding the fastest way to calculate permutations without reallocating arrays it’s not that interesting to me when bruteforcing it takes less than 2 seconds in my programming language of choice.

Even so, recursion isn’t always so straight forward. You need to clearly define base cases, something that needs practice, and with some inputs you’ll need memoization to avoid running your solution for 30 minutes, and you can even paralellize some problems if you’ve got spare cores.

Now let’s look at some challenges that gave me the oportunity to dive into some more interesting topics to me.

Advanced Text Parsing

Some of the challenges were fun because they required, or lend themselves to, interesting parsing techniques.

For example, Day 3 proposes an interesting subset of a programming language with few operations. It start’s with just mul(a,b) and adds some more in the second part. The issue is that the input is corrupted so it looks like this:

xmul(2,4)%&mul[3,7]!@^do_not_mul(5,5)+mul(32,64]then(mul(11,8)mul(8,5))

There are multiple ways to solve this; you could use regex to match the required pattern, read the input and manually check at different offsets that certain substrings are there, or you could write a lexer/tokenizer with a very simple parser. This comes from having recently read “Writing An Interpreter In Go”. I got to apply some of that knowledge at my work, so I figured I’d do it again since the problem space is quite similar.

Really there weren’t many parsing challenges but that one stuck out. I’ve heard that AoC 2019 is all about this kind of problems so I’ll probably check that out.

Pathfinding

There were many grid based exercise this year. Just as a quick check, there are a total of 11 exercises where I used [][]byte. Some are more fun than others, some are easier than others, but a couple of them gave me the opportunity to write the A* algorithm for the first time.

I’ve made a couple of small games so I was already quite familiar with the concept of A* but I’ve never wrote it myself, so I took the oportunity at Day 16 when I saw the first pathfinding challenge. Rather quickly I found this incredible resource from Red Blob Games that explains the concepts from the ground up.

Just with this challenge I wrote a heap-based priority queue and A* pathfinding over the input grid. Later I moved the implementation into its own package to reuse it in other challenges.

Virtual Machines

In Day 17 you are given instructions to create a very small Virtual Machine with 3 registers and 8 instructions. Then you are given an input with the starting values of the 3 registers, and a set of instructions to execute. You must submit the output of the virtual machine after executing the given input.

Part 1 of the exercise is fun byt also quite easy, as the eight instructions are really simple to implement. Part 2 makes a big jump in complexity, requiring you to find a quine, i.e. a value that when set as the starting point of the A register, produces the same set of instructions that were given as the input.

Part 2, for me, required a lot of experimentation to reverse-engineer the virtual machine and the given program. Multiple times I got stuck, continued with other exercise and came back. It’s a fun challenge and I encourage you to look at it.

Another similar challenge was Day 24.

Final Thoughts

It was nice to refresh some concepts and learn some new ones. I’ll be looking forward to next year’s Advent of Code, and I may go through some old ones for fun and practice.