Learning Python with Advent of Code Walkthroughs
Dazbo's Advent of Code solutions, written in Python
Advent of Code 2015 - Day 23
Day 23: Opening the Turing Lock
Useful Links
Concepts and Packages Demonstrated
Static MethodsLambda FunctionsExceptions
Page Navigation
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_ptrvariable, 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
0in the__init__()method. - We also initialise the
_instruction_ptrto0, 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 intoparts[1]. - We then further split
parts[1], if it contains any",". - If we read a
JMP, JIE or JIOinstruction, then we update the instruction pointer to point to the appropriate next instruction, and thencontinue` to the next loop iteration. - If the instruction is not
JMP, JIE or JIO, then pass the instruction and the register value to theInstructions.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!