from misc.helper import verify_answer
example_input_file_1 = "../inputs/example_day_17_1.txt"
example_input_file_2 = "../inputs/example_day_17_2.txt"
input_file = "../inputs/day_17.txt"Day 17
Today, together with historian elves we’re falling into despair, or rather having to debug some very weird computer program. Must admit, reading the instructions the first time made me question if I want to do it. Not because the task is hard, but because the instructions are so weird. But let’s not get ahead of ourselves.
We are falling through a void and the only way to save us is to debug a 3-bit (weird I might add!) computer program. Read the whole story on the official Day 17 of Advent of Code 2024 website.
Here’s a ChatGPT negotiated illustration of the setup:
Setting up
Part 1: Debug the debugging
We are given an input that specifies the state of input registers, and the program itself. Program is composed of 3-bit integers (0-7) separated by commas. Each pair of integers represent an instruction and an operand. An operand can be a literal operand, or can be a combo operand. Literal operand is just the number itself, while combo operand follows its separate rules. Whether an operand should be treated as a literal or a combo operand is determined by the instruction.
Combo operands:
* 0 - 3 - same as literal operand.
* 4 - value of register A.
* 5 - value of register B.
* 6 - value of register C.
* 7 - is reserved and does not appear as combo operand.
Instructions:
* 0 - division of value in register A by the 2 to the power of its combo operand; The result truncated to integer is stored in register A.
* 1 - bitwise XOR of register B and literal operand; The result is stored in register B.
* 2 - calculates its combo operand module 8 and saves it in register B.
* 3 - does nothing if register A is 0, but if register A is not 0, it jumps to the instruction specified by its literal operand.
* 4 - bitwise XOR of register B and register C and stores the result in register B.
* 5 - calculates combo operand modulo 8 and outputs the result.
* 6 - division of value in register A by the 2 to the power of its combo operand; The result truncated to integer is stored in register B.
* 7 - division of value in register A by the 2 to the power of its combo operand; The result truncated to integer is stored in register C.
# bitwise xor in python
def xor(a, b):
return a ^ bimport re
from pathlib import Path
def parse_input(input):
if Path(input).exists():
input = Path(input).read_text()
registers = {}
for line in input.strip().split("\n"):
if line.startswith("Register"):
# extract regster letter from "Register X:"
register = re.findall(r"Register (\w):", line)[0]
registers[register] = int(line.split(": ")[1])
elif line.startswith("Program"):
program = [int(el) for el in line.split(": ")[1].split(",")]
return registers, program
example = """
Register A: 17
Register B: 21
Register C: 3
Program: 0,1,2,3,5,3
"""
parse_input(example)({'A': 17, 'B': 21, 'C': 3}, [0, 1, 2, 3, 5, 3])def execute_program(program, registers):
program = program.copy()
registers = registers.copy()
def combo_operand(operand: int):
match operand:
case x if x < 4: # Guard clause for values less than 4
return operand
case 4:
return registers["A"]
case 5:
return registers["B"]
case 6:
return registers["C"]
case 7:
raise ValueError("Invalid operand")
case _:
raise ValueError("Operand not recognized")
i = 0
out = []
while i < len(program):
match program[i]:
case 0:
registers["A"] = int(
registers["A"] / 2 ** combo_operand(program[i + 1])
)
i += 2
case 1:
registers["B"] = xor(registers["B"], program[i + 1])
i += 2
case 2:
registers["B"] = combo_operand(program[i + 1]) % 8
i += 2
case 3:
if registers["A"] == 0:
i += 2
else:
i = program[i + 1]
case 4:
registers["B"] = xor(registers["B"], registers["C"])
i += 2
case 5: # out
out.append(combo_operand(program[i + 1]) % 8)
i += 2
case 6:
registers["B"] = int(
registers["A"] / 2 ** combo_operand(program[i + 1])
)
i += 2
case 7:
registers["C"] = int(
registers["A"] / 2 ** combo_operand(program[i + 1])
)
i += 2
case _:
raise ValueError("Invalid instruction")
return ",".join(map(str, out))def part_one(input):
registers, program = parse_input(input)
return execute_program(program, registers)verify_answer(part_one, example, "3")✔️ That's right! The answer is 3.verify_answer(part_one, example_input_file_1, "4,6,3,5,6,3,5,2,1,0")✔️ That's right! The answer is 4,6,3,5,6,3,5,2,1,0.%time part_one(input_file)CPU times: user 515 μs, sys: 601 μs, total: 1.12 ms
Wall time: 780 μs'1,5,3,0,2,5,2,5,3'That’s the right answer! You are one gold star ⭐ closer to finding the Chief Historian.
Part 2: Output the program sequence
In Part 2, we ae asked to fix the program by changing the register A value such that the program sequence is outputted.
It took me quite a few tries to get this one correct after my brute force approach was taking too long to be reasonable. I decided to turn to an LLM for guidance. I copied u/quetzelcoatlus1’s solution from this Reddit thread and asked ChatGPT to explain it step by step until I understood how it worked. It took longer than I’d like to admit, but I eventually pieced it all together.
The key insight came from understanding how numbers work in binary. Shifting a number to the left by 1 is equivalent to multiplying it by 2, and shifting it to the right by 1 is equivalent to dividing it by 2. It’s like moving a decimal number left or right by one place (e.g., multiplying 1 -> 10 or dividing by 10 100 -> 10) but in base-2. This property is what allowed me to construct the number A, appending a 3-bit value at each step.
Here’s an example that helped me understand binary shifting:
def print_binary(n):
return bin(n)[2:]
def binary_to_int(n):
return int(n, 2)
print(f"1 written in binary is `{print_binary(1)}` and shifted 1 bit to the left is '{print_binary(1 << 1)}' ({binary_to_int(print_binary(1 << 1))}). Shifting 1 bit to the left is the same as multiplying by 2^1 = 2")
print(f"2 written in binary is `{print_binary(2)}` and shifted 2 bits to the left is '{print_binary(2 << 1)}' ({binary_to_int(print_binary(2 << 1))}). Shifting 2 bits to the left is the same as multiplying by 2^2 = 4")
print(f"3 written in binary is `{print_binary(3)}` and shifted 3 bits to the left is '{print_binary(3 << 3)}' ({binary_to_int(print_binary(3 << 3))}). Shifting 3 bits to the left is the same as multiplying by 2^3 = 8")1 written in binary is `1` and shifted 1 bit to the left is '10' (2). Shifting 1 bit to the left is the same as multiplying by 2^1 = 2
2 written in binary is `10` and shifted 2 bits to the left is '100' (4). Shifting 2 bits to the left is the same as multiplying by 2^2 = 4
3 written in binary is `11` and shifted 3 bits to the left is '11000' (24). Shifting 3 bits to the left is the same as multiplying by 2^3 = 8In the task, the program outputs a 3-bit number (via the out operation that computes mod 8 of the combo operand). This constrains the search space for A to building it gradually, 3 bits at a time. Each recursive step shifts the current value of A left by 3 bits (making room for the next 3-bit value) and adds a candidate digit (0 to 7).
While we are shifting A leftwards (appending new 3-bit values to the least significant bits), the output is generated from left to right, matching the sequence of 3-bit values. This ensures the program’s constraints are respected, and the final value of A is built incrementally.
To build A recursively, we try all possible 3-bit values (0 to 7) at each step and check if the output sequence generated so far matches the expected sequence. If it does, we continue building A by shifting it left by 3 bits, appending the next candidate value, and moving the index to the next part of the output. If the output at any step does not match the expected output, we prune the current branch of the recursion and backtrack until we find a branch that produces the correct output.
def find_matching_a_recursive(program):
def run_program(a_value, index):
registers = {"A": a_value, "B": 0, "C": 0}
program_counter = 0
output = []
def combo_operand(operand):
match operand:
case x if x < 4:
return operand
case 4:
return registers["A"]
case 5:
return registers["B"]
case 6:
return registers["C"]
case 7:
raise ValueError("Reserved operand")
case _:
raise ValueError("Invalid combo operand")
while program_counter < len(program) - 1:
opcode = program[program_counter]
operand = program[program_counter + 1]
match opcode:
case 0: # adv
registers["A"] = registers["A"] // (
2 ** combo_operand(operand)
)
case 1: # bxl
registers["B"] ^= operand
case 2: # bst
registers["B"] = combo_operand(operand) % 8
case 3: # jnz
if registers["A"] != 0:
program_counter = operand
continue
case 4: # bxc
registers["B"] ^= registers["C"]
case 5: # out
output.append(combo_operand(operand) % 8)
if index < len(program) and output[-1] != program[index]:
return False
index += 1
case 6: # bdv
registers["B"] = registers["A"] // (
2 ** combo_operand(operand)
)
case 7: # cdv
registers["C"] = registers["A"] // (
2 ** combo_operand(operand)
)
case _:
raise ValueError(f"Unknown opcode: {opcode}")
program_counter += 2
return index == len(program)
def solve(a_value, index):
for i in range(8):
candidate_a = (a_value << 3) + i
if run_program(candidate_a, index):
if index == 0:
return candidate_a
result = solve(candidate_a, index - 1)
if result is not None:
return result
return None
return solve(0, len(program) - 1)def part_two(input):
_, program = parse_input(input)
return find_matching_a_recursive(program)verify_answer(part_two, example_input_file_2, 117440)✔️ That's right! The answer is 117440.%time part_two(input_file)CPU times: user 2.45 ms, sys: 799 μs, total: 3.25 ms
Wall time: 3.24 ms108107566389757That’s the right answer! You are one gold star ⭐ closer to finding the Chief Historian.