From a0e775b0a4805a7c1af12c1a956cd9fd74c54b2c Mon Sep 17 00:00:00 2001
From: Sebastiano Tronto <sebastiano@tronto.net>
Date: Tue, 17 Dec 2024 08:39:11 +0100
Subject: Day 17 2024 - this was fun

---
 2024/17/day17b.cpp | 88 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 88 insertions(+)
 create mode 100644 2024/17/day17b.cpp

(limited to '2024/17/day17b.cpp')

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;
+}
-- 
cgit v1.3