commit a3899249df1fe7aa84fd119c356de57ff0180397
parent 443d5279ed7f62916a1f62c7b4ffec5bda471bd5
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Tue, 17 Dec 2024 08:39:11 +0100
Day 17 2024 - this was fun
Diffstat:
11 files changed, 352 insertions(+), 0 deletions(-)
diff --git a/2024/17/Makefile 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
@@ -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
@@ -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
@@ -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
@@ -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)
diff --git a/2024/17/input b/2024/17/input
@@ -0,0 +1,5 @@
+Register A: 60589763
+Register B: 0
+Register C: 0
+
+Program: 2,4,1,5,7,5,1,6,4,1,5,5,0,3,3,0
diff --git a/2024/17/input-cleaned b/2024/17/input-cleaned
@@ -0,0 +1,2 @@
+60589763 0 0
+2 4 1 5 7 5 1 6 4 1 5 5 0 3 3 0
diff --git a/2024/17/solution b/2024/17/solution
@@ -0,0 +1,2 @@
+107413700225434 0 0
+2 4 1 5 7 5 1 6 4 1 5 5 0 3 3 0
diff --git a/2024/17/t1 b/2024/17/t1
@@ -0,0 +1,2 @@
+2024 0 0
+0 1 5 4 3 0
diff --git a/2024/17/test b/2024/17/test
@@ -0,0 +1,2 @@
+729 0 0
+0 1 5 4 3 0
diff --git a/2024/17/test2 b/2024/17/test2
@@ -0,0 +1,2 @@
+729 0 0
+0 3 5 4 3 0
