Advent of Code 2023
Coding there and back again.
In 2022, I've tried Advent of code (a fantastic community event happening each December) for the first time. Each day until the 25th a new puzzle unlocks - they get harder as the month goes. They have always two parts, you can access the second part after solving the first. It's language agnostic, hell, sometimes it's quicker to solve it on paper by hand.
I was excited to tackle the year 2023, with a simple goal - complete all of the puzzles and prepare a set of common tools so the subsequent years are more pleasant.
Hopefully you’ll be motivated to try it out for yourself - highly recommended if you enjoy coding puzzles. Perhaps you’d relive and older fond memory. Also, minor spoilers ahead and major spoilers in the footnotes.
The story (on Floating Islands!)
Santa has gone missing and the elves are desperate. They need your help! Collect all stars (solve all puzzles) and save Christmas!
Apparently, there are floating islands in the sky that are actually a set of factories producing snow. So the elves shoved you into a trebuchet and off you go.
Usually, the progression in the story is linear. One can argue this is the case here too. This time we are not only ascending through the islands, but as we debug the broken production process we are returning to previous stations to achieve the goal. I really liked that, I think it represents the debugging aspect quite well.
Is This Hard, or Is It a Skill Issue?
The first big curveball this year was already on day 5. The naive solution is kinda simple, just walk through the numbers to simulate the situation. However, part 2 introduced some really big intervals - it was infeasible to simulate the steps in time1.
The public agrees with me - it's the day with the most "silver" stars, meaning that people were solving part 1 but not part 2.
Getting To The Fun Parts
I liked the day 7 which was a "poker hand" identification task. Part 2 introduced wildcards - a fun additional challenge.
My cleanest solution of the year is on day 9 - once you figure out that you are doing some iterative differences it falls apart quickly.
Another fantastic day was day 10 - instead of a "normal maze" (square grid, each point is either an obstacle, space, or point of interest), you've got to work with a pipe maze - a list of symbols that are able to connect together based on their shapes. This is a square loop of pipe:
.....
.F-7.
.|.|.
.L-J.
.....In this view, | is a vertical pipe, - is horizontal, L is a bend, etc. There are many ways of moving forward here2.
While we are on the topics of obstacles and spaces, day 13 has you searching for reflections. I liked it.
A hard but fun puzzle was day 20 - you are doing a simulation of something like an electrical circuit. OK, you tackle it, prepare the simulation and it's simulating. Yay, onto the part 2. And of course, part 2 won't ever halt using this approach3.
Fighting The Hard parts
Day 21 is a weird one for me. Part 1 is not too bad, you send a "flood wave" and watch for the contour lines. In part 2, that's not really an option due to the size of the input 4.
Day 12 was a fight. In the end, it was an "enumerate all cases" type of scenario, but you needed to be smart about it (duh).
Another tough day was day 19. Part 1 was okay, another one of the "just simulate it". So I expected some huge numbers in part 2 and I wasn't disappointed. While I was happy to have the library for intervals from day 5, there still was a lot of work to be done.
Endurance
I was doing these on the day they were published (more or less). At the end of the month, I was exhausted. I can't imagine the fortitude of the leaderboard contestants who can crank these within an hour of publishing.
We raced within our company (I was 2nd in the end). It was a close one - the winner was more consistent in the mornings and it was enough to take the cake. GGs and kudos!
Of course, I would prefer winning, but that was a side mission (as I knew I wouldn't have the time when the puzzles were published). I wanted to finish (check) and I wanted to have the clunky parts ready for next years (check).
So, as we were approaching the final days, the gloves just went off and I tried everything to just solve the issue. That was when I decided that I wouldn't roll my own graph library, because I hate graph algorithms with passion. Oh, your solution is nice and you came with it yourself, but it's O(n^4) so it'll never finish. You should have realized you are dealing with a Dingledong graph so then you can utilize Flumperworths transformation to deploy the optimized Bingabong algorithm that runs in O(n^2*log(n)) and finishes under 20ms.
Anyway, day 25 was kinda like this5.
Snow Production Is Back
All and all, I enjoyed this year a lot. It's the first advent of code that I've fully completed and seeing the finished calendar was very satisfying. It also helps with the impostor syndrome as well as keeping my leet code skills somewhat functional. Check out my solutions at Github. Checkout also the year 2019 and the tooling.
And now, big spoilers:
After you squint your eyes for a while, you'll figure out that you need to be able to partition and "project" intervals (send (x,y) to (a,b)). So I put together a small interval class to do it.
One way of looking at the pipes is:
#.# ### #.#
| -> #.# - -> ... L -> #..
#.# ### ###
So I expanded the pipes to a grid-based map. Then you are able to reuse the standard map with some multipliers and off by one errors. In part 2, I've inverted the obstacles on the big map and flooded from (-1,-1).
Instead, you can take a good look at the circuit layout to realize that it has subsystems that all need to output at the same time. Then you can use the least common multiply of the circuit lengths to get your answer (which is absurdly high, thank goodness for Python handling of big numbers).
But then you realize that the way the flood propagates (in the diamond shape), you really need to consider only a handful of layouts. Then you'll tile the map and watch for edge cases and parity. I am not explaining it well. On the one hand, it's kinda smart to do it in this way, on the other hand, I prefer general solutions to problems.
In the end, I drew the graph and used my eyes to try and cut a few cables. One of them worked.