day17b.cpp (2151B)
1 /* 2 This solution is ad-hoc for my input. 3 4 Brute force was not working, so I inspected the input. I noticed that 5 the only jump instruction was at the end, jumping back to 0. So the 6 program is a 'while (A != 0)' loop. 7 8 Disassembling the program I got: 9 10 start: 11 2 4 // B = A % 8 12 1 5 // B = B ^ 5 13 7 5 // C = A >> B 14 1 6 // B = B ^ 6 15 4 1 // B = B ^ C 16 5 5 // print B % 8 17 0 3 // A = A >> 3 18 3 0 // If A != 0 goto start 19 20 Which can be rewritten as 21 22 for (A = a; A != 0; A >>= 3) { 23 B1 = (A % 8) ^ 5; 24 C = A >> B1; 25 B2 = (B1 ^ 6) ^ C; 26 print(B2 % 8); 27 } 28 29 Where a is the value initially in register A. Here I split B in B1 and 30 B2 for simplicity. 31 32 What we need to do now is work out a sequence of values a_1, a_2, a_3... 33 such that at step i the program prints p_i (the i-th instruction of 34 the program itself, i.e. the desired input) and leaves a_{i+1} in the 35 register. This is easier to do if we reason backwards: at the last step we 36 want the program to print 0 and leave 0 in register A. From the equations 37 above we can work out that this happens if at the second-to-last step 38 the value in the A register is 3. 39 40 Writing a_{i-1} = 8a_i + Y and x = B2 % 8 we have 41 42 x = (B1 ^ 6) ^ (a_{i-1} >> B1) % 8 = 43 = (Y ^ 5 ^ 6) ^ (a_{i-1} >> (Y ^ 5)) % 8 = 44 = (Y ^ 3) ^ ((8*a_i+Y) >> (Y ^ 5)) % 8 45 46 At each step there are multiple possible values for Y, we have to try 47 them all. 48 */ 49 50 #include <cstdint> 51 #include <iostream> 52 #include <vector> 53 using namespace std; 54 55 uint64_t f(uint64_t a, uint64_t Y) { 56 // This is what my input program outputs at each iteration 57 // if the value in register A is 8*a+Y 58 return (Y ^ 3) ^ ((8*a + Y) >> (Y ^ 5)); 59 } 60 61 bool tryi(const vector<uint64_t>& p, vector<uint64_t>& A, int i) { 62 if (i < 0) 63 return true; 64 65 for (uint64_t Y = 0; Y < 8; Y++) { 66 if (p[i] == f(A[i+1], Y) % 8) { 67 A[i] = (A[i+1] << 3) + Y; 68 if (tryi(p, A, i-1)) 69 return true; 70 } 71 } 72 73 return false; 74 } 75 76 int main() { 77 // Hard-coded input 78 vector<uint64_t> p {2, 4, 1, 5, 7, 5, 1, 6, 4, 1, 5, 5, 0, 3, 3, 0}; 79 80 uint64_t N {p.size()}; 81 vector<uint64_t> A(N+1); 82 A[N] = 0; // Last value in the register, so the program stops 83 84 tryi(p, A, N-1); 85 86 cout << A[0] << endl; 87 return 0; 88 }