From 4168644780bd1924119feb61d596553fa17c7c94 Mon Sep 17 00:00:00 2001
From: Thomas Schmucker <ts@its1.de>
Date: Tue, 2 Jan 2024 01:03:54 +0100
Subject: Lösung für Tag 25
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

---
 src/day25.cpp | 229 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 229 insertions(+)
 create mode 100644 src/day25.cpp

(limited to 'src/day25.cpp')

diff --git a/src/day25.cpp b/src/day25.cpp
new file mode 100644
index 0000000..b566725
--- /dev/null
+++ b/src/day25.cpp
@@ -0,0 +1,229 @@
+#include <algorithm>
+#include <cstdlib>
+#include <fstream>
+#include <iostream>
+#include <iterator>
+#include <list>
+#include <map>
+#include <queue>
+#include <set>
+#include <sstream>
+#include <string>
+#include <string_view>
+#include <vector>
+using namespace std;
+
+using graph_type = map<string, set<string>>;
+
+vector<string>
+split(const string& line, char sep)
+{
+	vector<string> parts;
+	stringstream   input{ line };
+
+	for ( string part; getline(input, part, sep); ) {
+		parts.emplace_back(part);
+	}
+
+	return parts;
+}
+
+graph_type
+read_file(string_view filename)
+{
+	fstream    input{ filename };
+	graph_type graph;
+
+	for ( string line; getline(input, line); ) {
+		const auto components = split(line.erase(line.find(':'), 1), ' ');
+
+		for ( size_t i = 1; i < components.size(); ++i ) {
+			graph[components[0]].insert(components[i]);
+			graph[components[i]].insert(components[0]);
+		}
+	}
+
+	return graph;
+}
+
+bool
+bfs(const graph_type& graph, const string& source, const string& dest, map<string, string>& parents) // NOLINT
+{
+	set<string> visited;
+
+	parents.clear();
+
+	queue<string> queue;
+	queue.emplace(source);
+
+	while ( !queue.empty() ) {
+		auto candidate = queue.front();
+		queue.pop();
+
+		if ( candidate == dest ) {
+			return true;
+		}
+
+		for ( const auto& neighbour: graph.at(candidate) ) {
+			if ( !visited.contains(neighbour) ) {
+				queue.emplace(neighbour);
+				parents[neighbour] = candidate;
+				visited.emplace(neighbour);
+			}
+		}
+	}
+
+	return false;
+}
+
+void
+dfs(const graph_type& graph, const string& source, set<string>& visited) // NOLINT
+{
+	visited.emplace(source);
+	for ( const auto& node: graph.at(source) ) {
+		if ( !visited.contains(node) ) {
+			dfs(graph, node, visited);
+		}
+	}
+}
+
+bool
+bfs1(graph_type graph, const string& source, const string& dest, function<void(const string&, const string&)> visit) // NOLINT
+{
+	set<string> visited;
+
+	queue<string> queue;
+	queue.emplace(source);
+
+	while ( !queue.empty() ) {
+		auto candidate = queue.front();
+		queue.pop();
+
+		if ( candidate == dest ) {
+			return true;
+		}
+
+		for ( const auto& neighbour: graph[candidate] ) {
+			if ( !visited.contains(neighbour) ) {
+				queue.emplace(neighbour);
+
+				visit(candidate, neighbour);
+				visited.emplace(neighbour);
+			}
+		}
+	}
+	return false;
+}
+
+void
+print_graph_stats(const graph_type& graph)
+{
+	size_t nodes = 0;
+	size_t edges = 0;
+	for ( const auto& link: graph ) {
+		nodes++;
+		edges += link.second.size();
+	}
+	cout << nodes << ", " << edges / 2 << endl;
+}
+
+void
+part1(graph_type graph)
+{
+	srand(unsigned(time(nullptr)));
+
+	vector<string> nodes(graph.size());
+	for ( const auto& foo: graph ) {
+		nodes.emplace_back(foo.first);
+	}
+
+	map<tuple<string, string>, int> counter;
+	for ( size_t idx = 0; idx != 2; ++idx ) {
+		for ( const auto& second: graph ) {
+			bfs1(graph, nodes[size_t(rand()) % nodes.size()], second.first, [&](const string& candidate, const string& neighbour) {
+				if ( candidate < neighbour ) {
+					counter[make_tuple(candidate, neighbour)]++;
+				}
+				else {
+					counter[make_tuple(neighbour, candidate)]++;
+				}
+			});
+		}
+	}
+
+	vector<tuple<tuple<string, string>, int>> all_links{ counter.begin(), counter.end() };
+
+	sort(all_links.begin(), all_links.end(), [](const auto& lhs, const auto& rhs) {
+		return get<1>(lhs) > get<1>(rhs);
+	});
+
+	for ( size_t i = 0; i != 3; ++i ) {
+		const auto [links, num] = all_links[i];
+		const auto [lhs, rhs]   = links;
+
+		graph[lhs].erase(rhs);
+		graph[rhs].erase(lhs);
+	}
+
+	set<string> reachable;
+	const auto start_from_a = get<0>(get<0>(all_links[0]));
+	bfs1(graph, start_from_a, "--not there--", [&](const string& candidate, const string& neighbour) {
+		reachable.insert(candidate);
+		reachable.insert(neighbour);
+	});
+
+	set<string> reachable2;
+	const auto start_from_b = get<1>(get<0>(all_links[0]));
+	bfs1(graph, start_from_b, "--not there--", [&](const string& candidate, const string& neighbour) {
+		reachable2.insert(candidate);
+		reachable2.insert(neighbour);
+	});
+
+	cout << reachable.size() * reachable2.size() << endl;
+}
+
+void
+print_graph(const graph_type& graph)
+{
+	for ( const auto& node: graph ) {
+		cout << node.first << ": ";
+		copy(node.second.begin(), node.second.end(), ostream_iterator<string>(cout, ", "));
+		cout << endl;
+	}
+}
+
+graph_type
+get_rgraph(const graph_type& graph)
+{
+	graph_type rgraph;
+	for ( const auto& node: graph ) {
+		for ( const auto& link: node.second ) {
+			rgraph[link].insert(node.first);
+		}
+	}
+	return rgraph;
+}
+
+int
+main()
+{
+	auto graph = read_file("data/day25.txt");
+
+	// print_graph(graph);
+
+	part1(graph);
+
+	// print_graph(graph);
+	// cout << " ------------ " << endl;
+	// print_graph(get_rgraph(graph));
+	// cout << " ------------ " << endl;
+	// print_graph(get_rgraph(get_rgraph(graph)));
+
+	// map<string, string> parents;
+
+	// if ( bfs(graph, "jqt", "bvb", parents) ) {
+	// 	for ( const auto& [lhs, rhs]: parents ) {
+	// 		cout << lhs << ": " << rhs << endl;
+	// 	}
+	// }
+}
-- 
cgit v1.3