Advent of Code - Day 17

Adrien Foucart

2024-12-17

@=programming @=python @=adventofcode

[Go to index] [Advent of Code website] [My code on Gitlab]

Well, that was painful.

Today was about building a computer, which was fine, then using it, which wasn’t. Let me explain.

Part 1 - making a computer

We have a computer with three registers (A, B and C), which is able to perform a bunch of different operations. The input is a text file containing the initial value of the registers, and a program like this example:

Register A: 729
Register B: 0
Register C: 0

Program: 0,1,5,4,3,0

The program is a succession of numbers, which need to be interpreted pairwise as opcode, operand. How to interpret those opcodes and operands is detailed on the puzzle page, but the main point is that everything is base-8: there are 8 operations, operands can take values 0-7, everything is encoded in 3 bits. That will turn out to be very useful later.

The goal in the first part is to determine the output of the program (one of the instructions is out, x, which outputs x (or rather the “combo” of x, as defined in the puzzle)).

For the program above, we could rewrite it assembly-like as:

adv 1
out 4
jnz 0

Which, given the rules laid out in the puzzle, would perform the operations:

0:  A <- A//2
1:  PRINT A%8
2:  if A != 0:
3:      goto 0
4:  END

From the initial state of A=729, we would therefore get:

A <- 364, PRINT 364%8 = 4
A <- 182, PRINT 6
A <- 91, PRINT 3
A <- 45, PRINT 5
A <- 22, PRINT 6
A <- 11, PRINT 3
A <- 5, PRINT 5
A <- 2, PRINT 2
A <- 1, PRINT 1
A <- 0, PRINT 0
END

So we just need to code all of the operations. Rather than going object-oriented, this time I went with some global variables, which felt more appropriately old school:

REGISTER = {
    'A': 0,
    'B': 0,
    'C': 0
}
STDOUT: list[str] = []
PROGRAM: list[int] = []
instrptr: int = 0

instrptr is the instruction pointer, which will tell us where we are in the program.

Then we encode the “combo value” thing:

class InvalidComboValueException(Exception):
    pass

def combo(op: int) -> int:
    if 0 <= op < 4: 
        return op
    if op == 4:
        return REGISTER['A']
    if op == 5:
        return REGISTER['B']
    if op == 6:
        return REGISTER['C']
    
    raise InvalidComboValueException(f"op: {op}")

Make some helper functions to manipulate things:

Instruction = Callable[[int], None]

def set_register(r: str, v: int) -> None:
    global REGISTER
    REGISTER[r] = v

def get_register(r: str) -> int:
    return REGISTER[r]

def incptr(i: int = 2) -> None:
    global instrptr
    instrptr += i

def jumpto(v: int) -> None:
    global instrptr
    instrptr = v

def printout(v: int) -> None:
    global STDOUT
    STDOUT.append(str(v))

def clearout() -> None:
    global STDOUT
    STDOUT.clear()

And finally create our instruction set:

def adv(op: int) -> None:
    set_register('A', int(get_register('A')/(2**combo(op))))
    incptr()

def bxl(op: int) -> None:
    set_register('B', get_register('B')^op)
    incptr()

def bst(op: int) -> None:
    set_register('B', combo(op)%8)
    incptr()

def jnz(op: int) -> None:
    if get_register('A') != 0:
        jumpto(op)
        return
    incptr()
    
def bxc(op: int) -> None:
    set_register('B', get_register('B')^get_register('C'))
    incptr()

def out(op: int) -> None:
    printout(combo(op)%8)
    incptr()

def bdv(op: int) -> None:
    set_register('B', int(get_register('A')/(2**combo(op))))
    incptr()

def cdv(op: int) -> None:
    set_register('C', int(get_register('A')/(2**combo(op))))
    incptr()

INSTRUCTION_SET = {
    0: adv,
    1: bxl,
    2: bst,
    3: jnz,
    4: bxc,
    5: out,
    6: bdv,
    7: cdv
}

Then we have the execution loop, and a function to print the status of the computer for debugging purposes.

def execute() -> bool:
    if instrptr >= len(PROGRAM):
        return False
    
    INSTRUCTION_SET[PROGRAM[instrptr]](PROGRAM[instrptr+1])
    return True

def execute_program():
    while execute():
        continue

def print_status():
    print(f"PROGRAM STATUS:")
    print(f"Register A: {get_register('A')}")
    print(f"Register B: {get_register('B')}")
    print(f"Register C: {get_register('C')}")
    print(f"PROGRAM: {PROGRAM}")
    print(f"instrptr: {instrptr}")
    print(f"STDOUT: {','.join(STDOUT)}")

Now we need to parse the input file and actually “load” the program by setting the registers and putting the opcodes and operands in the instruction list:

def load_program(data: str):
    global PROGRAM
    pattern = r"Register A: (\d+)\nRegister B: (\d+)\nRegister C: (\d+)\n\nProgram: ([\d|,]+)"
    
    things = re.match(pattern, data)
    if things is None or len(things.groups()) != 4:
        raise InvalidProgramException()

    a, b, c, program = things.groups()
    set_register('A', int(a))
    set_register('B', int(b))
    set_register('C', int(c))
    PROGRAM = [int(p) for p in program.split(',')]


def load_from_file():
    with open("day17", r) as fp:
        data = fp.read()
    load_program(data)

We can now load and execute the program and get the result:

load_from_file("")
execute_program()
print_status()

And we get our first part done fairly quickly.

Part 2 - that doesn’t seem so bad… until it is.

In part 2, we need to find the smallest possible initial value for the A register so that the program outputs itself. So for instance, if we have the program 0,3,5,4,3,0, and we set A to 117440, the output of the program will be 0,3,5,4,3,0: it outputs itself.

Okay, I thought naively. Let’s start by being dumb and just start from 0 and increment a until I find something that works.

A few minutes later, I cut it off and decided that I would not be that dumb. So I thought about it. And to think about it, I had to look at my actual puzzle input. My program was 2,4,1,1,7,5,1,5,0,3,4,4,5,5,3,0, which translated to:

bst 4
bxl 1
cdv 5
bxl 5
adv 3
bxc 4
out 5
jnz 0

Or, developing a bit further:

0:  B <- A%8
1:  B <- B xor 1
2:  C <- A//(2**B) = A >> B
3:  B <- B xor 5
4:  A <- A//8 = A >> 3
5:  B <- B xor C
6:  PRINT B%8
7:  if A != 0:
8:      goto 0
9:  END

It took me a while, but I eventually realized that with the sequence:

A <- A//8
if A != 0:
    goto 0

The length of the output was easily determined by the initial value of A. If A was between 0 and 7, I would get a single output. Between 8 and 63, I would get two numbers. In general, to get a size n output, I needed 8n1A<8n. Since I had 16 numbers in my program… That gave me lower and upper bounds on the value of A: 351843720888321<281474976710656.

Oh, no.

That was a bit too big of a space to explore.

I thought about it some more. Couldn’t really find a better idea. Almost quit. Then I realized something actually useful: at every loop of my program, I was using the value of A%8 to compute the output, but then I was dividing it by 8 (ignoring the remainder) and, crucially, the value of B and C at the “end” of the loop didn’t affect the next printed value.

In other words: if, for instance, I start with A = 34, the first number that I print will be some function of 34 (let’s call it f(34)). Then, A becomes 34//8 = 4 and the second number that I print will be f(4). Then A will be set at 0 and we will stop.

So the last number printed by the program will only depend on the last nonzero remainder of the successive divisions by 8… Which are the last 3 bits of A. So that gives me a procedure to find A:

First, for k between 0 and 7, check which ones gives me a 0 at the output. Those are “candidates” for the last three bits of A.

Then, for each of those candidates, add k*8 (still for k between 0 and 7) and check which k gives us two numbers corresponding the the last numbers in my program (3, 0). Keep going, eliminating the “wrong” paths as we go, until we get a bunch of candidates that produce the right program. Then select the smallest.

Because of the way I had set up my “computer”, this was a pain in the *** to implement. I ended up just manually rewriting “my” input program, which unfortunately makes my solution only work for my input. Here it is anyway:

def manual_program(a: int):
    out = []
    stop = False
    while not stop:
        b = (a % 8)^1
        c = a >> b
        b = (b^5)
        a = a >> 3
        b = b^c
        out.append(b%8)
        stop = a == 0
    return out


def find_min_a(factors: list[int], candidates: list[int]):
    for k in range(8):
        if len(factors) == 0:
            a = 0
        else:
            a = sum(f*(8**(len(factors)-i)) for i, f in enumerate(factors))
        out = manual_program(a+k)
        if len(out) == len(PROGRAM):
            if all(o == p for o, p in zip(out, PROGRAM)):
                candidates.append(a+k)
                return

        if all(o == p for o, p in zip(out, PROGRAM[-len(factors)-1:])):
            find_min_a(factors+[k], candidates)

factors = []
candidates = []
find_min_a(factors, candidates)
a = min(candidates)
print(f"Minimum value for a: {a}")

Finally free.