Advent of Code 2021

I’m working on this year’s Advent of Code programming puzzles, something that’s new to me.

I saw Tipa and a handful of others talking on Twitter about Advent of Code at the start of December. I hadn’t heard of it before, but it’s apparently been a yearly thing for a while now. I thought it was silly at first, but I got tired of seeing everyone else talk about it without me.

Throughout December, every day at midnight (my time, unfortunately), a new programming puzzle is revealed, and you get a gold star for submitting the correct answer. Each puzzle has two parts, so you actually get two gold stars for getting both parts correct.

I’m a programmer by trade (well, a software engineer), so you’d think programming puzzles would be right up my alley. Unfortunately I don’t particularly enjoy programming “for fun.” I usually need a practical or pragmatic reason to write code. Especially code that doesn’t have any particular use in daily life. Like programming puzzles.

But in this case, I can use it as an excuse to learn some Kotlin fundamentals. These sorts of programming puzzles are good exercise for brushing up on basic language skills.

I’ve been told that Kotlin is the wave of the future, or something like that, so I’m checking it out. It’s an object-oriented language that compiles down to Java JVM, Javascript, or (allegedly) native code. It’s the primary language used for Android development, supposedly, if you’re into that sort of thing. The point is it can run in a lot of places, and it’s a new thing if you don’t like the old thing. Personally I’m curious what it can do to abstract Javascript out of my life forever.

Anyway, the Advent of Code puzzles are typical of what you might see on a coding interview, so they’re useful to work through in that regard, too. It’s not a bad idea for one’s software development career to periodically work through those sorts of problems.

The problem statements in Advent of Code are considerably more verbose and detailed than you usually see, and you’re only judged on getting the right answer. There aren’t any time or memory constraints, so you can usually brute force your way through them. (Except in some cases where computing the answer might literally run you out of memory.) Unfortunately for me, I’m fast asleep at midnight every day, so I’ll never be able to rank very high, and I’ll never be one of the cool kids.

Anyway, I didn’t start solving the problems until Day 6, but I went back and solved all the ones back to the beginning to get all the stars. It’s important to get all the stars if you want to be taken seriously in this biz. I think.

I initially wrote the first seven solutions with Golang, which is what I use at work, but I decided to switch to Kotlin on the eighth day.

My solutions are on GitHub. [Update: I deleted that repo to make a better one.] There is room for improvement on many of them, but since these are one-and-done programs, and unlikely to form the basis of any real world software solutions, there’s not much reason to clean them up until the next time I’m looking for a job.

Puzzle Commentary

Day 1. Sonar Sweep. I solved this with both Golang and Kotlin. Technically this was the first code I ever wrote with Kotlin. The only trick on this one is handling boundaries.

Day 2. Dive! Straightforward. Just parsing input and adding numbers according to the given rules.

Day 3. Binary Diagnostic. I had to do this one twice because I accidentally deleted the first one. The first part was fairly straightforward, but the second part ended up fairly ugly on the first pass.

Day 4. Giant Squid. Bingo-playing squids. I ended up with a lot of supporting functions, but the main loop was pretty small.

Day 5. Hydrothermal Venture. Plotting simple lines on a grid. I used an interface and three types of lines. It turned out to be overkill and could have been simplified. This is one where the second part of the problem renders the first part of your solution somewhat obsolete.

Day 6. Lanternfish. This was the first one I attempted on the day, having become sufficiently jealous about everyone else bragging about earning gold stars without me. Unfortunately the second part showed me that brute force doesn’t always work in Advent of Code, as I ran out of memory modeling each individual fish like it was a video game. Later I went back and redid it from scratch in Kotlin using the 9 rotating states like I was supposed to, which I have to admit I saw online before I knew how to do it myself.

Day 7. The Treachery of Whales. I went with brute force again, rather than try anything fancy. Time is money! Basically just turned the problem explanation into code and out came the answer. This was the first day that I got both stars on the day, rather than backfilling the previous days.

Day 8. Seven Segment Search. This one was a bit of a chore, since it was the first one I tried with Kotlin. (All the previous ones I had solved with Golang.) In the end, I just used the easy-to-find “1” and “4” patterns to deduce the ambiguous digits.

Day 9. Smoke Basin. I recognized this as a flood fill algorithm right away. Fun fact: I first wrote a flood fill algorithm for Amiga image processing software somewhere around 1992.

Day 10. Syntax Scoring. This one was fairly easy for me because I had already done a very similar problem on Leetcode earlier this year and just repurposed it. I used an array and an index as a stack.

Day 11. Dumbo Octopus. I made a class to model the grid for this one. Another recursive traversal. Just for fun I used a one-dimensional array instead of a two-dimensional array, imagining that it was the 80s and every multiplication mattered. (It was a waste of time.)

Day 12. Passage Pathing. I hated this one with a burning passion. I don’t like graphs or pathing problems, and it took me a long time to work out the recursion. I initially went down the wrong road and tried to do it without maintaining a list of paths, which, well, didn’t work.

Day 13. Transparent Origami. Fairly straightforward. The only trick here is not to try to make a pixel grid, but rather just keep a list of points. (I mean, you probably could make a pixel grid, and it might work for this puzzle since it would only be 1000x1000 or so, but it would waste a lot of time and memory and it’s easier without it.)

Day 14. Extended Polymerization. Another annoying one where brute force on part 1 runs out of memory on part 2. The clue is in the offhand “polymer grows quickly” remark. I knew my first solution wasn’t going to work for part 2 but you’re scored on how fast you get an answer, not how elegant or efficient the code is. So I got the star for part 1 fairly quickly, then I had to rewrite it from scratch for part 2. I didn’t think a map of letter pairs would work so I went off on several false starts, but it turned out it worked fine in the end. Just for fun I re-wrote the solution in Golang, and it looked cleaner than Kotlin.

Day 15. Chiton. More disgusting pathing problems. I don’t know why these puzzle makers think “shortest path” solutions are general knowledge. Anyway I hated this one. Took basically all day. I knew right away that I didn’t know “the trick” to solving it, and my brute force floundering probably wouldn’t work within 24 hours. (Eventually I got a hint from a programmer friend, threw away the Kotlin code (which technically worked but didn’t scale), learned what a Dijkstra Algorithm was, and wrote one in Golang from the Wikipedia article. Even so, the second part still took a long time to compute, I had to run it on my gaming PC.) PS: It seemed rather unfair to require a very specific algorithm to solve this one.

Day 16. Packet Decoder. I braced myself for another monster, but this one was a fairly straightforward decoding of a binary stream, like the good old days. I made a serial binary reader class to simplify the parsing, the rest was typing out the complicated rules in code and debugging the problems as they occurred. And remembering yet again that Kotlin ints are 32-bit, not 64-bit. I went back and rewrote it in Golang, too.

Day 17. Trick Shot. I just fumbled around with a half-finished Trajectory class until I got the right answer. Didn’t even try to read the input from a file, I just hard-coded it and picked an arbitrary set of velocities to try. Luckily it was fairly easy to limit the number of possible [horizontal] trajectories so it didn’t scale way out of control like previous puzzles.

Day 18. Snailfish. It was a lazy, rainy Saturday and I was interrupted quite a bit during this one, so it took most of the day to complete it. Possibly the longest Kotlin code I’ve written to date. I recognized it as a binary tree problem right away, but I struggled to dredge up how they work out of my memory because nobody in real life actually works with binary trees. Eventually I looked up the “in-order binary tree traversal” algorithm I needed after going in circles with it for a while. In the end, I built a Number class that did all the work, and probably over-engineered it. Brute force for part 2.

Day 19. Beacon Scanner. (0/2) I got up early to work on this one. And was reminded immediately why I don’t don’t do math in programming. Let alone 3D math. I couldn’t even solve the first part of this one, even after looking up a number of clues, and wasted my entire Sunday being angry at myself. (The clues I received were: 1. How to manually make a list of the 24 possible rotations instead of trying to programmatically compute them. 2. Limit the possible point translations to a list of the differences between points instead of brute-forcing it.) On the second day, I threw away my Kotlin code and rewrote it from scratch in Golang. The main problem I’m running into over and over again is establishing a common frame of reference for beacons from different scanners, to determine which are duplicates.

Day 20. Trench Map. Yay, I don’t feel stupid anymore. A straightforward image processing convolution matrix, with a minor twist: Handling the infinite edges with enhancement[0] and enhancement[511]. I had plenty of time to go back and work on the Beacon Scanner again. Thank god there’s only four five more days of this nonsense.

Day 21. Dirac Dice. (1/2) Look, I’m a software engineer, not a mathematician. I have no idea how to solve part 2. None whatsoever. I wrote probably 10 different algorithms throughout the day, trying various ideas with recursion and optimization to get it to run on my weak little laptop. No luck.

Day 22. Reactor Reboot. Part 2 is another 3D math puzzle that boils down to: How well do you know the math and edge cases of intersecting cubes? And/or do you know a library to do it for you? I, it turns out, don’t know either, and can’t solve the problem. I’m 100% sure my algorithm will work at scale, I only need a working cube subdivision function, where the bulk of the work lies. Three days left and I’m now short by a total of four stars. Update: I got it! Rewrote my cube intersection function from scratch, accounted for all the bazillion edge cases, and it finally worked. Only short three stars.

Day 23. Amphipod. (1/2) Seriously? More graphs and pathing? Can we go back to decoding bitstreams? Anyway, after half a day of fussing with paths, I ended up doing the first part by hand. Part 2 is going to require programming, though, so I’m not getting that second star. Maybe there are game programmers out there jumping for joy at this Advent of Path Problems but I, for one, am back to being short four stars. Update: I did actually solve part 2 manually while watching Matrix Resurrection, but after three tries it wasn’t good enough to get the star. I’m sure I could find the right solution eventually, but it’s a pain to do in a text editor.

Day 24. Arithmetic Logic Unit. (0/2) Finally! Code that’s up my alley! An assembly language interpreter! I coded up the ALU in barely any time, it worked on the first try, and … then I read the fateful words “find the largest” and that’s when it turned into a reverse-engineering math problem. Ugh. Screw that. I gave up. I thought for sure I had the right last 10 digits and only had to brute force the first 4, but it didn’t work. I could have optimized my interpreter to get better at brute forcing the whole serial number, but it was obvious that’s not what they wanted us to do. Computer scientists and their b.s. math problems. Screw ’em.

Day 25. Sea Cucumber. (1/2) I have to assume they put an easy one (for me, at least) at the end on purpose because it’s Christmas Day. But unfortunately I can’t get the second star until I get the six missing stars from previous days. Christmas is ruined and Santa is going to a die a slow horrible death at the bottom of the ocean because he can’t get his sleigh keys. You’re welcome.

So in the end, my favorite puzzles were Day 3 (Binary Diagnostic), Day 8 (Seven Segment Search), Day 13 (Transparent Origami), and Day 16 (Packet Decoder). My least favorites were all the ones that involved math and formulae and specific computer science 101 algorithms, which was most of the second half. I’m definitely not a computer scientist, I’m a software engineer. I use libraries when I need an algorithm, I don’t waste my time writing them unless I have to.

But it was worth the effort because it was a good crash course in learning Kotlin basics.