This year, I participated in the Advent of Code. If you’ve never competed before, this is an advent calendar where you solve a puzzle each day in order to SAVE CHRISTMAS. Over the course of 25 days in December, you’ll tackle progressively harder challenges that encompass anything from logic puzzles, graphics processing, pathfinding algorithms, and many more classic computer science disciplines.
Each challenge comes in two parts, and each part awards a star. You’ll need 50 stars to complete the entire Advent of Code for a given year. The first part of each challenge is typically easier – it might have a smaller input or scope that lets you start digging into the guts of the puzzle – and the second half typically sees you solving it in a different way that might involve stricter performance requirements or additional constraints.
You are free to use any programming language you like (even none at all, although good luck with that!). You’ll be writing code that generates a very simple solution, typically a large number that’s obtained by multiplying or adding multiple results from each challenge together.
There’s also leaderboards you can use to compare yourself to others. The global leaderboard is quite competitive and most people don’t have a shot at scoring at all unless you have competitive programming experience (only the first 100 solutions to each part of each problem will earn a score on the global leaderboard). More interestingly, there are private leaderboards you can use to compare your code against your friends or coworkers.
Participating with Ruby
This year, I participated in the competition using Ruby as it’s the language I use on a day-to-day basis and what I’m most comfortable working in. Ruby isn’t known for its performance, but it does boast a fairly useful standard library and ease of readability and consumption. I didn’t end up using gems in most cases (the one exception is a priority queue that I could have implemented myself but was much easier to require a gem).
In terms of other good languages I can really see Python shining here with its extensive package list, specifically those geared towards scientific computing as there are problems that need vector math or matrix manipulation.
Highlights
- I finished all parts of all 25 problems this year.
- This was accomplished with varying degrees of assistance.
- The early problems were fairly trivial, so I was able to solve them with no outside assistance.
- Other problems required a little help, so I would gradually look towards hints on sites like Reddit as time passed.
- I posted a low score in the mid 2200’s on the global leaderboard.
- I didn’t score any points, as only the top 100 solutions score.
- I was able to use some math skills I haven’t exercised in a very long time.
- It’s always great ot learn a new skill or brush up on some old ones.
- I participated in a private leaderboard with several coworkers.
- This was great! We had engineers and non-engineers compete, and held a check-in weekly to talk about our favorite challenges.
- I met new people and made new friends through code!
Favorite Challenge
My favorite challenge this year was Day 19.
This challenge had you rotating points by 90 degree increments in 3D space, determining overlaps, and merging those points into a reference point cloud.
Although it took me nearly 5 days and who knows how many hours to solve, I’m not sure I’ve ever been quite as elated to have an algorithm to work in my entire life.
My algorithm was fairly naive – simply calculate the rotated points (there’s only 24 permutations), and then compare the distances to known references. If more than 12 overlap (a constraint given the challenge prompt), then you know that it’s a true overlap. Simply merge the rotated points into the reference cloud, the unique set of which is the solution to part 1, and the distance that matched is now the absolute origin of the rotated point cloud, which is conveniently used to calculate the solution to part 2.
Essentially, this is simply a compound transformation (rotation + translation) where a successful match isn’t a complete match of all points. An example of each is shown below. The examples are in 2D but the math is the same in the 3rd dimension as well:
(Image credit: https://www.mathwarehouse.com/)
Here’s a great visualization of the point clouds from someone else’s solution:
Advent of Code Day 19 Visualization
My Not-So-Favorite Challenge
I didn’t particularly enjoy Day 24.
This challenge asked you to essentially decompile custom assembly instructions for a fictional CPU called the ALU that is tasked with validating a 14 digit serial number. This required no code, and in fact depending on your strengths as a programmer it might even be faster to do it by hand (which I did). To make matters worse, the instruction set contained 14 blocks of code (1 for each digit), but each block only had 3 relevant lines of code.
On top of this, my particular instruction set was pretty adversarial. The ALU’s z register functions as a stack, and each block is a push or a pop instruction to this stack (in base 26, but that’s not relevant for this discussion). My instruction set was 7 consecutive push operations before I made it to the first pop, meaning a LOT of decompilation by hand just to discover that I really only needed 3 lines of each block to solve the task.
Others I’ve talked to received a bit nicer prompt, with anywhere from 3 to 5 pushes before their first pop operation. They, of course, solved the challenge faster than me.
All in all, it was a lot of fun this year. I’m certainly ready to rest my brain for a while, but I look forward to next year and the challenges it will bring.
If you’re interested, you can check out my repo with all the 2021 solutions here. Since I solved Day 23 by hand as well, that solution will be omitted.
That’s all for now. Thanks for reading!