I almost wonder if I would have had a quicker solution time on Advent of Code's Day 24 puzzle if I had tried to do it while distracted with holiday celebrations, instead of deciding there was no way I could attempt it without clear focus time. I spun my wheels for a long time overengineering part of the solution, because I had convinced myself after a first, quick, read that this problem was reversing a hash, and so its search space would be huge, even after I figured out the "trick". It's not pencil-and-paper small with my final technique, but it is still milliseconds-of-computer-time small all the same.

I started with a simple implementation of the ALU that could run both the example and full code with a given input. I don't think I even bothered trying fourteen 9's in a row, just in case that was the answer, at this point.

Instead I moved on immediately to giving the
ALU support for "symbolic" operations. That is,
instead of integers, I could also pass atoms, and the ALU would give
me back exentially
the s-expression
representing the algebraic formula for the ending state of each
register. I included some basic identity operations, so that it
could replace things like `{mul, x, 0}` with just `0`,
but the resulting s-expression was still a partial binary tree with
maximum depth of 170. The Erlang shell did not like printing that
result.

Turning to code inspection, a hand-run of the first few operations initially led me to believe that there was a comparison that could never be true. But I could only tell that because I knew that the inputs would never be outside of 1..9 in the real problem. To get my ALU to recognize the same, it needed to know that too. I decided to add one more input type: lists of possible values.

But, while teaching the mathematical operations to add a number to a list of numbers was easy, comparing lists proved too complex, except for the specific case where they were exactly equal. This was wheel-spinning spot number one. Did I need to start a branched search here? Did partial overlap mean something specific?

I went back to the puzzle code to have another look. I had tried hand-evaluation, both forward from the beginning, and backward from the end. Both quickly ended up with growing formulas, like my symbolic evaluation had returned. Finally, looking at the rest of the file, I noticed that it's not 200-something lines of code. It's 14 repetitions of 18 lines of code. Each repetition starts with reading the next digit, and then runs an identical set of operations, except with different constant values.

Above is a run of the first 18 line section, with all possible first
digits. The output is a record named `reg` with fields for the
ending values of each register (w,x,y,z), in order. What this shows
is that the first block of code will produce a 14 in
register `z` if the first input digit is `1`. It will
produce a 15 in `z` if the digit is a `2`. Sixteen for
three, and so on. Neat, what happens with the next block?

I've appended repetition 2 to repetition 1, and added another 1..9
input for it to try. The result of running each of the 14..22
input `z` values against each of the 1..9 input digits is is
81 possible output `z` values. If this keeps up, we could
have 22,876,792,454,961 (=9^{14}) output values to check!
Let's go look at the last block.

The last block's output is very similar to the first block. But,
none of those output values would cause MONAD to consider the input
model number valid. We need this block to produce `0` for
that to be the case. What input would cause this block to be zero?

inp w mul x 0 add x z mod x 26 div z 26 add x -5 eql x w eql x 0

This is how the block starts. It's clear that we care whether the
value we have accumulated in `z`, which has been copied
to `x` (`mul x 0, add x z`), is equal to the final
digit (`inp w, eql x w`), after some math (`mod x 26, add
x -5`). What value(s) would make that true?

I've prepended an `{inp, z}` instruction here, so I can pass
`z`'s initial value in as input. The puzzle code sets
the `x` and `y` registers get set to zero (`mul x
0, mul y 0`) before using them, so their input state can remain
arbitrary. Giving `z` the same 1..9 value that the next digit
will have produces the above "mess". But in that mess lies the
confirmation that the math on z is
simple: `{eql,[-4,-3,-2,-1,0,1,2,3,4],[1,2,3,4,5,6,7,8,9]}`
is the comparison of our input `z` to our input `w`,
after `z` has been shifted down -5, just as `add x -5`
says.

If we pre-shift our input `z` up to 6..14, that `add x
-5` produces 1..9, and the whole block collapses to
produce `0` for every input digit! This is progress. We just
need to figure out how to tell the previous block, D13, to produce
an output `z` value in the range 6..14.

inp w mul x 0 add x z mod x 26 div z 26 add x -3 eql x w eql x 0

Block 13 starts the same way as block 14, but with a `-3`
being added to `x` instead of `-5`. Our trick will
work to get us a zero value. How do we get up to 6..14 though?

The key is two lines before the addition: `mod x 26`. This
means that an input 26 higher than our zero output will have the
same result in terms of the `eql x w` comparison. The useful
part is that bumping input `z` up 26 bumps output `z`
up one! We can get output `z` into the range we need by
giving input `z` any value in 160..168 (=6*26 + 4..12),
186..194 (=7*26 + 4..12), … 368..376 (=14*26 + 4..12). That's great
…

… except it means we have the same 9^{N} growth as from the
top down. I spun wheels here again for a *long* time, trying to
figure out a compact way to express a growing pattern of steps and
strides. One of the things that made that concept complicated is
something I've glossed over a little: one of the constants that
changes between blocks is the `div z …` operation. The two
I've shown so far both say `div z 26`. But the first block
says `div z 1`. In fact, all blocks uses either 26 or 1 on
this line, and that groups them into two categories:

I've discussed only the first shape so far, the one that will give
us `z=N` output for a `z=26*N+c` input. The second
shape does the opposite - it gives us `z=26*N+c` output for
a `z=N` input. The inscrutable names I've given them here
(`add_out` and `mult_out`), reflect how I was missing
the point of this duality. I nearly named them
generically `shape_a` and `shape_b` just to move on.

It wasn't until I put in significant work trying to come up with a
compact representation of the combination of these two "functions"
that I finally gave up and decided to just let the exponential
explosion run wild. And that's when I finally saw it: one shape
increases the number of valid inputs (`add_out`), and the
other shape decreases it (`mult_out`). I hadn't seen it
before, because in the forward direction, input-shrinking is
output-growing, and the program begins with output-growing in the
direction I hand-simulated.

Starting from the last block and working backward, there are only five input-growing blocks in a row. The fifth power of nine is "only" 59,049 - too many options for me to consider by hand, but trivial for a computer. After that, there is some interleaving of input-growing and -shrinking blocks, before a final string of three input-shrinking blocks at the start. This implementation could work!

My solver starts from the end, where we know the output value must
be 0, and then works backward through the blocks, passing block N's
valid inputs to block N-1 as valid outputs. Once it reaches block 1,
we have no choice in `z` input, so given that
input `z` will be `0`, it selects the largest input
digit that will cause the function to produce one of the
valid `z` outputs that were passed up. It passes the choice
of digit and the `z` output it produced back through the
stack, where each block does the same.

Interestingly, it's only the input-shrinking (output-growing) blocks
that have a choice in which digit they should use. The input-growing
(output-shrinking) blocks have to use the digit that matches
the `z` input they were given.

As predicted, the maximum number of options under consideration by
any block was 59,049 (=9^{5}) - an easy task for a modern
computer. The output is in reverse order, because I left this code
in I'm-just-working-in-the-shell state.

I worried as I clicked to proceed to Part 2 of this puzzle. Part 1 had taken a lot of analysis, and if Part 2 was going to make some major change like adding a new operation, or allowing zeros in some cases, I was probably going to give up. But thankfully, the change was the easiest one I had considered: find the lowest model number instead.

I copy-pasted and then made the change instead of parameterizing my
existing functions. But the only difference is in considering input
digits in 1..9 ordering instead of 9..1 order. Literally a one-line
change: remove the `lists:reverse` from the last line
of `highest_digit_for`.

Most output has been elided here in order to highlight what I mean by this being a trivial task for a modern computer. The solver runs in 10ms. This model-number-checking ALU has a lock nearly as weak as the old video games that asked for the Nth word on a specific page of the manual!

This puzzle brought back memories of tracing through EVM bytecode - something I haven't done in nearly two years now. I can't say that it made me want to do it again. Full code is on github, as usual. On to the final puzzle!

Categories: Development AdventOfCode

Post Copyright © 2021 Bryan Fink