Advent of Code 2019 - Lucky 14
(Yes, I’m aware that my post titles have off-by-one errors.)
In my last article, I lamented that progress on the project had stalled. Well, writing that post was the impetus I needed to get back on the horse, or the camel as it were. Lo and behold, a few days later I solved day 14 of the Advent of Code, and what’s more: I enjoyed it. (and then, of course, it took me two months to publish this article).
Two reasons for this: better tools, and a fun problem.
Better tools
For work-related reasons, I recently spent some time getting WSL (slogan: “The performance of Windows, the user friendliness of Linux”) to suck less. I configured some basic stuff, installed or updated some packages, tweaked some settings. I bit the bullet and learned about .vimrc. The result: my WSL is now a usable Linux shell.
Along the way, I installed opam, and this unlocked some cool OCaml tools: merlin for auto-completion, and utop for a better REPL. Crucially, with a simple opam switch 4.10.0 I jumped to the latest Ocaml version, leaving behind Ubuntu’s slightly outdated 4.05 version. This gave me access to a language feature (to_seq) I wanted to use to solve the problem at hand. So, major step forward in the tooling department.
I still don’t have a decent OCaml IDE, but I’ve grown used to vim; Stockholm syndrome, probably.
A fun problem
Day 14 sounds suspiciously easy when you first read it. You’re provided with a list of reactions, which are recipes to generate chemical compounds from different input chemicals. All chemicals can ultimately be generated from a primordial input called “ORE”. Given all this, you are asked how many “ORE” inputs are required to produce one “FUEL” output.
Simple, right? You repeatedly substitute each chemical by its component inputs, until you’re only left with ORE. The trick is the order in which to do the substitutions: if you get it wrong, you’ll end up using more ORE than necessary. To get the correct quantity, you have to substitute each chemical exactly once.
Long story short, this requires performing a topological sort on a directed acyclic graph. (Fancy terms, right? Finding what words to google was half the battle. I learned them when solving this problem, so don’t beat yourself up). This great article covers the theory and gives not one but two algorithms for topological sort!
From there, it’s straightforward to code the solution.
I didn’t get too fancy with data structures; the entire solution is cobbled from hash tables. There’s certainly a more elegant way to build and traverse the DAG, but I couldn’t think of one. That’s ok. Hash tables don’t judge you when you write ugly code. They’re just glad to help.
To my amazement, my code gave the correct answer right away. Well, after I’d fixed all the syntax errors, obviously. So chalk this up as a net win for team side project! Day 15 requires interpreting keyboard presses, this is going to be a whole ‘nother can of worms to tackle.
Addendum
By the time I wrote the draft for this post and publication, I solved the first part of day 15. The solution was not as elaborate as it could be, but there’ll be time to improve the I/O routines if I end up reusing them for another problem.