Notable problems from Advent of Code 2021

As this year’s Advent of Code comes to a close, I wanted to reflect on my AoC journey thus far.

These are some of the notable problems from this year.

This was by far my favourite problem. Although my solution was not the shortest, I used object-oriented principles/features like inheritance and abstract classes and was very pleased with how my abstractions turned out. I’ve heard that the 2019 Intcode problems were similar to this and I’m excited to work on them next!

(Most enlightening) Day 6: Lanternfish

This problem involved simulating a bunch of fish that would spawn new fish every 7 days. Like many others, my first instinct was to treat each Lanternfish as an individual entity (e.g. as a Python object) and iterate through an array of individual fish to spawn new fish. This worked fine for part 1 but not for part 2, which involved simulating more than 10¹² fish.

This was clearly not feasible and I was forced to try a new approach. I realised that each individual fish was not important and that I could group the fish based on the number of days until they next spawn a new fish. Hence, the only relevant piece of information was how many fish there were in each group. I was glad that I had arrived at this realisation all on my own, which made for a far more memorable learning experience compared to if someone had told me the trick directly.

This concept (stop trying to deal with things as individuals, group them and keep track of only the relevant aggregated information) seemed to be a recurring theme and it came in useful for Day 14: Extended Polymerisation (my solution) and Day 21: Dirac Dice (my solution). To this day, I remember this strategy as the “Lanternfish optimisation”.

Later, I discussed my solution with two other friends who were also doing AoC and we realised that we had each come up with a different solution to the problem. We had a blast ~~arguing about fish~~ explaining our solutions to each other and we learned a lot from the discussion.

(Most interesting) Day 8: Seven Segment Search

This problem involved spotting patterns in the given problem statement and devising an algorithm that could eliminate possibilities, finally narrowing down to the last one. This was not particularly difficult, but there were many different ways to approach the problem. Some methods were more complicated and painful to code than others, while others were simpler and more elegant. I was not particularly pleased with my first solution, so I picked a cool algorithm on Reddit and re-implemented it from scratch.

My main takeaway from this day was to identify the best/simplest algorithm on paper first, before starting to code. Perhaps if I had taken more time to look for the simplest pattern, I would have been able to come up with a simpler and more elegant solution on my own.

(Most interesting) Day 23: Amphipod

One challenge I had solving this problem was figuring out how to represent the problem in terms of code. I eventually treated it as a standard shortest path graph problem to be solved using Dijkstra’s. What was unique to this problem was the way of generating neighbours, which was highly visual and involved generating possible next states given a current state.

(Most challenging) Day 19: Beacon Scanner

I did not particularly enjoy this one, but I’m glad I ploughed through and finished it. I did learn a lot from having to wrestle with the complexity of the problem. There are still optimisations I could make to my solution, but I’m in no rush to relive this day…

(Most satisfying) Day 13: Transparent Origami

This problem involved simulating folding a piece of paper with dots on it and printing the final output. This was not computationally difficult, but it made the list because the answer was extremely satisfying, in a visual way. It felt incredible to run my program on the puzzle input and have it print out the letters very clearly in the terminal.