1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
|
#include <filesystem>
#include <fstream>
#include <functional>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
using namespace std;
namespace {
using Graph = map<string, set<string>>;
vector<string>
split(const string& str, const string& delims)
{
vector<string> result;
size_t start = str.find_first_not_of(delims);
while ( start != string::npos ) {
size_t end = str.find_first_of(delims, start);
if ( end == string::npos ) {
// letzter Teil
result.push_back(str.substr(start));
break;
}
result.push_back(str.substr(start, end - start));
start = str.find_first_not_of(delims, end);
}
return result;
}
Graph
read_file(const filesystem::path& filename)
{
ifstream file{ filename };
Graph graph;
for ( string line; getline(file, line); ) {
auto parts = split(line, ": ");
graph[parts[0]].insert(parts.begin() + 1, parts.end());
}
return graph;
}
void
part1(const Graph& graph)
{
map<string, long> cache;
function<long(const string&)> dfs = [&](const string& src) {
if ( src == "out" ) {
return 1L;
}
if ( cache.contains(src) ) {
return cache.at(src);
}
long count = 0;
for ( const auto& node: graph.at(src) ) {
count += dfs(node);
}
return cache[src] = count;
};
cout << "Part 1: " << dfs("you") << '\n';
}
void
part2(const Graph& graph)
{
map<tuple<string, bool, bool>, long> cache;
function<long(const string&, bool, bool)> dfs = [&](const string& src, bool dac_visited, bool fft_visited) {
if ( src == "out" ) {
return (dac_visited && fft_visited) ? 1L : 0L;
}
const auto args = make_tuple(src, dac_visited, fft_visited);
if ( cache.contains(args) ) {
return cache.at(args);
}
long count = 0;
for ( const auto& node: graph.at(src) ) {
count += dfs(node, dac_visited || node == "dac", fft_visited || node == "fft");
}
return cache[args] = count;
};
cout << "Part 2: " << dfs("svr", false, false) << '\n';
}
void
part2_alt(const Graph& graph)
{
map<tuple<string, string>, long> cache;
function<long(const string&, const string&)> dfs = [&](const string& src, const string& dst) {
if ( src == dst ) {
return 1L;
}
const auto args = make_tuple(src, dst);
if ( cache.contains(args) ) {
return cache.at(args);
}
long count = 0;
if ( graph.contains(src) ) {
for ( const auto& node: graph.at(src) ) {
count += dfs(node, dst);
}
}
return cache[args] = count;
};
// clang-format off
const auto total = (dfs("svr", "dac") * dfs("dac", "fft") * dfs("fft", "out"))
+ (dfs("svr", "fft") * dfs("fft", "dac") * dfs("dac", "out"));
// clang-format on
cout << "Part 2 (alternative): " << total << '\n';
}
} // namespace
int
main()
{
auto graph = read_file("data/day11.txt");
part1(graph);
part2(graph);
part2_alt(graph);
}
|
