Advent of Code 2024, Day 17

Part 1 was easy enough: just write an interpreter. Part 2 was tough.

I first tried counting up the A’s by brute force, but after about half an hour or so, I was still at around 0.00014% of the actual answer.

So I manually disassembled the program. I noticed that the program consumes A from the right in steps of 3 bits, like an input tape. When I tried to construct A by hand, starting from the end of the execution, I got confused about left and right of the program and of A.

So I hard-coded a program to automate my steps: begin from the end of the execution and construct A in steps of 3 bits. I had a bug where I had wrongly interpreted “xor a 3-bit value with 4” as “add a 1 bit to the left” instead of “flip the leftmost bit”. But even after my fix, the helper program didn’t terminate successfully and the intermediate values gave wrong outputs.

So I used my interpreter from part 1 to print small values of A whose output had a suffix match with the program. When I printed the values in octal (because of the 3-bit steps), I noticed that the longer candidates had the (various) shorter candidates as prefixes — you could represent them as a tree, starting from the left, with branches splitting, running in parallel, and some ending before others. (In my manual attempt, I had assumed that there would always be a unique intermediate value instead of multiple in parallel.)

So I wrote a program to check 3-bit candidates for A, keep the successful ones (whose output gives a suffix match with the program), and recursively extend them to the right, one octal digit at a time. I ran into the maximum recursion depth at first. But when I rewrote it with gradually growing sets, it worked.

Part 1

import sys

def combo(arg, A, B, C):
    return [0, 1, 2, 3, A, B, C][arg]

def run(P, A, B, C):
    O = []
    i = 0
    while 0 <= i < len(P):
        arg = P[i+1]
        if P[i] == 0:
            A = A >> combo(arg, A, B, C)
        elif P[i] == 1:
            B ^= arg
        elif P[i] == 2:
            B = combo(arg, A, B, C) % 8
        elif P[i] == 3:
            if A != 0:
                i = arg-2
        elif P[i] == 4:
            B ^= C
        elif P[i] == 5:
            O.append(combo(arg, A, B, C) % 8)
        elif P[i] == 6:
            B = A >> combo(arg, A, B, C)
        elif P[i] == 7:
            C = A >> combo(arg, A, B, C)
        i += 2
    return O

with open(sys.argv[1]) as f:
    for line in f:
        if "A" in line:
            A = int(line.split()[-1])
        elif "B" in line:
            B = int(line.split()[-1])
        elif "C" in line:
            C = int(line.split()[-1])
        elif "P" in line:
            P = [int(x) for x in line.split()[-1].split(",")]

print(",".join([str(x) for x in run(P, A, B, C)]))

Part 2

import sys

def combo(arg, A, B, C):
    return [0, 1, 2, 3, A, B, C][arg]

def run(P, A, B, C):
    O = []
    i = 0
    while 0 <= i < len(P):
        arg = P[i+1]
        if P[i] == 0:
            A = A >> combo(arg, A, B, C)
        elif P[i] == 1:
            B ^= arg
        elif P[i] == 2:
            B = combo(arg, A, B, C) % 8
        elif P[i] == 3:
            if A != 0:
                i = arg-2
        elif P[i] == 4:
            B ^= C
        elif P[i] == 5:
            O.append(combo(arg, A, B, C) % 8)
        elif P[i] == 6:
            B = A >> combo(arg, A, B, C)
        elif P[i] == 7:
            C = A >> combo(arg, A, B, C)
        i += 2
    return O

def check(P, As, B, C):
    rec = set()
    fin = set()
    for prev_A in As:
        for A in range(8*prev_A, 8*prev_A + 8):
            O = run(P, A, B, C)
            if P == O:
                fin.add(A)
            elif P[-len(O):] == O and A != 0:
                rec.add(A)
    return rec, fin

with open(sys.argv[1]) as f:
    for line in f:
        if "A" in line:
            A = int(line.split()[-1])
        elif "B" in line:
            B = int(line.split()[-1])
        elif "C" in line:
            C = int(line.split()[-1])
        elif "P" in line:
            P = [int(x) for x in line.split()[-1].split(",")]

rec, fin = {0}, set()
while len(rec) != 0:
    rec, nfin = check(P, rec, B, C)
    fin.update(nfin)
print(min(fin))

2024-12-17