Advent of Code 2024 Day 17 Solve

[@augustdahlkvist3998]

You know the problem is cooked when this guy is taking an hour to solve it.

[@tylermmalone]

@@augustdahlkvist3998 fr lol

[@oofmatoes]

My bruteforce from 7 hours ago is still running

[@tylermmalone]

lol

[@LogicalErrors]

What speed are you up to? After some optimisation mine was doing more than a billion per hour, without further info that looked fast, so also kept it running. Then took a closer look at the numbers. The 3-bit, modulo 8, situation seems to indicate that the amount of numbers in the output increase for n in 8^n. Given the amount of numbers in my input program a quick calculation later it seems that would take at least 34 years for a full brute force at my speed 😅.

[@NStripleseven]

DW, you’ll get there eventually. Final answer is only like 2^45

[@n0ne0ne]

still running?

[@mathiaskern7031]

Try A=0...7 for your program and see which values output the last number of the program. Try those (recursively). Shift them 3 bits to the left, and then combine them via OR once more with values 0 to 7, and see which produce the second last number of the program, and so on. You will encounter some dead ends and then the recursion backtracks, but in the end you will have a number (at least one) of candidates for A that produce the desired program. Pick the smallest one. The code is not very long as it uses the run/execute method from part 1.

[@bikkel77]

Was a nice journey this one (I made a walkthrough video about my solution). Had a couple of insights after decompiling the program which turned all operations into bit operations ('left shift', 'right shift', 'and' and 'xor', modulo 8 is just 'and' 7 and division by '2 to the power i' is just 'right shift i'): - The input value has to be 3*instructions.length in terms of bits (so 48 bits long) - The program runs basically a loop until the output value (new value of 'a' after one loop) is zero - Each step at most uses the 10 least significant bits of value a, however to yield a zero output it's possible to only try 8 different values. - The outputValue of each loop has to match up with the required inputValue of each loop to yield the expected output string. So a basic DFS or BFS can be done by starting from the end of the instruction list and working your way backwards to the start, each time left shifting your value with 3 bits. For each instruction you only have to do at most 8 iterations to match 3 bits of input. Doing this the code runs in less than 50 ms.

[@tylermmalone]

Gonna reference this later

[@IulianYT]

I am not a speed coder, but I didn't even bother to write code to parse input, I just manually introduced the variables straight away

[@MalicePandrodor]

Interesting approach. I just printed first ~10k outputs and tried to spot the pattern. If you look at the first number in all outputs you can see it creates a sequence that repeats every 1024 (I assume this is the case for all test cases). The second number in all outputs appears at 8th position (for reg A = 8) and follows the same sequence but every number is repeated 8 times (you need to skip the first element for the first occurrence in the sequence, not sure why :D). The same for 3rd number in the output. Starts from the 8*8 (reg A = 64) and follows the sequence when every number is repeated 64 times. And so on. To find the answer you have to create a number in form: a15 * 8^15 + a14 * 8^14 + ... + a2 * 8^2 + a1 * 8^1 + a0 * 8^0 and put it as a input for the program (testing even very high number is very fast). You have to find the a15 that gives expected last number, then to find a14 that gives the second last number and so on, up to the a0.

[@bikkel77]

If you look at the decompiled program, this can be explained by the fact that at most 10 bits are used of the value of A. It is at most right shifted 7 times and then the three least significant bits are used in an xor.

[@NStripleseven]

Did everyone get the same input for this one?

[@MalicePandrodor]

@@NStripleseven I don't think so

[@nicklase0000]

I'm not sure the code will look correct, but this was my solution for the second part: def test(a, b, c, prg, k): idx = k while idx < len(prg): b = a % 8 b = b ^ 1 c = int(a / (2**b)) a = int(a / 8) b = b ^ c b = b ^ 6 if b % 8 == prg[idx]: idx += 1 else: return idx return idx prg = [2, 4, 1, 1, 7, 5, 0, 3, 4, 3, 1, 6, 5, 5, 3, 0] def solve(idx, a): if idx < 0: print("solution", a) return for aa in range(0, 8): aaa = 8 * a + aa res = test(aaa, 0, 0, prg, idx) if res == 16: print(idx, res) solve(idx - 1, aaa) solve(15, 0)

[@gerardomiranda2284]

I used brute force... But, the trick for me was reducing the range. basically I noticed that the last elements were the last to change, so I just narrowed the range based on the last elements of the output and comparing them with the last elements of program. That way the brute force took like 5 minutes

[@1vader]

You can actually just do modulus, bit shift, and division on bit vecs in z3. I mostly just re-used my code from part 1, replaced "a" with a z3 BitVec variable, and let that build up the right conditions. Had to replace // with / (which is always floor division on a BitVec) and 2**x with 1

[@artemistrubacheev7704]

I've tried using z3 too, but I am so bad at it I ended up doing bitwise brute force as everyone else :D

[@DoctorDuckload]

Amazing. I actually coded your very last idea. No way I could have reverse engineered the thing without any hints. But the recursive DFS with backtracking is simple to code and it works very fast once you figure it out.

[@WayoshiM]

I saw the every three contiguous bits of A maps to each output fairly early on, just didn't expect that to be brute forceable (laughably so - the sample space really grows small).

[@Tresorthas]

What an insanely inane problem. Every year has at least one, usually around day 20-23, but this year we seem to get it early. Let's hope there will only be more sensible ones going forward.

[@Whateverworksism]

Why do you think it's inane? And not just inane, but *insanely* inane.

[@stephenmorse8207]

No day 18 video? It was an easy one!

[@tomwatson7114]

Mine was a pretty awful bruteforce solution that somehow worked, but I recognised that my reversed outputs would "roughly" increment as my A register got larger, and so using a binary search to find the approximate region of the correct answer and then iterating in chunks of descending size as I got closer to the input program got me the answer in sub 4 seconds (Python). Disgusting, but it worked :D

[@Bundas102]

I wrote the inverse of the instructions. One instruction in the loop needed an operand that wasn't yet resolved, but only 0..7 give different results, so i just did a dfs on that. I got 62 possible answers and the minimum is the right answer. Too bad it took me 2 hours do it :D JS screwed me a bit. I don't usually use it, basically only for AoC, so I didn't know xor casts to 32 bit integers. Luckily I noticed it quickly enough. Btw the divisions are actually right shifts by the combo op.

[@God-i2]

Abu Bakar Al Bagdadi Is Dead

[@cursed_nerd]

bro you lagging irl

[@God-i2]

@cursed_nerd He died like a dog

[@jacobgsutton]

that part 2 almost put me in a early grave

[@jacobgsutton]

I gave up on part 2 the night of then finally solved it in the shower in the morning lmao. I move through the commands backwards and increase the most significant 3 bits by 1 until condition 16 is met then move on to the next 3 bits for satisfying condition 15 and so. Moving backwards allows for you to not to worry about the wacky dependance on bits "ahead" of where you currently are at in the bit string. If I ever can't satisfy a cond by looping through all 8, I go back a cond and increase again and "back propagate" until I can satisfy everything. Moving down to the next 3 bits after finding the smallest possible number in the current segment also guarantees minimality of the solution. Here's my code: cmds=[2,4,1,3,7,5,0,3,1,5,4,1,5,5,3,0] def good_bits(n, out): expr = (n%8)^3 return ((expr^5)^(n//2**expr))%8 == out A_init = 0 i = len(cmds)-1 chosen_bits = {} while True: # print(i, bin(A_init)) bits = chosen_bits[i]+1 if i in chosen_bits else 0 while True and bits < 8: A_init = A_init&int('1'*(len(cmds)-1-i)*3+'000',2) | bits if good_bits(A_init, cmds[i]): break bits += 1 if bits >= 8: chosen_bits[i] = 0 A_init >>= 3 i += 1 else: if i == 0: break chosen_bits[i] = bits A_init