Advent of Code 2021

Day 24: Arithmetic Logic Unit

introspection ↗ tqdm progress bar
ALU

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 ALU object, 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 an inp instruction.
  • We also maintain an instruction pointer - _ip - that points to the current instruction being processed in the program.
  • We have a convenience property, vars to 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 a str, in order to identify any attribute (or method) that matches the str passed in.
    • We’ve created a number of methods in the 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?

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 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.
  • Each block updates the value of 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:

  • 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:

  1. \(z_{next} = z_{prev} // 26\), when \(x\) == 0

  2. \(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 x to be 0 at instruction 17, then x has been set to 0 by instruction 8 (eql x 0).
  • If x has been set to 0 by instruction 8, then x must have been set to 1 by instruction 7 (eql x w).
  • If 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\)

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 a for loop, where:
    • We iterate 14 times.
    • With each iteration:
      • We slice the original list of 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 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_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.
  • For each list, store only the variable value. E.g. if the instruction were div z 26, then we store 26 in div_z_instructions.
  • Build a 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.
  • For each block, 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…

  • 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 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)
      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 z to shrink.
  • We iterate through all possible any_digits values. There are only 97 = 4782969 of them. (Not 9999999, because we’re only working with digits 1-9, not 0-9.) For each:
    • Start by initialising z to 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 list to 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 z to be z // 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 z to be (26 * z) + digits_candidate[digits_idx] + add_y, as required for the next block.
    • If we managed to process each block without an early exit, then the computed 14-digit serial number is valid. Convert the 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)

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.