After a mentally painful Day 16, I was very happy we got the first computer puzzle of the year. This is another Advent of Code stable where the first part is about implementing the rules and operations and then the second part is figuring out how to do things without actually running that computer.
Read input
Our input today comes in two parts: the registers and the program code.
Register A: 729
Register B: 0
Register C: 0
Program: 0,1,5,4,3,0Today I decided to skip regex since the input is simple enough.
To read the registers, we split the section to lines and manually point the values to correct registers. If the amount of registers was higher or they could be in any random order, I would have done it with regex.
def map_registers(section):
lines = section.split("\n")
a = int(lines[0].split(": ")[1])
b = int(lines[1].split(": ")[1])
c = int(lines[2].split(": ")[1])
return {"A": a, "B": b, "C": c}The program is even simpler as we just split it from commas and convert to integers:
def map_program(section):
codes = section.split(": ")[1]
return [int(code) for code in codes.split(",")]Part 1
The program input is a series of opcodes and operands. There are eight opcodes in total:
0 is adv where we divide the number from register A with 2 to the power of a combo value of operand. combo means if the operand is 3 or smaller, it’s that number and if it’s 4-6, it gets the value from registers A-C. Final result is truncated to integer.
def adv(registers: Registers, operand: int) -> ReturnValue:
numerator = registers["A"]
value = combos[operand]
if operand > 3:
value = registers[value]
denominator = 2**value
registers["A"] = numerator // denominator
return registers, None, None1 is bxl which calculates bitwise XOR of the value in register B and the literal value of operand:
def bxl(registers: Registers, operand: int) -> ReturnValue:
registers["B"] = registers["B"] ^ operand
return registers, None, None2 is bst which calculates the combo value modulo 8 and stores it into register B:
def bst(registers: Registers, operand: int) -> ReturnValue:
value = combos[operand]
if operand > 3:
value = registers[value]
registers["B"] = value % 8
return registers, None, None3 is jnz which is notorious for creating complexity in Advent of Code puzzles as it checks the value from register A and if it is not zero, jumps to a new pointer value:
def jnz(registers: Registers, operand: int) -> ReturnValue:
jump_to = None
if registers["A"] != 0:
jump_to = operand
return registers, jump_to, None4 is bxc which takes the XOR of B and C and stores it back to B:
def bxc(registers: Registers, operand: int) -> ReturnValue:
registers["B"] = registers["B"] ^ registers["C"]
return registers, None, None5 is out which outputs the value of the combo operand modulo 8:
def out(registers: Registers, operand: int) -> ReturnValue:
value = combos[operand]
if operand > 3:
value = registers[value]
return registers, None, value % 86 is bdv which is the same as adv but the value is stored in register B:
def bdv(registers: Registers, operand: int) -> ReturnValue:
numerator = registers["A"]
value = combos[operand]
if operand > 3:
value = registers[value]
denominator = 2**value
registers["B"] = numerator // denominator
return registers, None, Noneand 7 is cdv which is the same as previous but stored in C:
def cdv(registers: Registers, operand: int) -> ReturnValue:
numerator = registers["A"]
value = combos[operand]
if operand > 3:
value = registers[value]
denominator = 2**value
registers["C"] = numerator // denominator
return registers, None, NoneOur interface choice here is that we input registers and operand to each function (even bxc which doesn’t do anything with it) and we output a tuple of Registers, NewPointer and Output.
This unified interface makes it possible for us to store the functions in a dictionary and pick the right one by the opcode. Because of this, we don’t have to do any if or match logic inside our program processor:
opcodes = {0: adv, 1: bxl, 2: bst, 3: jnz, 4: bxc, 5: out, 6: bdv, 7: cdv}
combos = {0: 0, 1: 1, 2: 2, 3: 3, 4: "A", 5: "B", 6: "C"}
def process(program, registers):
pointer = 0
prints = []
while pointer < len(program):
opcode = program[pointer]
operand = program[pointer + 1]
func = opcodes[opcode]
registers, pointer_movement, output = func(registers, operand)
if output is not None:
prints.append(output)
if pointer_movement is not None:
pointer = pointer_movement
else:
pointer = pointer + 2
return printsTo run this program, I call process for the program and join the output with commas:
def part_1():
registers, program = read_multisection_input(17, [map_registers, map_program])
output = process(program, registers)
output = ",".join([str(number) for number in output])
print(f"Part 1: {output}")Part 2
The second part throws in a new twist. What the program should be doing is returning its own input as output and our job is to find the smallest value of register A that results in the same output as the input.
Usually these are about recognising patterns or loops that can be minified to avoid running every step.
So my first action was to reduce my input program into something simplified. My program, when written out, looked like the following.
Syntax legend
|name of the operation|(actual calculation)|→ where to store|
Math operations:
%== modulo^== XOR//== integer division**= exponential
bst (A % 8) -> B
bxl (B ^ 1) -> B
cdv (A // 2**B) -> C
bxl (B ^ 5) -> B
adv (A // 8) -> A
bxc (B ^ C) -> B
out (B % 8) -> OUTPUT
jnz (0)First I noticed that jnz only ever happens at the end and always jumps to the start. That’s a big relief because I’ve been working for days on Day 12 of 2016 where it’s more complex. If you got a kick out of today’s puzzle, that’s a nice one to solve next.
Then I noticed that A only ever changes by being divided by 8.
So we can simplify the output calculation to:
OUTPUT = (((A % 8) ^ 1) ^ 5) ^ (A // 2**((A%8) ^ 1)) % 8A single expression in where we calculate the individual output in terms of A without having to run the program.
I then put this into a function:
def process_simplified(A):
output = []
while A != 0:
a = (A % 8) ^ 1
b = a ^ 5
c = A // (2**a)
res = (b ^ c) % 8
output.append(res)
A = A // 8
return outputand tested that it still worked with the first step. Great, I got an optimised version of my original solution.
Even with that, running this brute force won’t work so the next step was to start thinking about the program output from the end towards the front.
To reach the end, the result of the final division (before integer truncation) needs to be inside the [0..1) range ([ means included, ) means not included). So any number between 0 and 1 but not 1. The problem with that is that there’s an infinite amount of them and I don’t even know if we’d be looking for a larger or smaller end of that.
With a few hints, I was able to figure out that to get the last output, I’d need to run it with an A value of less than 8. I could then find that number by looping through all the options and seeing if it matches:
for A in range(1, 8):
output = process_simplified(A)
if output == program[-1:]:
print(A)which gave me the correct number.
Next, I would multiply that by 8 (as we divide by 8 going backwards) and try again, finding the next number that provides the correct sub-output (two last items):
A = A * 8
for A in range(A, A+8):
output = process(simplified(A))
if output == program[-2:]:
print(A)I would then repeat this for as many times as there are numbers in the program:
A = 1
for i in range(1, len(program) + 1):
for a in range(A, A + 8):
output = process_simplified(a)
if output == program[(-1 * i) :]:
A = a
break
A = A * 8
print(A // 8)The final A//8 is because we multiply it once too many.
This worked for the first (or last, depending on how you count) 10 outputs but then the rest were filled with 4s. I figured it might have been because the range of potential as didn’t go far enough so I added a few.
This resulted in the following 2 star performance:
def part_2():
_, program = read_multisection_input(17, [map_registers, map_program])
A = 1
for i in range(1, len(program) + 1):
for a in range(A, A + (8**i)):
output = process_simplified(a)
if output == program[(-1 * i) :]:
A = a
break
A = A * 8
result = A // 8
print(f"Part 2: {result}")I used 8**i because it felt appropriate. Since we divide/multiply by 8 every time (depending on the direction), the upper bound likely also multiplies with 8. As long as the upper limit is high enough, I guess it’s enough because we stop on the smallest one we find anyway.
Today was probably the kindest version of the “build a computer” puzzles over the years and I think it’s the first time I’ve gotten the second star.
I always get excited because implementing a system based on rules is fun. Finding patterns and using them to solve the second part is usually less to my liking but today was quite fun.
It feels good to be back on the 2-star gang.