Day 24 2024 still don't know how I managed to solve this

5 files changed, 350 insertions, 0 deletions

diff --git a/2024/24/Makefile b/2024/24/Makefile
new file mode 100644
index 0000000..1291678
--- /dev/null
+++ b/2024/24/Makefile
@@ -0,0 +1,11 @@
+CC=g++ -std=c++20 -g -Wall
+
+a:
+        ${CC} -o a.out day24a.cpp
+        ./a.out
+
+b:
+        ${CC} -o b.out day24b.cpp
+        ./b.out
+
+.PHONY: a b
diff --git a/2024/24/clean.sh b/2024/24/clean.sh
new file mode 100755
index 0000000..891ecf7
--- /dev/null
+++ b/2024/24/clean.sh
@@ -0,0 +1,3 @@
+#!/bin/sh
+
+sed 's/XOR/^/; s/OR/|/; s/AND/\&/'
diff --git a/2024/24/day24a.cpp b/2024/24/day24a.cpp
new file mode 100644
index 0000000..231b206
--- /dev/null
+++ b/2024/24/day24a.cpp
@@ -0,0 +1,88 @@
+/* Use clean.sh on the input first */
+
+#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;
+
+int8_t state[36*36*36];
+
+int d(char x) { return x >= 'a' && x <= 'z' ? x-'a' : 26+x-'0'; }
+int index(char a, char b, char c) { return d(c) + 36 * (d(b) + 36 * d(a)); }
+int z(int i) { return index('z', (i/10)+'0', (i%10)+'0'); }
+
+enum class Op { AND, OR, XOR };
+
+class Gate {
+public:
+        int x, y, z;
+        Op op;
+
+        bool ready() const {
+                return state[x] != -1 && state[y] != -1;
+        }
+
+        bool operate() const { /* Returns true if the operation flips a bit */
+                auto oldstate = state[z];
+                switch (op) {
+                case Op::AND:
+                        state[z] = state[x] & state[y];
+                        break;
+                case Op::OR:
+                        state[z] = state[x] | state[y];
+                        break;
+                case Op::XOR:
+                        state[z] = state[x] ^ state[y];
+                        break;
+                }
+                return oldstate != state[z];
+        }
+};
+
+Op make_op(char c) {
+        switch (c) {
+        case '&': return Op::AND;
+        case '|': return Op::OR;
+        default: return Op::XOR;
+        }
+}
+
+int main() {
+        vector<Gate> gates;
+        fill(state, state + 36*36*36, -1);
+        string line;
+
+        while (getline(cin, line) && line != "")
+                state[index(line[0], line[1], line[2])] = line[5]-'0';
+
+        while (getline(cin, line))
+                gates.push_back(Gate {
+                        .x = index(line[0], line[1], line[2]),
+                        .y = index(line[6], line[7], line[8]),
+                        .z = index(line[13], line[14], line[15]),
+                        .op = make_op(line[4])
+                });
+
+        for (bool flag = true; flag; ) {
+                flag = false;
+                for (auto g : gates)
+                        if (g.ready())
+                                flag = flag || g.operate();
+        }
+
+        int64_t result = 0;
+        for (int64_t i = 0, j = 1; state[z(i)] != -1; i++, j *= 2)
+                result += (int64_t)state[z(i)] * j;
+
+        cout << result << endl;
+
+        return 0;
+}
diff --git a/2024/24/day24b.cpp b/2024/24/day24b.cpp
new file mode 100644
index 0000000..ba8e347
--- /dev/null
+++ b/2024/24/day24b.cpp
@@ -0,0 +1,247 @@
+/*
+
+I don't know what addition circuits look like, but they should have some
+kind of regular structure. I manually inspected how the first few digits
+behave to get an idea.
+
+With some more manual inspection I noticed that the "temporary result"
+gates that are results of a XOR operation always appear as terms in
+exactly one XOR and one AND operation; the same thing happens for
+OR-results, while AND-results appear as terms only in one OR operation.
+
+This excludes z-gates, which are the result of a XOR operation (except
+for z45, which is the result of an OR operation) and do not appear as
+terms in any other operation. And of course "errors" do not follow this
+pattern either.
+
+So what I do is going through all gates and see if their result
+satisfies the conditions above. This gives 8 candidates for the error,
+but unfortunately they were not the correct answer (I tried submitting
+this list 3 times).
+
+I thought about it a bit longer and I realized that one of the entries
+in my list is rfg, which appears as the result of x00 & y00. I thought
+that since this was the first digit, it could be an edge case and thus
+correctly behaving differently from the others. This leaves me with
+7 candidates only, so I have to find another one.
+
+One of the gates I had to swap (z23) was the result of an OR operation,
+but should have been the result o a XOR. But any XOR-result could be
+swapped with an OR-result without breaking the conditions I guessed at the
+beginning. So I tried them all: for every XOR-gate I swapped the results
+with my other 7 candidates in every way possible according to my rules,
+and checked which of these re-arrangements gave the correct answer for
+the example input.
+
+I found two candidates (kdf and nsr). I could have checked more inputs
+to see which of the two worked, or I could just try both of them. Of
+course, I choose the second option, and kdf worked.
+
+Did I get the gold star? Yes. Do I know how I was supposed to solve this
+problem? Not a clue. But hey, I solved it without hints, a win is a win.
+
+*/
+
+#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;
+
+enum class Op { AND, OR, XOR };
+
+class Gate {
+public:
+        int x, y, z;
+        Op op;
+
+        bool ready(const int8_t *state) const {
+                return state[x] != -1 && state[y] != -1;
+        }
+
+        bool operate(int8_t *state) const { /* Returns true if the operation flips a bit */
+                auto oldstate = state[z];
+                switch (op) {
+                case Op::AND:
+                        state[z] = state[x] & state[y];
+                        break;
+                case Op::OR:
+                        state[z] = state[x] | state[y];
+                        break;
+                case Op::XOR:
+                        state[z] = state[x] ^ state[y];
+                        break;
+                }
+                return oldstate != state[z];
+        }
+};
+
+int8_t state[36*36*36];
+vector<Gate> gates;
+
+int d(char x) { return x >= 'a' && x <= 'z' ? x-'a' : 26+x-'0'; }
+char h(int i) { return i >= 26 ? i-26+'0' : i+'a'; }
+int index(char a, char b, char c) { return d(c) + 36 * (d(b) + 36 * d(a)); }
+string name(int i) {
+        string r = "   ";
+        r[0] = h(i / (36*36));
+        r[1] = h((i/ 36) % 36);
+        r[2] = h(i % 36);
+        return r;
+}
+
+int64_t digit(int i, char c) {
+        return index(c, (i/10)+'0', (i%10)+'0');
+}
+
+int64_t getnum(char c, int m) {
+        int64_t result = 0;
+        for (int64_t i = 0, j = 1; i < m; i++, j *= 2)
+                result += (int64_t)state[digit(i, c)] * j;
+        return result;
+}
+
+Op make_op(char c) {
+        switch (c) {
+        case '&': return Op::AND;
+        case '|': return Op::OR;
+        default: return Op::XOR;
+        }
+}
+
+char opname(Op op) {
+        switch (op) {
+        case Op::AND: return '&';
+        case Op::OR: return '|';
+        default: return '^';
+        }
+}
+
+void printop(Gate g, const vector<Op>& a) {
+        cout << name(g.z) << " is " << name(g.x) << " " << opname(g.op)
+             << " " << name(g.y) << " but appears in ";
+        for (auto op : a)
+                cout << opname(op) << " ";
+        cout << endl;
+}
+
+int gg(const string& rr) {
+        for (unsigned i = 0; i < gates.size(); i++)
+                if (name(gates[i].z) == rr)
+                        return i;
+        return -1;
+}
+
+void swapgates(vector<Gate>& local_gates, vector<int> ixsa,
+    vector<int> iasx, int iosx, int gswap) {
+}
+
+void run(int8_t *state, const vector<Gate>& gates) {
+        for (bool flag = true; flag; ) { 
+                flag = false;
+                for (auto g : gates)
+                        if (g.ready(state))
+                                flag = flag || g.operate(state);
+        }
+        int64_t x = getnum('x', 45);
+        int64_t y = getnum('y', 45);
+        int64_t z = getnum('z', 46);
+        if (x+y == z) cout << "Correct result! " << z << endl;
+}
+
+int main() {
+        fill(state, state + 36*36*36, -1);
+        string line;
+
+        while (getline(cin, line) && line != "")
+                state[index(line[0], line[1], line[2])] = line[5]-'0';
+
+        while (getline(cin, line))
+                gates.push_back(Gate {
+                        .x = index(line[0], line[1], line[2]),
+                        .y = index(line[6], line[7], line[8]),
+                        .z = index(line[13], line[14], line[15]),
+                        .op = make_op(line[4])
+                });
+
+#if 0
+        /* Print error candidates */
+        vector<string> bad;
+        for (auto g : gates) {
+                if (name(g.z)[0] == 'z') {
+                        if ((name(g.z) == "z45" && g.op != Op::OR) ||
+                            (name(g.z) != "z45" && g.op != Op::XOR)) {
+                                printop(g, vector<Op>());
+                                bad.push_back(name(g.z));
+                        }
+                        continue;
+                }
+                vector<Op> appears_in;
+                for (auto f : gates)
+                        if (g.z == f.x || g.z == f.y)
+                                appears_in.push_back(f.op);
+                if (g.op == Op::AND) {
+                        if (appears_in.size() != 1 || appears_in[0] != Op::OR) {
+                                printop(g, appears_in);
+                                bad.push_back(name(g.z));
+                        }
+                } else {
+                        if (appears_in.size() != 2 ||
+                            find(appears_in.begin(), appears_in.end(), Op::AND) == appears_in.end() ||
+                            find(appears_in.begin(), appears_in.end(), Op::XOR) == appears_in.end()) {
+                                printop(g, appears_in);
+                                bad.push_back(name(g.z));
+                        }
+                }
+        }
+
+        sort(bad.begin(), bad.end());
+
+        for (auto b : bad)
+                cout << b << ",";
+        cout << endl;
+#endif
+
+        vector<string> is_xor_shouldbe_and = { "ckj", "rpp", "dbp" };
+        vector<string> is_and_shouldbe_xor = { "fdv", "z15", "z39" };
+        string is_or_shouldbe_xor = "z23";
+
+        vector<int> ixsa = { gg("ckj"), gg("rpp"), gg("dbp") };
+        vector<int> iasx = { gg("fdv"), gg("z15"), gg("z39") };
+        int iosx = gg("z23");
+
+        vector<vector<pair<int, int>>> swaps = {
+                {{ixsa[0],iasx[0]}, {ixsa[1],iasx[1]}, {ixsa[2],iasx[2]}},
+                {{ixsa[0],iasx[0]}, {ixsa[1],iasx[2]}, {ixsa[2],iasx[1]}},
+                {{ixsa[0],iasx[1]}, {ixsa[1],iasx[0]}, {ixsa[2],iasx[2]}},
+                {{ixsa[0],iasx[1]}, {ixsa[1],iasx[2]}, {ixsa[2],iasx[0]}},
+                {{ixsa[0],iasx[2]}, {ixsa[1],iasx[1]}, {ixsa[2],iasx[0]}},
+                {{ixsa[0],iasx[2]}, {ixsa[1],iasx[0]}, {ixsa[2],iasx[1]}}
+        };
+
+        for (unsigned gswap = 0; gswap < gates.size(); gswap++) {
+                if (find(ixsa.begin(), ixsa.end(), gswap) != ixsa.end() ||
+                    find(iasx.begin(), iasx.end(), gswap) != iasx.end() ||
+                    (int)gswap == iosx || gates[gswap].op != Op::XOR)
+                        continue;
+                cout << "Trying gswap " << name(gates[gswap].z) << endl;
+                for (auto ss : swaps) {
+                        auto local_state = state;
+                        auto local_gates = gates;
+                        swap(local_gates[ss[0].first].z, local_gates[ss[0].second].z);
+                        swap(local_gates[ss[1].first].z, local_gates[ss[1].second].z);
+                        swap(local_gates[ss[2].first].z, local_gates[ss[2].second].z);
+                        swap(local_gates[iosx].z, local_gates[gswap].z);
+                        run(local_state, local_gates);
+                }
+        }
+
+        return 0;
+}
diff --git a/2024/learned.txt b/2024/learned.txt
index 8dce20a..844def5 100644
--- a/2024/learned.txt
+++ b/2024/learned.txt
@@ -11,3 +11,4 @@ List of things I learned (or refreshed) with this year's AoC.
 * Day 11: if(init; cond)
 * Day 19: more practice with std::string_view for constant string
 * Day 22: std::views::values for map (and keys)
+* Day 24: std::fill