Coding together, learning, and tackling challenges

We organized a workshop on one of the puzzles from last year's Advent of Code on Friday, January 31st. 

The 10th edition of Advent of Code took place in December 2024. As in previous years, I tried to encourage my colleagues to participate.

What is Advent of Code?

Advent of Code is an annual advent calendar for programmers. From December 1st to December 25th, 2024, the 10th edition took place, with over 273,000 people participating.

The concept is simple: every day, a new problem is presented, embedded in a continuous storyline. The difficulty level gradually increases, challenging your knowledge of algorithms, best practices, and programming languages more and more each day.

The goal? A fun challenge that is different from your daily work, while also allowing you to learn something new.

How we participate at th[is]

The website features a leaderboard, but it is dominated by participants who make it a sport to solve the puzzles as quickly as possible. Some people are ready at 6:00 AM every morning to write solutions at high speed.

That’s not how most participants approach it. And neither do we.

At th[is], we did it our own way:

• Our Slack channel automatically posted a message when a colleague earned a star.
• Everyone shared links to their Git repository.
• At the coffee machine and during lunch, we discussed the story and how we tackled the problems.

One of the great things about Advent of Code is that you can set your own pace. Is Day 6 too difficult, or do you just not have time? Then there's another puzzle waiting for you tomorrow. Didn't have time last week and now have a moment to catch up? You can always go back. You can complete challenges from all ten editions at any time.

The workshop

Many colleagues found Advent of Code interesting, but they didn’t have time in December. So, we decided to organize a workshop.

The idea: work together on one of the challenges, see if we could successfully solve it, and compare our solutions. What challenges did we encounter? How did we solve them? How did our solutions differ?

The Challenge: Day 11

With six colleagues, we split into small groups and tackled the puzzle from Day 11.

The Task

"A row of stones with engraved numbers changes every time you blink, following a fixed set of rules. The value may change, or the stones may split in two. How many stones remain after 25 blinks?"

We worked in three different teams: The Go team, the TypeScript team, and a PHP developer.

Soon, we encountered a problem: out-of-memory issues. The row of stones multiplied so quickly that the available memory filled up.

One of the interesting aspects of Advent of Code puzzles is that when you run into these problems, simply adding more memory won’t help. The puzzles are designed so that the wrong approach requires an impossible amount of memory or computing power.

The TypeScript team was the first to complete the challenge and immediately started working on part 2 of the puzzle. This part introduced a new twist: instead of 25 blinks, you now had to blink 75 times. This didn’t just make the problem larger, but significantly more difficult to solve without smart optimizations.

The Go team also faced performance issues in part 2. The computation took too long and didn't seem to be getting faster anytime soon. In preparation, I had already run some tests in Emacs-Lisp, and I couldn’t get my code to run faster than 0.001 seconds for 75 blinks. Anything that took longer than a few seconds was essentially too slow.

After a short break, a colleague from the Go team decided to try solving the problem in PHP. Within a few minutes, he had found a completely different approach and solved part 2.

The Solutions

The Naïve Approach

The naïve approach directly follows the problem statement: Each stone changes simultaneously with every blink. This means you eventually need to keep 250,000,000,000,000 numbers in memory. If we assume 4 bytes per number, that amounts to 1000 terabytes of data. 

Recursive Approach

The recursive method processes one stone at a time, calculating how many stones appear after each blink. If we haven’t blinked 75 times yet, we apply the same method to every stone in the result. Then, we add up all the values. Since a specific number at a certain depth might appear multiple times, we optimized the approach using caching.

We stored the number of stones after blinking (value) at a given stone and depth (key). This allowed us to skip redundant calculations if we encountered the same combination again. Without caching, this method would take hours. With caching, it was completed in under a second in most cases.

Sparse Map Method

With the sparse map method, we tracked how often a particular stone appeared, rather than processing each stone individually.

If a stone appeared 1000 times, we didn’t calculate its effect 1000 times. Instead, we computed the transformation once and multiplied the result by 1000.

This had two major benefits: We only needed to store around 4000 stones in memory instead of millions. This reduced memory usage to just 16 KB, making the problem manageable. Since the sparse map method was already optimized by grouping calculations, additional caching wasn’t necessary.

Conclusion

Discussing each other’s solutions was not just interesting, but also insightful. It was fascinating to see how different programming languages and problem-solving approaches led to faster and more efficient algorithms.

For us, Advent of Code is more than just a puzzle. It’s a way to learn new techniques, think creatively, and collaborate with colleagues to find the best solutions. At th[is], we thrive on challenges, innovation, and continuous learning. The next edition? We’ll be there!

Jeroen

Backend Developer