Fun with the 2017 Advent of Code

I found Eric Wastl‘s Advent of Code puzzle site in 2015 from a Hacker News link. The idea was to have an Advent calendar with a small, two-part coding challenge every day From December 1st until Christmas. It quickly gained popularity, and I half-heartedly solved a couple days’ worth of puzzles, and forgot all about it.

In late November, I found myself potentially queued up to work with a client who had Python as a prominent tool in their tech stack. My work with Python had been minimal, as I’m one of those old cranks who prefers Perl. When December 1st came around, I decided to use Advent of Code as an excuse to train myself up in Python. After a couple days of bumbling around with novice “how do I append to an array?” type questions, I started to appreciate Python’s expressiveness, and quickly found myself thinking in list comprehensions and generators.

I kept up with the puzzles, finishing a couple days late, which I attribute to my family’s preference for me to interact with them rather than my laptop, and having many Christmas presents for daughters, nieces, and nephews to square away. Predictably, my next project used Node.js, but I don’t regret learning Python in the slightest.

The Day 23 challenge I found very interesting. Your input is a psuedo-assembly language with the commands set to set a register, sub to subtract, mul to multiply, and jnz to jump to a new instruction if the compare value isn’t 0. The two values after an instruction could refer to numbers or to registers, and your code that parses the assembly must act accordingly. All registers are assumed to be initialized to 0. Here are some examples:

• set a 15 – Set register a to 15
• mul b a – Multiply register b by the value of register a
• jnz b -5 – If register b isn’t 0, jump back 5 instructions, otherwise continue to the next instruction

If any jumps land you outside of the assembly lines, stop and answer the puzzle question. Part one of the puzzle asks for how many times the multiply instruction is called. Here is a relatively direct Python3 solution, using the assembly instructions I was given, which runs in sub-second time and gives the right answer to my input, 9409:

Part two, however, takes a neat twist. Register a is initialized to 1, and your answer is the value of register h after the script exits. However, when a is 1, the assembly ends up being very unoptimized. The part two instructions include the following description:

Immediately, the coprocessor begins to overheat. Whoever wrote this program obviously didn’t choose a very efficient implementation. You’ll need to optimize the program if it has any hope of completing before Santa needs that printer working.

Oh, right, this year you’ve been Tron-ed into a computer, and are trying to fix its printer so Santa can print his Naughty or Nice list… long story. The stated goal is to fix the algorithm of the assembly code, and run that instead, so let’s take a closer look at what we were given.

It was difficult for me to scan this code and get a sense of what it does, mainly because I normally work in higher level languages. But I was able to transform it into pseudocode, one concept at a time, and after a handful of steps the intent leapt out from the code, and the whole endeavor ended up being very fun. I’d like to take you through (roughly) the same steps here.

As we combine instructions together to form more expressive statements, the jump instructions will point to the wrong places, so let’s start by adding goto markers where the destinations start, and replacing the jnz values with those markers:

Next, let’s replace the assembly instructions with something more C-like:

The next thing that jumps out are the goto statements on lines 4, 36, and 39. These check that 1 doesn’t equal 0 before jumping. In assembly-speak this just means to always jump, but it looks silly here, so we can take out those trailing if statements. Also, on line 36, jumping to :j8 will exit the program, so we can get rid of that marker, and change that goto to an exit statement instead:

The next obvious thing to do to make this readable is flip all the statements that subtract negatives (lines 7, 9, 22, 26, 31, and 38) into just adding positive numbers:

Now let’s combine sequential operations on the same variable:

Now we can start to apply some higher-order thinking to the code. The puzzle mentions that in this run we’re initializing register a to 1. The only line that references a in the code is line 3, the first goto statement. Since a won’t equal 0, we’ll always be jumping to j1, meaning the the goto statement on line 4 will never be triggered. This concept can be simplified by simply removing those three lines, leaving the beginning of the program looking like this:

This can be simplified to:

…and then to:

…making our full program look a lot simpler:

Now we can start thinking a little more critically about the code. All of the value changes on register g (lines 9, 14, 17, and 22) happen before goto tests. These can be combined, and the references to g can be removed:

In all those goto tests, we’re subtracting a variable, and comparing with 0. A little algebra will make the meaning more clear:

The goto test on line 19 exists just to avoid the exit statement that follows. We can instead say that we will exit if registers b and c are the same:

Now the last 3 lines make sense. We’re in a loop that starts at :j2, and continues until register b increments its way up to c. That can be replaced with a for loop, and we can remove the reference to c altogether:

The goto test on line 14 is similarly just avoiding incrementing register h, so that can be simiplied as incrementing h if f is 0:

The :j5 marker on line 4 and its associated goto on line 13 is a loop that happens until register d increments its way to b:

…and the same is true with :j4 and register e on lines 6 and 11:

The remaining goto on line 7 avoids setting register f to 0. Flipping the logic on that test lets us get rid of our final goto, making our code less harmful:

Now things get interesting. The inner loop on lines 6 through 8 increments register e, starting at 2, to see if that times d is b. Ultimately this is checking to see if d is a factor of b. Let’s replace that construct with a simple English statement:

We can see now that register d is doing sort of the same thing. It’s being walked from 2 to b to see if any of those are a factor of b. That’s a primality test. Register f is set to 0 any time b is a composite number, so we can replace that chunk of code with an equivalent English statement:

Lastly, we have no need for f. We’re just incrementing h if b is composite:

Our final pseudocode snippet asks a simple question: How many composite numbers are between (and including) 109,900 and 126,900, if we only consider every 17th number? With ranges and list comprehensions, this is very easy question to ask Python:

The answer turned out to be 913, which the Wolfram Programming Lab, agreed with, as shown in this fairly straightforward notebook using the Wolfram language:

I can’t say enough good things about Wolfram and it’s myriad of uses… but we’ll save that for my next blog entry.

Enjoy!
Curtis