Advent of Code is a yearly programming challenge involving 25 puzzles, released daily in December. I published all my solutions for 2021 on GitHub. I’m featuring some of the more interesting or odd ones in a series of posts.

In this problem we are asked to simulate an arithmetic logic unit (ALU) over a sequence of assembly-like instructions, e.g. inp w for “read an input value and write it to variable w” or div z 3 for “update the variable z to floor(z/3).” The ALU maintains variables w, x, y, z. We must find the lexicographically greatest (or least) sequence of 14 digits \(w_0, \dots, w_{13} \in \{1, \dots, 9\}\) which, when input to the ALU, leaves z == 0 after all instructions have been executed.

The input contains 14 segments of instructions with 18 instructions each, all starting with inp w. These segments are identical everywhere except in 3 instructions, namely

  • 5th instr: div z a;
  • 6th instr: add x b;
  • 15th instr: add y c;

where a, b, c vary as follows:

\[\begin{align} a &\in \{1, 26\}; \\ b &\in \begin{cases} \{10, \dots, 13\} & \text{if } a = 1, \\ \{-13, \dots, 0\} & \text{otherwise}; \end{cases} \\ c &\in \{0, \dots, 16\}. \end{align}\]

Approach 1: Math

My initial approach was to formulate the program as a composition of 14 closely related functions. Each segment \(i\) accepts some input \(w_i\) and updates the ALU state \((w, x, y, z)\) given parameters \(p_i := (a_i, b_i, c_i)\). We don’t actually care what the new value of w is, since it is immediately overwritten in the next segment (or we’re done, in which case we only care about z). Writing \(v_i := (x_i, y_i, z_i)\); we can characterize each of the 14 instruction segments as functions

\[f_i: (w_i, v_i; p_i) \mapsto v_{i+1}.\]

I wrote some code to simulate the ALU and computed values of \(f_i\) for all possible values of \(w_i\) and \(p_i\) and “a lot” of tuples \(v_i\). (We’re not really doing math, after all.) I quickly noticed that the values of \(x_i\) and \(y_i\) had no apparent effect on the output. Begrudgingly peeking at the instruction sequence, I saw that the first instruction involving x was always mul x 0, wiping whatever we stored in x in the previous segment. The same was true for y. Hence we may as well dump useless information and reformulate the segment’s operation as

\[f_i: (w_i, z_i; p_i) \mapsto z_{i+1};\]

then the output of the entire program is given by

\[f(\mathbf w; \mathbf p) := f_{13}(w_{13}, \dotsm f_1(w_1, f_0(w_0, z_0 = 0; p_0); p_1); \dotsm p_{13})\]

and we need to find vectors \(\mathbf w\) with \(f(\mathbf w; \mathbf p) = 0\).

At this point I launched an ill-conceived search for the kernel of \(f\). I wrote awful code like this:

for w in range(1, 10):
    for z in range(-10, 11):
        for a in [1, 26]:
            for b in range(10, 14) if a == 1 else range(-13, 1):
                for c in range(17):
                    if f_i(w, z, a, b, c) == 0:
                        ker.add((w, z, a, b, c))

I drew some plots, none of them six-dimensional. I found some small patterns, like that \(f_i\) was 0 when \(z + b = w\), but felt the trail towards a proper understanding of \(f_i\) running cold. I realized my most useful ideas thus far had come from manually inspecting my specific input, so I decided to scrap the plots and go all in on decompilation.

Approach 2: Manual decompilation

A generic segment is given below, along with a step-by-step Python translation:

inp w     w = input()
mul x 0   x = 0
add x z   x += z
mod x 26  x %= 26
div z a   z //= a
add x b   x += b
eql x w   x = int(x == w)
eql x 0   x = int(x == 0)
mul y 0   y = 0
add y 25  y += 25
mul y x   y *= x
add y 1   y += 1
mul z y   z *= y
mul y 0   y = 0
add y w   y += w
add y c   y += c
mul y x   y *= x
add z y   z += y

Or, compressed into more readable Python,

w = input()
relation = z % 26 + b == w
z //= a
if not relation:
    z = 26 * z + w + c

The number 26 occurs in 2 places (really 3, since a is either 1 or 26) — let’s think of z as a base-26 number. In this view, relation is True exactly if the last digit of z matches w - b. Then, if a == 26 we pop a digit off of z; else, a == 1 and we do nothing. Finally, if relation was False, we append the digit w + c to z.

Initially z == 0, i.e. it has “zero digits” in base-26. We need z to also have zero digits upon termination.

  • Case 1: a == 1. Notice in this case that relation is always False since b > 9, but we require each w <= 9 as well. Since z //= 1 is a no-op, in each of these 7 cases we add a digit to z, namely w + c.
  • Case 2: a == 26. In this case b is always nonpositive, so relation may or may not hold. In this case we always lop off a digit from z, but if relation is False we add another digit right back.

Actual values of (a, b, c) for each segment and their interpretations are given below:

0:  (1, 11, 1)      # add digit w0 + 1 to z
1:  (1, 10, 10)     # add digit w1 + 10 to z
2:  (1, 13, 2)      # ...
3:  (26, -10, 5)    # add digit w3 + 5 to z if relation, else pop digit from z
4:  (1, 11, 6)      # ...
5:  (1, 11, 0)
6:  (1, 12, 16)
7:  (26, -11, 12)
8:  (26, -7, 15)
9:  (1, 13, 7)
10: (26, -13, 6)
11: (26, 0, 5)
12: (26, -11, 6)
13: (26, 0, 15)

There are 7 tuples each with a == 1 and a == 26. Since z must have “zero digits” at the end, and we know the a == 1 tuples will add 7 digits, we need relation to hold in each a == 26 tuple such that those segments only remove digits from z. This reduces the problem to a system of 7 equations, where we track digit additions and deletions across segments as if z were a stack:

\[\begin{align} w_0 + 1 &= w_{13} \\ w_1 + 10 &= w_{12} + 11 \\ w_2 + 2 &= w_3 + 10 \\ w_4 + 6 &= w_{11} \\ w_5 &= w_8 + 7 \\ w_6 + 16 &= w_7 + 11 \\ w_9 + 7 &= w_{10} + 13 \end{align}\]

Finding the lexicographically greatest \(\mathbf w\) is then a matter of choosing the solution to this system with the highest possible most significant digits, e.g.

\[\begin{align} w_0 + 1 = w_{13} &\implies w_0 = 8, w_{13} = 9; \\ w_1 + 10 = w_{12} + 11 &\implies w_1 = 9, w_{12} = 8; \\ &\dotsm \end{align}\]

which yields the solution for part 1

\[89913949293989\]

and, doing the opposite to find the lexicographically least \(\mathbf w\) for part 2,

\[12911816171712.\]