Advent of Code 2015

Day 23: Opening the Turing Lock

CPU Registers

Problem Intro

Thank God!

After the horrendous experience from yesterday, it was such a relief to have a simple task that didn’t take… well, forever!

We’re told we have a computer that has two regiters and understands six different instructions. The registers are named a and b and can store non-negative integers. Both registers start with their value set to 0.

Our six instructions are as follows:

Instruction Action
hlf r Halves the value in register r, then on to next instruction.
tpl r Triples the value in register r, then on to next instruction.
inc r Increments the value of register r by 1, then on to next instruction.
jmp sn Continues with the instruction at location i +/- n, where i is the current instruction,
and s is either + or -.
jie r, sn “jump if even” - like jmp n, but only jumps if register r contains an even value.
jio r, sn “jump if one” - like jmp n, but only jumps if register r = 1.

We’re given a sample program that looks like this:

inc a
jio a, +2
tpl a
inc a

Part 1

What is the value in register b when the program in your puzzle input is finished executing?

Okay, so this is a pretty simple problem. My strategy is to create a Computer class that:

  • Represents the values stored in two registers.
  • Is able to set and retrieve the register values.
  • Stores an instruction_ptr variable, i.e. a variable that points to the current instruction in the program.
  • Is able to execute the instructions in the supplied program, jumping to different instructions as required.

I start with an Instructions class, which stores contains the instructions our computer can execute.

class Instructions():
    """ Define an instruction set, made up of instruction constants """
    JMP = "jmp"
    JIO = "jio"
    JIE = "jie"
    HLF = "hlf"
    TPL = "tpl"
    INC = "inc"

    @staticmethod
    def _hlf(x):
        return x // 2

    @staticmethod
    def _tpl(x):
        return x * 3
    
    @staticmethod
    def _inc(x):
        return x + 1

    @classmethod
    def execute(cls, instr, x):
        """ Dispatch to the specified instruction, with the specified value """
        method = getattr(cls, f'_{instr}', None)
        if method:
            return method(x)
        raise ValueError(f"Invalid instruction: {instr}") 

This class defines six constants, representing the six allowed instructions. It also provides three static methods, represeting the three “non-jumping” instructions. These are static, because these instructions simply take a value and do something to it. They don’t rely on any other methods or values stored in the Instructions class.

And this class includes an execute() method, which dispatches to the appropriate static method, depending on which instructions was passed as an argument. For example, if we call Instructions.execute("jmp", 4) then this method retrieves the method called _jmp, and then calls it, passing in 4 as an argument.

If we try to execute an instruction that doesn’t exist, then we raise ValueError.

Another interesting way we could have achieved the same thing is by using lambda functions, like this:

    _methods = {
        HLF: lambda x: x // 2, 
        TPL: lambda x: x * 3, 
        INC: lambda x: x + 1
    }

    @classmethod
    def execute(cls, instr, x):
        """ Dispatch to the specified instruction, with the specified value """
        if instr in cls._methods:
            return cls._methods[instr](x)
        raise ValueError(f"Invalid instruction: {instr}") 

Now I’ll create the Computer class:

class Computer:
    """ Simulate a computer with 2 registers """
    
    def __init__(self, init_val: int = 0) -> None:
        self._registers = {
            'a': init_val,
            'b': init_val
        }
        self._instruction_ptr = 0
    
    @property
    def registers(self):
        """ Return the registers """
        return self._registers
    
    def get_register_value(self, register: str):
        return self._registers[register]
    
    def set_register_value(self, register: str, val: int):
        self._registers[register] = val

    def run_program(self, program):
        """ Execute the specified program """

        # exit the loop when we reach an instruction that does not exist
        while self._instruction_ptr < len(program):
            program_line = program[self._instruction_ptr]
            parts = program_line.split(" ", 1) # split at the first space only
            instr = parts[0]
            instr_args = [arg.strip() for arg in parts[1].split(',')]
            
            if instr == Instructions.JMP: # e.g. jmp +19
                self._instruction_ptr += int(instr_args[0])
                continue
            
            # all other instructions have a register argument
            reg = instr_args[0]
            if instr == Instructions.JIE: # jie a, +4
                # jump if reg is even
                if self.get_register_value(reg) % 2 == 0:
                    self._instruction_ptr += int(instr_args[1])
                    continue
            elif instr == Instructions.JIO: # jio a, +8
                # jump if reg is ONE
                if self.get_register_value(reg) == 1:
                    self._instruction_ptr += int(instr_args[1])
                    continue
            else:
                try:
                    self.set_register_value(reg, Instructions.execute(instr, self.get_register_value(reg)))
                except ValueError as e:
                    e_val = e.args[0] if e.args else str(e)
                    raise ValueError(f"{e_val} at instruction {self._instruction_ptr}") from e

            self._instruction_ptr += 1

Things to say about this…

  • The registers are stored as a dictionary, and initialised to 0 in the __init__() method.
  • We also initialise the _instruction_ptr to 0, i.e. to point to the first line.
  • We run a program by passing the input program as an argument.
    • It executes each line, until there are no more lines.
    • It splits the current instruction at the first space, into two parts: i.e. the instruction into parts[0] and the rest of the line into parts[1].
    • We then further split parts[1], if it contains any ",".
    • If we read a JMP, JIE or JIO instruction, then we update the instruction pointer to point to the appropriate next instruction, and then continue` to the next loop iteration.
    • If the instruction is not JMP, JIE or JIO, then pass the instruction and the register value to the Instructions.execute(), which will dispatch as required.
    • If we haven’t continued the loop yet, we add one to the instruction pointer, then loop.

All that remains is to read in the input file, and pass it as instructions to our computer.

def main():
    # with open(locations.sample_input_file, mode="rt") as f:
    with open(locations.input_file, mode="rt") as f:
        data = f.read().splitlines()
    
    computer = Computer()        
    computer.run_program(data)
    
    for reg_key, reg_val in computer.registers.items():
        logger.info(f"Register {reg_key}: {reg_val}")

I.e. read the computer program, create a Computer, and execute the program by passing it to run_program(). Then retrieve teh register values to solve for Part 1.

Part 2

We’re asked to re-run our program, but initialising register a with a value of 1, rather than 0.

The changes here are trivial!

def main():
    # with open(locations.sample_input_file, mode="rt") as f:
    with open(locations.input_file, mode="rt") as f:
        data = f.read().splitlines()
    
    run_part(1, data)
    run_part(2, data)
    
def run_part(part_num, program):
    computer = Computer()
    if part_num == 2:
        computer.set_register_value('a', 1)
        
    computer.run_program(program)
    
    logger.info("PART %d:", part_num)
    for reg_key, reg_val in computer.registers.items():
        logger.info(f"Register {reg_key}: {reg_val}")
    
    logger.info(".")

I’ve just extracted the actual computer execution to a separate method, called run_part(). If we pass in 2 for the part, then our code initialises register a to a value of 1. It then runs the program, as before.

Results

Hurah, it works! Here’s the output:

15:20:48.992:computer - INF: PART 1:
15:20:48.993:computer - INF: Register a: 1
15:20:48.993:computer - INF: Register b: 255
15:20:48.993:computer - INF: .
15:20:48.995:computer - INF: PART 2:
15:20:48.996:computer - INF: Register a: 1
15:20:48.996:computer - INF: Register b: 334
15:20:48.996:computer - INF: .
15:20:48.997:computer - INF: Execution time: 0.006 seconds

Not much code, and it runs pretty fast too!