Advent of Code 2019 in Varyx: A Postmortem
Background
Advent of Code is an advent calendar for programming enthusiasts, providing a new pair of programming puzzles each of the first 25 days of December.
I first learned about Advent of Code in 2017, its third year, and decided to give it a try. Having started developing my own language two and a half years earlier, I opted to "eat my own dogfood" and use it exclusively for solving the puzzles.
(At the time, it was just the "V Programming Language". Now it’s named Varyx.)
First, a synopsis of the prior years follows. Here’s how I did in 2017:
--------Part 1-------- --------Part 2--------
Day Time Rank Score Time Rank Score
7 00:20:22 793 0 - - -
6 00:13:13 370 0 00:15:57 325 0
5 00:05:10 283 0 - - -
4 00:03:53 341 0 00:08:19 371 0
3 00:14:49 234 0 00:44:47 311 0
2 00:10:37 716 0 00:16:48 516 0
1 20:07:33 17538 0 20:11:51 14525 0
Day 1 is always the easiest — my low rank is due to starting late. Day 3 posed more of a challenge, with part 2 taking me twice the time of part 1, but it was nonetheless my best performance (relative to other participants).
Day 5 finally threw me for a loop (so to speak). I got part 1 in mere minutes, but I wasn’t mentally prepared for a part 2 that in just as many minutes hadn’t produced any output. I assumed there was a flaw in my code somewhere causing an infinite loop, and gave up. (On the machine on which I write this, part 1 takes 2.3 seconds, whereas part 2 takes eight minutes!)
On Day 6 I was back in form, my solutions taking a comparatively reasonable 16 or 17 seconds — only to be knocked out by Day 7’s part 2. The run time wasn’t an issue, but an algorithm to solve the problem eluded me. I wasn’t having fun anymore, so I quit and went back to working on Varyx itself.
The following year (2018), my results were even more mixed:
--------Part 1-------- --------Part 2--------
Day Time Rank Score Time Rank Score
2 00:06:49 435 0 - - -
1 00:01:54 198 0 00:35:08 1207 0
Starting promptly, I was rewarded with my best time and ranking yet for part 1 (which was literally adding up a bunch of numbers) finishing in under two minutes, in the top 200 — but unexpectedly challenged by part 2 (taking over 30 minutes, not even close to the top 1000). And then Day 2’s part 2 was beyond my grasp. Once again, I gave up on Advent of Code to work on other things, such as an application that animates a black and white Nyan Cat on a classic Macintosh, a Mac emulator to run it in, and bugfixes for Varyx’s garbage collector.
2019
This year was different.
You have 120 points.
--------Part 1-------- --------Part 2--------
Day Time Rank Score Time Rank Score
25 02:49:26 819 0 02:50:47 613 0
24 00:26:53 486 0 05:34:19 1113 0
23 00:39:13 492 0 13:48:25 2252 0
22 00:28:38 447 0 05:01:15 442 0
21 00:15:21 90 11 00:27:36 49 52
20 01:47:52 752 0 12:19:59 1510 0
19 00:18:18 810 0 03:29:29 1298 0
18 20:06:27 1736 0 22:36:17 1361 0
17 00:22:19 775 0 00:53:07 168 0
16 00:22:45 513 0 06:00:49 1226 0
15 01:23:49 609 0 02:13:34 728 0
14 00:32:40 143 0 02:09:03 718 0
13 00:11:23 1071 0 01:02:41 907 0
12 00:30:24 946 0 05:06:04 2221 0
11 00:18:23 338 0 00:51:29 1071 0
10 00:36:16 608 0 01:19:24 469 0
9 00:40:14 787 0 00:42:55 810 0
8 00:05:52 191 0 00:17:34 393 0
7 00:12:55 239 0 00:34:33 138 0
6 00:08:23 233 0 00:16:22 237 0
5 00:14:07 82 19 00:19:19 63 38
4 00:12:36 1754 0 00:17:29 917 0
3 13:41:27 15328 0 13:59:06 12574 0
2 23:21:27 32273 0 23:33:35 28696 0
1 >24h 50796 0 >24h 44784 0
Cognizant that I hadn’t added any major new features to Varyx in the last year (and perhaps demoralized from previous attempts), I wasn’t even planning to participate in Advent of Code this year. But upon learning that a small subset of the Lobsters community had set up an IRC channel and a private leaderboard, I relented. Unfortunately, Day 1 had passed and Day 2 was almost over, though I quickly caught up.
Day 1: The Tyranny of the Rocket Equation
Part 1 is a simple map-reduce problem. My published code contains more boilerplate than actual business logic. Here it is as a one-liner:
vx -e 'print ((load argv[1]).lines() map {int v div 3 - 2} per {a + b})' input.txt
Part 2 added a wrinkle in the form of a recursive definition. I opted for a literal solution using actual recursion, since the numbers involved were too small for performance to matter.
Day 2: 1202 Program Alarm
Advent of Code has barely left the launch pad and we already have a virtual-machine-building puzzle disguised as an irreverent Apollo 11 shout-out. Taking about twelve minutes for part 2, I’m off to a good start.
The proto-Intcode machine can only add, multiply, and halt, but we’re warned that it will reappear later with more features to be added.
Day 3: Crossed Wires
We have to find where two wires cross on a grid. Glancing at my input, I’m not surprised in the slightest to see wire segments spanning hundreds of grid points. I have an advantage here, having first reverse-engineered and then reimplemented QuickDraw regions as part of Advanced Mac Substitute. I can see that it’s folly to plot out each individual grid point the wires contact and then intersect them all, when I can just intersect the line segments themselves.
But it doesn’t work — my answer is wrong. I ask in the channel if wires can "cross" by overlapping instead of intersecting perpendicularly, and I’m told yes. I write additional code to detect this condition, and my result doesn’t change. For the the third year in a row and third out of three, I give up. Again.
After a night’s sleep I take another look. Turns out my approach was sound, but my code contained a logic error: Intending to compute the intersections of wire A’s horizontal segments with wire B’s vertical segments and vice versa, I had reversed the order of the arguments in the second call to a function that required them the other way. Turns out I’d gotten my own wires crossed. (Subsequently I added assertions that would have caught this error.)
Day 4: Secure Container
It’s a password-checking puzzle. I spot the blessing in disguise — rather than just another predicate that permits or rejects a password, one of the requirements can be worked into the increment function itself, so that passwords which are defective in this regard are never checked in the first place. Without this optimization, run time would be two orders of magnitude longer. Having built-in primitives for converting between integers and numeral strings is indispensible.
I finally achieve a three-digit rank (917 for part 2). For an encore, I solve part 2 of 2018’s Day 2 (with creative use of XOR), and then after a night’s rest, both parts of Day 3 (explicitly creating a million-byte vector instead of a sparse grid).
On a roll, I take a look at 2018’s Day 4 and realize two things: One, it needs ordering keys for min/max — e.g. rather than just reporting what the best score is, you need to know who had that score. (Min/max is a subset of sorting in which you only care about the first element.) Second, it’s certain I’m going to need ordering keys and sorting to finish Advent of Code this year, and I’d better start implementing them now.
Day 5: Sunny with a Chance of Asteroids
Intcode is back, adding I/O instructions and addressing modes, and fun with acronyms (viz. "Thermal Environment Supervision Terminal (TEST)") begins. In part 2, Intcode adds conditional jumps and becomes Turing-complete.
Much to my astonishment, I made the global leaderboard! It probably helps that I’ve written an emulator, and all of these concepts are familiar to me.
Day 6: Universal Orbit Map
The orbit map is just a tree of nodes. Rather than create a tree data structure in Varyx, I opt instead for a simple associative array mapping each child node to its parent node. I add a second associative array for memoizing the results of a recursively calculated node property. (Plane change maneuvers are expensive, but even more so at O(n log n).)
Actually, Varyx’s associative arrays are currently thinly veiled linked lists, so my O(n) solution is really O(n^2), which is probably why it takes over 400 milliseconds to run. But at n = 1444, it’s not a problem... yet.
Day 7: Amplification Circuit
Intcode is back! There are no new instructions or addressing modes, but there is a twist — we have to run five separate instances. For part 1, they run serially, and it’s sufficient to have one machine state and reset it between runs. But part 2 uses a feedback loop, and all five machines have to be maintained simultaneously (though only one is actively running at any given time).
Either way, each machine has to be seeded with a unique "phase setting", but we
don’t know which machine should get what phase signal, and the only way to find
the correct assignments is to try out every possible arrangement.
Later on I wrote a proper module implementing a permute function,
but in the interest of speed I hastily code five nested loops, each deeper one
skipping the current value of the outer ones. It’s ugly, but it works.
Varyx doesn’t have classes or other user-defined types yet, but you can still
approximate object-oriented programming with records and closures.
A record is basically an immutable associative array whose members are accessed
with dot syntax instead of brackets, i.e. x.foo rather than x["foo"].
It looks like a C struct, but you can define one at run time. A closure is
a function that retains access to variables defined by a parent function even
after the parent has returned.
The new IntCode_machine function acts as a constructor, returning a record
containing other functions, each of which closes over the machine state,
which is to say that these functions have access to those state variables even
though they’re otherwise inaccessible after the constructor returns. Also,
each call to IntCode_machine creates its own set of state variables, shared by
the closures it returns but not by those returned from other calls to it.
This leads to my discovery of a bug in Varyx’s garbage collector that prematurely destroyed objects. In the process of trying to figure out a workaround I can use temporarily, by some odd coincidence I trip over another premature destruction bug, which while having similar effects is otherwise entirely unrelated to the first.
In spite of these setbacks, I manage to achieve a respectable rank 138 on part 2.
Day 8: Space Image Format
You have to paint a bunch of pixels to see what message they spell out, but they’re spread out over a hundred semi-transparent layers, requiring you to implement a compositor.
My message was "LGYHB", but the L was flush left and bottom, blending with
the terminal window edge and the prompt below and leading me to submit "GYHB"
first. Lesson learned: Pad grid output with blank lines and a left margin.
Day 9: Sensor Boost
The Intcode machine needs an additional addressing mode and special register, auto-extending memory, and large integer support. Word on the street is that signed 64-bit integers are sufficient; in any case, Varyx automatically uses bigints, so the issue is moot.
Today’s acronym is BOOST: Basic Operation Of System Test.