Advent of Code 2024 - Day 17: Chronospatial Computer

:: programming, python, puzzle

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
val = lambda a: ((((a % 8) ^ 1) ^ 4) ^ int(a / 2 ** ((a % 8) ^ 1))) % 8

def part1(a):
    def gen_digits(a):
        while a != 0:
            b = val(a)
            yield b
            a = int(a / 8)

    return ",".join([ str(d) for d in gen_digits(a) ])

def part2():
    expected = list(reversed([2,4,1,1,7,5,1,4,0,3,4,5,5,5,3,0]))

    def check(m, n, idx):
        for a in range(m, n):
            if val(a) == expected[idx]:
                if idx == 15:
                    yield a
                else:
                    yield from check(a*8, (a+1)*8, idx+1)

    return next(check(0,8,0))

# ---------------------------------------------------------------------------------------------

assert part1(65804993) == "5,1,4,0,5,1,0,2,6"
assert part2()         == 202322936867370

Part 1

As soon as I read today’s puzzle, I knew part 1 would be writing a simulator, and part 2 would propose a puzzle for which simply running the simulator N times would be infeasible :) Regardless, I took the opportunity to use Python’s dataclasses to create a nice, tidy simulator. You can view day17_dataclass.py on github - it was enough to solve part 1. After I solved part 2, I refactored part 1 with that knowledge resulting in the version above.

Before computing the closed form function, I converted my simulator to the following. I think it helped me to come up with the closed form. It was this more efficient version below that I tried brute forcing briefly :)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
 
def run(a):
    idx, pc, b, c = 0, 0, 0, 0
    output = []

    while a != 0:
        b = a % 8
        b ^= 1   
        c = int(a / 2 ** b) 
        b ^= 4              
        a = int(a / 8) 
        b ^= c              
        v = b % 8
        output.append(v)

    return output

Part 2

To solve part 2, I did try running the simulator N times on a whim, but I was 99% sure that would be in vain, so I had to analyze the information more deeply. First I created a function for calculating b that only depends on a, since the value of b is used for each output digit. Here’s that function:

1
 
val = lambda a: ((((a % 8) ^ 1) ^ 4) ^ int(a / 2 ** ((a % 8) ^ 1))) % 8

The key insight I had after thinking about the problem, and running some simulations, was that I only needed to check “modulo 8” values for the last digit of the output, and so on, for the others. The only real actions from each loop of the simulator are to change b and a. b is the output digit, and a is both input to b and the loop termination value. Since a is reduced each time through the loop via a = int(a / 8), there are only a % 8 values to check for each digit. By working backward, we start with a small, tractable value of a which expands rapidly, but always in a range of 8 values.

I tested this theory at first manually via the following :)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
 
for a0 in range(8):
    if val(a0) == 0:
        for a1 in range(a0*8, (a0+1)*8):
            if val(a1) == 3:
                for a2 in range(a1*8, (a1+1)*8):
                    if val(a2) == 5:
                        for a3 in range(a2*8, (a2+1)*8):
                            if val(a3) == 5:
                                for a4 in range(a3*8, (a3+1)*8):
                                    if val(a4) == 5:
                                        for a5 in range(a4*8, (a4+1)*8):
                                            if val(a5) == 4:
                                                for a6 in range(a5*8, (a5+1)*8):
                                                    if val(a6) == 3:
                                                        print(a6)

I formed that crazy nested code one clause at a time, and verified it was producing the values from back to front properly. Once I verified it, I knew I needed to create a simpler construct, so I created the following recursive function:

1
2
3
4
5
6
7
 
def check(m, n, idx):
    for a in range(m, n):
        if val(a) == expected[idx]:
            if idx == 15:
                yield a
            else:
                yield from check(a*8, (a+1)*8, idx+1)

After that, it was simply a matter of choosing the first value it generated:

1
 
return next(check(0,8,0))

It takes 57 μs to compute part 2 !

New Python Concepts

  • ^ xor operator
  • next()
  • yield from
  • yield

Conclusion

Today’s puzzle had similarities to Advent of Code 2020 Day 8. I remember not liking that puzzle very much for two reasons: 1) I struggled to find real world applicability for the type of work I do, or want to do, and 2) It was very difficult - I think I had to pull the plug, and ask for help.

Those two reasons applied today also, but I persevered a little longer this time, and was very fortunate to be successful, so it’s much more gratifying. In the end, I’m very pleased with my solution, and with Python’s assistance.