commit 21e1237e93703f632253f042bd5877998d81c507
parent cffdd7d528607f7281fc0a1fed9195e711c1b70f
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Mon, 23 Dec 2024 07:55:11 +0100
Day 23 2024
Diffstat:
4 files changed, 118 insertions(+), 0 deletions(-)
diff --git a/2024/23/Makefile b/2024/23/Makefile
@@ -0,0 +1,11 @@
+CC=g++ -std=c++20 -g -Wall
+
+a:
+ ${CC} -o a.out day23a.cpp
+ ./a.out
+
+b:
+ ${CC} -o b.out day23b.cpp
+ ./b.out
+
+.PHONY: a b
diff --git a/2024/23/day23a.cpp b/2024/23/day23a.cpp
@@ -0,0 +1,40 @@
+#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;
+
+set<int> computers;
+bool m[26*26][26*26];
+
+int index(char a, char b) { return (int)(a-'a') + 26*(int)(b-'a'); }
+bool t(int i) { return i % 26 == 't' - 'a'; }
+
+int main() {
+ string line;
+ while (getline(cin, line)) {
+ int i = index(line[0], line[1]);
+ int j = index(line[3], line[4]);
+ computers.insert(i);
+ computers.insert(j);
+ m[i][j] = m[j][i] = true;
+ }
+
+ vector cv(computers.begin(), computers.end());
+ int tot = 0;
+ for (unsigned i = 0; i < cv.size(); i++)
+ for (unsigned j = i+1; j < cv.size(); j++)
+ for (unsigned k = j+1; k < cv.size(); k++)
+ tot += m[cv[i]][cv[j]] && m[cv[j]][cv[k]] && m[cv[k]][cv[i]] &&
+ (t(cv[i]) || t(cv[j]) || t(cv[k]));
+
+ cout << tot << endl;
+ return 0;
+}
diff --git a/2024/23/day23b.cpp b/2024/23/day23b.cpp
@@ -0,0 +1,66 @@
+#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;
+
+set<int> computers;
+bool m[26*26][26*26];
+
+int index(char a, char b) { return (int)(b-'a') + 26*(int)(a-'a'); }
+void printnode(int i) { cout << (char)('a'+i/26) << (char)('a'+i%26); }
+bool t(int i) { return i % 26 == 't' - 'a'; }
+
+bool all(int i, const set<int>& v) {
+ for (auto j : v)
+ if (!m[i][j])
+ return false;
+ return true;
+}
+
+int main() {
+ string line;
+ while (getline(cin, line)) {
+ int i = index(line[0], line[1]);
+ int j = index(line[3], line[4]);
+ computers.insert(i);
+ computers.insert(j);
+ m[i][j] = m[j][i] = true;
+ }
+
+ vector<set<int>> cliques[15];
+ cliques[0].push_back(set<int>());
+ for (int i = 1; ; i++) {
+ for (auto& c : cliques[i-1]) {
+ int mm = *max_element(c.begin(), c.end());
+ for (auto j : computers) {
+ if (j <= mm) continue;
+ if (all(j, c)) {
+ set nw = c;
+ nw.insert(j);
+ cliques[i].push_back(nw);
+ }
+ }
+ }
+ auto n = cliques[i].size();
+ cout << "Found " << n << " cliques of size " << i << endl;
+ if (n == 0) break;
+ auto cc = *cliques[i].begin();
+ vector<int> cv(cc.begin(), cc.end());
+ sort(cv.begin(), cv.end());
+ for (auto j : cv) {
+ printnode(j);
+ cout << ",";
+ }
+ cout << endl;
+ }
+
+ return 0;
+}
diff --git a/2024/learned.txt b/2024/learned.txt
@@ -10,3 +10,4 @@ List of things I learned (or refreshed) with this year's AoC.
* Day 9: std::views
* 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)
