Lösung für Tag 25

1 files changed, 229 insertions, 0 deletions

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;
+        //      }
+        // }
+}