Dazbo's Advent of Code solutions, written in Python
Oh, this one looks easy enough. Wrong!
I just need to write an ALU simulator that knows how to process some instructions. Wrong!
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.
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.
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?
ALU
object, we initialise our four variables to 0, in dict._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 an inp
instruction._ip
- that points to the current instruction being processed in the program.vars
to allow an external program to read the current value of any of the variables.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
).run_program()
method, which expects the 14 digit value as input. It then iterates through all instruction pairs, running _execute_instruction()
for each.
_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 a str
, in order to identify any attribute (or method) that matches the str
passed in.ALU
class, such as _op_inp()
, op_add()
, op_mul()
. So, when we do something like self.__getattribute__(f"_op_{instr}")
, passing in the instr
type 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.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?
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 5div z 1 div z 1 div z 1 div z 1 div z 26 6add 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 16add 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:
inp
, add
, mul
) are identical between blocks.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 = z_{0} 4 mod x 26 mod x 26 mod x 26 mod x 26 mod x 26 x = z_{0} % 26 5div z 1 div z 1 div z 1 div z 1 div z 26 z_{1} = z_{0} // var1 6add x 12 add x 12 add x 13 add x 12 add x -3 x = z_{0} % 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 z_{2} = 26(z_{0} // var1) if x == 1, else z_{0} // 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 16add 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(z_{0} // var1) + w + var3 if x == 1, else 26(z_{0} // var1)
Some important observations:
w
with each block.x
and y
are both reset in each block before we do anything with them. Thus, the final values of x
and y
from the previous block are irrelevant.z
, using the previous value of z
.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:
Thus, there appear to be two types of block.
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 = z_{0} 4 mod x 26 x = z_{0} % 26 5div z 1 z_{1} = z_{0} 6add x 14 x = z_{0} % 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 z_{2} = 26z_{0} 14 mul y 0 y = 0 (Reset y) 15 add y w y = w 16add y 7 y = w + var3 17 mul y x y = w + var3 18 add z y z = 26z_{0} + w + var3
In summary:
\(z_{next} = 26z_{prev} + w + a\)
Where \(a\) is the variable from instruction 16.
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 = z_{0} 4 mod x 26 x = z_{0} % 26 5div z 26 z_{1} = z_{0} // 26 6add x -3 x = z_{0} % 26 + var2 7 eql x w x = 1 if w == z_{0} % 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 z_{0} // 26 if x == 0, else z_{2} = z_{0} 14 mul y 0 y = 0 (Reset y) 15 add y w y = w 16add y 6 y = w + var3 17 mul y x y = 0 if x == 0, else y = w + var3 18 add z y z = z_{0} // 26 if x == 0, else z = z_{0} + 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\)
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.
x
to be 0 at instruction 17, then x
has been set to 0 by instruction 8 (eql x 0
).x
has been set to 0 by instruction 8, then x
must have been set to 1 by instruction 7 (eql x w
).x
has been set to 1 by instruction 7, then x
must have been set to a value equal to w
by 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\)
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:
list
. It does this using a for
loop, where:
list
of program lines, multiplying the slice start and slice start by the iteration count.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:
lists
. One for each of the three variable instructions:
div_z_instructions
contains instruction 5 from each block.add_x_instruction
contains instruction 6 from each block.add_y_instruction
contains instruction 16 from each block.div z 26
, then we store 26
in div_z_instructions
.list
of Bool
values, 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 the div z
instruction value for type 2 blocks is always 26. Thus, our new list
is False
whenever the div z
variable is 1, and True
whenever the div z
variable is 26.zip
up three variables, i.e. the boolean (that is based on the div z
variable), the add x
variable, and the add y
variable. Thus we end up with a list
of 14 tuples
, where each one looks something like (False, 12, 7)
.Here’s the clever bit…
product()
to generate a list
(called any_digits
) of tuples
, 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)
z
to shrink.any_digits
values. There are only 9
^{7} = 4782969
of them. (Not 9999999
, because we’re only working with digits 1-9, not 0-9.) For each:
z
to 0.[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
list
to store valid computed serial numbers.z
to be z // 26
, as required for the next block.any_digits
.z
to be (26 * z) + digits_candidate[digits_idx] + add_y
, as required for the next block.list
of individual int
values to a str
, and then to an int
. Add this to our valid
list.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)
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.