Advent of Code 2016 - Day 23

Useful Links

Concepts and Packages Demonstrated

Problem Intro

We’re back with the Assembunny computer from Day 12! This time, we have a new instruction: tgl x. This instruction toggles the instruction x instructions away from the current one.

The toggle logic is as follows:

For one-argument instructions, inc becomes dec, and all others become inc.
For two-argument instructions, jnz becomes cpy, and all others become jnz.

Our goal is to run the Assembunny program and find the value in register a.

Part 1

With register a starting at 7, what value is left in register a?

My approach is to extend the Computer class from Day 12. I’ll create a new class, Assembunny2, that inherits from Computer and adds the _op_tgl method.

class Assembunny2(Computer):
    def _op_tgl(self, instr_params:list):
        tgl_param = instr_params[0]
        offset = tgl_param if isinstance(tgl_param, int) else self.registers[tgl_param]
        
        if self._ip + offset >= len(self._instructions):
            return
        
        old_instr, params = self._instructions[self._ip + offset]
        if len(params) == 1:
            if old_instr == "inc":
                self._instructions[self._ip + offset][0] = "dec"
            else:
                self._instructions[self._ip + offset][0] = "inc"
        elif len(params) == 2:
            if old_instr == "jnz":
                self._instructions[self._ip + offset][0] = "cpy"
            else:
                self._instructions[self._ip + offset][0] = "jnz"

This method implements the toggle logic as described in the puzzle. The rest of the Computer class remains the same.

Part 2

With register a starting at 12, what value is left in register a?

Running the program with a set to 12 takes a very long time. This is a strong hint that there’s an inefficient loop in the Assembunny code that needs to be optimized.

By inspecting the instructions, I found patterns that correspond to multiplication and addition. For example, a sequence like inc a, dec b, jnz b -2 is equivalent to a += b. Similarly, there’s a pattern for multiplication.

To optimize this, I created another subclass, MultiplyingAssembunny, which overrides the run_program method. Before running the program, it uses regular expressions to find and replace these inefficient patterns with new, more efficient instructions: add and mul.

class MultiplyingAssembunny(Assembunny2):
    def run_program(self, instructions_input: list):
        new_instructions = self.optimise(instructions_input)
        super().run_program(new_instructions)
    
    def optimise(self, instructions_input: list) -> list[str]:
        code = '\n'.join(line for line in instructions_input)

        replacements = [
            (   # Multiplication
                r'inc ([a-d])\ndec ([a-d])\njnz \2 -2\ndec ([a-d])\njnz \3 -5',
                r'mul \2 \3 \1\ncpy 0 \2\ncpy 0 \3\nnop\nnop',
            ), 
            (   # Addition
                r'inc ([a-d])\ndec ([a-d])\njnz \2 -2',
                r'add \1 \2 \1\ncpy 0 \2\nnop',
            ),
            # ... (other replacements)
        ]

        for pattern, replacement in replacements:
            code = re.sub(pattern, replacement, code)

        return code.split('\n')
        
    def _op_nop(self, instr_params:list): ...
    def _op_add(self, instr_params:list): ...
    def _op_mul(self, instr_params:list): ...

The optimise method converts the list of instructions into a single string, performs the regex substitutions, and then converts the string back into a list of instructions. The new add and mul instructions are implemented as methods in the MultiplyingAssembunny class.

This optimization reduces the execution time from over an hour to under a second.

Results

Part 1: Computer{'a': 13685, 'b': 1, 'c': 0, 'd': 0}
Part 2: MultiplyingAssembunny{'a': 479010245, 'b': 1, 'c': 0, 'd': 0}
Execution time: 0.2121 seconds

This puzzle was a great follow-up to the Assembunny introduction. It required not only implementing a new instruction but also analyzing the program’s logic to find and optimize inefficiencies.

‹›