From e87bceffc3a19c0dd8acbcbc1b1195c60797ea5f Mon Sep 17 00:00:00 2001
From: Thomas Schmucker <ts@its1.de>
Date: Mon, 23 Dec 2024 12:02:40 +0100
Subject: aoc 2024, day 23, part 2

---
 2024/src/day23.cpp | 90 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 90 insertions(+)

diff --git a/2024/src/day23.cpp b/2024/src/day23.cpp
index 45d6d28..36f40e6 100644
--- a/2024/src/day23.cpp
+++ b/2024/src/day23.cpp
@@ -20,6 +20,23 @@ split(const string& line, char sep = ' ')
 	return parts;
 }
 
+template<typename Container>
+string
+join(const Container& container, const string& delimiter)
+{
+	ostringstream oss;
+	auto          it = container.begin();
+	if ( it != container.end() ) {
+		oss << *it;
+		++it;
+	}
+	while ( it != container.end() ) {
+		oss << delimiter << *it;
+		++it;
+	}
+	return oss.str();
+}
+
 map<string, set<string>>
 read_file(string_view filename)
 {
@@ -57,9 +74,82 @@ part1(const map<string, set<string>>& nodes)
 	cout << connected.size() << endl;
 }
 
+void
+bronKerbosch(set<string> R, set<string> P, set<string> X, const map<string, set<string>>& graph, set<set<string>>& maxCliques)
+{
+	if ( P.empty() && X.empty() ) {
+		// Found a maximal clique
+		maxCliques.insert(R);
+		return;
+	}
+
+	// Choose a pivot (heuristic: choose a vertex with maximum connections in P union X)
+	string      pivot;
+	set<string> unionPX;
+	set_union(P.begin(), P.end(), X.begin(), X.end(), inserter(unionPX, unionPX.begin()));
+
+	if ( !unionPX.empty() ) {
+		pivot = *unionPX.begin(); // Choose the first vertex as pivot (simple heuristic)
+	}
+
+	set<string> candidates;
+	set_difference(P.begin(), P.end(), graph.at(pivot).begin(), graph.at(pivot).end(), inserter(candidates, candidates.begin()));
+
+	for ( const string& candidate: candidates ) {
+		set<string> newR = R;
+		newR.insert(candidate);
+
+		set<string> newP;
+		set<string> newX;
+		for ( const string& neighbor: graph.at(candidate) ) {
+			if ( P.find(neighbor) != P.end() ) {
+				newP.insert(neighbor);
+			}
+			if ( X.find(neighbor) != X.end() ) {
+				newX.insert(neighbor);
+			}
+		}
+
+		bronKerbosch(newR, newP, newX, graph, maxCliques);
+
+		P.erase(candidate);
+		X.insert(candidate);
+	}
+}
+
+set<string>
+findLargestSet(const set<set<string>>& sets)
+{
+	set<string> largest;
+	for ( const auto& sub: sets ) {
+		if ( sub.size() > largest.size() ) {
+			largest = sub;
+		}
+	}
+	return largest;
+}
+
+void
+part2(const map<string, set<string>>& nodes)
+{
+	set<string> R; // Initially empty
+	set<string> P; // All vertices are potential candidates
+	set<string> X; // Initially empty
+
+	for ( const auto& [vertex, _]: nodes ) {
+		P.insert(vertex);
+	}
+
+	set<set<string>> max_cliques;
+	bronKerbosch(R, P, X, nodes, max_cliques);
+
+	cout << join(findLargestSet(max_cliques), ",") << endl;
+}
+
 int
 main()
 {
 	auto data = read_file("data/day23.txt");
 	part1(data);
+	part2(data);
 }
-- 
cgit v1.3