aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--2024/17/Makefile24
-rw-r--r--2024/17/day17a.cpp82
-rw-r--r--2024/17/day17b-bruteforce.cpp102
-rw-r--r--2024/17/day17b.cpp88
-rw-r--r--2024/17/disassembly41
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 @@
1CC=g++ -std=c++20 -g -Wall
2
3a:
4 ${CC} -o a.out day17a.cpp
5
6b:
7 ${CC} -o b.out day17b.cpp
8
9clean:
10 rm -f a b
11
12atest: a
13 ./a.out
14
15btest: b
16 ./b.out
17
18arun: a
19 ./a.out < input
20
21brun: b
22 ./b.out < input
23
24.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 @@
1#include <algorithm>
2#include <cstdint>
3#include <iostream>
4#include <map>
5#include <queue>
6#include <ranges>
7#include <set>
8#include <sstream>
9#include <string>
10#include <string_view>
11#include <vector>
12using namespace std;
13
14class CPU {
15public:
16 CPU(uint64_t a, uint64_t b, uint64_t c) : A{a}, B{b}, C{c} {}
17
18 void process(const vector<uint64_t>& v) {
19 for (unsigned ip = 0; ip < v.size(); ) {
20 switch (v[ip]) {
21 case 0:
22 A >>= combo(v[ip+1]);
23 ip += 2;
24 break;
25 case 1:
26 B ^= v[ip+1];
27 ip += 2;
28 break;
29 case 2:
30 B = combo(v[ip+1]) % 8;
31 ip += 2;
32 break;
33 case 3:
34 ip = A == 0 ? ip+2 : v[ip+1];
35 break;
36 case 4:
37 B ^= C;
38 ip += 2;
39 break;
40 case 5:
41 cout << combo(v[ip+1])%8 << ",";
42 ip += 2;
43 break;
44 case 6:
45 B = A >> combo(v[ip+1]);
46 ip += 2;
47 break;
48 case 7:
49 C = A >> combo(v[ip+1]);
50 ip += 2;
51 break;
52 default:
53 cout << "Error! Operator " << v[ip] << endl;
54 exit(1);
55 }
56 }
57 cout << endl;
58 }
59private:
60 uint64_t A, B, C;
61
62 uint64_t& reg(uint64_t i) {
63 return i == 0 ? A : (i == 1 ? B : C);
64 }
65
66 uint64_t combo(uint64_t i) {
67 return i <= 3 ? i : reg(i-4);
68 }
69};
70
71int main() {
72 uint64_t a, b, c;
73 cin >> a >> b >> c;
74 CPU cpu(a, b, c);
75
76 vector<uint64_t> instructions;
77 while (cin >> a)
78 instructions.push_back(a);
79
80 cpu.process(instructions);
81 return 0;
82}
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 @@
1#include <algorithm>
2#include <cstdint>
3#include <iostream>
4#include <map>
5#include <queue>
6#include <ranges>
7#include <set>
8#include <sstream>
9#include <string>
10#include <string_view>
11#include <vector>
12using namespace std;
13
14class CPU {
15public:
16 CPU(uint64_t a, uint64_t b, uint64_t c) : A{a}, B{b}, C{c} {}
17
18 bool process(const vector<uint64_t>& v) {
19 unsigned j = 0;
20 for (unsigned ip = 0; ip < v.size() && j <= v.size(); ) {
21 switch (v[ip]) {
22 case 0:
23 A >>= combo(v[ip+1]);
24 ip += 2;
25 break;
26 case 1:
27 B ^= v[ip+1];
28 ip += 2;
29 break;
30 case 2:
31 B = combo(v[ip+1]) % 8;
32 ip += 2;
33 break;
34 case 3:
35 ip = A == 0 ? ip+2 : v[ip+1];
36 break;
37 case 4:
38 B ^= C;
39 ip += 2;
40 break;
41 case 5:
42 if (j == v.size() || v[j] != combo(v[ip+1])%8)
43 return false;
44 j++;
45 ip += 2;
46 break;
47 case 6:
48 B = A >> combo(v[ip+1]);
49 ip += 2;
50 break;
51 case 7:
52 C = A >> combo(v[ip+1]);
53 ip += 2;
54 break;
55 default:
56 cout << "Error! Operator " << v[ip] << endl;
57 exit(1);
58 }
59 }
60 return j == v.size();
61 }
62
63 void setreg(uint64_t a, uint64_t b, uint64_t c) {
64 A = a;
65 B = b;
66 C = c;
67 }
68private:
69 uint64_t A, B, C;
70
71 uint64_t& reg(uint64_t i) {
72 return i == 0 ? A : (i == 1 ? B : C);
73 }
74
75 uint64_t combo(uint64_t i) {
76 return i <= 3 ? i : reg(i-4);
77 }
78};
79
80int main() {
81 uint64_t a, b, c;
82 cin >> a >> b >> c;
83 CPU cpu(a, b, c);
84
85 vector<uint64_t> instructions;
86 while (cin >> a)
87 instructions.push_back(a);
88
89 const uint64_t M = 10000000000;
90 const uint64_t N = 100000000000;
91 for (a = M; a < N; a++) {
92if (a % 1000000 == 0)
93cout << "tring " << a << endl;
94 cpu.setreg(a, 0, 0);
95 if (cpu.process(instructions)) {
96 cout << "Found it: " << a << endl;
97 return 0;
98 }
99 }
100 cout << "Not found for A < " << N << endl;
101 return 0;
102}
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 @@
1/*
2This solution is ad-hoc for my input.
3
4Brute force was not working, so I inspected the input. I noticed that
5the only jump instruction was at the end, jumping back to 0. So the
6program is a 'while (A != 0)' loop.
7
8Disassembling the program I got:
9
10start:
112 4 // B = A % 8
121 5 // B = B ^ 5
137 5 // C = A >> B
141 6 // B = B ^ 6
154 1 // B = B ^ C
165 5 // print B % 8
170 3 // A = A >> 3
183 0 // If A != 0 goto start
19
20Which can be rewritten as
21
22for (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
29Where a is the value initially in register A. Here I split B in B1 and
30B2 for simplicity.
31
32What we need to do now is work out a sequence of values a_1, a_2, a_3...
33such that at step i the program prints p_i (the i-th instruction of
34the program itself, i.e. the desired input) and leaves a_{i+1} in the
35register. This is easier to do if we reason backwards: at the last step we
36want the program to print 0 and leave 0 in register A. From the equations
37above we can work out that this happens if at the second-to-last step
38the value in the A register is 3.
39
40Writing a_{i-1} = 8a_i + Y and x = B2 % 8 we have
41
42x = (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
46At each step there are multiple possible values for Y, we have to try
47them all.
48*/
49
50#include <cstdint>
51#include <iostream>
52#include <vector>
53using namespace std;
54
55uint64_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
61bool 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
76int 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}
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 @@
1start:
22 4 // B = A % 8
31 5 // B = B ^ 5
47 5 // C = A >> B
51 6 // B = B ^ 6
64 1 // B = B ^ C
75 5 // print B % 8
80 3 // A = A >> 3
93 0 // If A != 0 goto start
10
11for (A = a; A != 0; A >> 3) {
12 B1 = (A % 8) ^ 5;
13 C = A >> B1;
14 B2 = (B1 ^ 6) ^ C;
15 print(B2 % 8);
16}
17
18Goal: Find A such that one iteration prints x and leaves A = a
19Going backwards:
20A >> 3 = a -> A = 8a + Y
21B2 = x
22B1 = (A % 8) ^ 5 = Y^5
23x = (B1 ^ 6) ^ (A >> B1) = (Y^5 ^ 6) ^ (A >> Y^5)
24 = (Y ^ 3) ^ (A >> Y^5)
25-> x ^ (Y^3) = A >> Y^5
26-> A = ((a^Y^3) << Y^5) + Z for some Z < Y^5 < 8
27
28At the last iteartion, x = 0 and a = 0 so:
29-> A = Y
30-> x = (Y^3) ^ (Y >> Y^5)
31
32Y = 0 => x = 3
33Y = 1 => x = 2 ^ (1 >> 4) = 2
34Y = 2 => x = 1 ^ (2 >> 7) = 1
35Y = 3 => x = 0 ^ (3 >> 2) = 0
36
37=> A = Y = 3
38
39Second to last, x = 3 and a = 3, so
40-> A = 24 + Y
413 = (A - 24) ^ 3 ^ ((A-24) >> (A-24)^5)

Generated with cgit - Back to sebastiano.tronto.net