wolfgang ziegler

„make stuff and blog about it“

Advent of Code 2020

December 30, 2020

Apparently I have been living under a rock for the last five years when it comes to Advent of Code and I heard about this awesome project by @ericwastl for the first time this year. I was immediately intrigued by the idea of solving a daily programming puzzle (actually two since these consists of two parts) being part of an overarching, Christmas-related story.

The Advent of Code puzzle screen

My Experience

Initially, I found the complexity of the puzzles just right and I even started some puzzles from older Advent of Code Events because I enjoyed it that much.

However, around day 17 I realized that I had been spending more and more time on the puzzles each day. I'm honestly in awe of folks who manage to solve them that quickly since these last puzzles had cost me 3-4 hours each evening and I decided to take a break, focus on Christmas preparations and my family and finish the remaining puzzles later during my Christmas vacation.

I actually managed to do so and picked up the puzzles on the 26th of December (starting with Day 17). My goal was to finish them in 2020 and I did so in the early morning hours of the 30th.

Fifty stars!

The Puzzles

Here are a few random remarks about some puzzles I found especially hard or challenging.

Day 10 was really hard for me. I found a very cumbersome solution with exponential runtime. I head to cheat a little bit and check for an answer on the internet and found this impressive solution on YouTube. The answer was to use recursion and dynamic programming (memoization) to get the complexity down to O(n*n).

The second part of Day 13 was also too tough for me. I found a solution for the simple examples, but for the puzzle input the runtime was just too bad and my program would not finish. After researching the issue on the internet, I found solutions mentioning the Chinese Remainder Theorem which is probably the correct number theory approach. I did not bother to understand that in detail yet to be honest, since I also found this very compact and elegant C++ solution that I "borrowed" for my solution then.

Day 15 was surprisingly easy after the puzzles had quite increased in complexity over the last couple of days. My solution is probably not ideal and the second part ran for quite a while (~30 seconds) but it terminated and yielded the correct solution.

Day 17 had a confusing explanation which cost me a lot of time. In fact, I had noticed that these puzzles now took a significant amount of my time each day. So I decided to pause this activity for now and finish it up when my Christmas vacation was over. Kind of beats the purpose of a Christmas calendar, but everyone's time is precious and needs to be well spent.

I'm pretty proud of my solution for Day 23. This was the first puzzle I successfully optimized in terms of runtime performance. The initial solution (using a List<int>) was running for more than one hour AND producing an incorrect result. So debugging was a bit of a problem here. However, I quickly managed to bring the runtime down to a couple of seconds using a LinkedList<int> and an index-to-node cache (using a LinkedListNode<int>[]) for O(1) lookup. That way I could figure out my bug (I forgot to update the maximum value to 1.000.000).

To get into the right mood I was listening to Christams songs while solving the puzzles. For the most part I was listening to Indie Christmas on Spotify.

The Code

I used.NET and C# for solving the puzzles and put the code up on GitHub (https://github.com/z1c0/adventofcode2020). It's not pretty, most of the time not ideal let alone optimized since my only focus was to "just get the puzzle done".

So don't code-shame me, OK?

Next Year?

Some way down the road of the last puzzles in the early morning hours I had already sworn to myself that I would not do this again since I had made this a bit of a burden to myself but now that I finished successfully, that's quickly forgotten. I'm pretty sure that I will join this event next year again.