Day 17 2024 - this was fun

5 files changed, 337 insertions, 0 deletions

diff --git a/2024/17/Makefile b/2024/17/Makefile
new file mode 100644
index 0000000..68d9689
--- /dev/null
+++ b/2024/17/Makefile
@@ -0,0 +1,24 @@
+CC=g++ -std=c++20 -g -Wall
+
+a:
+        ${CC} -o a.out day17a.cpp
+
+b:
+        ${CC} -o b.out day17b.cpp
+
+clean:
+        rm -f a b
+
+atest: a
+        ./a.out
+
+btest: b
+        ./b.out
+
+arun: a
+        ./a.out < input
+
+brun: b
+        ./b.out < input
+
+.PHONY: a b clean atest btest arun brun
diff --git a/2024/17/day17a.cpp b/2024/17/day17a.cpp
new file mode 100644
index 0000000..27f8aed
--- /dev/null
+++ b/2024/17/day17a.cpp
@@ -0,0 +1,82 @@
+#include <algorithm>
+#include <cstdint>
+#include <iostream>
+#include <map>
+#include <queue>
+#include <ranges>
+#include <set>
+#include <sstream>
+#include <string>
+#include <string_view>
+#include <vector>
+using namespace std;
+
+class CPU {
+public:
+        CPU(uint64_t a, uint64_t b, uint64_t c) : A{a}, B{b}, C{c} {}
+
+        void process(const vector<uint64_t>& v) {
+                for (unsigned ip = 0; ip < v.size(); ) {
+                        switch (v[ip]) {
+                        case 0:
+                                A >>= combo(v[ip+1]);
+                                ip += 2;
+                                break;
+                        case 1:
+                                B ^= v[ip+1];
+                                ip += 2;
+                                break;
+                        case 2:
+                                B = combo(v[ip+1]) % 8;
+                                ip += 2;
+                                break;
+                        case 3:
+                                ip = A == 0 ? ip+2 : v[ip+1];
+                                break;
+                        case 4:
+                                B ^= C;
+                                ip += 2;
+                                break;
+                        case 5:
+                                cout << combo(v[ip+1])%8 << ",";
+                                ip += 2;
+                                break;
+                        case 6:
+                                B = A >> combo(v[ip+1]);
+                                ip += 2;
+                                break;
+                        case 7:
+                                C = A >> combo(v[ip+1]);
+                                ip += 2;
+                                break;
+                        default:
+                                cout << "Error! Operator " << v[ip] << endl;
+                                exit(1);
+                        }
+                }
+                cout << endl;
+        }
+private:
+        uint64_t A, B, C;
+
+        uint64_t& reg(uint64_t i) {
+                return i == 0 ? A : (i == 1 ? B : C);
+        }
+
+        uint64_t combo(uint64_t i) {
+                return i <= 3 ? i : reg(i-4);
+        }
+};
+
+int main() {
+        uint64_t a, b, c;
+        cin >> a >> b >> c;
+        CPU cpu(a, b, c);
+
+        vector<uint64_t> instructions;
+        while (cin >> a)
+                instructions.push_back(a);
+
+        cpu.process(instructions);
+        return 0;
+}
diff --git a/2024/17/day17b-bruteforce.cpp b/2024/17/day17b-bruteforce.cpp
new file mode 100644
index 0000000..a400d5c
--- /dev/null
+++ b/2024/17/day17b-bruteforce.cpp
@@ -0,0 +1,102 @@
+#include <algorithm>
+#include <cstdint>
+#include <iostream>
+#include <map>
+#include <queue>
+#include <ranges>
+#include <set>
+#include <sstream>
+#include <string>
+#include <string_view>
+#include <vector>
+using namespace std;
+
+class CPU {
+public:
+        CPU(uint64_t a, uint64_t b, uint64_t c) : A{a}, B{b}, C{c} {}
+
+        bool process(const vector<uint64_t>& v) {
+                unsigned j = 0;
+                for (unsigned ip = 0; ip < v.size() && j <= v.size(); ) {
+                        switch (v[ip]) {
+                        case 0:
+                                A >>= combo(v[ip+1]);
+                                ip += 2;
+                                break;
+                        case 1:
+                                B ^= v[ip+1];
+                                ip += 2;
+                                break;
+                        case 2:
+                                B = combo(v[ip+1]) % 8;
+                                ip += 2;
+                                break;
+                        case 3:
+                                ip = A == 0 ? ip+2 : v[ip+1];
+                                break;
+                        case 4:
+                                B ^= C;
+                                ip += 2;
+                                break;
+                        case 5:
+                                if (j == v.size() || v[j] != combo(v[ip+1])%8)
+                                        return false;
+                                j++;
+                                ip += 2;
+                                break;
+                        case 6:
+                                B = A >> combo(v[ip+1]);
+                                ip += 2;
+                                break;
+                        case 7:
+                                C = A >> combo(v[ip+1]);
+                                ip += 2;
+                                break;
+                        default:
+                                cout << "Error! Operator " << v[ip] << endl;
+                                exit(1);
+                        }
+                }
+                return j == v.size();
+        }
+
+        void setreg(uint64_t a, uint64_t b, uint64_t c) {
+                A = a;
+                B = b;
+                C = c;
+        }
+private:
+        uint64_t A, B, C;
+
+        uint64_t& reg(uint64_t i) {
+                return i == 0 ? A : (i == 1 ? B : C);
+        }
+
+        uint64_t combo(uint64_t i) {
+                return i <= 3 ? i : reg(i-4);
+        }
+};
+
+int main() {
+        uint64_t a, b, c;
+        cin >> a >> b >> c;
+        CPU cpu(a, b, c);
+
+        vector<uint64_t> instructions;
+        while (cin >> a)
+                instructions.push_back(a);
+
+        const uint64_t M = 10000000000;
+        const uint64_t N = 100000000000;
+        for (a = M; a < N; a++) {
+if (a % 1000000 == 0)
+cout << "tring " << a << endl;
+                cpu.setreg(a, 0, 0);
+                if (cpu.process(instructions)) {
+                        cout << "Found it: " << a << endl;
+                        return 0;
+                }
+        }
+        cout << "Not found for A < " << N << endl;
+        return 0;
+}
diff --git a/2024/17/day17b.cpp b/2024/17/day17b.cpp
new file mode 100644
index 0000000..499a559
--- /dev/null
+++ b/2024/17/day17b.cpp
@@ -0,0 +1,88 @@
+/*
+This solution is ad-hoc for my input.
+
+Brute force was not working, so I inspected the input. I noticed that
+the only jump instruction was at the end, jumping back to 0. So the
+program is a 'while (A != 0)' loop.
+
+Disassembling the program I got:
+
+start:
+2 4 // B = A % 8
+1 5 // B = B ^ 5
+7 5 // C = A >> B
+1 6 // B = B ^ 6
+4 1 // B = B ^ C
+5 5 // print B % 8
+0 3 // A = A >> 3
+3 0 // If A != 0 goto start
+
+Which can be rewritten as
+
+for (A = a; A != 0; A >>= 3) {
+        B1 = (A % 8) ^ 5;
+        C = A >> B1;
+        B2 = (B1 ^ 6) ^ C;
+        print(B2 % 8);
+}
+
+Where a is the value initially in register A. Here I split B in B1 and
+B2 for simplicity.
+
+What we need to do now is work out a sequence of values a_1, a_2, a_3...
+such that at step i the program prints p_i (the i-th instruction of
+the program itself, i.e. the desired input) and leaves a_{i+1} in the
+register. This is easier to do if we reason backwards: at the last step we
+want the program to print 0 and leave 0 in register A. From the equations
+above we can work out that this happens if at the second-to-last step
+the value in the A register is 3.
+
+Writing a_{i-1} = 8a_i + Y and x = B2 % 8 we have
+
+x = (B1 ^ 6) ^ (a_{i-1} >> B1) % 8 =
+  = (Y ^ 5 ^ 6) ^ (a_{i-1} >> (Y ^ 5)) % 8 =
+  = (Y ^ 3) ^ ((8*a_i+Y) >> (Y ^ 5)) % 8
+
+At each step there are multiple possible values for Y, we have to try
+them all.
+*/
+
+#include <cstdint>
+#include <iostream>
+#include <vector>
+using namespace std;
+
+uint64_t f(uint64_t a, uint64_t Y) {
+        // This is what my input program outputs at each iteration
+        // if the value in register A is 8*a+Y
+        return (Y ^ 3) ^ ((8*a + Y) >> (Y ^ 5));
+}
+
+bool tryi(const vector<uint64_t>& p, vector<uint64_t>& A, int i) {
+        if (i < 0)
+                return true;
+
+        for (uint64_t Y = 0; Y < 8; Y++) {
+                if (p[i] == f(A[i+1], Y) % 8) {
+                        A[i] = (A[i+1] << 3) + Y;
+                        if (tryi(p, A, i-1))
+                                return true;
+                }
+        }
+
+        return false;
+}
+
+int main() {
+        // Hard-coded input
+        vector<uint64_t> p {2, 4, 1, 5, 7, 5, 1, 6, 4, 1, 5, 5, 0, 3, 3, 0};
+
+        uint64_t N {p.size()};
+        vector<uint64_t> A(N+1);
+        A[N] = 0; // Last value in the register, so the program stops
+
+        tryi(p, A, N-1);
+
+        cout << A[0] << endl;
+        return 0;
+}
diff --git a/2024/17/disassembly b/2024/17/disassembly
new file mode 100644
index 0000000..edabb41
--- /dev/null
+++ b/2024/17/disassembly
@@ -0,0 +1,41 @@
+start:
+2 4 // B = A % 8
+1 5 // B = B ^ 5
+7 5 // C = A >> B
+1 6 // B = B ^ 6
+4 1 // B = B ^ C
+5 5 // print B % 8
+0 3 // A = A >> 3
+3 0 // If A != 0 goto start
+
+for (A = a; A != 0; A >> 3) {
+        B1 = (A % 8) ^ 5;
+        C = A >> B1;
+        B2 = (B1 ^ 6) ^ C;
+        print(B2 % 8);
+}
+
+Goal: Find A such that one iteration prints x and leaves A = a
+Going backwards:
+A >> 3 = a -> A = 8a + Y
+B2 = x
+B1 = (A % 8) ^ 5 = Y^5
+x = (B1 ^ 6) ^ (A >> B1) = (Y^5 ^ 6) ^ (A >> Y^5)
+  = (Y ^ 3) ^ (A >> Y^5)
+-> x ^ (Y^3) = A >> Y^5
+-> A = ((a^Y^3) << Y^5) + Z for some Z < Y^5 < 8
+
+At the last iteartion, x = 0 and a = 0 so:
+-> A = Y
+-> x = (Y^3) ^ (Y >> Y^5)
+
+Y = 0 => x = 3
+Y = 1 => x = 2 ^ (1 >> 4) = 2
+Y = 2 => x = 1 ^ (2 >> 7) = 1
+Y = 3 => x = 0 ^ (3 >> 2) = 0
+
+=> A = Y = 3
+
+Second to last, x = 3 and a = 3, so
+-> A = 24 + Y
+3 = (A - 24) ^ 3 ^ ((A-24) >> (A-24)^5)