commit 19be9f44dbecdde03662be2248eda5b739d67038
parent 21e1237e93703f632253f042bd5877998d81c507
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Wed, 25 Dec 2024 00:40:50 +0100
Day 24 2024 still don't know how I managed to solve this
Diffstat:
5 files changed, 350 insertions(+), 0 deletions(-)
diff --git a/2024/24/Makefile 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
@@ -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
@@ -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
@@ -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
@@ -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
