commentary-2022.md

Reflections on Advent of Code 2022 from a guy who kinda knows Racket

I've gotten into the habit of doing Advent of Code, the annual puzzle-a-day programming challenge. There's a competitive aspect to it, but I'm mostly interested in it as a way to challenge myself and get exposed to algorithms and concepts I haven't seen before. I'm not a programmer by trade; I learned the basics of C in college and a little bit of numerical methods in grad school, but most of what I've learned since then is self-taught as a hobby, so structured programming challenges like this are a good way for me to gauge my skill level and see how CS theory is put into practice.

The language I'm most comfortable with is Racket, a general-purpose high-level language in the Scheme family, so it's what I used this year for Advent of Code. In my experience, Racket is pretty well-suited for the kinds of problems you find in programming challenges; there hasn't been any problem yet where I've felt like trying to solve it in Racket has been a handicap. For the first few days I used Jupyter Notebook with the IRacket kernel to annotate my answers, but I eventually gave up on that because it ended up being harder to debug.

So, here's my day-by-day opinion on how this year went for me.

• Day 1. Parse a list of lists and return the top three sums. This is the kind of problem Racket feels made for -- the code is basically a direct declarative translation of the problem statement.
• Day 2. Rock-paper-scissors strategy. Lots of pattern-matching; the hardest part was probably figuring out the rules of the tournament.
• Day 3. Find common items in rucksacks. Another problem well-suited to declarative style.
• Day 4. Find overlapping and redundant ranges. I used the rebellion library here for its range data type, which takes care of most of the problem by itself. AoC is a good opportunity to explore a language's ecosystem.
• Day 5. Move stacks of boxes around. Linked lists make first-in, last-out stack problems like this pretty easy. The major difficulty here was actually parsing the input (and it was probably the hardest input to parse out of all the problems), but once that was resolved it was smooth sailing.
• Day 6. Find chunks of unique characters in a string. Another one that Racket handles without difficulty -- the entire problem statement can be represented as one for comprehension.
• Day 7. Parse terminal output and calculate directory sizes. The first speedbump of the year, and probably the first day where there's a rift between "do it right" and "just get the answer". I saw a lot of solutions that properly built the file hierarchy and walked the tree to calculate directory sizes, while I just made a hashtable of absolute paths and the sizes of everything within them.
• Day 8. Scout a forest for the treehouse site with the best visibility. A traditional AoC "search a grid of integers for something" problem, and the first one of the year where I represented a grid as a hashtable of coordinates. Racket doesn't have great multidimensional data structures built in, but rolling my own sparse matrix representation is pretty painless.
• Day 9. Simulate a rope. Simulation problems are my favorite kind of AoC problem (probably because they're the most similar to the kind of stuff I did in school). The solution I wrote for a one-segment rope in part 1 just needed to be folded over a list to give me a solution for the ten-segment rope in part 2. Higher-order functions are nice.
• Day 10. The traditional fake-ASM parsing problem, and another problem that's just largely just folding a function over an accumulator. I feel like if you get comfortable with for/fold you can get about 25 AoC stars right off the bat.
• Day 11. Monkeys take your stuff. This problem features my least favorite AoC trope, which is a Part 2 that requires you to know a particular fact about modular arithmetic to solve it in a reasonable amount of time. It also had a data file I found less annoying to retype by hand than to parse. Probably the worst one of the set.
• Day 12. Find a hiking route up a spiral mountain. I leaned pretty hard on the graph package for this one. Eventually I'd like to learn how to implement Dijkstra and A* and other graph traversal algorithms myself, but for now I'm satisfied with just figuring out how to use the prepackaged versions.
• Day 13. Sort a recursive data type. I'm really glad for two features of Racket for this one. First, the ability to read data as code, which meant I could read the nested lists directly with just one tweak to the readtable and without doing any string parsing at all. Second, structural pattern matching. Racket's matching syntax isn't as elegant as some languages (I miss the [x | xs] form from Elixir compared to (list* x xs), for example), but it's powerful.
• Day 14. Simulate falling sand. A fun simulation problem, and one that both has a naive solution that solves in a reasonable amount of time and an optimized backtracking solution that's easy to reason out. This was my favorite puzzle of the set.
• Day 15. Find the only possible place for a missing beacon. The fundamental problem here is finding out a way to represent a range of integers sparsely (or using a library that does that for you). Lots of opportunities for optimization.
• Day 16. Teach an elephant to open valves. The first of a few heuristic search problems with enormous solution spaces. Part 1 (one person opening valves) is OK, but I only eventually solved Part 2 (two people simultaneously opening valves) a week later by watching console output and making a reasonable guess. Nearly half of the remaining participants in AoC quit at this point and I don't really blame them.
• Day 17 (no solution). Find the period in the pattern of falling rocks. I'm sure this one isn't too bad, but I was feeling too burnt out by Day 16 to give it more than a token try.
• Day 18. Find the surface area of an irregular rock. A nice straightforward volume-scanning problem, and another opportunity to use my sparse matrix data type.
• Day 19 (no solution). Pick the best plan for building mining robots. Another heuristic search problem, so I skipped this one since I was still failing at day 16 part 2. Picking out an optimized robot building strategy had more moving parts than I knew how to deal with.
• Day 20. Repeatedly shift elements around in a circular array. Singly-linked lists are terrible for repeated arbitrary access, but I don't care. I figured out an algorithm that worked and I was happy enough with that to accept it and move on. After the previous streak of problems, I was just happy to figure out Part 2 on my own. (There was a modulo math trick element to Part 2 here as well, but this one was a lot more obvious to spot.)
• Day 21. Figure out what to shout in the monkeys' math game. I have a feeling the intended solution for Part 2 of this one was to build the expression tree and backtrack through the operations to calculate the unknown value. However, I just blindly started evaluating the result for various guesses and discovered through trial and error that the relationship between the guess and the result is linear, so all you need for part 2 is two guesses, their corresponding results, and some algebra. It's fun to accidentally discover simple solutions to complex-looking problems.
• Day 22 (no solution). Something involving walking around on a map. I skipped this one because of the flu. C'est la vie.
• Day 23. Cellular elfomata. Another AoC staple, though later than usual. I think the story got in the way of the problem description a little bit here, but once I talked through the rules with someone else it was a straight shot to the solution.
• Day 24 (no solution). Walk through a blizzard. I had to skip this one because of holiday travel (ironically made more difficult by a blizzard) and family obligations. It looks interesting, though, so I'm hoping to have some time to come back to it before January.
• Day 25. Figure out balanced penternary. The final AoC problem is always a clever little math brain teaser with one part, and this one was fun to puzzle out with pencil and paper.

I think Days 16 and 19 could've used a second pass to narrow the possible solution space, or at least make the best heuristic a little more straightforward to reason out, but on the balance, I enjoyed myself this year, and I'm generally happy with my solutions and implementations.