Problem Intro
Oh, this one looks easy enough. Wrong!
I just need to write an ALU simulator that knows how to process some instructions. Wrong!
Overview
We’re told that the sub runs off an arithmetic logic unit that takes four integer variables (w, x, y, and z), and is capable of performing dix different instructions with these variables.
The ALU processes programs, which are sets of instructions. The instructions are procesed in order, from beginning to end.
We’re given a few sample input programs. Like this one:
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
We’re told we need to use our ALU to validate the sum’s model number. We’re given a program called MONAD which takes any 14-digit number (where the digits must be 1 to 9, inclusive), and processes the number. My actual MONAD data, for example, 14 inp w instructions.
We’re told a given model number is only valid if, after processing all the instructions in the MONAD program, variable z is set to 0.
Part 1
What is the largest model number accepted by MONAD?
So the goal is to find the largest possible 14-digit number which results in a z value of 0, after running the number through our program.
The ALU Simulator
Having done a few AOCs before, I jumped straight to writing an ALU simulator. (Spoiler alert: this was a mistake!)
class ALU():
""" Simulate processor with four registers and six instructions """
def __init__(self) -> None:
self._vars = {'w': 0, 'x': 0, 'y': 0, 'z': 0}
self._input = None
self._input_posn = 0 # which digit of the input value we're currently on
self._instructions: list[tuple[str, list[str]]] = [] # list of instructions in the format [instr, [parms]]
self._ip = 0
@property
def vars(self):
return self._vars
def _set_input(self, value: str):
""" Take a number and store as a str representation """
assert value.isdigit, "Must be number"
assert len(value) == 14, "Must be 14 digit input"
self._input = value
self._input_posn = 0
def _set_var(self, var, value):
""" Sets the specified var to the specified value. """
if var not in self._vars:
raise KeyError(f"No such var '{var}'")
self._vars[var] = value
def _reset(self):
for var in self._vars:
self._vars[var] = 0
self._input = None
self._input_posn = 0
self._ip = 0
def run_program(self, input_str: str):
""" Process instructions in the program. """
self._reset()
self._set_input(input_str)
for instruction in self._instructions:
self._execute_instruction(instruction)
self._ip += 1
def set_program(self, instructions_input: list[str]):
""" Create a list of instructions,
where each instruction is of the format: (str, list[str]) """
self._instructions = []
for line in instructions_input:
instr_parts = line.split()
instr = instr_parts[0]
instr_parms = instr_parts[1:]
self._instructions.append((instr, instr_parms))
def _execute_instruction(self, instruction:tuple[str, list[str]]):
""" Takes an instruction, and calls the appropriate implementation method.
Args:
instr_and_parms (list): The instruction, in the format (instr, [parms])
Raises:
AttributeError if instruction is not understood
"""
# logger.debug("Instruction: %s", instruction)
instr = instruction[0]
instr_parms = instruction[1]
# call the appropriate instruction method
try:
self.__getattribute__(f"_op_{instr}")(instr_parms)
except AttributeError as err:
raise AttributeError(f"Bad instruction {instr} at {self._ip}") from err
def int_or_reg_val(self, x) -> int:
""" Determine if the variable is an int value, or the value is a register """
if x in self._vars:
return self._vars[x]
else:
return int(x)
def _op_inp(self, parms:list[str]):
var = parms[0]
assert self._input, "Input value not set"
assert self._input_posn < len(self._input), "Too many input digits!"
input_digit = int(self._input[self._input_posn])
self._vars[var] = input_digit
self._input_posn += 1
def _op_add(self, parms:list[str]):
""" Add a to b and store in a. Param b could be a var or a number. """
self._vars[parms[0]] += self.int_or_reg_val(parms[1])
def _op_mul(self, parms:list[str]):
""" Multiply a by b and store in a. Param b could be a var or a number. """
self._vars[parms[0]] *= self.int_or_reg_val(parms[1])
def _op_div(self, parms:list[str]):
""" Divide a by b and store in a. Param b could be a var or a number. """
parm_b = self.int_or_reg_val(parms[1])
assert parm_b != 0, "Integer division by 0 is bad."
self._vars[parms[0]] //= parm_b
def _op_mod(self, parms:list[str]):
""" Modulo a by b and store in a. Param b could be a var or a number. """
parm_a = self._vars[parms[0]]
parm_b = self.int_or_reg_val(parms[1])
try:
assert parm_a >= 0 and parm_b != 0, "Integer division by 0 is bad."
self._vars[parms[0]] %= parm_b
except AssertionError as err:
raise AttributeError(f"Bad instruction: {parm_a} mod {parm_b}") from err
def _op_eql(self, parms:list[str]):
""" Chec if a and b are equal. Store 1 if equal. Param b could be a var or a number. """
self._vars[parms[0]] = 1 if self._vars[parms[0]] == self.int_or_reg_val(parms[1]) else 0
def __repr__(self):
return f"{self.__class__.__name__}{self._vars}"
So what does this do?
- When we create an
ALUobject, we initialise our four variables to 0, in dict. - We maintain an index pointer -
_input_posn- that points to the position of the current digit being processed, in our 14-digit number. Recall that we act on one digit at a time from this number, every time we see aninpinstruction. - We also maintain an instruction pointer -
_ip- that points to the current instruction being processed in the program. - We have a convenience property,
varsto allow an external program to read the current value of any of the variables. - We define the program that the ALU will run, by running
set_program(), passing in a list of of instructions. This takes each instruction line, and converts each to an instruction part (instr), and a parameters part (instr_parms). - We run the input program using the
run_program()method, which expects the 14 digit value as input. It then iterates through all instruction pairs, running_execute_instruction()for each.- Within the
_execute_instruction(), we now do a bit of introspection. This is where we use Python to examine its own objects at run time, in order to determine information about those objects. Specifically, we’re using the__getattribute__()method, and passing in astr, in order to identify any attribute (or method) that matches thestrpassed in. - We’ve created a number of methods in the
ALUclass, such as_op_inp(),op_add(),op_mul(). So, when we do something likeself.__getattribute__(f"_op_{instr}"), passing in theinstrtype from the current instruction, Python actually returns the method with that name, and runs it!! Thus, this is a clever way to map a bunch of method names to a bunch of instructions.
- Within the
Great! So now all we have to do is create the ALU, initialise the program to our set of instructions, and then run it with every possible 14 digit number that doesn’t contain a 0. We could do something like this:
input_file = os.path.join(SCRIPT_DIR, INPUT_FILE)
with open(input_file, mode="rt") as f:
data = f.read().splitlines()
alu = ALU()
alu.set_program(data)
for int_val in tqdm(range(99999999999999, 11111111111110, -1)):
val = str(int_val)
if '0' in val:
continue
alu.run_program(val)
if alu.vars['z'] == 0:
logger.info("%s verified.", val)
As I’ve done with an earlier program, I’ve wrapped my for loop with tqdm, in order to give me a progress bar for this long running loop. Usefully, the progress bar includes an estimated completion time. So yeah… It’s going to take about 200 years. We’re going to need a bigger boat. Or a better solution.
TIME TO THROW ALL THAT AWAY!
So, what have we learned? We’ve learned that running each instruction in MONAD is going to take too long. So instead…
Maybe we need to determine what MONAD is actually trying to do, and come up with a more efficient way to do that?
Understanding What MONAD Does
When I examine my MONAD input, it turns out that the program is made up of 14 repeating blocks of 18 nearly identical lines. Here I’m showing the first 5 repeats, side by side…
1 2 3 4 5
-------- -------- -------- -------- --------
1 inp w inp w inp w inp w inp w
2 mul x 0 mul x 0 mul x 0 mul x 0 mul x 0
3 add x z add x z add x z add x z add x z
4 mod x 26 mod x 26 mod x 26 mod x 26 mod x 26
5 div z 1 div z 1 div z 1 div z 1 div z 26
6 add x 12 add x 12 add x 13 add x 12 add x -3
7 eql x w eql x w eql x w eql x w eql x w
8 eql x 0 eql x 0 eql x 0 eql x 0 eql x 0
9 mul y 0 mul y 0 mul y 0 mul y 0 mul y 0
10 add y 25 add y 25 add y 25 add y 25 add y 25
11 mul y x mul y x mul y x mul y x mul y x
12 add y 1 add y 1 add y 1 add y 1 add y 1
13 mul z y mul z y mul z y mul z y mul z y
14 mul y 0 mul y 0 mul y 0 mul y 0 mul y 0
15 add y w add y w add y w add y w add y w
16 add y 7 add y 8 add y 2 add y 11 add y 6
17 mul y x mul y x mul y x mul y x mul y x
18 add z y add z y add z y add z y add z y
Here’s what we know:
- There are 14 repeats.
- Each repeat is a set of 18 instructions. I’ll refer any given set of 18 instructions as a block.
- The sequence of instruction operations (e.g.
inp,add,mul) are identical between blocks. - 3 of the instructions show variance in their variables. In my data: these are the 5th, 6th and 16th instructions (which have been coloured in the example above).
So, what do the blocks do?
I’ve rewritten these instructions, along with their net effect:
1 2 3 4 Result?
-------- -------- -------- -------- -------- ------------
1 inp w inp w inp w inp w inp w Input w (Any number 1 through 9)
2 mul x 0 mul x 0 mul x 0 mul x 0 mul x 0 x = 0 (Reset x)
3 add x z add x z add x z add x z add x z x = z0
4 mod x 26 mod x 26 mod x 26 mod x 26 mod x 26 x = z0 % 26
5 div z 1 div z 1 div z 1 div z 1 div z 26 z1 = z0 // var1
6 add x 12 add x 12 add x 13 add x 12 add x -3 x = z0 % 26 + var2
7 eql x w eql x w eql x w eql x w eql x w x = 1 if x == w (input), else 0
8 eql x 0 eql x 0 eql x 0 eql x 0 eql x 0 x = 0 if x == 1, else 1
9 mul y 0 mul y 0 mul y 0 mul y 0 mul y 0 y = 0 (Reset y)
10 add y 25 add y 25 add y 25 add y 25 add y 25 y = 25
11 mul y x mul y x mul y x mul y x mul y x y = 25 if x == 1, else 0
12 add y 1 add y 1 add y 1 add y 1 add y 1 y = 26 if x == 1, else 1
13 mul z y mul z y mul z y mul z y mul z y z2 = 26(z0 // var1) if x == 1, else z0 // var1
14 mul y 0 mul y 0 mul y 0 mul y 0 mul y 0 y = 0 (Reset y)
15 add y w add y w add y w add y w add y w y = w
16 add y 7 add y 8 add y 2 add y 11 add y 6 y = w + var3
17 mul y x mul y x mul y x mul y x mul y x y = w + var3 if x == 1, else 0
18 add z y add z y add z y add z y add z y z = 26(z0 // var1) + w + var3 if x == 1, else 26(z0 // var1)
Some important observations:
- We read our next digit into
wwith each block. xandyare both reset in each block before we do anything with them. Thus, the final values ofxandyfrom the previous block are irrelevant.- Each block updates the value of
z, using the previous value ofz.
Thus z is the only variable that persists between blocks.
That’s handy, since z is the value we ultimately care about. Recall that our goal is for z to be 0 when MONAD has finished.
Let’s look at the 14 possible values of the 3 variables:
var1 var2 var3 ---- ---- ---- 1 12 8 1 13 2 1 12 11 1 12 7 26 -3 6 1 10 12 1 14 14 26 -16 13 1 12 15 26 -8 10 26 -12 6 26 -7 10 26 -6 8 26 -11 5
Some observations:
- var1 can either be 1 or 26. In our 14 blocks, there are 7 of each.
- var2 is:
- A positive integer >9, when var1 is 1.
- A negative integer, when _var_1 is 26.
- var3 is a variable positive integer.
Thus, there appear to be two types of block.
Type 1 Block: var1 is 1, var2 > 9
Block Result?
-------- ------------
1 inp w Input w (Any number 1 through 9)
2 mul x 0 x = 0 (Reset x)
3 add x z x = z0
4 mod x 26 x = z0 % 26
5 div z 1 z1 = z0
6 add x 14 x = z0 % 26 + var2
7 eql x w x = 0, since w is always <= 9, but var2 is always > 9.
8 eql x 0 x = 1
9 mul y 0 y = 0 (Reset y)
10 add y 25 y = 25
11 mul y x y = 25
12 add y 1 y = 26
13 mul z y z2 = 26z0
14 mul y 0 y = 0 (Reset y)
15 add y w y = w
16 add y 7 y = w + var3
17 mul y x y = w + var3
18 add z y z = 26z0 + w + var3
In summary:
\(z_{next} = 26z_{prev} + w + a\)
Where \(a\) is the variable from instruction 16.
Type 2 Block: var1 is 26, var2 is negative
Block Result?
-------- --------
1 inp w Input w (Any number 1 through 9)
2 mul x 0 x = 0 (Reset x)
3 add x z x = z0
4 mod x 26 x = z0 % 26
5 div z 26 z1 = z0 // 26
6 add x -3 x = z0 % 26 + var2
7 eql x w x = 1 if w == z0 % 26 + var2, else 0
8 eql x 0 x = 0 if x == 1, else 1
9 mul y 0 y = 0 (Reset y)
10 add y 25 y = 25
11 mul y x y = 0 if x == 0, else 25
12 add y 1 y = 1 if x == 0, else 26
13 mul z y z0 // 26 if x == 0, else z2 = z0
14 mul y 0 y = 0 (Reset y)
15 add y w y = w
16 add y 6 y = w + var3
17 mul y x y = 0 if x == 0, else y = w + var3
18 add z y z = z0 // 26 if x == 0, else z = z0 + w + var3
Thus, there are two possible outcomes of a Type 2 block:
When final \(x\) == 0: \(z_{next} = z_{prev} // 26\)
When final \(x\) == 1: \(z_{next} = z_{prev} + w + a\)
What Have We Learned?
Half the blocks are type 1. Each block results in a new value of z, according to the equation:
\(z_{next} = 26z_{prev} + w + a\)
I.e. z gets multiplied by 26, plus a constant. Thus, type 1 blocks result in z getting much larger.
Half the blocks are type 2. Each block results in a new value of z, according to the equations:
-
\(z_{next} = z_{prev} // 26\), when \(x\)
== 0 -
\(z_{next} = z_{prev} + w + a\), when \(x\)
== 1
The first equation results in z getting much smaller. Whereas the second equations results in z getting larger.
So, in order for z to be 0 at the end of MONAD, we need all the type 2 blocks to result in z getting smaller. And thus, all type 2 blocks require x to be equal to 0 when instruction 17 (mul y x) is run in each block.
How do we ensure that x == 0 at instruction 17?
- For
xto be 0 at instruction 17, thenxhas been set to 0 by instruction 8 (eql x 0). - If
xhas been set to 0 by instruction 8, thenxmust have been set to 1 by instruction 7 (eql x w). - If
xhas been set to 1 by instruction 7, thenxmust have been set to a value equal towby instruction 6 (add x var2)
So now we have enough information to determine what value of w we need, in order for z to shrink in any block 2:
\(w = x = (z \;\mathrm{mod}\; 26) + var2\)
The Solution
First, let’s read the data, and split it into our 14 blocks:
input_file = os.path.join(SCRIPT_DIR, INPUT_FILE)
with open(input_file, mode="rt") as f:
data = f.read().splitlines()
COUNT_INSTRUCTION_BLOCKS = 14
EXPECTED_INSTRUCTIONS_PER_BLOCK = 18
instruction_block_size = len(data) // COUNT_INSTRUCTION_BLOCKS
assert instruction_block_size == EXPECTED_INSTRUCTIONS_PER_BLOCK
# Split all instructions into repeating blocks of instructions
instruction_blocks: list[list[str]] = []
for i in range(COUNT_INSTRUCTION_BLOCKS):
instruction_blocks.append(data[i*instruction_block_size:(i+1)*instruction_block_size])
alu = ALU()
alu.set_program(data)
valid_vals = compute_valid_inputs(instruction_blocks)
This code:
- Reads all the data and splits into separate lines.
- Checks that the total number of lines divided by the 14 results in our expected block size, i.e. 18.
- Splits our instruction lines in 14 blocks, where each block is itself a
list. It does this using aforloop, where:- We iterate 14 times.
- With each iteration:
- We slice the original
listof program lines, multiplying the slice start and slice start by the iteration count. - E.g. slicing from lines 0 to 18, 18 to 36, 36 to 54, etc.
- We slice the original
We then pass all 14 blocks into the compute_valid_inputs() function:
def compute_valid_inputs(instruction_blocks: list[list[str]]) -> list[int]:
""" Our goal is determine valid values of w,
where w is each successive digit of the 14-digit input value.
The 14 input values are used in the 14 blocks of instructions. """
# instruction types, based on "div z" instruction parameter
SHRINKAGE = 26
div_z_instructions = []
add_x_instructions = []
add_y_instructions = []
for block in instruction_blocks:
# Retrieve the param value from each instruction
# The instructions we care about are at specific locations in the block
div_z_instructions.append(int(block[4].split()[-1]))
add_x_instructions.append(int(block[5].split()[-1]))
add_y_instructions.append(int(block[15].split()[-1]))
# Values of these variables in our input data
# z [1, 1, 1, 1, 26, 1, 1, 26, 1, 26, 26, 26, 26, 26]
# x [12, 12, 13, 12, -3, 10, 14, -16, 12, -8, -12, -7, -6, -11]
# y [7, 8, 2, 11, 6, 12, 14, 13, 15, 10, 6, 10, 8, 5]
# E.g. [False, False, False, False, True...]
shrink_instructions = [z == SHRINKAGE for z in div_z_instructions]
shrink_count = sum(x for x in shrink_instructions)
assert shrink_count == 7, "We expect 7 shrink types for our input"
# list of tuples by index, e.g. (False, 12, 7)
instruction_vars = list(zip(shrink_instructions, add_x_instructions, add_y_instructions))
# Get the cartesian product of all digits where any digit is possible
# E.g. 9999999, 9999998, 9999997, etc
any_digits = list(product(range(9, 0, -1), repeat=shrink_count))
assert len(any_digits) == 9**shrink_count, "Cartesian product messed up"
valid: list[int] = [] # Store valid 14-digit input values
for digits_candidate in tqdm(any_digits):
num_blocks = len(instruction_blocks)
z = 0
digit = [0] * num_blocks
early_exit = False
digits_idx = 0
for block_idx in range(num_blocks):
is_shrink, add_x, add_y = instruction_vars[block_idx]
if is_shrink:
# We want to compute a value w, where w = (z % 26) + a
digit[block_idx] = ((z % 26) + add_x) # digit[block_idx] = w
z //= 26 # New z is given by z = z//26
if not (1 <= digit[block_idx] <= 9):
early_exit = True
break
else: # expansion type, so just use the candidate digit
z = (26 * z) + digits_candidate[digits_idx] + add_y
digit[block_idx] = digits_candidate[digits_idx]
digits_idx += 1
if not early_exit:
valid.append(int("".join(str(i) for i in digit)))
return valid
This code:
- Creates three
lists. One for each of the three variable instructions:div_z_instructionscontains instruction 5 from each block.add_x_instructioncontains instruction 6 from each block.add_y_instructioncontains instruction 16 from each block.
- For each list, store only the variable value. E.g. if the instruction were
div z 26, then we store26indiv_z_instructions. - Build a
listofBoolvalues, to represent whether the current instruction is a type 2 block (aka a potential shrink z block), or whether it is a type 1 block. Recall that thediv zinstruction value for type 2 blocks is always 26. Thus, our newlistisFalsewhenever thediv zvariable is 1, andTruewhenever thediv zvariable is 26. - For each block,
zipup three variables, i.e. the boolean (that is based on thediv zvariable), theadd xvariable, and theadd yvariable. Thus we end up with alistof 14tuples, where each one looks something like(False, 12, 7).
Here’s the clever bit…
- We know that 7 of the 14 digits of our serial number will be processed by a type 1 block.
- For these, we just have to try every allowed value. Thus 7 digits, where each digit can be 1-9 (inclusive).
- I’ve used a cartesian
product()to generate alist(calledany_digits) oftuples, where each tuple contains a unique 7 digit combination. E.g.
(9, 9, 9, 9, 9, 9, 9)
(9, 9, 9, 9, 9, 9, 8)
(9, 9, 9, 9, 9, 9, 7)
Etc. - And the other 7 of the 14 digits will be processed by a type 2 block. For these, we can compute the digit value that we need in order for
zto shrink.
- We iterate through all possible
any_digitsvalues. There are only97= 4782969of them. (Not9999999, because we’re only working with digits 1-9, not 0-9.) For each:- Start by initialising
zto 0. - Create a 14-digit candidate number template, which looks like
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] - Create a
listto store valid computed serial numbers. - Iterate through the 14 blocks. For each:
- If a type 2 (shrink) block, then:
- Set the digit in this position of the 14-digit serial number to be the computed necessary value.
- If the computed value is not in the range 1-9, then this value is no good, so exit the loop and move on to the next candidate serial number.
- Else, the computed value is good. Set
zto bez // 26, as required for the next block.
- If a type 1 (expansion) block, then:
- Set the digit in this position of the 14-digit serial number to be the next available digit from our current 7-digit value from
any_digits. - Then set
zto be(26 * z) + digits_candidate[digits_idx] + add_y, as required for the next block.
- Set the digit in this position of the 14-digit serial number to be the next available digit from our current 7-digit value from
- If a type 2 (shrink) block, then:
- If we managed to process each block without an early exit, then the computed 14-digit serial number is valid. Convert the
listof individualintvalues to astr, and then to anint. Add this to ourvalidlist.
- Start by initialising
Finally, return the valid list; i.e. all the valid serial numbers, as integer values.
Recall that Part 1 has asked us to determine the largest model number accepted by MONAD. So, we just need to determine the largest value of our valid values. That’s easy…
if valid_vals:
max_input_val = max(valid_vals)
Part 2
What is the smallest model number accepted by MONAD?
I can’t tell you how relieved I am about that!!
All we need to do is add one line…
if valid_vals:
max_input_val = max(valid_vals)
min_input_val = max(valid_vals)
But for completeness, and so that my ALU simulator was not completely wasted, I’ve run my min and max values through the ALU, to verify it produces a 0 result.
So the final code looks like this:
alu = ALU()
alu.set_program(data)
valid_vals = compute_valid_inputs(instruction_blocks)
if valid_vals:
max_input_val = max(valid_vals)
min_input_val = min(valid_vals)
# check them by running them through the ALU
for val in (min_input_val, max_input_val):
alu.run_program(str(val))
if alu.vars['z'] == 0:
logger.info("%s verified.", val)
else:
logger.info("%s does not work??")
else:
logger.info("Fail bus, all aboard.")
And the output looks like this:
100%|███████████████████████████████████████████████████████████| 4782969/4782969 [00:05<00:00, 908376.41it/s]
08:27:28.010:INFO:__main__: 51619131181131 verified.
08:27:28.010:INFO:__main__: 97919997299495 verified.
08:27:28.010:INFO:__main__: Execution time: 5.7623 seconds
Wow. What a horrendous day.