aboutsummaryrefslogtreecommitdiff
path: root/src/day25.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/day25.cpp')
-rw-r--r--src/day25.cpp140
1 files changed, 0 insertions, 140 deletions
diff --git a/src/day25.cpp b/src/day25.cpp
deleted file mode 100644
index 1d5e19e..0000000
--- a/src/day25.cpp
+++ /dev/null
@@ -1,140 +0,0 @@
1#include <algorithm>
2#include <array>
3#include <fstream>
4#include <iostream>
5#include <map>
6#include <queue>
7#include <random>
8#include <set>
9#include <sstream>
10#include <string>
11#include <string_view>
12#include <vector>
13using namespace std;
14
15using graph_type = map<string, set<string>>;
16
17vector<string>
18split(const string& line, char sep)
19{
20 vector<string> parts;
21 stringstream input{ line };
22
23 for ( string part; getline(input, part, sep); ) {
24 parts.emplace_back(part);
25 }
26
27 return parts;
28}
29
30graph_type
31read_file(string_view filename)
32{
33 fstream input{ filename };
34 graph_type graph;
35
36 for ( string line; getline(input, line); ) {
37 const auto components = split(line.erase(line.find(':'), 1), ' ');
38
39 for ( size_t i = 1; i < components.size(); ++i ) {
40 graph[components[0]].insert(components[i]);
41 graph[components[i]].insert(components[0]);
42 }
43 }
44
45 return graph;
46}
47
48bool
49bfs(graph_type graph, const string& source, const string& dest, function<void(const string&, const string&)> visit) // NOLINT
50{
51 set<string> visited;
52
53 queue<string> queue;
54 queue.emplace(source);
55
56 while ( !queue.empty() ) {
57 auto candidate = queue.front();
58 queue.pop();
59
60 if ( candidate == dest ) {
61 return true;
62 }
63
64 for ( const auto& neighbour: graph[candidate] ) {
65 if ( !visited.contains(neighbour) ) {
66 queue.emplace(neighbour);
67
68 visit(candidate, neighbour);
69 visited.emplace(neighbour);
70 }
71 }
72 }
73 return false;
74}
75
76auto
77random_node(const graph_type& graph)
78{
79 static random_device dev;
80 static mt19937 generator(dev());
81
82 uniform_int_distribution<graph_type::size_type> distribute(0, graph.size()-1);
83
84 auto iter = graph.begin();
85 advance(iter, distribute(generator));
86 return iter->first;
87}
88
89void
90part1(graph_type graph)
91{
92 map<tuple<string, string>, int> frequencies;
93 for ( size_t idx = 0; idx != 2; ++idx ) {
94 for ( const auto& second: graph ) {
95 bfs(graph, random_node(graph), second.first, [&](const string& candidate, const string& neighbour) {
96 if ( candidate < neighbour ) {
97 frequencies[make_tuple(candidate, neighbour)]++;
98 }
99 else {
100 frequencies[make_tuple(neighbour, candidate)]++;
101 }
102 });
103 }
104 }
105
106 vector<tuple<tuple<string, string>, int>> sorted_frequencies{ frequencies.begin(), frequencies.end() };
107
108 sort(sorted_frequencies.begin(), sorted_frequencies.end(), [](const auto& lhs, const auto& rhs) {
109 return get<1>(lhs) > get<1>(rhs);
110 });
111
112 sorted_frequencies.erase(sorted_frequencies.begin() + 3, sorted_frequencies.end());
113
114 for ( const auto& link: sorted_frequencies ) {
115 const auto [left, right] = get<0>(link);
116
117 graph[left].erase(right);
118 graph[right].erase(left);
119 }
120
121 auto reachable = [&graph](const string& start_node) {
122 set<string> nodes;
123 bfs(graph, start_node, "", [&nodes](const string& candidate, const string& neighbour) {
124 nodes.insert(candidate);
125 nodes.insert(neighbour);
126 });
127 return nodes.size();
128 };
129
130 const auto [left, right] = get<0>(sorted_frequencies[0]);
131
132 cout << reachable(left) * reachable(right) << endl;
133}
134
135int
136main()
137{
138 auto graph = read_file("data/day25.txt");
139 part1(graph);
140}