Advent of Code 2024 (Days 17, 18)

Here is my private leaderboard code if you want to come join the fun: 1598637-22d94a1d.

Feel free to introduce yourself if you ever decide to enter.

Day 17 : A Program That Writes Itself ?

The problem has a lot of follow directions vibes, based on the eight possible instructions we have. I’ll let you read the eight possible instructions first, and then come back here and buckle up for the ride.

Part A

Unbound local variables

So, my first attempt was buggy because I tried being a smart-ass and use “global” variables for the registers.

def solution_17a(data=None, filename=None):
    if not data:
        register, program = parse_17(filename)
    else:
        register, program = data
        
    a, b, c = register
    p = 0
    
    outputs = []

    # ... #
        
    def bxl(n):
        b = b ^ n

After some digging, I discover that what happens here is

Python tries to compute b ^ n.
b is not declared in the local scope AND the variable b is assigned a value at any point in the function, then it complains.

If the variable b is not reassigned at any point in the function, Python assumes that we are referring to the variable b outside the scope. Otherwise, Python assumes we are using a local variable b. Neat.

To summarize, this works:

def test():
    b = 0
    def bxl(n):
        b^n
    bxl(1)
test()

But this does not:

def test():
    b = 0
    def bxl(n):
        b^n
        b=0
    bxl(1)
test()

And so, I decided to be smart (or dumb) about it and convert this problem into another problem!

Using a dictionary instead

In this shameful solution, I use a dictionary called registers to get around that initial problem. Why not throw P into the mix as well?

Who needs future-proofing when the future is within a couple minutes from now, amirite?

def solution_17a(data=None, filename=None):
    if not data:
        register, program = parse_17(filename)
    else:
        register, program = data
        
    registers = {
        'A': register[0],
        'B': register[1],
        'C': register[2],
        'P': 0
    }
    
    outputs = []
    
    def get_num(cmb):
        if 0 <= cmb < 4:
            return cmb
        if cmb == 4:
            return registers['A']
        if cmb == 5:
            return registers['B']
        if cmb == 6:
            return registers['C']
        
    def adv(cmb):
        n = get_num(cmb)
        registers['A'] = registers['A'] // (2**n)
        
    def bxl(n):
        registers['B'] = registers['B'] ^ n
        
    def bst(cmb):
        n = get_num(cmb)
        registers['B'] = n % 8
        
    def jnz(cmb):
        if registers['A'] != 0:
            n = get_num(cmb)
            registers['P'] = n
            registers['P'] -= 2 # compensation
    
    def bxc(cmb):
        registers['B'] = registers['B'] ^ registers['C']
    
    def out(cmb):
        n = get_num(cmb)
        outputs.append(n%8)
        
    def bdv(cmb):
        n = get_num(cmb)
        registers['B'] = registers['A'] // (2**n)
        
    def cdv(cmb):
        n = get_num(cmb)
        registers['C'] = registers['A'] // (2**n)
        
    instruction = [adv, bxl, bst, jnz, bxc, out, bdv, cdv]
        
    while registers['P'] < len(program)-1:
        p = registers['P']
        operand = program[p+1]
        instruction[program[p]](operand)
        registers['P'] += 2
    
    return str(outputs)[1:-1].replace(" ", "")

While this solution worked and let me view Part B, this is code that is reserved for coding competitions and not for real-life software.

Part B

My elegant solution for getting out of this “global” scope / local scope hell was to make a Program class. I didn’t know what to name it at that time, so Program it is!

def solution_17b(data=None, filename=None):
    if not data:
        register, program = parse_17(filename)
    else:
        register, program = data
    
    class Program():
        def __init__(self, a, b=0, c=0):
            self.a = a
            self.b = b
            self.c = c
            self.p = 0
            self.outputs = []
    
        def get_num(self, cmb):
            if 0 <= cmb < 4:
                return cmb
            if cmb == 4:
                return self.a
            if cmb == 5:
                return self.b
            if cmb == 6:
                return self.c

        def adv(self, cmb):
            n = self.get_num(cmb)
            self.a = self.a // (2**n)

        def bxl(self, n):
            self.b = self.b ^ n

        def bst(self, cmb):
            n = self.get_num(cmb)
            self.b = n % 8

        def jnz(self, cmb):
            if self.a != 0:
                n = self.get_num(cmb)
                self.p = n
                self.p -= 2 # compensation

        def bxc(self, cmb):
            self.b = self.b ^ self.c

        def out(self, cmb):
            n = self.get_num(cmb)
            self.outputs.append(n%8)
            return n%8

        def bdv(self, cmb):
            n = self.get_num(cmb)
            self.b = self.a // (2**n)

        def cdv(self, cmb):
            n = self.get_num(cmb)
            self.c = self.a // (2**n)

My Specific Test Case

As most solvers of this problem would know, a big chunk of the thinking time would be dedicated to deciphering the program that appears in your big input.

My big input looks like this:

2 4 1 6 7 5 4 4 1 7 0 3 5 5 3 0

Interpreting the program it represents, we have:

i    | bst 2 4 | B = A % B
ii   | bxl 1 6 | B = B XOR 6
iii  | cdv 7 5 | C = A // (2**B)
iv   | bxc 4 4 | B = B XOR C
v    | bxl 1 7 | B = B XOR 7
vi   | adv 0 3 | A = A // (2**3)
vii  | out 5 5 | OUTPUT B % 8
viii | jnz 3 0 | RESTART UNLESS A IS 0

Loops

From a quick look, we can conclude the following:

The program stops at the loop when A becomes 0.
Otherwise, we go back to i after the check at viii.

This means that we repeat steps i through vii again and again. Let’s call that a loop.

How Many Loops?

For each loop, we can conclude the following:

We output one number (during step vii).
The only thing that happens to A is that it loses 3 bits every loop.

From this, we can conclude that if a starting value $A_0$ for A exists such that the program outputs itself (i.e. 16 numbers from 0 to 7), then $A_0$ must be a number which has at most $48$ bits.

This narrows down our search from the very very big set of positive integers to a very small set of positive integers¹.

To be more precise, $A_0$ must be less than the integer 281474976710656, also known as $2^{48}$ .

Focus on `B`.

Let’s zoom in on B’s story, especially because the numbers we output depend on the last 3 bits of B.

i    | bst 2 4 | B = A % B
ii   | bxl 1 6 | B = B XOR 6
iii  | cdv 7 5 | C = A // (2**B)
iv   | bxc 4 4 | B = B XOR C
v    | bxl 1 7 | B = B XOR 7
vii  | out 5 5 | OUTPUT B % 8

Let’s rewrite these instructions into friendlier-sounding statements, focusing on the last 3bits of B.

i takes the last three bits of A and XORs it with the last three bits of B (from the previous loop²)

ii flips some of the last three bits.
iii tells us to copy the value of A onto C but remove the last B bits.
iv takes the XOR of B and the new value of C.
v flips some of the last three bits.

To summarize, the taking the new value of B depends on the XOR of the following things:

the value of B from the previous loop
the last three bits of A
some consecutive three bits of A
6 XOR 7, which is 1

XOR is addition modulo 2, which is a fancy way of saying that we can reorder the XOR operations.

A Smaller Problem

Suppose we only want to output 0. Let’s start by guessing $A_0 = 0$ .

Let’s keep track of what B will look like by the time we output it. Let’s denote XOR by ⊕.

i  |    000 | Last bits of A0
i  | ⊕ 000 | The current value of B
ii | ⊕ 110 | 
   |  = 110 | The value of B now is 6.
-----------------------------------------
   |    110 |
iv | ⊕ 000 | A0 is all zeros. So removing 6 bits still ends up with `0`
v  | ⊕ 111 | 
   |  = 001 | We output `1`.

But only if A0 was 1 to begin with, then we would have had output 0.

In fact, that is one solution! $A_0 = 1$ would indeed output 0.

And so, if the program we need to output only has $1$ number, then we have solved it!

Going Past the First Instruction

Now, how do we use that information to output 3,0?

Remember that every iteration, we need to add $3$ bits to keep the program running so that we get to output enough numbers. So add $3$ bits we will do!

And we have $8$ choices of combinations of bits to add.

But can we solve for the exact bits without trying them all?

Is the Process Two-Way?

I made the mistake of assuming these steps are one-to-one and therefore easily reverse engineered. In particular, step iv depends on the result of ii, so it’s actually not easy to reverse engineer. So we can’t bank on the fact that there is a unique $A_0$ that will make us win.

We will, a priori, have to try all $8$ choices.

Still Doesn’t Work

Actually, it is entirely possible that all $8$ choices wont work. Does that mean we can’t output the program? Not necessarily.

Remember that, contrary to reality, we can actually change past choices. For example, waht if there was a different $A_0$ that could have output 0 before? ³

We’d have to try that out as well. And so we end up with a search tree and some backtracking.

Armed with this, we can find either all valid $A_0$ less than $2^{48}$ and take the minimum among them, or be clever with our searching.

Here is the code I used to find my answer

from heapq import heappush, heappop

def solution_17b(data=None, filename=None):
    if not data:
        register, program = parse_17(filename)
    else:
        register, program = data
    
    class Program():
        def __init__(self, a, b=0, c=0):
            self.a = a
            self.b = b
            self.c = c
            self.p = 0
    
        def get_num(self, cmb):
            if 0 <= cmb < 4:
                return cmb
            if cmb == 4:
                return self.a
            if cmb == 5:
                return self.b
            if cmb == 6:
                return self.c

        def adv(self, cmb):
            n = self.get_num(cmb)
            self.a = self.a // (2**n)

        def bxl(self, n):
            self.b = self.b ^ n

        def bst(self, cmb):
            n = self.get_num(cmb)
            self.b = n % 8

        def jnz(self, cmb):
            if self.a != 0:
                n = self.get_num(cmb)
                self.p = n
                self.p -= 2 # compensation

        def bxc(self, cmb):
            self.b = self.b ^ self.c

        def out(self, cmb):
            n = self.get_num(cmb)
            return n%8

        def bdv(self, cmb):
            n = self.get_num(cmb)
            self.b = self.a // (2**n)

        def cdv(self, cmb):
            n = self.get_num(cmb)
            self.c = self.a // (2**n)
                
        def get_output(self, program):
            
            instruction = [self.adv, self.bxl, self.bst, self.jnz, self.bxc, self.out, self.bdv, self.cdv]
            
            while self.p < len(program)-1:
                operand = program[self.p+1]
                new_output = instruction[program[self.p]](operand)
                if program[self.p] == 5:
                    return new_output
                self.p += 2
                
    
    def get_complete_output(a):
        
        prog = Program(a)
        complete_output = []
        
        while True:
            output = prog.get_output(program=program)
            complete_output.append(output)
            prog = Program(prog.a, prog.b, prog.c)
            if prog.a == 0:
                return complete_output
    
    target = tuple(program)    

    to_run = [(i, 0, 0, len(target)) for i in range(8, 0, -1)]
    while len(to_run) > 0:
        a, b, c, t = to_run.pop()
        prog = Program(a, b, c)
        output = prog.get_output(program)
        if target[t-1] == output:
            if t == 1 and tuple(get_complete_output(a)) == tuple(program):
                return a
            if t > 0:
                for i in range(8, 0, -1):
                    to_run.append((a*8+i, 0, 0, t-1))

All in all, this whole Part B took me 3 hours and 10 minutes to resolve.⁴

And since I haven’t wasted enough time for this problem… there’s more!

Part C

While I was quite sure that my solution was too specialized to be a end-all be-all to any possible input, I took comfort about the fact that this could be the intended solution for all players.

I was like, hey, I feel that my solution was general enough to take on any program from the Advent of Code. And so I asked Seba for his big input. My program did not work.

In fact, it seemed to get stuck in an infinite loop. This was because Seba’s input was a bit different than mine. His looked like this:

Output Before Decrement

i'    | bst 2 4
ii'   | bxl 1 5
iii'  | cdv 7 5
iv'   | bxl 1 6
v'    | bxc 4 1
vi'   | out 5 5
vii'  | adv 0 3
viii' | jnz 3 0

One big difference is that his output step is at vi' instead of my vii'. Unfortunately, I had made the assumption that all inputs would have the output step (vii) immediately before the restart step (viii) but indeed steps vi and vii are interchangeable without much other consequence since they are completely independent from each other.

So my code, which was like this:

def get_output(self, program):

    instruction = [self.adv, self.bxl, self.bst, self.jnz, self.bxc, self.out, self.bdv, self.cdv]
    
    while self.p < len(program)-1:
        operand = program[self.p+1]
        new_output = instruction[program[self.p]](operand)
        if program[self.p] == 5:
            return new_output
        self.p += 2

Had to look like this:

def get_output(self, program):
    
    instruction = [self.adv, self.bxl, self.bst, self.jnz, self.bxc, self.out, self.bdv, self.cdv]
    
    to_output = None
    while self.p < len(program)-1:
        operand = program[self.p+1]
        new_output = instruction[program[self.p]](operand)
        if program[self.p] == 5:
            to_output = new_output
        if program[self.p] == 3 and operand == 0:
            self.p = 0
            return to_output
        self.p += 2

And that seemed to put a stop to that infinite loop.

I went to Seba and I was like “Was your answer 113151776532890?” and he was like “No, it was 107413700225434.”.⁵

One Last Bug

Welp. Maybe I made more mathematical assumptions that I shouldn’t have. But apparently, my assumptions were sound.

I also checked if maybe I wasn’t returning the minimum answer. So I tried keeping the answer in a variable and comparing it against all other answers I was finding. The minimum was still 113151776532890. I wasn’t finding the answer all along!

After some minutes of panicking and debating on whether I should full on inspect the program in greater detail, I found the really subtle bug in the body of my main function (i.e. target = tuple(program) and below). I’ll leave that to you to find!

Day 18 : Navigate the Maze Until You Can’t

Here is the link to the problem.

I will be more brief today since Day 17’s write-up was LONG.

It took 11 minutes between Part A and Part B

Part A

This was a basic path-finding problem. I got sniped once because I did not read the whole statement and was treating the whole sample (and big) input file. But apparently, I only needed to take the first 12 obstacles from the sample. This resulted in a lot of head scratching.

But I managed to make a program that finishes under a second.

from heapq import heappush, heappop
from collections import defaultdict

def solution_18a(data=None, filename=None, end = (70, 70), up_to = 1024):
    if not data:
        coords = parse_18(filename)
    else:
        coords = data
    
    def find_shortest_path(obstacle_list, end, up_to):
        visited = set()
        start = (0, 0)
        to_visit = [(0, start)]
        
        obstacles = set(obstacle_list[:up_to])
        
        max_x, max_y = end
        
        n_steps_to = defaultdict(lambda: 10**100)
        n_steps_to[start] = 0
        parent = {start: None}
        answer = 10**100
        
        ctr = 0
        
        while True:
            if len(to_visit) == 0:
                break
            visiting = heappop(to_visit)
            (steps, (x, y)) = visiting
            if (x, y) in visited:
                continue
            if steps > answer:
                continue
            visited.add((x, y))
            if (x, y) == end:
                return steps
            for d in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
                dx, dy = d
                xx, yy = x+dx, y+dy
                if xx in range(0, max_x+1) and yy in range(0, max_y+1) and (xx, yy) not in visited and (xx, yy) not in obstacles:
                    n_steps_to[(xx, yy)] = min(n_steps_to[(xx, yy)], steps+1)
                    parent[(xx, yy)] = (x, y)
                    heappush(to_visit, (steps+1, (xx, yy)))
        return answer
    
    return find_shortest_path(coords, end=end, up_to=up_to)

Part B

I got sniped again because I answered an integer instead of a coordinate. I ended up with a 5 minute anti-brute-force wait time which is why I ended up having 11 minutes between the two parts.

I didn’t bother optimizing and decided to wait it out. It took 48 seconds to run. However, one optimization I had in mind that is easier said than done is: Keep the working path until one of the cells get blocked, then find a new working path! Now, it is said. But someone else can make it done.

I didn’t bother cleaning the code either. I think I’m still tired from yesterday.

%%time
from heapq import heappush, heappop
from collections import defaultdict

def solution_18b(data=None, filename=None, end = (70, 70), up_to = 1024, start_at = 0):
    if not data:
        coords = parse_18(filename)
    else:
        coords = data
    
    def find_shortest_path(obstacle_list, end, up_to):
        visited = set()
        start = (0, 0)
        to_visit = [(0, start)]
        
        obstacles = set(obstacle_list[:up_to])
        
        max_x, max_y = end
        
        n_steps_to = defaultdict(lambda: 10**100)
        n_steps_to[start] = 0
        parent = {start: None}
        answer = 10**100
        
        ctr = 0
        
        while True:
            if len(to_visit) == 0:
                break
            visiting = heappop(to_visit)
            (steps, (x, y)) = visiting
            if (x, y) in visited:
                continue
            if steps > answer:
                continue
            visited.add((x, y))
            if (x, y) == end:
                return steps
            for d in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
                dx, dy = d
                xx, yy = x+dx, y+dy
                if xx in range(0, max_x+1) and yy in range(0, max_y+1) and (xx, yy) not in visited and (xx, yy) not in obstacles:
                    n_steps_to[(xx, yy)] = n_steps_to[(xx, yy)], steps+1
                    parent[(xx, yy)] = (x, y)
                    heappush(to_visit, (steps+1, (xx, yy)))
        if answer > 10**99:
            return obstacle_list[:up_to][-1]
        return answer
    
    while True:
        answer = find_shortest_path(coords, end=end, up_to=ct)
        if type(answer) is tuple:
            return(answer)

In fact, I could say with a very neutral tone of voice and with a lack of punctuation that this set is a subset of the positive integers less than 17! ↩
On the first loop, B is 0 according to my input (and I suppose everyone else’s)! ↩
In the simplified example, there isn’t. But this could happen in a more complex example, such as the big input. ↩
Time started when I finished Part A. ↩
Totally normal conversation. ↩

«Advent of Code 2024 (Days 13, 14, 15, 16)All posts on Advent of Code|

«Advent of Code 2024 (Days 13, 14, 15, 16)Living on the Edge Case: Charging a Navigo Card on Your iPhone»

GUISSMO

GUISSMO

Advent of Code 2024 (Days 17, 18)

Day 17 : A Program That Writes Itself ?

Part A

Unbound local variables

Using a dictionary instead

Part B

My Specific Test Case

Loops

How Many Loops?

Focus on `B`.

A Smaller Problem

Going Past the First Instruction

Is the Process Two-Way?

Still Doesn’t Work

Part C

Output Before Decrement

One Last Bug

Day 18 : Navigate the Maze Until You Can’t

Part A

Part B

GUISSMO

GUISSMO

Advent of Code 2024 (Days 17, 18)

Day 17 : A Program That Writes Itself ?

Part A

Unbound local variables

Using a dictionary instead

Part B

My Specific Test Case

Loops

How Many Loops?

Focus on B.

A Smaller Problem

Going Past the First Instruction

Is the Process Two-Way?

Still Doesn’t Work

Part C

Output Before Decrement

One Last Bug

Day 18 : Navigate the Maze Until You Can’t

Part A

Part B

Footnotes

Focus on `B`.