[Advent of Code 2021] Day 24 | Arithmetic Logic Unit

Part 1

Magic smoke starts leaking from the submarine's arithmetic logic unit (ALU). Without the ability to perform basic arithmetic and logic functions, the submarine can't produce cool patterns with its Christmas lights!

It also can't navigate. Or run the oxygen system.

Don't worry, though - you probably have enough oxygen left to give you enough time to build a new ALU.

The ALU is a four-dimensional processing unit: it has integer variables w, x, y, and z. These variables all start with the value 0. The ALU also supports six instructions:

• inp a - Read an input value and write it to variable a.
• add a b - Add the value of a to the value of b, then store the result in variable a.
• mul a b - Multiply the value of a by the value of b, then store the result in variable a.
• div a b - Divide the value of a by the value of b, truncate the result to an integer, then store the result in variable a. (Here, "truncate" means to round the value toward zero.)
• mod a b - Divide the value of a by the value of b, then store the remainder in variable a. (This is also called the modulo operation.)
• eql a b - If the value of a and b are equal, then store the value 1 in variable a. Otherwise, store the value 0 in variable a.

In all of these instructions, a and b are placeholders; a will always be the variable where the result of the operation is stored (one of w, x, y, or z), while b can be either a variable or a number. Numbers can be positive or negative, but will always be integers.

The ALU has no jump instructions; in an ALU program, every instruction is run exactly once in order from top to bottom. The program halts after the last instruction has finished executing.

(Program authors should be especially cautious; attempting to execute div with b=0 or attempting to execute mod with a<0 or b<=0 will cause the program to crash and might even damage the ALU. These operations are never intended in any serious ALU program.)

For example, here is an ALU program which takes an input number, negates it, and stores it in x:

inp x
mul x -1

Here is an ALU program which takes two input numbers, then sets z to 1 if the second input number is three times larger than the first input number, or sets z to 0 otherwise:

inp z
inp x
mul z 3
eql z x

Here is an ALU program which takes a non-negative integer as input, converts it into binary, and stores the lowest (1's) bit in z, the second-lowest (2's) bit in y, the third-lowest (4's) bit in x, and the fourth-lowest (8's) bit in w:

inp w
add z w
mod z 2
div w 2
add y w
mod y 2
div w 2
add x w
mod x 2
div w 2
mod w 2

Once you have built a replacement ALU, you can install it in the submarine, which will immediately resume what it was doing when the ALU failed: validating the submarine's model number. To do this, the ALU will run the MOdel Number Automatic Detector program (MONAD, your puzzle input).

Submarine model numbers are always fourteen-digit numbers consisting only of digits 1 through 9. The digit 0 cannot appear in a model number.

When MONAD checks a hypothetical fourteen-digit model number, it uses fourteen separate inp instructions, each expecting a single digit of the model number in order of most to least significant. (So, to check the model number 13579246899999, you would give 1 to the first inp instruction, 3 to the second inp instruction, 5 to the third inp instruction, and so on.) This means that when operating MONAD, each input instruction should only ever be given an integer value of at least 1 and at most 9.

Then, after MONAD has finished running all of its instructions, it will indicate that the model number was valid by leaving a 0 in variable z. However, if the model number was invalid, it will leave some other non-zero value in z.

MONAD imposes additional, mysterious restrictions on model numbers, and legend says the last copy of the MONAD documentation was eaten by a tanuki. You'll need to figure out what MONAD does some other way.

To enable as many submarine features as possible, find the largest valid fourteen-digit model number that contains no 0 digits. What is the largest model number accepted by MONAD?

Proposed solution: at first I created an ALU simulator to run the program but quickly realized that brute forcing the answer was not going to work very well; instead I opted for reverse engineering the problem and figured it out with just pen and paper – the simulator still helped for validation

#!/usr/bin/env python3
import sys

if len(sys.argv) != 3:
    print("Usage: {} <input file> <model #>".format(sys.argv[0]))
    sys.exit(1)

model_num = sys.argv[2]
if len(model_num) != 14 or not model_num.isnumeric() or "0" in model_num:
    print("Model number must be 14 digits with no 0's")
    sys.exit(1)

file_input = open(sys.argv[1], "r").read().strip().split("\n")

i = 0
variables = {var: 0 for var in ["w", "x", "y", "z"]}
for line in file_input:
    if line == "":
        continue
    instr = line.split()
    if instr[0] == "inp":
		print(variables)
        variables[instr[1]] = model_num[i]
        i += 1
    if instr[0] == "add":
        operand = instr[2] if instr[2].strip("-").isnumeric() else variables[instr[2]]
        variables[instr[1]] += int(operand)
    if instr[0] == "mul":
        operand = instr[2] if instr[2].strip("-").isnumeric() else variables[instr[2]]
        variables[instr[1]] *= int(operand)
    if instr[0] == "div":
        operand = instr[2] if instr[2].strip("-").isnumeric() else variables[instr[2]]
        if int(operand) == 0:
            print("Divide by zero error")
            sys.exit(1)
        variables[instr[1]] //= int(operand)
    if instr[0] == "mod":
        if variables[instr[1]] < 0:
            print("Modulo dividend < 0")
            sys.exit(1)
        operand = instr[2] if instr[2].strip("-").isnumeric() else variables[instr[2]]
        if int(operand) <= 0:
            print("Modulo divisor <= 0")
            sys.exit(1)
        variables[instr[1]] %= int(operand)
    if instr[0] == "eql":
        operand = instr[2] if instr[2].strip("-").isnumeric() else variables[instr[2]]
        variables[instr[1]] = int(variables[instr[1]] == int(operand))

print(variables)

❯ python3 solution24.py input24 11111111111111
...
...
{'w': '1', 'x': 1, 'y': 10, 'z': 3118601834}

What I discovered about the input program is that there were 14 segments that looked very similar to each other: one for each number in the model number. However, there are two distinct operations that were being performed based on the position within the model number.

inp w
mul x 0
add x z
mod x 26
div z 1
add x 15
eql x w
eql x 0
mul y 0
add y 25
mul y x
add y 1
mul z y
mul y 0
add y w
add y 9
mul y x
add z y

The first type of block multiplies z by 26 and adds the next digit in the model number and some offset. In the above example, this offset is 9.

inp w
mul x 0
add x z
mod x 26
div z 26
add x -6
eql x w
eql x 0
mul y 0
add y 25
mul y x
add y 1
mul z y
mul y 0
add y w
add y 7
mul y x
add z y

This second type of block is basically the reverse of the first. Some lines in particular which make this not trivial:

mul y 0
add y 25
mul y x
add y 1
mul z y

x here is 1 if (z % 26) + offset != w and 0 otherwise. In the example block above, this offset is -6. We want x to be 0, meaning that (z % 26) + offset == w otherwise, this ends up resulting in z *= 26 instead of z *= 1 which reverses the z /= 26 performed earlier in the same block. Basically, we need to choose numbers in the respective first block type which results in x becoming 0 in the respective second block type.

Here, I am saying respective because this multiplication/division by 26 is like a stack operation. There are 7 numbers which have respective blocks like the first section and 7 numbers which have the second section – but not necessarily in that order. For example, my input program has the blocks in the following order:

first  (offset: 9)    >
first  (offset: 1)     >
first  (offset: 11)     >
first  (offset: 3)       >
second (offset: -11)      <
first  (offset: 5)       >
first  (offset: 0)        >
second (offset: -6)        <
first  (offset: 9)        >
second (offset: -6)        <
second (offset: -6)       <
second (offset: -16)     <
second (offset: -4)     <
second (offset: -2)    <

I tried to represent the stack growing and shrinking based on the first/second blocks. Of course the "stack" in this case is the value of the z register and each second block only divides the number by 26 successfully if that condition is met. Our goal is to craft the largest model number that satisfies all of these conditions for all second blocks. This will produce a z value of 0 at the end of the program.

I try this with pen and paper by setting each first block with the model digit as 9 and when hitting a second block, calculating what digit would satisfy the condition to set x as 0. If no digit will satisfy this (because the number needed is more than a single digit), I backtracked to the respective first block and lowered the digit until we could use a single digit for the second block.

z=0
w=9 z = 26*z+9+w = 18
w=9 z = 26*18+1+w = 478
w=9 z = 26*478+11+w = 12448
w=9 z = 26*12448+3+w = 323660
w=1 (323660 % 26) - 11 == 1
w=9 z = 26*12448+5+w = 323662
w=9 z = 26*323662+0+w = 8415221
w=3 (8415221 % 26) - 6 == 3
w=9 z = 26*323662+9+w = 8415230
w=? (8415230 % 26) - 6 == 12

We hit a problem with the 10th digit since we need w to be 12 but this comes from inp w which just takes a single digit from the model number. We have to backtrack to the 9th digit. If we set the 9th digit to 6, we should be able to set the 10th digit as 9 and continue.

z=0
w=9 z = 26*z+9+w = 18
w=9 z = 26*18+1+w = 478
w=9 z = 26*478+11+w = 12448
w=9 z = 26*12448+3+w = 323660
w=1 (323660 % 26) - 11 == 1
w=9 z = 26*12448+5+w = 323662
w=9 z = 26*323662+0+w = 8415221
w=3 (8415221 % 26) - 6 == 3
w=6 z = 26*323662+9+w = 8415227
w=9 (8415227 % 26) - 6 == 9
w=8 (323662 % 26) - 6 == 8
w=4 (12448 % 26) - 16 == 4
w=6 (478 % 26) - 4 == 6
w=? (18 % 26) - 2 == 16

We have to backtrack one more time. For the 14th digit, the condition resolves to 16 which is too large. We have to decrement the first digit by 7 in order to have the 14th digit work out to be a single digit 9. This will be the largest valid model number that passes the program resulting in z = 0.

z=0
w=2 z = 26*z+9+w = 11
w=9 z = 26*11+1+w = 296
w=9 z = 26*296+11+w = 7716
w=9 z = 26*7716+3+w = 200628
w=1 (200628 % 26) - 11 == 1
w=9 z = 26*7716+5+w = 200630
w=9 z = 26*200630+0+w = 5216389
w=3 (5216389 % 26) - 6 == 3
w=6 z = 26*200630+9+w = 5216395
w=9 (5216395 % 26) - 6 == 9
w=8 (200630 % 26) - 6 == 8
w=4 (7716 % 26) - 16 == 4
w=6 (296 % 26) - 4 == 6
w=9 (11 % 26) - 2 == 9

And some validation with our simulator:

❯ python3 solution24.py input24 29991993698469
{'w': 0, 'x': 0, 'y': 0, 'z': 0}
{'w': '2', 'x': 1, 'y': 11, 'z': 11}
{'w': '9', 'x': 1, 'y': 10, 'z': 296}
{'w': '9', 'x': 1, 'y': 20, 'z': 7716}
{'w': '9', 'x': 1, 'y': 12, 'z': 200628}
{'w': '1', 'x': 0, 'y': 0, 'z': 7716}
{'w': '9', 'x': 1, 'y': 14, 'z': 200630}
{'w': '9', 'x': 1, 'y': 9, 'z': 5216389}
{'w': '3', 'x': 0, 'y': 0, 'z': 200630}
{'w': '6', 'x': 1, 'y': 15, 'z': 5216395}
{'w': '9', 'x': 0, 'y': 0, 'z': 200630}
{'w': '8', 'x': 0, 'y': 0, 'z': 7716}
{'w': '4', 'x': 0, 'y': 0, 'z': 296}
{'w': '6', 'x': 0, 'y': 0, 'z': 11}
{'w': '9', 'x': 0, 'y': 0, 'z': 0}

Part 2

As the submarine starts booting up things like the Retro Encabulator, you realize that maybe you don't need all these submarine features after all.

What is the smallest model number accepted by MONAD?

Proposed solution: same solution but picking the smallest numbers for each digit which make a valid model number

❯ python3 solution24.py input24 14691271141118
{'w': 0, 'x': 0, 'y': 0, 'z': 0}
{'w': '1', 'x': 1, 'y': 10, 'z': 10}
{'w': '4', 'x': 1, 'y': 5, 'z': 265}
{'w': '6', 'x': 1, 'y': 17, 'z': 6907}
{'w': '9', 'x': 1, 'y': 12, 'z': 179594}
{'w': '1', 'x': 0, 'y': 0, 'z': 6907}
{'w': '2', 'x': 1, 'y': 7, 'z': 179589}
{'w': '7', 'x': 1, 'y': 7, 'z': 4669321}
{'w': '1', 'x': 0, 'y': 0, 'z': 179589}
{'w': '1', 'x': 1, 'y': 10, 'z': 4669324}
{'w': '4', 'x': 0, 'y': 0, 'z': 179589}
{'w': '1', 'x': 0, 'y': 0, 'z': 6907}
{'w': '1', 'x': 0, 'y': 0, 'z': 265}
{'w': '1', 'x': 0, 'y': 0, 'z': 10}
{'w': '8', 'x': 0, 'y': 0, 'z': 0}