Advent of Code 2019
Space, rockets, asteroids, custom computers, retro games and bugs!
Advent of Code is a fantastic community event happening each December (starting in 2015). Each day until the 25th a new puzzle unlocks - they get harder as the month goes on. They always have 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.
In this article, I'll praise the year 2019, which was recommended to me as one of the best years. My original plan was to develop the tool set for this event to make everything smoother. Needless to say, I got completely caught up in the process (although I did achieve the original goal).
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 (in Space!)
Santa has gone missing and the elves are desperate. They need your help! Collect all stars (solve all puzzles) and save Christmas!
This time it seems that Santa got lost somewhere in the solar system. So the elves shoved you into a rocket and off you go.
Ever Evolving Intcode Computer
The key concept of this year is the so-called Intcode computer, that blew up on day 2. So you'd need to create your own. You'd need it to run Intcode programs, which is assembly-like set of 10 instructions that are Turing complete.
Over the course of the month you are implementing many upgrades and mechanisms. Prepare for turtle drawing, navigation, and even some basic networking (day 23). Then you are running some classic games such as:
"Breakout" (day 13),
"Super Mario" (day 21)- you have an avatar and are jumping over holes,
In these puzzles, you have the Intcode program prepared. To me, it's amazing how much effort went into these as I know that puzzles are randomly generated per user. It's a huge achievement that they've been able to pull automatic puzzle creation with their own assembly language. I realize that all you (probably) need to do is to change a couple of int values, but still. Amazing.
They are a pain to debug though. Nobody will provide you a dumbed-down testing program. You can try reverse-engineering them, but it's hard.1
These puzzles also had an amazing learning curve. Should you just dump this all on a person for a single sitting, I doubt they'd be able to solve it. But the course of the month eased me into it and I was actually looking forward to Intcode puzzles as time went by. It also put some emphasis on maintainability and refactoring. Those two factors are sorely missing from most programming competitions (IMO).
Probably the single biggest refactor was on day 7 as I needed a way to connect several computers that would send their outputs to other machines’ inputs all while processing their own instructions. I figured, that now was the time to make the code completely asynchronous. And while this investment paid off, I was sweating.
I was just blown away. I was giggling while programming. What kind of sorcery is this?
Plutonian Civilization
Another highlight for me was the two late puzzles related to the "long lost Plutonian civilization". They specialize in infinite recursive folding space.
Once you realize this and do some connections and translations, day 20 is not that bad. The recursive game of life was also a treat (day 24).
I just loved the tiny bit of lore and mystery. How they were able to survive and thrive in such bad conditions? Where did they get such advanced technology? Were those bugs their downfall? Were those bugs the civilization we talked about? We don't have the time nor the resources to figure it out, we must press on.
Graphs and searches
It wouldn't be a coding puzzle event without graph algorithms and optimal path searches.
I liked day 14, I’ve selected good algorithm for the job2. I very much disliked day 18, which was the hardest puzzle this year for me3 . That being said, moving from indefinite solution time to about 2 minutes (I know, I know) is very satisfying. Honorable mention for a hard day goes to day 22, but due to my background in algebra, I was quite well equipped for it.
I found the day 17 quite bizarre. In part two you have to figure out how to partition a path into such subsets that you can cover them using only three patterns4.
I was surprised by how uniquely frustrating day 15 was. You get an Intcode program. It’s a robot you can control that can walk around in a standard maze (grid, empty spaces, obstacle spaces). So far so good - however, you can’t see the map therefore you are walking around with the robot and smacking straight into walls like a Roomba. Then you have to figure out the shortest path to the object from the start. I don’t know, something about smacking the head into the wall so many times didn’t sit right with me - I was thinking so long, but didn’t figure out a better solution. Smacking the head it was.
To end this section on a positive note, I am quite proud of my solution to day 19, part 2 as I figured out how to traverse the image efficiently.
A Space Odyssey
If you haven't tried to do Advent of Code, I'd recommend it. The year 2019 is the coolest set of programming puzzles I've ever seen - I know I am repeating myself here. Checkout my solutions at Github. Checkout also the tooling article.
And now, for the big spoilers:
I was successfully able to reverse the Breakout game and then modify the source code so that my line stretched all the way and thus the ball couldn't fall out.
It could be solved by a topological sort which drastically simplifies the reasoning about the problem.
Requiring dynamic programming (which I knew couple years ago, forgot, and wasn't able to relearn properly ever since).
I've no idea how to approach this in a general case -> this was easier to do on paper for me.