aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/day01.cpp82
-rw-r--r--src/day02.cpp100
-rw-r--r--src/day03.cpp174
-rw-r--r--src/day04.cpp114
-rw-r--r--src/day05.cpp183
-rw-r--r--src/day06.cpp74
-rw-r--r--src/day07.cpp189
-rw-r--r--src/day08.cpp110
-rw-r--r--src/day09.cpp75
-rw-r--r--src/day10.cpp216
-rw-r--r--src/day11.cpp100
-rw-r--r--src/day12.cpp182
-rw-r--r--src/day13.cpp115
-rw-r--r--src/day14.cpp239
-rw-r--r--src/day15.cpp102
-rw-r--r--src/day16.cpp132
-rw-r--r--src/day17.cpp112
-rw-r--r--src/day18.cpp115
-rw-r--r--src/day19.cpp183
-rw-r--r--src/day20.cpp293
-rw-r--r--src/day21.cpp148
-rw-r--r--src/day22.cpp157
-rw-r--r--src/day23.cpp152
-rw-r--r--src/day24.cpp173
-rw-r--r--src/day25.cpp140
25 files changed, 0 insertions, 3660 deletions
diff --git a/src/day01.cpp b/src/day01.cpp
deleted file mode 100644
index ff357bc..0000000
--- a/src/day01.cpp
+++ /dev/null
@@ -1,82 +0,0 @@
1#include <algorithm>
2#include <fstream>
3#include <iostream>
4#include <map>
5#include <string>
6#include <vector>
7using namespace std;
8
9void
10part1()
11{
12 string digits{ "0123456789" };
13 fstream input{ "data/day01.txt" };
14
15 int sum = 0;
16 for ( string line; input >> line; ) {
17 auto first = find_first_of(begin(line), end(line), begin(digits), end(digits));
18 auto last = find_first_of(rbegin(line), rend(line), begin(digits), end(digits));
19
20 auto value = (*first - '0') * 10 + (*last - '0');
21
22 sum += value;
23 }
24 cout << sum << endl;
25}
26
27void
28part2()
29{
30 map<string, int> map{
31 { "0", 0 },
32 { "1", 1 },
33 { "2", 2 },
34 { "3", 3 },
35 { "4", 4 },
36 { "5", 5 },
37 { "6", 6 },
38 { "7", 7 },
39 { "8", 8 },
40 { "9", 9 },
41 { "one", 1 },
42 { "two", 2 },
43 { "three", 3 },
44 { "four", 4 },
45 { "five", 5 },
46 { "six", 6 },
47 { "seven", 7 },
48 { "eight", 8 },
49 { "nine", 9 },
50 };
51
52 fstream input{ "data/day01.txt" };
53
54 auto sum = 0;
55 for ( string line; input >> line; ) {
56 string sub;
57 vector<int> digits;
58
59 for ( auto ch: line ) {
60 sub += ch;
61
62 for ( const auto& word: map ) {
63 if ( sub.ends_with(word.first) ) {
64 digits.push_back(word.second);
65 }
66 }
67 }
68
69 auto first = digits.front();
70 auto last = digits.back();
71
72 sum += (first * 10) + last;
73 }
74 cout << sum << endl;
75}
76
77int
78main()
79{
80 part1();
81 part2();
82}
diff --git a/src/day02.cpp b/src/day02.cpp
deleted file mode 100644
index df560c3..0000000
--- a/src/day02.cpp
+++ /dev/null
@@ -1,100 +0,0 @@
1#include <cctype>
2#include <cstdio>
3#include <fstream>
4#include <iostream>
5#include <map>
6#include <sstream>
7#include <string>
8#include <vector>
9using namespace std;
10
11vector<string>
12split(const string& line, char sep)
13{
14 vector<string> parts{};
15 stringstream input{ line };
16
17 for ( string part; getline(input, part, sep); ) {
18 parts.emplace_back(part);
19 }
20
21 return parts;
22}
23
24void
25part1()
26{
27 fstream input{ "data/day02.txt" };
28
29 auto sum = 0;
30 for ( string line; getline(input, line); ) {
31 auto game = split(line, ':');
32
33 auto gameId = 0;
34 sscanf(game[0].data(), "Game %d", &gameId); // NOLINT
35
36 auto subsets = split(game[1], ';');
37
38 auto fail = false;
39
40 for ( const auto& subset: subsets ) {
41 auto cubes = split(subset, ',');
42
43 map<string, int> counts{};
44
45 for ( const auto& cube: cubes ) {
46 auto data = split(cube, ' ');
47
48 auto count = stoi(data[1]);
49 auto color = data[2];
50
51 counts[color] += count;
52 }
53
54 fail |= (counts["red"] > 12) || (counts["green"] > 13) || (counts["blue"] > 14); // NOLINT
55 }
56
57 if ( !fail ) {
58 sum += gameId;
59 }
60 }
61 cout << sum << endl;
62}
63
64void
65part2()
66{
67 fstream input{ "data/day02.txt" };
68
69 auto sum = 0;
70
71 for ( string line; getline(input, line); ) {
72 auto game = split(line, ':');
73
74 auto subsets = split(game[1], ';');
75
76 map<string, int> colors{};
77
78 for ( const auto& subset: subsets ) {
79 auto cubes = split(subset, ',');
80
81 for ( const auto& cube: cubes ) {
82 auto data = split(cube, ' ');
83
84 auto count = stoi(data[1]);
85 auto color = data[2];
86
87 colors[color] = max(colors[color], count);
88 }
89 }
90 sum += colors["red"] * colors["green"] * colors["blue"];
91 }
92 cout << sum << endl;
93}
94
95int
96main()
97{
98 part1();
99 part2();
100}
diff --git a/src/day03.cpp b/src/day03.cpp
deleted file mode 100644
index b266f59..0000000
--- a/src/day03.cpp
+++ /dev/null
@@ -1,174 +0,0 @@
1#include <cctype>
2#include <fstream>
3#include <iostream>
4#include <string>
5#include <string_view>
6#include <vector>
7
8using namespace std;
9
10vector<string>
11read_file(string_view filename)
12{
13 fstream input{ filename };
14 vector<string> data;
15
16 for ( string line; getline(input, line); ) {
17 data.emplace_back(line);
18 }
19
20 return data;
21}
22
23bool
24is_digit(char chr)
25{
26 return std::isdigit(static_cast<unsigned char>(chr)) != 0;
27}
28
29vector<tuple<size_t, size_t>>
30positions(size_t row, size_t col)
31{
32 return {
33 { row - 1, col - 1 },
34 { row - 0, col - 1 },
35 { row + 1, col - 1 },
36
37 { row - 1, col },
38 { row + 1, col },
39
40 { row - 1, col + 1 },
41 { row - 0, col + 1 },
42 { row + 1, col + 1 },
43 };
44}
45
46void
47part1() // NOLINT
48{
49 auto lines = read_file("data/day03.txt");
50
51 auto is_symbol = [&lines](size_t row, size_t col) -> bool {
52 static const string symbols{ "*#+$%=-@&/" };
53
54 if ( row >= lines.size() || col >= lines[row].size() ) {
55 return false;
56 }
57
58 auto symbol = lines[row][col];
59
60 return symbols.find(symbol) != string::npos;
61 };
62
63 auto bordering = [&is_symbol](size_t row, size_t col) -> bool {
64 bool result = false;
65
66 for (const auto& position: positions(row, col)) {
67 result |= is_symbol(get<0>(position), get<1>(position));
68 }
69
70 return result;
71 };
72
73 auto sum = 0;
74 for ( size_t row = 0; row != lines.size(); ++row ) {
75 const auto& line = lines[row];
76
77 string::size_type start = 0;
78 while ( start != line.size() ) {
79 while ( start != line.size() && !is_digit(line[start]) ) {
80 ++start;
81 }
82
83 auto end = start;
84 while ( end != line.size() && is_digit(line[end]) ) {
85 ++end;
86 }
87
88 if ( start != end ) {
89 auto result = false;
90
91 for ( auto col = start; col != end; ++col ) {
92 result |= bordering(row, col);
93 }
94
95 if ( result ) {
96 sum += stoi(line.substr(start, end - start));
97 }
98
99 start = end;
100 }
101 }
102 }
103 cout << sum << endl;
104}
105
106void
107part2() // NOLINT
108{
109 auto lines = read_file("data/day03.txt");
110
111 auto find_integer = [](vector<string>& lines, size_t row, size_t col, int& value) -> bool { // NOLINT
112 if ( row >= lines.size() || col >= lines[row].size() ) {
113 return false;
114 }
115
116 auto& line = lines[row];
117
118 if ( !is_digit(line[col]) ) {
119 return false;
120 }
121
122 // Anfang der Zahl suchen
123 auto start = col;
124 for ( ; start != 0 && is_digit(line[start - 1]); --start ) // NOLINT
125 ;
126
127 auto end = col;
128 for ( ; end != line.size() && is_digit(line[end]); ++end ) // NOLINT
129 ;
130
131 value = stoi(line.substr(start, end - start));
132
133 for ( ; start != end; ++start ) {
134 line[start] = '.';
135 }
136
137 return true;
138 };
139
140 auto sum = 0;
141 for ( size_t row = 0; row != lines.size(); ++row ) {
142 const auto& line = lines[row];
143
144 auto col = line.find('*');
145 while ( col != string::npos ) {
146 vector<int> values;
147
148 auto lines_copy{ lines };
149
150 for ( const auto& position: positions(row, col) ) {
151 auto value = 0;
152
153 if ( find_integer(lines_copy, get<0>(position), get<1>(position), value) ) {
154 values.emplace_back(value);
155 }
156 }
157
158 if ( values.size() == 2 ) {
159 auto ratio = values[0] * values[1];
160 sum += ratio;
161 }
162
163 col = line.find('*', col + 1);
164 }
165 }
166 cout << sum << endl;
167}
168
169int
170main()
171{
172 part1();
173 part2();
174}
diff --git a/src/day04.cpp b/src/day04.cpp
deleted file mode 100644
index 0d3e552..0000000
--- a/src/day04.cpp
+++ /dev/null
@@ -1,114 +0,0 @@
1#include <fstream>
2#include <iostream>
3#include <set>
4#include <sstream>
5#include <string>
6#include <string_view>
7#include <vector>
8
9using namespace std;
10
11vector<string>
12read_file(string_view filename)
13{
14 fstream input{ filename };
15 vector<string> data;
16
17 for ( string line; getline(input, line); ) {
18 data.emplace_back(line);
19 }
20
21 return data;
22}
23
24vector<string>
25split(const string& line, char sep)
26{
27 stringstream input{ line };
28 vector<string> parts;
29
30 for ( string part; getline(input, part, sep); ) {
31 parts.emplace_back(part);
32 }
33
34 return parts;
35}
36
37template<typename Container>
38Container
39read_ints(const string& line)
40{
41 Container container{};
42 stringstream input{ line };
43
44 for ( typename Container::value_type value; input >> value; ) {
45 container.emplace(value);
46 }
47
48 return container;
49}
50
51auto
52build_data_set(string_view filename)
53{
54 vector<unsigned long> values;
55
56 for ( const auto& line: read_file(filename) ) {
57 const auto cards = split(line, ':');
58 const auto numbers = split(cards[1], '|');
59
60 const auto winning_numbers = read_ints<set<int>>(numbers[0]);
61 const auto card_numbers = read_ints<set<int>>(numbers[1]);
62
63 auto count = 0U;
64 for ( auto number: winning_numbers ) {
65 if ( card_numbers.contains(number) ) {
66 ++count;
67 }
68 }
69 values.emplace_back(count);
70 }
71
72 return values;
73}
74
75void
76pass1(const vector<unsigned long>& values)
77{
78 auto sum = 0U;
79 for ( auto value: values ) {
80 if ( value != 0 ) {
81 sum += (1U << (value - 1));
82 }
83 }
84
85 cout << sum << endl;
86}
87
88void
89pass2(const vector<unsigned long>& values)
90{
91 auto count = 0U;
92
93 function<void(size_t, size_t)> process = [&](size_t start, size_t end) -> void {
94 for ( ; start != end; ++start ) {
95 auto value = values[start];
96
97 ++count;
98
99 process(start + 1, start + value + 1);
100 }
101 };
102
103 process(0, values.size());
104
105 cout << count << endl;
106}
107
108int
109main()
110{
111 const auto values = build_data_set("data/day04.txt");
112 pass1(values);
113 pass2(values);
114}
diff --git a/src/day05.cpp b/src/day05.cpp
deleted file mode 100644
index 42fda29..0000000
--- a/src/day05.cpp
+++ /dev/null
@@ -1,183 +0,0 @@
1#include <algorithm>
2#include <fstream>
3#include <iostream>
4#include <iterator>
5#include <limits>
6#include <map>
7#include <sstream>
8#include <string>
9#include <vector>
10using namespace std;
11
12struct Entry {
13 Entry(long destination, long source, long amount) // NOLINT
14 : destination_(destination)
15 , source_(source)
16 , amount_(amount)
17 {
18 }
19
20 [[nodiscard]] bool in_range(long value) const
21 {
22 return source_ <= value && value < (source_ + amount_);
23 }
24
25 [[nodiscard]] long get_destination(long value) const
26 {
27 auto delta = value - source_;
28 return destination_ + delta;
29 }
30
31 long destination_;
32 long source_;
33 long amount_;
34};
35
36vector<string>
37read_file(string_view filename)
38{
39 fstream input{ filename };
40 vector<string> data;
41
42 for ( string line; getline(input, line); ) {
43 data.emplace_back(line);
44 }
45
46 return data;
47}
48
49vector<string>
50split(const string& line, char sep)
51{
52 vector<string> parts;
53 stringstream input{ line };
54
55 for ( string part; getline(input, part, sep); ) {
56 parts.emplace_back(part);
57 }
58
59 return parts;
60}
61
62void
63part1(const vector<string>& lines)
64{
65 auto read_ints = [](const string& line) {
66 stringstream iss{ line };
67 return vector<long>{ istream_iterator<long>{ iss }, istream_iterator<long>{} };
68 };
69
70 auto seeds = read_ints(lines[0].substr(6));
71
72 map<string, string> category_mapping;
73 map<string, vector<Entry>> range_mapping;
74
75 // read blocks
76 for ( size_t idx = 1; idx < lines.size(); ) {
77 ++idx; // skip empty line
78
79 auto description = lines[idx++];
80 description.erase(description.find(' '));
81 auto parts = split(description, '-');
82
83 category_mapping[parts[0]] = parts[2];
84
85 vector<Entry> mapping;
86
87 for ( ; idx < lines.size() && !lines[idx].empty(); ++idx ) {
88 auto values = read_ints(lines[idx]);
89
90 auto destination = values[0];
91 auto source = values[1];
92 auto amount = values[2];
93
94 mapping.emplace_back(destination, source, amount);
95 }
96
97 range_mapping[parts[0]] = mapping;
98 }
99
100 auto min_value = numeric_limits<long>::max();
101 for ( auto seed: seeds ) {
102 for ( string category{ "seed" }; !category.empty(); category = category_mapping[category] ) {
103 const auto& ranges = range_mapping[category];
104
105 for (const auto& range: ranges) {
106 if (range.in_range(seed)) {
107 seed = range.get_destination(seed);
108 break;
109 }
110 }
111 }
112 min_value = min(min_value, seed);
113 }
114 cout << min_value << endl;
115}
116
117void
118part2(const vector<string>& lines)
119{
120 auto read_ints = [](const string& line) {
121 stringstream iss{ line };
122 return vector<long>{ istream_iterator<long>{ iss }, istream_iterator<long>{} };
123 };
124
125 auto seeds = read_ints(lines[0].substr(6));
126
127 map<string, string> category_mapping;
128 map<string, vector<Entry>> range_mapping;
129
130 // read blocks
131 for ( size_t idx = 1; idx < lines.size(); ) {
132 ++idx; // skip empty line
133
134 auto description = lines[idx++];
135 description.erase(description.find(' '));
136 auto parts = split(description, '-');
137
138 category_mapping[parts[0]] = parts[2];
139
140 vector<Entry> mapping;
141
142 for ( ; idx < lines.size() && !lines[idx].empty(); ++idx ) {
143 auto values = read_ints(lines[idx]);
144
145 auto destination = values[0];
146 auto source = values[1];
147 auto amount = values[2];
148
149 mapping.emplace_back(destination, source, amount);
150 }
151
152 range_mapping[parts[0]] = mapping;
153 }
154
155 // brute force -- slow, but works
156 auto min_value = numeric_limits<long>::max();
157 for ( size_t idx = 0; idx != seeds.size(); idx += 2 ) {
158 for ( auto start = seeds[idx]; start != seeds[idx] + seeds[idx+1]; ++start ) {
159 auto seed = start;
160
161 for ( string category{ "seed" }; !category.empty(); category = category_mapping[category] ) {
162 const auto& ranges = range_mapping[category];
163
164 for (const auto& range: ranges) {
165 if (range.in_range(seed)) {
166 seed = range.get_destination(seed);
167 break;
168 }
169 }
170 }
171 min_value = min(min_value, seed);
172 }
173 }
174 cout << min_value << endl;
175}
176
177int
178main()
179{
180 auto lines = read_file("data/day05.txt");
181 part1(lines);
182 part2(lines);
183}
diff --git a/src/day06.cpp b/src/day06.cpp
deleted file mode 100644
index 9a429c5..0000000
--- a/src/day06.cpp
+++ /dev/null
@@ -1,74 +0,0 @@
1#include <cstdint>
2#include <fstream>
3#include <iostream>
4#include <numeric>
5#include <sstream>
6#include <vector>
7using namespace std;
8
9template<typename T = long>
10vector<T>
11read_ints(const string& line)
12{
13 stringstream iss{ line };
14 return vector<T>{ istream_iterator<T>{ iss }, istream_iterator<T>{} };
15}
16
17long
18solve(long time, long winningDistance)
19{
20 long counter = 0;
21 for ( long pushTime = 0; pushTime < time; ++pushTime ) {
22 auto distance = (time * pushTime - pushTime * pushTime);
23 counter += long(distance > winningDistance);
24 }
25 return counter;
26}
27
28void
29part1()
30{
31 fstream input{ "data/day06.txt" };
32 string line;
33
34 getline(input, line);
35 auto times = read_ints(line.substr(line.find(':') + 1));
36
37 getline(input, line);
38 auto distances = read_ints(line.substr(line.find(':') + 1));
39
40 long result = 1;
41 for ( size_t idx = 0; idx != times.size(); ++idx ) {
42 result *= solve(times[idx], distances[idx]);
43 }
44 cout << result << endl;
45}
46
47string
48join(const string& line)
49{
50 stringstream iss{ line };
51 return accumulate(istream_iterator<string>{ iss }, istream_iterator<string>{}, string{});
52}
53
54void
55part2()
56{
57 fstream input{ "data/day06.txt" };
58 string line;
59
60 getline(input, line);
61 auto time = stol(join(line.substr(line.find(':') + 1)));
62
63 getline(input, line);
64 auto distance = stol(join(line.substr(line.find(':') + 1)));
65
66 cout << solve(time, distance) << endl;
67}
68
69int
70main()
71{
72 part1();
73 part2();
74}
diff --git a/src/day07.cpp b/src/day07.cpp
deleted file mode 100644
index 1f44ac5..0000000
--- a/src/day07.cpp
+++ /dev/null
@@ -1,189 +0,0 @@
1#include <algorithm>
2#include <cassert>
3#include <fstream>
4#include <iostream>
5#include <map>
6#include <sstream>
7#include <tuple>
8#include <vector>
9using namespace std;
10
11enum kind_type {
12 five_kind,
13 four_kind,
14 full_house_kind,
15 three_kind,
16 two_pair_kind,
17 one_pair_kind,
18 high_card_kind
19};
20
21kind_type
22kind1(string hand)
23{
24 map<char, size_t> mapping{};
25
26 for ( auto chr: hand ) {
27 ++mapping[chr];
28 }
29
30 sort(hand.begin(), hand.end());
31 hand.erase(unique(hand.begin(), hand.end()), hand.end());
32
33 if ( mapping.size() == 1 ) {
34 return five_kind;
35 }
36 if ( mapping.size() == 2 ) {
37 if ( mapping[hand[0]] == 4 || mapping[hand[1]] == 4 ) {
38 return four_kind;
39 }
40 return full_house_kind;
41 }
42 if ( mapping.size() == 3 ) {
43 if ( mapping[hand[0]] == 3 || mapping[hand[1]] == 3 || mapping[hand[2]] == 3 ) {
44 return three_kind;
45 }
46 return two_pair_kind;
47 }
48 if ( mapping.size() == 4 ) {
49 return one_pair_kind;
50 }
51
52 return high_card_kind;
53}
54
55kind_type
56kind2(const string& hand)
57{
58 map<char, size_t> mapping{};
59
60 for ( auto chr: hand ) {
61 ++mapping[chr];
62 }
63
64 auto joker_amount = mapping['J'];
65 mapping.erase('J');
66
67 vector<size_t> amounts{};
68 amounts.reserve(mapping.size());
69 for ( const auto& entry: mapping ) {
70 amounts.emplace_back(entry.second);
71 }
72
73 sort(amounts.begin(), amounts.end(), greater<>());
74 if ( amounts.empty() ) {
75 amounts.emplace_back(joker_amount);
76 }
77 else {
78 amounts[0] += joker_amount;
79 }
80
81 if ( amounts[0] == 5 ) {
82 return five_kind;
83 }
84 if ( amounts[0] == 4 ) {
85 return four_kind;
86 }
87 if ( amounts[0] == 3 and amounts[1] == 2 ) {
88 return full_house_kind;
89 }
90 if ( amounts[0] == 3 ) {
91 return three_kind;
92 }
93 if ( amounts[0] == 2 && amounts[1] == 2 ) {
94 return two_pair_kind;
95 }
96 if ( amounts[0] == 2 ) {
97 return one_pair_kind;
98 }
99
100 return high_card_kind;
101}
102
103void
104solve(const function<kind_type(string)>& kind, map<char, int> weights)
105{
106 fstream input{ "data/day07.txt" };
107 vector<tuple<string, kind_type, long>> values{};
108
109 string hand;
110 long bid = 0;
111 while ( input >> hand >> bid ) {
112 values.emplace_back(hand, kind(hand), bid);
113 }
114
115 sort(values.begin(), values.end(), [&](const tuple<string, kind_type, long>& first, const tuple<string, kind_type, long>& second) {
116 const auto& first_hand = get<0>(first);
117 const auto& second_hand = get<0>(second);
118
119 auto first_kind = get<1>(first);
120 auto second_kind = get<1>(second);
121
122 if ( first_kind == second_kind ) {
123 for ( size_t idx = 0; idx != 5; ++idx ) {
124 const auto first_weight = weights[first_hand[idx]];
125 const auto second_weight = weights[second_hand[idx]];
126
127 if ( first_weight != second_weight ) {
128 return first_weight < second_weight;
129 }
130 }
131 }
132 return first_kind > second_kind;
133 });
134
135 long total = 0;
136 long rank = 1;
137 for ( const auto& value: values ) {
138 total += rank * get<2>(value);
139 ++rank;
140 }
141 cout << total << endl;
142}
143
144int
145main()
146{
147 assert(kind1("AAAAA") == five_kind);
148 assert(kind1("AA8AA") == four_kind);
149 assert(kind1("23332") == full_house_kind);
150 assert(kind1("TTT98") == three_kind);
151 assert(kind1("23432") == two_pair_kind);
152 assert(kind1("A23A4") == one_pair_kind);
153 assert(kind1("23456") == high_card_kind);
154
155 map<char, int> weights1 = {
156 { '2', 2 },
157 { '3', 3 },
158 { '4', 4 },
159 { '5', 5 },
160 { '6', 6 },
161 { '7', 7 },
162 { '8', 8 },
163 { '9', 9 },
164 { 'T', 10 },
165 { 'J', 11 },
166 { 'Q', 12 },
167 { 'K', 13 },
168 { 'A', 14 },
169 };
170
171 map<char, int> weights2 = {
172 { 'J', 1 },
173 { '2', 2 },
174 { '3', 3 },
175 { '4', 4 },
176 { '5', 5 },
177 { '6', 6 },
178 { '7', 7 },
179 { '8', 8 },
180 { '9', 9 },
181 { 'T', 10 },
182 { 'Q', 11 },
183 { 'K', 12 },
184 { 'A', 13 },
185 };
186
187 solve(kind1, weights1);
188 solve(kind2, weights2);
189}
diff --git a/src/day08.cpp b/src/day08.cpp
deleted file mode 100644
index 3e1b6c9..0000000
--- a/src/day08.cpp
+++ /dev/null
@@ -1,110 +0,0 @@
1#include <array>
2#include <fstream>
3#include <iostream>
4#include <map>
5#include <regex>
6#include <numeric>
7using namespace std;
8
9struct Generator {
10 explicit Generator(string_view init)
11 : values_(init)
12 , iter_(values_.begin())
13
14 {
15 }
16
17 size_t next()
18 {
19 size_t gen = (*iter_ == 'L') ? 0 : 1;
20
21 ++iter_;
22 if ( iter_ == values_.end() ) {
23 iter_ = values_.begin();
24 }
25
26 return gen;
27 }
28
29 string values_;
30 string::iterator iter_;
31};
32
33void
34part1()
35{
36 fstream input{ "data/day08.txt" };
37
38 string line;
39 getline(input, line);
40
41 Generator generator{ line };
42
43 map<string, array<string, 2>> puzzle;
44
45 const regex pattern{ R"((.*) = \((.*), (.*)\))" };
46 while ( getline(input, line) ) {
47 if ( line.empty() ) {
48 continue;
49 }
50
51 smatch sub_match;
52 if ( regex_search(line, sub_match, pattern) ) {
53 puzzle[sub_match[1]] = { sub_match[2], sub_match[3] };
54 }
55 }
56
57 auto counter = 0;
58 for ( string str{ "AAA" }; str != "ZZZ"; str = puzzle[str][generator.next()] ) {
59 ++counter;
60 }
61 cout << counter << endl;
62}
63
64void
65part2()
66{
67 fstream input{ "data/day08.txt" };
68
69 string firstline;
70 getline(input, firstline);
71
72 map<string, array<string, 2>> puzzle;
73
74 const regex pattern{ R"((.*) = \((.*), (.*)\))" };
75 for ( string line; getline(input, line); ) {
76 if ( line.empty() ) {
77 continue;
78 }
79
80 smatch sub_match;
81 if ( regex_search(line, sub_match, pattern) ) {
82 puzzle[sub_match[1]] = { sub_match[2], sub_match[3] };
83 }
84 }
85
86 auto value = 1L;
87 for ( const auto& entry: puzzle ) {
88 if ( entry.first[2] != 'A' ) {
89 continue;
90 }
91
92 Generator generator{ firstline };
93
94 auto counter = 0L;
95
96 for ( string str{ entry.first }; str[2] != 'Z'; str = puzzle[str][generator.next()] ) {
97 ++counter;
98 }
99
100 value = lcm(value, counter);
101 }
102 cout << value << endl;
103}
104
105int
106main()
107{
108 part1();
109 part2();
110}
diff --git a/src/day09.cpp b/src/day09.cpp
deleted file mode 100644
index 4b30e6e..0000000
--- a/src/day09.cpp
+++ /dev/null
@@ -1,75 +0,0 @@
1#include <fstream>
2#include <iostream>
3#include <sstream>
4#include <string>
5#include <vector>
6using namespace std;
7
8vector<string>
9read_file(string_view filename)
10{
11 fstream input{ filename };
12 vector<string> data;
13
14 for ( string line; getline(input, line); ) {
15 data.emplace_back(line);
16 }
17
18 return data;
19}
20
21template<typename T = long>
22vector<T>
23read_ints(const string& line)
24{
25 stringstream iss{ line };
26 return vector<T>{ istream_iterator<T>{ iss }, istream_iterator<T>{} };
27}
28
29template<typename T>
30T
31solve_rec(const vector<T>& values)
32{
33 vector<T> differences;
34
35 for ( size_t idx = 1; idx < values.size(); ++idx ) {
36 differences.emplace_back(values[idx] - values[idx - 1]);
37 }
38 auto all_zeros = all_of(differences.begin(), differences.end(), [](T diff) { return diff == 0; });
39 if ( !all_zeros ) {
40 return solve_rec(differences) + values.back();
41 }
42 else {
43 return values.back();
44 }
45}
46
47void
48part1(const vector<string>& lines)
49{
50 long sum = 0;
51 for ( const auto& line: lines ) {
52 sum += solve_rec(read_ints(line));
53 }
54 cout << sum << endl;
55}
56
57void
58part2(const vector<string>& lines)
59{
60 long sum = 0;
61 for ( const auto& line: lines ) {
62 auto values = read_ints(line);
63 reverse(values.begin(), values.end());
64 sum += solve_rec(values);
65 }
66 cout << sum << endl;
67}
68
69int
70main()
71{
72 auto lines = read_file("data/day09.txt");
73 part1(lines);
74 part2(lines);
75}
diff --git a/src/day10.cpp b/src/day10.cpp
deleted file mode 100644
index 264e111..0000000
--- a/src/day10.cpp
+++ /dev/null
@@ -1,216 +0,0 @@
1#include <algorithm>
2#include <fstream>
3#include <iostream>
4#include <sstream>
5#include <string>
6#include <vector>
7using namespace std;
8
9using pos_t = tuple<size_t, size_t>;
10using puzzle_t = vector<string>;
11
12puzzle_t
13read_file(string_view filename)
14{
15 fstream input{ filename };
16 puzzle_t data;
17
18 for ( string line; getline(input, line); ) {
19 data.emplace_back(line);
20 }
21
22 return data;
23}
24
25pos_t
26find_start_pos(const puzzle_t& puzzle)
27{
28 for ( size_t y = 0; y != puzzle.size(); ++y ) { // NOLINT
29 auto x = puzzle[y].find('S'); // NOLINT
30 if ( x != string::npos ) {
31 return { x, y };
32 }
33 }
34
35 return { 0, 0 };
36};
37
38bool
39predict_direction(const puzzle_t& puzzle, pos_t& current, char& direction)
40{
41 auto [x, y] = current;
42
43 if ( direction == 'S' ) {
44 ++y;
45 if ( y >= puzzle.size() ) {
46 return false;
47 }
48 const auto tile = puzzle[y][x];
49 if ( tile != 'J' && tile != '|' && tile != 'L' ) {
50 return false;
51 }
52 if ( tile == 'J' ) {
53 direction = 'W';
54 }
55 else if ( tile == 'L' ) {
56 direction = 'E';
57 }
58 }
59 else if ( direction == 'N' ) {
60 --y;
61 if ( y >= puzzle.size() ) {
62 return false;
63 }
64 const auto tile = puzzle[y][x];
65 if ( tile != '7' && tile != '|' && tile != 'F' ) {
66 return false;
67 }
68 if ( tile == '7' ) {
69 direction = 'W';
70 }
71 else if ( tile == 'F' ) {
72 direction = 'E';
73 }
74 }
75 else if ( direction == 'E' ) {
76 ++x;
77 if ( x >= puzzle[y].size() ) {
78 return false;
79 }
80 const auto tile = puzzle[y][x];
81 if ( tile != 'J' && tile != '-' && tile != '7' ) {
82 return false;
83 }
84 if ( tile == 'J' ) {
85 direction = 'N';
86 }
87 else if ( tile == '7' ) {
88 direction = 'S';
89 }
90 }
91 else if ( direction == 'W' ) {
92 --x;
93 if ( x >= puzzle[y].size() ) {
94 return false;
95 }
96 const auto tile = puzzle[y][x];
97 if ( tile != 'L' && tile != '-' && tile != 'F' ) {
98 return false;
99 }
100 if ( tile == 'L' ) {
101 direction = 'N';
102 }
103 else if ( tile == 'F' ) {
104 direction = 'S';
105 }
106 }
107 else {
108 cerr << "invalid direction " << direction << ")!" << endl;
109 return false;
110 }
111
112 current = { x, y };
113 return true;
114};
115
116void
117part1(const puzzle_t& puzzle)
118{
119 const auto start_pos = find_start_pos(puzzle);
120
121 auto max_steps = 0;
122
123 for ( const auto direction: { 'N', 'S', 'E', 'W' } ) {
124 auto current_direction = direction;
125 auto current_pos = start_pos;
126
127 auto steps = 0;
128 for ( ;; ) {
129 ++steps;
130
131 if ( !predict_direction(puzzle, current_pos, current_direction) ) {
132 break;
133 }
134 }
135
136 max_steps = max(max_steps, steps);
137 }
138
139 cout << max_steps / 2 << endl;
140}
141
142bool
143flood_fill(puzzle_t& puzzle, size_t x, size_t y)
144{
145 if ( y >= puzzle.size() || x >= puzzle[0].size() ) {
146 return false;
147 }
148
149 if ( puzzle[y][x] == ' ' ) {
150 puzzle[y][x] = 'o';
151 if ( !flood_fill(puzzle, x, y + 1) ||
152 !flood_fill(puzzle, x, y - 1) ||
153 !flood_fill(puzzle, x + 1, y) ||
154 !flood_fill(puzzle, x - 1, y) ) {
155 return false;
156 }
157 }
158
159 return true;
160};
161
162void
163part2(const puzzle_t& puzzle_original)
164{
165 puzzle_t puzzle{ puzzle_original.size(), string(puzzle_original[0].size(), ' ') };
166
167 const auto start_pos = find_start_pos(puzzle_original);
168
169 for ( const auto direction: { 'N', 'S', 'E', 'W' } ) {
170 auto current_direction = direction;
171 auto current_pos = start_pos;
172
173 for ( ;; ) {
174 auto [x, y] = current_pos;
175
176 puzzle[y][x] = puzzle_original[y][x];
177
178 if ( !predict_direction(puzzle_original, current_pos, current_direction) ) {
179 break;
180 }
181 }
182 }
183
184 for ( size_t y = 0; y != puzzle.size(); ++y ) { // NOLINT
185 for ( size_t x = 0; x != puzzle[y].size(); ++x ) { // NOLINT
186 auto test_puzzle{ puzzle };
187
188 if ( flood_fill(test_puzzle, x, y) ) {
189 puzzle = test_puzzle;
190 }
191 }
192 }
193
194 auto sum = 0;
195 for ( auto& line: puzzle ) {
196 auto pipes = 0U;
197 for ( auto chr: line ) {
198 if ( chr == '|' || chr == 'L' || chr == 'J' ) {
199 ++pipes;
200 }
201 if ( chr == 'o' && (pipes & 1U) == 1U ) {
202 ++sum;
203 }
204 }
205 }
206
207 cout << sum << endl;
208}
209
210int
211main()
212{
213 const auto puzzle = read_file("data/day10.txt");
214 part1(puzzle);
215 part2(puzzle);
216}
diff --git a/src/day11.cpp b/src/day11.cpp
deleted file mode 100644
index e1a0882..0000000
--- a/src/day11.cpp
+++ /dev/null
@@ -1,100 +0,0 @@
1#include <cmath>
2#include <fstream>
3#include <iostream>
4#include <set>
5#include <string>
6#include <vector>
7using namespace std;
8
9vector<string>
10read_file(string_view filename)
11{
12 fstream input{ filename };
13 vector<string> data;
14
15 for ( string line; getline(input, line); ) {
16 data.emplace_back(line);
17 }
18
19 return data;
20}
21
22vector<tuple<long, long>>
23find_points(const vector<string>& input)
24{
25 vector<tuple<long, long>> result;
26
27 for ( size_t row = 0; row != input.size(); ++row ) {
28 const auto& line = input[row];
29
30 for ( size_t col = 0; col != line.size(); ++col ) {
31 if ( line[col] == '#' ) {
32 result.emplace_back(long(row), long(col));
33 }
34 }
35 }
36
37 return result;
38}
39
40void
41find_empty_rows_and_cols(const vector<string>& input, set<long>& cols, set<long>& rows)
42{
43 for ( size_t row = 0; row != input.size(); ++row ) {
44 const auto& line = input[row];
45 if ( line.find('#') == line.npos ) {
46 rows.insert(long(row));
47 }
48 }
49
50 for ( size_t col = 0; col != input[0].size(); ++col ) {
51 bool empty_col = true;
52 for ( const auto& line: input ) {
53 if ( line[col] == '#' ) {
54 empty_col = false;
55 }
56 }
57 if ( empty_col ) {
58 cols.insert(long(col));
59 }
60 }
61}
62
63long
64solve(const vector<string>& input, long scale)
65{
66 auto points = find_points(input);
67
68 set<long> cols;
69 set<long> rows;
70
71 find_empty_rows_and_cols(input, cols, rows);
72
73 for ( auto& point: points ) {
74 const auto row = get<0>(point) + count_if(rows.begin(), rows.end(), [&](long row) { return row < get<0>(point); }) * (scale - 1);
75 const auto col = get<1>(point) + count_if(cols.begin(), cols.end(), [&](long col) { return col < get<1>(point); }) * (scale - 1);
76
77 point = { row, col };
78 }
79
80 auto sum = 0L;
81 for ( size_t i = 0; i != points.size(); ++i ) {
82 for ( size_t j = i + 1; j != points.size(); ++j ) {
83 const auto& from = points[i];
84 const auto& to = points[j];
85
86 sum += abs(get<0>(from) - get<0>(to)) + abs(get<1>(from) - get<1>(to));
87 }
88 }
89
90 return sum;
91}
92
93int
94main()
95{
96 const auto input = read_file("data/day11.txt");
97
98 cout << "Part1: " << solve(input, 2) << endl;
99 cout << "Part2: " << solve(input, 1000000) << endl;
100}
diff --git a/src/day12.cpp b/src/day12.cpp
deleted file mode 100644
index 11bd80b..0000000
--- a/src/day12.cpp
+++ /dev/null
@@ -1,182 +0,0 @@
1#include <fstream>
2#include <iostream>
3#include <map>
4#include <sstream>
5#include <string>
6#include <vector>
7using namespace std;
8
9vector<string>
10read_file(string_view filename)
11{
12 fstream input{ filename };
13 vector<string> data;
14
15 for ( string line; getline(input, line); ) {
16 data.emplace_back(line);
17 }
18
19 return data;
20}
21
22vector<string>
23split(const string& line, char sep)
24{
25 vector<string> parts{};
26 stringstream input{ line };
27
28 for ( string part; getline(input, part, sep); ) {
29 parts.emplace_back(part);
30 }
31
32 return parts;
33}
34
35template<typename T = long>
36vector<T>
37read_ints(const string& line)
38{
39 vector<T> parts{};
40 stringstream input{ line };
41
42 for ( string part; getline(input, part, ','); ) {
43 parts.emplace_back(stol(part));
44 }
45
46 return parts;
47}
48
49vector<long>
50count_groups(string_view str)
51{
52 vector<long> groups;
53
54 size_t idx = 0U;
55 while ( idx != str.length() ) {
56 while ( idx != str.length() && str[idx] == '.' ) {
57 ++idx;
58 }
59 if ( idx != str.length() && str[idx] == '#' ) {
60 auto num = 0L;
61 while ( idx != str.length() && str[idx] == '#' ) {
62 ++num;
63 ++idx;
64 }
65 groups.emplace_back(num);
66 }
67 }
68
69 return groups;
70}
71
72long
73brute_force(string_view springs, const vector<long>& groups)
74{
75 long counts = count_if(springs.begin(), springs.end(), [](char chr) { return chr == '?'; });
76
77 string test_pattern;
78
79 auto arrangements = 0L;
80 for ( size_t counter = 0; counter != (1U << size_t(counts)); ++counter ) {
81 auto bit_pattern = counter;
82
83 for ( char chr: springs ) {
84 if ( chr == '?' ) {
85 if ( (bit_pattern & 1U) != 0U ) {
86 test_pattern += '.';
87 }
88 else {
89 test_pattern += '#';
90 }
91 bit_pattern >>= 1U;
92 }
93 else {
94 test_pattern += chr;
95 }
96 }
97 if ( groups == count_groups(test_pattern) ) {
98 arrangements++;
99 }
100
101 test_pattern.clear();
102 }
103
104 return arrangements;
105}
106
107long
108count(const string& springs, const vector<long>& groups)
109{
110 map<tuple<string, vector<long>>, long> cache;
111
112 function<long(string, const vector<long>&)> count_rec = [&](string springs, const vector<long>& groups) -> long {
113 auto cached_value = cache.find(make_tuple(springs, groups));
114 if ( cached_value != cache.end() ) {
115 return cached_value->second;
116 }
117
118 springs.erase(0, springs.find_first_not_of('.'));
119
120 if ( springs.empty() ) {
121 return groups.empty() ? 1 : 0;
122 }
123
124 if ( groups.empty() ) {
125 return springs.find('#') == string_view::npos ? 1 : 0;
126 }
127
128 if ( springs[0] == '#' ) {
129 auto gidx = size_t(groups[0]);
130 if ( springs.length() < gidx || springs.substr(0, gidx).find('.') != string_view::npos || springs[gidx] == '#' ) {
131 return 0;
132 }
133
134 return count_rec(springs.substr(gidx + 1), { groups.begin() + 1, groups.end() });
135 }
136
137 auto value = count_rec(string("#") + springs.substr(1), groups) + count_rec(springs.substr(1), groups);
138
139 cache[make_tuple(springs, groups)] = value;
140
141 return value;
142 };
143
144 return count_rec(springs + ".", groups);
145}
146
147void
148part1(const vector<string>& input)
149{
150 auto sum = 0L;
151 for ( const auto& line: input ) {
152 auto parts = split(line, ' ');
153 auto springs = parts[0];
154 auto groups = read_ints(parts[1]);
155
156 sum += brute_force(springs, groups);
157 // sum += count(springs, groups);
158 }
159 cout << sum << endl;
160}
161
162void
163part2(const vector<string>& input)
164{
165 auto sum = 0L;
166 for ( const auto& line: input ) {
167 auto parts = split(line, ' ');
168 auto springs = parts[0] + "?" + parts[0] + "?" + parts[0] + "?" + parts[0] + "?" + parts[0];
169 auto groups = read_ints(parts[1] + "," + parts[1] + "," + parts[1] + "," + parts[1] + "," + parts[1]);
170
171 sum += count(springs, groups);
172 }
173 cout << sum << endl;
174}
175
176int
177main()
178{
179 const auto input = read_file("data/day12.txt");
180 part1(input);
181 part2(input);
182}
diff --git a/src/day13.cpp b/src/day13.cpp
deleted file mode 100644
index 549457b..0000000
--- a/src/day13.cpp
+++ /dev/null
@@ -1,115 +0,0 @@
1#include <algorithm>
2#include <fstream>
3#include <iostream>
4#include <iterator>
5#include <sstream>
6#include <string>
7#include <vector>
8using namespace std;
9
10string
11read_file(string_view filename)
12{
13 fstream input{ filename };
14 return { istreambuf_iterator<char>{ input }, istreambuf_iterator<char>{} };
15}
16
17vector<string>
18split(string_view line, string_view delimiter)
19{
20 size_t pos_start = 0;
21 size_t pos_end = 0;
22
23 vector<string> res;
24
25 while ( (pos_end = line.find(delimiter, pos_start)) != std::string::npos ) {
26 auto token = line.substr(pos_start, pos_end - pos_start);
27 pos_start = pos_end + delimiter.length();
28
29 res.emplace_back(token);
30 }
31
32 res.emplace_back(line.substr(pos_start));
33 return res;
34}
35
36vector<string>
37transpose(const vector<string>& lines)
38{
39 vector<string> result(lines[0].size());
40
41 for ( const auto& line: lines ) {
42 for ( size_t i = 0; i < line.size(); ++i ) {
43 result[i] += line[i];
44 }
45 }
46 return result;
47}
48
49long
50find_mirror(const vector<string>& input)
51{
52 for ( size_t idx = 1; idx < input.size(); ++idx ) {
53 bool equal = true;
54 for ( size_t cnt = 0; cnt != min(idx, input.size() - idx); ++cnt ) {
55 if ( !(input[idx + cnt] == input[idx - 1 - cnt]) ) {
56 equal = false;
57 break;
58 }
59 }
60 if ( equal ) {
61 return long(idx);
62 }
63 }
64 return 0;
65}
66
67long
68count_differences(string_view str1, string_view str2)
69{
70 long diffs = 0;
71 for ( size_t idx = 0; idx != str1.size(); ++idx ) {
72 diffs += long(str1[idx] != str2[idx]);
73 }
74 return diffs;
75}
76
77long
78find_mirror_part2(const vector<string>& input)
79{
80 for ( size_t idx = 1; idx < input.size(); ++idx ) {
81 long errs = 0;
82 for ( size_t i = 0; i != min(idx, input.size() - idx); ++i ) {
83 errs += count_differences(input[idx + i], input[idx - 1 - i]);
84 }
85 if ( errs == 1 ) {
86 return long(idx);
87 }
88 }
89 return 0;
90}
91
92void
93solve(const function<long(const vector<string>&)>& find_mirror)
94{
95 static const long multiplier = 100;
96
97 auto contents = read_file("data/day13.txt");
98 auto parts = split(contents, "\n\n");
99
100 long sum = 0;
101 for ( const auto& part: parts ) {
102 auto lines = split(part, "\n");
103
104 sum += find_mirror(transpose(lines));
105 sum += find_mirror(lines) * multiplier;
106 }
107 cout << sum << endl;
108}
109
110int
111main()
112{
113 solve(find_mirror);
114 solve(find_mirror_part2);
115}
diff --git a/src/day14.cpp b/src/day14.cpp
deleted file mode 100644
index 8816ce1..0000000
--- a/src/day14.cpp
+++ /dev/null
@@ -1,239 +0,0 @@
1#include <chrono>
2#include <cstddef>
3#include <fstream>
4#include <iostream>
5#include <map>
6#include <string>
7#include <vector>
8using namespace std;
9
10vector<string>
11read_file(string_view filename)
12{
13 fstream input{ filename };
14 vector<string> data;
15
16 for ( string line; getline(input, line); ) {
17 data.emplace_back(line);
18 }
19
20 return data;
21}
22
23void
24part1(const vector<string>& lines)
25{
26 auto start = chrono::steady_clock::now();
27
28 size_t sum = 0;
29 for ( size_t col = 0; col != lines[0].size(); ++col ) {
30 size_t counter = lines.size();
31
32 for ( size_t row = 0; row != lines.size(); ++row ) {
33 if ( lines[row][col] == 'O' ) {
34 sum += counter;
35 --counter;
36 }
37 if ( lines[row][col] == '#' ) {
38 counter = lines.size() - row - 1;
39 }
40 }
41 }
42
43 auto duration = chrono::duration_cast<chrono::microseconds>(chrono::steady_clock::now() - start).count();
44
45 cout << sum << " (" << duration << " μs)" << endl;
46}
47
48void
49tilt_north(vector<string>& lines)
50{
51 for ( size_t col = 0; col != lines[0].size(); ++col ) {
52 size_t row = 0;
53 while ( row != lines.size() ) {
54 size_t stones = 0;
55 size_t empty = 0;
56
57 for ( size_t idx = row; idx != lines.size() && lines[idx][col] != '#'; ++idx ) {
58 if ( lines[idx][col] == '.' ) {
59 ++empty;
60 }
61 if ( lines[idx][col] == 'O' ) {
62 ++stones;
63 }
64 }
65
66 while ( stones-- != 0 ) {
67 lines[row++][col] = 'O';
68 }
69
70 while ( empty-- != 0 ) {
71 lines[row++][col] = '.';
72 }
73
74 while ( row != lines.size() && lines[row][col] == '#' ) {
75 ++row;
76 }
77 }
78 }
79}
80
81void
82tilt_south(vector<string>& lines)
83{
84 for ( size_t col = 0; col != lines[0].size(); ++col ) {
85 size_t row = 0;
86 while ( row != lines.size() ) {
87 size_t stones = 0;
88 size_t empty = 0;
89
90 for ( size_t idx = row; idx != lines.size() && lines[idx][col] != '#'; ++idx ) {
91 if ( lines[idx][col] == '.' ) {
92 ++empty;
93 }
94 if ( lines[idx][col] == 'O' ) {
95 ++stones;
96 }
97 }
98
99 while ( empty-- != 0 ) {
100 lines[row++][col] = '.';
101 }
102
103 while ( stones-- != 0 ) {
104 lines[row++][col] = 'O';
105 }
106
107 while ( row != lines.size() && lines[row][col] == '#' ) {
108 ++row;
109 }
110 }
111 }
112}
113
114void
115tilt_west(vector<string>& lines)
116{
117 for ( size_t row = 0; row != lines.size(); ++row ) {
118 size_t col = 0;
119 while ( col != lines[0].size() ) {
120 size_t stones = 0;
121 size_t empty = 0;
122
123 for ( size_t idx = col; idx != lines[0].size() && lines[row][idx] != '#'; ++idx ) {
124 if ( lines[row][idx] == '.' ) {
125 ++empty;
126 }
127 if ( lines[row][idx] == 'O' ) {
128 ++stones;
129 }
130 }
131
132 while ( stones-- != 0 ) {
133 lines[row][col++] = 'O';
134 }
135
136 while ( empty-- != 0 ) {
137 lines[row][col++] = '.';
138 }
139
140 while ( col != lines[0].size() && lines[row][col] == '#' ) {
141 ++col;
142 }
143 }
144 }
145}
146
147void
148tilt_east(vector<string>& lines)
149{
150 for ( size_t row = 0; row != lines.size(); ++row ) {
151 size_t col = 0;
152 while ( col != lines[0].size() ) {
153 size_t stones = 0;
154 size_t empty = 0;
155
156 for ( size_t idx = col; idx != lines[0].size() && lines[row][idx] != '#'; ++idx ) {
157 if ( lines[row][idx] == '.' ) {
158 ++empty;
159 }
160 if ( lines[row][idx] == 'O' ) {
161 ++stones;
162 }
163 }
164
165 while ( empty-- != 0 ) {
166 lines[row][col++] = '.';
167 }
168
169 while ( stones-- != 0 ) {
170 lines[row][col++] = 'O';
171 }
172
173 while ( col != lines[0].size() && lines[row][col] == '#' ) {
174 ++col;
175 }
176 }
177 }
178}
179
180void
181tilt(vector<string>& lines)
182{
183 for ( auto tilt: { tilt_north, tilt_west, tilt_south, tilt_east } ) {
184 tilt(lines);
185 }
186}
187
188size_t
189calc(const vector<string>& lines)
190{
191 size_t sum = 0;
192 size_t counter = lines.size();
193 for ( const auto& line: lines ) {
194 sum += counter * static_cast<size_t>(count_if(line.begin(), line.end(), [](char chr) { return chr == 'O'; }));
195 --counter;
196 }
197 return sum;
198}
199
200void
201part2(vector<string> lines)
202{
203 auto start = chrono::steady_clock::now();
204 map<vector<string>, long> cache;
205
206 const long dest = 1'000'000'000;
207
208 for ( long index = 0;; ++index ) {
209 auto iter = cache.find(lines);
210 if ( iter != cache.end() ) {
211 auto offset = iter->second;
212 auto cycle_length = index - offset;
213
214 auto moves_required = (dest - offset) % cycle_length;
215
216 while ( moves_required-- != 0 ) {
217 tilt(lines);
218 }
219
220 auto duration = chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - start).count();
221
222 cout << calc(lines) << " (" << duration << " ms)" << endl;
223 break;
224 }
225 else {
226 cache[lines] = index;
227 }
228
229 tilt(lines);
230 }
231}
232
233int
234main()
235{
236 const auto lines = read_file("data/day14.txt");
237 part1(lines);
238 part2(lines);
239}
diff --git a/src/day15.cpp b/src/day15.cpp
deleted file mode 100644
index 6fcbfc2..0000000
--- a/src/day15.cpp
+++ /dev/null
@@ -1,102 +0,0 @@
1#include <algorithm>
2#include <fstream>
3#include <iostream>
4#include <list>
5#include <numeric>
6#include <sstream>
7#include <string>
8#include <vector>
9using namespace std;
10
11string
12read_file(string_view filename)
13{
14 fstream input{ filename };
15 return { istreambuf_iterator<char>{ input }, istreambuf_iterator<char>{} };
16}
17
18void
19rtrim(string& str)
20{
21 str.erase(find_if(str.rbegin(), str.rend(), [](auto chr) { return !isspace(chr); }).base(), str.end());
22}
23
24vector<string>
25split(const string& line, char sep)
26{
27 vector<string> parts{};
28 stringstream input{ line };
29
30 for ( string part; getline(input, part, sep); ) {
31 rtrim(part);
32 parts.emplace_back(part);
33 }
34
35 return parts;
36}
37
38unsigned int
39calculate_hash(string_view str)
40{
41 unsigned int value = 0;
42 for ( auto chr: str ) {
43 value += static_cast<unsigned char>(chr);
44 value *= 17;
45 }
46 return value % 256;
47}
48
49void
50part1()
51{
52 const auto parts = split(read_file("data/day15.txt"), ',');
53 cout << accumulate(parts.begin(), parts.end(), 0UL, [](auto init, const auto& str) { return init + calculate_hash(str); }) << endl;
54}
55
56void
57part2()
58{
59 vector<list<tuple<string, long>>> boxes(256);
60
61 const auto line = read_file("data/day15.txt");
62 const auto parts = split(line, ',');
63 for ( const auto& part: parts ) {
64 const auto pos = part.find_first_of("=-");
65 const auto lens = part.substr(0, pos);
66 auto& box = boxes[calculate_hash(lens)];
67
68 if ( part[pos] == '=' ) {
69 const auto value = stol(part.substr(pos + 1));
70
71 auto iter = find_if(box.begin(), box.end(), [&lens](const auto& element) { return get<0>(element) == lens; });
72 if ( iter == box.end() ) {
73 box.emplace_back(lens, value);
74 }
75 else {
76 get<1>(*iter) = value;
77 }
78 }
79 else {
80 box.remove_if([&lens](const auto& element) { return get<0>(element) == lens; });
81 }
82 }
83
84 long value = 0;
85 for ( size_t idx = 0; idx != boxes.size(); ++idx ) {
86 const auto& box = boxes[idx];
87
88 long lens_number = 1;
89 for ( const auto& lens: box ) {
90 value += static_cast<long>(idx + 1) * lens_number * get<1>(lens);
91 ++lens_number;
92 }
93 }
94 cout << value << endl;
95}
96
97int
98main()
99{
100 part1();
101 part2();
102}
diff --git a/src/day16.cpp b/src/day16.cpp
deleted file mode 100644
index 93c7479..0000000
--- a/src/day16.cpp
+++ /dev/null
@@ -1,132 +0,0 @@
1#include <array>
2#include <chrono>
3#include <fstream>
4#include <iostream>
5#include <map>
6#include <queue>
7#include <set>
8#include <string>
9#include <vector>
10using namespace std;
11
12vector<string>
13read_file(string_view filename)
14{
15 fstream input{ filename };
16 vector<string> data;
17
18 for ( string line; getline(input, line); ) {
19 data.emplace_back(line);
20 }
21
22 return data;
23}
24
25const unsigned DIR_UP = 0;
26const unsigned DIR_RIGHT = 1;
27const unsigned DIR_DOWN = 2;
28const unsigned DIR_LEFT = 3;
29
30size_t
31solve(const vector<string>& lines, tuple<size_t, size_t, unsigned int> start)
32{
33 static const array<tuple<size_t, size_t>, 4> movement{
34 make_tuple(0, -1),
35 make_tuple(1, 0),
36 make_tuple(0, 1),
37 make_tuple(-1, 0),
38 };
39
40 map<tuple<size_t, size_t, unsigned int>, bool> visited;
41
42 queue<tuple<size_t, size_t, unsigned int>> positions;
43
44 positions.emplace(start);
45
46 while ( !positions.empty() ) {
47 auto [row, col, dir] = positions.front();
48 positions.pop();
49
50 while ( true ) {
51 col += get<0>(movement.at(dir % 4));
52 row += get<1>(movement.at(dir % 4));
53
54 if ( row >= lines.size() || col >= lines[0].size() ) {
55 break;
56 }
57
58 if ( visited[{ row, col, dir }] ) {
59 break;
60 }
61
62 visited[{ row, col, dir }] = true;
63
64 const auto chr = lines[row][col];
65
66 if ( (chr == '|' && (dir == DIR_LEFT || dir == DIR_RIGHT)) ||
67 (chr == '-' && (dir == DIR_UP || dir == DIR_DOWN)) ) {
68 dir = dir + 1;
69 positions.emplace(row, col, dir + 2);
70 }
71 else if ( (chr == '/' && (dir == DIR_LEFT || dir == DIR_RIGHT)) ||
72 (chr == '\\' && (dir == DIR_UP || dir == DIR_DOWN)) ) {
73 dir = dir + 3;
74 }
75 else if ( (chr == '\\' && (dir == DIR_LEFT || dir == DIR_RIGHT)) ||
76 (chr == '/' && (dir == DIR_UP || dir == DIR_DOWN)) ) {
77 dir = dir + 1;
78 }
79
80 dir %= 4;
81 }
82 }
83
84 set<tuple<size_t, size_t>> foo;
85 for ( const auto& bar: visited ) {
86 foo.emplace(get<0>(bar.first), get<1>(bar.first));
87 }
88 return foo.size();
89}
90
91void
92part1(const vector<string>& lines)
93{
94 auto start = chrono::steady_clock::now();
95
96 auto sum = solve(lines, { 0, -1, DIR_RIGHT });
97
98 auto duration = chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - start).count();
99
100 cout << sum << " (" << duration << "ms)" << endl;
101}
102
103void
104part2(const vector<string>& lines)
105{
106 const auto rows = lines.size();
107 const auto cols = lines[0].size();
108
109 auto start = chrono::steady_clock::now();
110
111 size_t sum = 0;
112 for ( size_t row = 0; row != rows; ++row ) {
113 sum = max(sum, solve(lines, { row, -1, DIR_RIGHT }));
114 sum = max(sum, solve(lines, { row, cols, DIR_LEFT }));
115 }
116 for ( size_t col = 0; col != cols; ++col ) {
117 sum = max(sum, solve(lines, { -1, col, DIR_DOWN }));
118 sum = max(sum, solve(lines, { rows, col, DIR_UP }));
119 }
120
121 auto duration = chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - start).count();
122
123 cout << sum << " (" << duration << "ms)" << endl;
124}
125
126int
127main()
128{
129 const auto lines = read_file("data/day16.txt");
130 part1(lines);
131 part2(lines);
132}
diff --git a/src/day17.cpp b/src/day17.cpp
deleted file mode 100644
index 4098bba..0000000
--- a/src/day17.cpp
+++ /dev/null
@@ -1,112 +0,0 @@
1#include <array>
2#include <fstream>
3#include <functional>
4#include <iostream>
5#include <queue>
6#include <set>
7#include <string>
8#include <vector>
9using namespace std;
10
11using puzzle_t = vector<vector<int>>;
12
13puzzle_t
14read_file(string_view filename)
15{
16 fstream input{ filename };
17 puzzle_t data;
18
19 for ( string line; getline(input, line); ) {
20 puzzle_t::value_type numbers;
21 for ( auto chr: line ) {
22 numbers.emplace_back(chr - '0');
23 }
24 data.emplace_back(numbers);
25 }
26
27 return data;
28}
29
30int
31solve(const puzzle_t& puzzle, size_t min_steps, size_t max_steps)
32{
33 using pos_t = tuple<size_t, size_t>;
34 using dir_t = tuple<size_t, size_t>;
35 using entry = tuple<int, pos_t, dir_t>;
36
37 static const array<pos_t, 4> directions = {
38 make_tuple(0, 1),
39 make_tuple(0, -1),
40 make_tuple(1, 0),
41 make_tuple(-1, 0)
42 };
43
44 priority_queue<entry, vector<entry>, greater<>> queue;
45
46 set<tuple<pos_t, dir_t>> seen;
47
48 const pos_t target = { puzzle.size() - 1, puzzle[0].size() - 1 };
49
50 queue.emplace(0, pos_t(0, 0), dir_t(0, 0));
51
52 while ( !queue.empty() ) {
53 const auto [heat, pos, dir] = queue.top();
54 queue.pop();
55
56 if ( pos == target ) {
57 return heat;
58 }
59
60 const auto key = make_tuple(pos, dir);
61 if ( seen.contains(key) ) {
62 continue;
63 }
64 seen.emplace(key);
65
66 const dir_t inv_dir = { -get<0>(dir), -get<1>(dir) };
67
68 for ( const auto& next_dir: directions ) {
69 if ( next_dir == dir || next_dir == inv_dir ) {
70 continue;
71 }
72
73 auto heat_so_far = heat;
74
75 for ( size_t steps = 1; steps <= max_steps; ++steps ) {
76 const pos_t next_pos = { get<0>(pos) + get<0>(next_dir) * steps,
77 get<1>(pos) + get<1>(next_dir) * steps };
78
79 if ( get<0>(next_pos) >= puzzle.size() || get<1>(next_pos) >= puzzle[0].size() ) {
80 continue;
81 }
82
83 heat_so_far += puzzle[get<0>(next_pos)][get<1>(next_pos)];
84
85 if ( steps >= min_steps ) {
86 queue.emplace(heat_so_far, next_pos, next_dir);
87 }
88 }
89 }
90 }
91 return -1;
92}
93
94void
95part1(const puzzle_t& puzzle)
96{
97 cout << solve(puzzle, 1, 3) << endl;
98}
99
100void
101part2(const puzzle_t& puzzle)
102{
103 cout << solve(puzzle, 4, 10) << endl;
104}
105
106int
107main()
108{
109 const auto puzzle = read_file("data/day17.txt");
110 part1(puzzle);
111 part2(puzzle);
112}
diff --git a/src/day18.cpp b/src/day18.cpp
deleted file mode 100644
index 3037739..0000000
--- a/src/day18.cpp
+++ /dev/null
@@ -1,115 +0,0 @@
1#include <fstream>
2#include <iostream>
3#include <map>
4#include <sstream>
5#include <string>
6#include <vector>
7using namespace std;
8
9using puzzle_t = vector<pair<long, long>>;
10
11puzzle_t
12read_file_part1(string_view filename, long& border_steps)
13{
14 static map<char, pair<int, int>> movement = {
15 { 'U', { 0, -1 } }, // up
16 { 'D', { 0, 1 } }, // down
17 { 'L', { -1, 0 } }, // left
18 { 'R', { 1, 0 } }, // right
19 };
20
21 border_steps = 0;
22
23 fstream input{ filename };
24 puzzle_t data;
25
26 data.emplace_back(0, 0);
27
28 for ( string line; getline(input, line); ) {
29 char dir{};
30 long steps{};
31 stringstream sstrm{ line };
32
33 if ( sstrm >> dir >> steps ) {
34 data.emplace_back(get<0>(data.back()) + get<0>(movement[dir]) * steps,
35 get<1>(data.back()) + get<1>(movement[dir]) * steps);
36
37 border_steps += steps;
38 }
39 }
40
41 return data;
42}
43
44puzzle_t
45read_file_part2(string_view filename, long& border_steps)
46{
47 static map<char, pair<int, int>> movement = {
48 { '0', { 1, 0 } }, // right
49 { '1', { 0, 1 } }, // down
50 { '2', { -1, 0 } }, // left
51 { '3', { 0, -1 } }, // up
52 };
53
54 border_steps = 0;
55
56 fstream input{ filename };
57 puzzle_t data;
58
59 data.emplace_back(0, 0);
60
61 for ( string line; getline(input, line); ) {
62 char dir{};
63 long steps{};
64 string hexcode;
65 stringstream sstrm{ line };
66
67 if ( sstrm >> dir >> steps >> hexcode ) {
68 steps = stol(hexcode.substr(2, 5), nullptr, 16);
69 dir = hexcode[7];
70
71 data.emplace_back(get<0>(data.back()) + get<0>(movement[dir]) * steps,
72 get<1>(data.back()) + get<1>(movement[dir]) * steps);
73
74 border_steps += steps;
75 }
76 }
77
78 return data;
79}
80
81long
82shoelace(const puzzle_t& puzzle, const long border_steps)
83{
84 long area = 0;
85 for ( size_t i = 1; i < puzzle.size(); ++i ) {
86 const auto [x1, y1] = puzzle[i - 1];
87 const auto [x2, y2] = puzzle[i];
88
89 area += (x1 * y2 - y1 * x2);
90 }
91 return (border_steps + area) / 2 + 1;
92}
93
94void
95part1()
96{
97 long border_steps = 0;
98 auto puzzle = read_file_part1("data/day18.txt", border_steps);
99 cout << shoelace(puzzle, border_steps) << endl;
100}
101
102void
103part2()
104{
105 long border_steps = 0;
106 auto puzzle = read_file_part2("data/day18.txt", border_steps);
107 cout << shoelace(puzzle, border_steps) << endl;
108}
109
110int
111main()
112{
113 part1();
114 part2();
115}
diff --git a/src/day19.cpp b/src/day19.cpp
deleted file mode 100644
index a1d4eab..0000000
--- a/src/day19.cpp
+++ /dev/null
@@ -1,183 +0,0 @@
1#include <fstream>
2#include <functional>
3#include <iostream>
4#include <map>
5#include <regex>
6#include <string>
7#include <vector>
8using namespace std;
9
10string
11read_file(string_view filename)
12{
13 fstream input{ filename };
14 return { istreambuf_iterator<char>{ input }, istreambuf_iterator<char>{} };
15}
16
17vector<string>
18split(string_view line, string_view delimiter)
19{
20 size_t pos_start = 0;
21 size_t pos_end = 0;
22
23 vector<string> res;
24
25 while ( (pos_end = line.find(delimiter, pos_start)) != string::npos ) {
26 auto token = line.substr(pos_start, pos_end - pos_start);
27 pos_start = pos_end + delimiter.length();
28
29 res.emplace_back(token);
30 }
31
32 if ( pos_start != line.size() ) {
33 res.emplace_back(line.substr(pos_start));
34 }
35 return res;
36}
37
38void
39part1(map<string, tuple<vector<tuple<string, string, long, string>>, string>> rules, const vector<string>& parts)
40{
41 long sum = 0;
42 for ( const auto& part: parts ) {
43 static const regex parts_pattern{ R"(\{x=(\d*),m=(\d*),a=(\d*),s=(\d*)\})" };
44
45 smatch smatch;
46 if ( !regex_search(part, smatch, parts_pattern) ) {
47 continue;
48 }
49
50 map<string, long> values = {
51 { "x", stol(smatch[1]) },
52 { "m", stol(smatch[2]) },
53 { "a", stol(smatch[3]) },
54 { "s", stol(smatch[4]) },
55 };
56
57 string rule = "in";
58 while ( rule != "A" && rule != "R" ) {
59 auto [sub_rules, next_rule] = rules[rule];
60
61 for ( const auto& sub_rule: sub_rules ) {
62 const auto [field, cmp, value, dest] = sub_rule;
63
64 if ( values.contains(field) && ((cmp == ">" && values[field] > value) || (cmp == "<" && values[field] < value)) ) {
65 next_rule = dest;
66 break;
67 }
68 }
69
70 rule = next_rule;
71 }
72
73 if ( rule == "A" ) {
74 sum += values["x"];
75 sum += values["m"];
76 sum += values["a"];
77 sum += values["s"];
78 }
79 }
80 cout << sum << endl;
81}
82
83void
84part2(map<string, tuple<vector<tuple<string, string, long, string>>, string>> rules)
85{
86 function<long(map<string, tuple<long, long>>, string)> count = [&](map<string, tuple<long, long>> ranges, const string& name) -> long {
87 if ( name == "R" ) {
88 return 0;
89 }
90
91 if ( name == "A" ) {
92 long result = 1;
93 for ( const auto& range: ranges ) {
94 const auto [lo, hi] = range.second;
95 result *= hi - lo + 1;
96 }
97 return result;
98 }
99
100 const auto [sub_rules, fallback] = rules[name];
101
102 long result = 0;
103
104 bool run_trough = true;
105 for ( const auto& [key, cmp, value, target]: sub_rules ) {
106 const auto [lo, hi] = ranges[key];
107 pair<long, long> T; // NOLINT
108 pair<long, long> F; // NOLINT
109 if ( cmp == "<" ) {
110 T = { lo, min(value - 1, hi) };
111 F = { max(value, lo), hi };
112 }
113 else {
114 T = { max(value + 1, lo), hi };
115 F = { lo, min(value, hi) };
116 }
117 if ( T.first <= T.second ) {
118 auto copy = ranges;
119 copy[key] = T;
120 result += count(copy, target);
121 }
122 if ( F.first <= F.second ) {
123 ranges[key] = F;
124 }
125 else {
126 run_trough = false;
127 break;
128 }
129 }
130 if ( run_trough ) {
131 result += count(ranges, fallback);
132 }
133
134 return result;
135 };
136
137 cout << count({
138 { "x", { 1, 4000 } },
139 { "m", { 1, 4000 } },
140 { "a", { 1, 4000 } },
141 { "s", { 1, 4000 } },
142 },
143 "in")
144 << endl;
145}
146
147int
148main()
149{
150 const auto input = split(read_file("data/day19.txt"), "\n\n");
151 const auto rules_string = split(input[0], "\n");
152 const auto parts = split(input[1], "\n");
153
154 map<string, tuple<vector<tuple<string, string, long, string>>, string>> rules;
155
156 for ( const auto& rule: rules_string ) {
157 static const regex rules_pattern{ R"((.*)\{(.*),(.*)\})" };
158
159 smatch smatch;
160 if ( !regex_search(rule, smatch, rules_pattern) ) {
161 continue;
162 }
163
164 string name = smatch[1];
165 string default_rule = smatch[3];
166
167 vector<tuple<string, string, long, string>> sub_rules;
168
169 for ( const auto& sub_rule: split(smatch[2].str(), ",") ) {
170 static const regex sub_rules_pattern{ R"((.)(.)(\d*):(.*))" };
171
172 std::smatch smatch2;
173 if ( regex_search(sub_rule, smatch2, sub_rules_pattern) ) {
174 sub_rules.emplace_back(smatch2[1], smatch2[2], stol(smatch2[3]), smatch2[4]);
175 }
176 }
177
178 rules[name] = make_tuple(sub_rules, default_rule);
179 }
180
181 part1(rules, parts);
182 part2(rules);
183}
diff --git a/src/day20.cpp b/src/day20.cpp
deleted file mode 100644
index f85ac90..0000000
--- a/src/day20.cpp
+++ /dev/null
@@ -1,293 +0,0 @@
1#include <algorithm>
2#include <fstream>
3#include <iostream>
4#include <map>
5#include <memory>
6#include <numeric>
7#include <queue>
8#include <string>
9#include <vector>
10
11using namespace std;
12
13vector<string>
14read_file(string_view filename)
15{
16 fstream input{ filename };
17 vector<string> data;
18
19 for ( string line; getline(input, line); ) {
20 data.emplace_back(line);
21 }
22
23 return data;
24}
25
26vector<string>
27split(string_view line, string_view delimiter)
28{
29 size_t pos_start = 0;
30 size_t pos_end = 0;
31
32 vector<string> res;
33
34 while ( (pos_end = line.find(delimiter, pos_start)) != string::npos ) {
35 auto token = line.substr(pos_start, pos_end - pos_start);
36 pos_start = pos_end + delimiter.length();
37
38 res.emplace_back(token);
39 }
40
41 if ( pos_start != line.size() ) {
42 res.emplace_back(line.substr(pos_start));
43 }
44 return res;
45}
46
47struct Module { // NOLINT
48protected:
49 explicit Module(string_view name, queue<tuple<string, int, string>>& queue)
50 : name_(name)
51 , queue_(queue)
52 {
53 }
54 virtual ~Module() = default;
55
56public:
57 virtual void trigger(string_view sender, int signal) = 0;
58
59 void register_sender(string_view sender) { senders_.emplace(sender, 0); }
60
61protected:
62 void send_signal(int signal) const
63 {
64 for ( const auto& link: links_ ) {
65 queue_.emplace(name_, signal, link);
66 }
67 }
68
69public:
70 void add_link(string_view link) { links_.emplace_back(link); }
71
72protected:
73 const string name_;
74 queue<tuple<string, int, string>>& queue_;
75
76public:
77 vector<string> links_;
78 map<string, int> senders_;
79};
80
81struct BroadcasterModuler : public Module {
82 explicit BroadcasterModuler(string_view name, queue<tuple<string, int, string>>& queue)
83 : Module(name, queue)
84 {
85 }
86 void trigger(string_view, int signal) override
87 {
88 send_signal(signal);
89 }
90};
91
92struct FlipFlopModule : public Module {
93 explicit FlipFlopModule(string_view name, queue<tuple<string, int, string>>& queue)
94 : Module(name, queue)
95 {
96 }
97 void trigger(string_view, int signal) override
98 {
99 if ( signal == 1 ) {
100 return;
101 }
102 state_ = (state_ + 1) % 2;
103 send_signal(state_);
104 }
105 int state_{ 0 };
106};
107
108struct ConjunctionModule : public Module {
109 explicit ConjunctionModule(string_view name, queue<tuple<string, int, string>>& queue)
110 : Module(name, queue)
111 {
112 }
113 void trigger(string_view sender, int signal) override
114 {
115 senders_[string(sender)] = signal;
116 if ( all_of(senders_.begin(), senders_.end(), [](const auto& link) { return link.second == 1; }) ) {
117 send_signal(0);
118 }
119 else {
120 send_signal(1);
121 }
122 }
123};
124
125struct OutputModule : public Module {
126 explicit OutputModule(string_view name, queue<tuple<string, int, string>>& queue)
127 : Module(name, queue)
128 {
129 }
130 void trigger(string_view, int) override
131 {
132 }
133};
134
135void
136part1(const vector<string>& input)
137{
138 queue<tuple<string, int, string>> queue;
139 map<string, shared_ptr<Module>> modules;
140
141 modules["output"] = make_shared<OutputModule>("output", queue);
142
143 for ( const auto& line: input ) {
144 const auto parts = split(line, " -> ");
145 auto module = parts[0];
146 const auto dests = split(parts[1], ", ");
147
148 shared_ptr<Module> ptr;
149 if ( module == "broadcaster" ) {
150 ptr = make_shared<BroadcasterModuler>(module, queue);
151 }
152 else if ( module.starts_with('%') ) {
153 module.erase(0, 1);
154 ptr = make_shared<FlipFlopModule>(module, queue);
155 }
156 else if ( module.starts_with('&') ) {
157 module.erase(0, 1);
158 ptr = make_shared<ConjunctionModule>(module, queue);
159 }
160 else {
161 cerr << "unknown module type: " << module << endl;
162 return;
163 }
164
165 for ( const auto& dest: dests ) {
166 ptr->add_link(dest);
167 }
168
169 modules[module] = ptr;
170 }
171
172 // register senders
173 for ( auto& module: modules ) {
174 auto [name, ptr] = module;
175
176 for ( const auto& link: ptr->links_ ) {
177 if ( modules.contains(link) ) {
178 modules[link]->register_sender(name);
179 }
180 }
181 }
182
183 long sums[2] = { 0, 0 };
184 for ( int i = 0; i != 1000; ++i ) {
185 queue.emplace("button", 0, "broadcaster");
186 while ( !queue.empty() ) {
187 const auto [sender, signal, receiver] = queue.front();
188 queue.pop();
189
190 sums[signal]++;
191
192 if ( modules.contains(receiver) ) {
193 modules[receiver]->trigger(sender, signal);
194 }
195 }
196 }
197 cout << sums[0] * sums[1] << endl;
198}
199
200void
201part2(const vector<string>& input)
202{
203 queue<tuple<string, int, string>> queue;
204 map<string, shared_ptr<Module>> modules;
205
206 modules["output"] = make_shared<OutputModule>("output", queue);
207
208 for ( const auto& line: input ) {
209 const auto parts = split(line, " -> ");
210 auto module = parts[0];
211 const auto dests = split(parts[1], ", ");
212
213 shared_ptr<Module> ptr;
214 if ( module == "broadcaster" ) {
215 ptr = make_shared<BroadcasterModuler>(module, queue);
216 }
217 else if ( module.starts_with('%') ) {
218 module.erase(0, 1);
219 ptr = make_shared<FlipFlopModule>(module, queue);
220 }
221 else if ( module.starts_with('&') ) {
222 module.erase(0, 1);
223 ptr = make_shared<ConjunctionModule>(module, queue);
224 }
225 else {
226 cerr << "unknown module type: " << module << endl;
227 return;
228 }
229
230 for ( const auto& dest: dests ) {
231 ptr->add_link(dest);
232 }
233
234 modules[module] = ptr;
235 }
236
237 // register senders
238 string to_rx;
239 for ( auto& module: modules ) {
240 auto [name, ptr] = module;
241
242 for ( const auto& link: ptr->links_ ) {
243 if ( modules.contains(link) ) { // link == "rx"
244 modules[link]->register_sender(name);
245 }
246 else {
247 to_rx = name;
248 }
249 }
250 }
251
252 map<string, long> cycle_modules;
253 for ( auto& module: modules ) {
254 auto [name, ptr] = module;
255 const auto links = ptr->links_;
256
257 if ( find(links.begin(), links.end(), to_rx) != links.end() ) {
258 cycle_modules[name] = 0;
259 }
260 }
261
262 for ( long i = 1;; ++i ) {
263 queue.emplace("button", 0, "broadcaster");
264 while ( !queue.empty() ) {
265 const auto [sender, signal, receiver] = queue.front();
266 queue.pop();
267
268 if ( signal == 1 && cycle_modules.contains(sender) ) {
269 cycle_modules[sender] = i;
270 }
271
272 if ( modules.contains(receiver) ) {
273 modules[receiver]->trigger(sender, signal);
274 }
275 }
276 if ( all_of(cycle_modules.begin(), cycle_modules.end(), [](const auto& module) { return module.second != 0; }) ) {
277 long result = 1;
278 for ( const auto& module: cycle_modules ) {
279 result = lcm(result, module.second);
280 }
281 cout << result << endl;
282 break;
283 }
284 }
285}
286
287int
288main()
289{
290 const auto input = read_file("data/day20.txt");
291 part1(input);
292 part2(input);
293}
diff --git a/src/day21.cpp b/src/day21.cpp
deleted file mode 100644
index c633155..0000000
--- a/src/day21.cpp
+++ /dev/null
@@ -1,148 +0,0 @@
1#include <cstddef>
2#include <fstream>
3#include <iostream>
4#include <queue>
5#include <set>
6#include <string>
7#include <vector>
8using namespace std;
9
10using position = tuple<size_t, size_t>;
11
12vector<string>
13read_file(string_view filename)
14{
15 fstream input{ filename };
16 vector<string> data;
17
18 for ( string line; getline(input, line); ) {
19 data.emplace_back(line);
20 }
21
22 return data;
23}
24
25position
26find_start_position(const vector<string>& lines)
27{
28 for ( size_t row = 0; row != lines.size(); ++row ) {
29 for ( size_t col = 0; col != lines[row].size(); ++col ) {
30 if ( lines[row][col] == 'S' ) {
31 return { row, col };
32 }
33 }
34 }
35 return {};
36}
37
38set<position>
39find_neighbours(position pos, const vector<string>& lines)
40{
41 static const vector<position> movements = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
42
43 set<position> neighbours;
44 const auto [row, col] = pos;
45
46 for ( const auto& [drow, dcol]: movements ) {
47 const auto nrow = row + drow;
48 const auto ncol = col + dcol;
49
50 if ( nrow < lines.size() && ncol < lines[0].size() && (lines[nrow][ncol] == '.' || lines[nrow][ncol] == 'S') ) {
51 neighbours.emplace(nrow, ncol);
52 }
53 }
54
55 return neighbours;
56}
57
58size_t
59count(vector<string> lines, position start, size_t rounds)
60{
61 queue<position> positions;
62 positions.emplace(start);
63
64 size_t sum = 0;
65 for ( size_t round = 0; round != rounds; ++round ) {
66 set<position> next_positions;
67
68 sum = 0;
69 while ( !positions.empty() ) {
70 const auto [curr_row, curr_col] = positions.front();
71 lines[curr_row][curr_col] = '.';
72
73 const auto neighbours = find_neighbours(positions.front(), lines);
74 positions.pop();
75
76 for ( const auto& [row, col]: neighbours ) {
77 lines[row][col] = 'O';
78 next_positions.emplace(row, col);
79 ++sum;
80 }
81 }
82
83 for ( const auto& position: next_positions ) {
84 positions.emplace(position);
85 }
86 }
87 return sum;
88}
89
90void
91part1(const vector<string>& lines)
92{
93 const auto start = find_start_position(lines);
94 cout << count(lines, start, 64) << endl;
95}
96
97void
98part2(const vector<string>& lines)
99{
100 const auto start = find_start_position(lines);
101 const auto [row, col] = start;
102
103 const auto pow2 = [](size_t val) -> size_t {
104 return val * val;
105 };
106
107 const auto size = lines.size();
108 const size_t steps = 26501365;
109 const auto grid_width = steps / size - 1;
110
111 const auto num_odd_tiles = pow2(grid_width / 2 * 2 + 1);
112 const auto num_even_tiles = pow2((grid_width + 1) / 2 * 2);
113 const auto num_odd_points = count(lines, start, size * 2 + 1);
114 const auto num_even_points = count(lines, start, size * 2);
115
116 auto sum = num_odd_tiles * num_odd_points + num_even_tiles * num_even_points;
117
118 const auto corner_top = count(lines, { size - 1, col }, size - 1);
119 const auto corner_right = count(lines, { row, 0 }, size - 1);
120 const auto corner_bottom = count(lines, { 0, col }, size - 1);
121 const auto corner_left = count(lines, { row, size - 1 }, size - 1);
122
123 sum += corner_top + corner_right + corner_bottom + corner_left;
124
125 const auto small_top_right = count(lines, { size - 1, 0 }, size / 2 - 1);
126 const auto small_top_left = count(lines, { size - 1, size - 1 }, size / 2 - 1);
127 const auto small_bottom_right = count(lines, { 0, 0 }, size / 2 - 1);
128 const auto small_bottom_left = count(lines, { 0, size - 1 }, size / 2 - 1);
129
130 sum += (grid_width + 1) * (small_top_right + small_top_left + small_bottom_right + small_bottom_left);
131
132 const auto large_top_right = count(lines, { size - 1, 0 }, size * 3 / 2 - 1);
133 const auto large_top_left = count(lines, { size - 1, size - 1 }, size * 3 / 2 - 1);
134 const auto large_bottom_right = count(lines, { 0, 0 }, size * 3 / 2 - 1);
135 const auto large_bottom_left = count(lines, { 0, size - 1 }, size * 3 / 2 - 1);
136
137 sum += grid_width * (large_top_right + large_top_left + large_bottom_right + large_bottom_left);
138
139 cout << sum << endl;
140}
141
142int
143main()
144{
145 auto lines = read_file("data/day21.txt");
146 part1(lines);
147 part2(lines);
148}
diff --git a/src/day22.cpp b/src/day22.cpp
deleted file mode 100644
index 1afb994..0000000
--- a/src/day22.cpp
+++ /dev/null
@@ -1,157 +0,0 @@
1#include <fstream>
2#include <iostream>
3#include <map>
4#include <regex>
5#include <set>
6#include <string>
7#include <vector>
8using namespace std;
9
10struct piece {
11 int x1, y1, z1;
12 int x2, y2, z2;
13};
14
15vector<piece>
16read_file(string_view filename)
17{
18 static const regex pattern{ R"((\d+),(\d+),(\d+)~(\d+),(\d+),(\d+))" };
19
20 fstream input{ filename };
21 vector<piece> data;
22
23 for ( string line; getline(input, line); ) {
24 smatch matches;
25 if ( regex_search(line, matches, pattern) ) {
26 data.emplace_back(piece{
27 stoi(matches[1]),
28 stoi(matches[2]),
29 stoi(matches[3]),
30 stoi(matches[4]),
31 stoi(matches[5]),
32 stoi(matches[6]) });
33 }
34 }
35 sort(data.begin(), data.end(), [](const auto& lhs, const auto& rhs) { return lhs.z1 < rhs.z1; });
36
37 return data;
38}
39
40void
41part1(vector<piece> puzzle)
42{
43 map<int, map<int, int>> grid;
44
45 map<size_t, vector<size_t>> supported_by;
46 map<size_t, vector<size_t>> supports;
47
48 for ( size_t idx = 0; idx != puzzle.size(); ++idx ) {
49 auto& piece = puzzle[idx];
50
51 int max_z = 0;
52 for ( auto x = piece.x1; x <= piece.x2; ++x ) {
53 for ( auto y = piece.y1; y <= piece.y2; ++y ) {
54 max_z = max(max_z, grid[x][y]);
55 }
56 }
57
58 auto height = piece.z2 - piece.z1 + 1;
59
60 for ( auto x = piece.x1; x <= piece.x2; ++x ) {
61 for ( auto y = piece.y1; y <= piece.y2; ++y ) {
62 grid[x][y] = max_z + height;
63 }
64 }
65
66 piece.z1 = max_z + 1;
67 piece.z2 = max_z + height;
68
69 for ( size_t idx2 = idx; idx2-- > 0; ) {
70 if ( piece.x1 > puzzle[idx2].x2 || puzzle[idx2].x1 > piece.x2 ) {
71 continue;
72 }
73 if ( piece.y1 > puzzle[idx2].y2 || puzzle[idx2].y1 > piece.y2 ) {
74 continue;
75 }
76 if ( puzzle[idx].z1 == puzzle[idx2].z2 + 1 ) {
77 supports[idx2].emplace_back(idx);
78 supported_by[idx].emplace_back(idx2);
79 }
80 }
81 }
82
83 long number = 0;
84 for ( size_t idx = 0; idx != puzzle.size(); ++idx ) {
85 if ( all_of(supports[idx].begin(), supports[idx].end(), [&](const auto& idx2) { return supported_by[idx2].size() > 1; }) ) {
86 ++number;
87 }
88 }
89 cout << number << endl;
90}
91
92void
93part2(vector<piece> puzzle)
94{
95 map<int, map<int, int>> grid;
96
97 for ( auto& piece: puzzle ) {
98 int max_z = 0;
99 for ( auto x = piece.x1; x <= piece.x2; ++x ) {
100 for ( auto y = piece.y1; y <= piece.y2; ++y ) {
101 max_z = max(max_z, grid[x][y]);
102 }
103 }
104
105 auto height = piece.z2 - piece.z1 + 1;
106
107 for ( auto x = piece.x1; x <= piece.x2; ++x ) {
108 for ( auto y = piece.y1; y <= piece.y2; ++y ) {
109 grid[x][y] = max_z + height;
110 }
111 }
112
113 piece.z1 = max_z + 1;
114 piece.z2 = max_z + height;
115 }
116
117 int num = 0;
118 for ( size_t idx = 0; idx != puzzle.size(); ++idx ) {
119 map<int, map<int, int>> grid;
120
121 for ( size_t idx2 = 0; idx2 != puzzle.size(); ++idx2 ) {
122 if ( idx == idx2 ) {
123 continue;
124 }
125
126 const auto& piece = puzzle[idx2];
127
128 int max_z = 0;
129 for ( auto x = piece.x1; x <= piece.x2; ++x ) {
130 for ( auto y = piece.y1; y <= piece.y2; ++y ) {
131 max_z = max(max_z, grid[x][y]);
132 }
133 }
134
135 auto height = piece.z2 - piece.z1 + 1;
136
137 for ( auto x = piece.x1; x <= piece.x2; ++x ) {
138 for ( auto y = piece.y1; y <= piece.y2; ++y ) {
139 grid[x][y] = max_z + height;
140 }
141 }
142
143 if ( piece.z1 != max_z + 1 ) {
144 ++num;
145 }
146 }
147 }
148 cout << num << endl;
149}
150
151int
152main()
153{
154 const auto puzzle = read_file("data/day22.txt");
155 part1(puzzle);
156 part2(puzzle);
157}
diff --git a/src/day23.cpp b/src/day23.cpp
deleted file mode 100644
index d8c20d3..0000000
--- a/src/day23.cpp
+++ /dev/null
@@ -1,152 +0,0 @@
1#include <algorithm>
2#include <array>
3#include <fstream>
4#include <functional>
5#include <iostream>
6#include <iterator>
7#include <map>
8#include <queue>
9#include <set>
10#include <string>
11#include <vector>
12using namespace std;
13
14using position_t = tuple<size_t, size_t>;
15
16vector<string>
17read_file(string_view filename)
18{
19 fstream input{ filename };
20 vector<string> data;
21
22 for ( string line; getline(input, line); ) {
23 data.emplace_back(line);
24 }
25
26 return data;
27}
28
29set<position_t>
30get_neighbours(const vector<string>& maze, position_t possition)
31{
32 static const position_t deltas[] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } }; // NOLINT
33
34 static const auto SYM_UP = '^';
35 static const auto SYM_RIGHT = '>';
36 static const auto SYM_DOWN = 'v';
37 static const auto SYM_LEFT = '<';
38
39 const auto [row, col] = possition;
40
41 switch ( maze[row][col] ) {
42 case SYM_UP:
43 return { make_tuple(row - 1, col) };
44 case SYM_RIGHT:
45 return { make_tuple(row, col + 1) };
46 case SYM_DOWN:
47 return { make_tuple(row + 1, col) };
48 case SYM_LEFT:
49 return { make_tuple(row, col - 1) };
50 }
51
52 set<position_t> positions;
53
54 for ( const auto& delta: deltas ) {
55 const auto new_row = row + get<0>(delta);
56 const auto new_col = col + get<1>(delta);
57
58 if ( new_row >= maze.size() || new_col >= maze[0].size() ) {
59 continue;
60 }
61
62 if ( maze[new_row][new_col] == '#' ) {
63 continue;
64 }
65
66 if ( new_row < row && maze[new_row][new_col] == SYM_DOWN ) {
67 continue;
68 }
69 if ( new_row > row && maze[new_row][new_col] == SYM_UP ) {
70 continue;
71 }
72 if ( new_col < col && maze[new_row][new_col] == SYM_RIGHT ) {
73 continue;
74 }
75 if ( new_col > col && maze[new_row][new_col] == SYM_LEFT ) {
76 continue;
77 }
78
79 positions.emplace(new_row, new_col);
80 }
81
82 return positions;
83}
84
85set<position_t>
86get_neighbours2(const vector<string>& maze, position_t possition)
87{
88 static const position_t deltas[] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } }; // NOLINT
89
90 const auto [row, col] = possition;
91
92 set<position_t> positions;
93
94 for ( const auto& delta: deltas ) {
95 const auto new_row = row + get<0>(delta);
96 const auto new_col = col + get<1>(delta);
97
98 if ( new_row >= maze.size() || new_col >= maze[0].size() ) {
99 continue;
100 }
101
102 if ( maze[new_row][new_col] == '#' ) {
103 continue;
104 }
105
106 positions.emplace(new_row, new_col);
107 }
108
109 return positions;
110}
111
112void
113solve(const vector<string>& maze, function<set<position_t>(const vector<string>&, position_t)> neighbours)
114{
115 const position_t start = { 0, maze[0].find('.') };
116 const position_t end = { maze.size() - 1, maze[maze.size() - 1].find('.') };
117
118 vector<vector<bool>> visited(maze.size(), vector<bool>(maze[0].size()));
119
120 function<long(position_t, long)> find_longest_path = [&](position_t position, long current) -> long {
121 const auto [row, col] = position;
122
123 if ( visited[row][col] ) {
124 return 0;
125 }
126
127 if ( position == end ) {
128 return current;
129 }
130
131 long value = 0;
132
133 visited[row][col] = true;
134 for ( const auto& neighbour: neighbours(maze, position) ) {
135 value = max(value, find_longest_path(neighbour, current + 1));
136 }
137 visited[row][col] = false;
138
139 return value;
140 };
141
142 auto value = find_longest_path(start, 0);
143 cout << value << endl;
144}
145
146int
147main()
148{
149 const auto maze = read_file("data/day23.txt");
150 solve(maze, get_neighbours);
151 solve(maze, get_neighbours2);
152}
diff --git a/src/day24.cpp b/src/day24.cpp
deleted file mode 100644
index 76f459b..0000000
--- a/src/day24.cpp
+++ /dev/null
@@ -1,173 +0,0 @@
1#include <cstdlib>
2#include <fstream>
3#include <iostream>
4#include <limits>
5#include <map>
6#include <string>
7#include <tuple>
8#include <vector>
9#include <z3++.h>
10
11using namespace std;
12
13using line_type = tuple<double, double, double, double, double, double>;
14using point_type = tuple<double, double>;
15using puzzle_type = vector<line_type>;
16
17template<typename T>
18int
19sgn(T val)
20{
21 return (T(0) < val) - (val < T(0));
22}
23
24puzzle_type
25read_file(string_view filename)
26{
27 fstream input{ filename };
28 puzzle_type result;
29
30 for ( string line; getline(input, line); ) {
31 const auto NFIELDS = 6;
32
33 double x, y, z, dx, dy, dz; // NOLINT
34
35 if ( sscanf(line.data(), "%lf, %lf, %lf @ %lf, %lf, %lf", &x, &y, &z, &dx, &dy, &dz) != NFIELDS ) {
36 continue;
37 }
38
39 result.emplace_back(make_tuple(x, y, z, dx, dy, dz));
40 }
41
42 return result;
43}
44
45point_type
46get_direction(line_type line)
47{
48 const auto [x, y, z, dx, dy, dz] = line;
49
50 return make_tuple(sgn(dx), sgn(dy));
51}
52
53point_type
54get_direction(line_type from, point_type to)
55{
56 const auto [x, y, z, dx, dy, dz] = from;
57 const auto [to_x, to_y] = to;
58
59 return make_tuple(sgn(to_x - x), sgn(to_y - y));
60}
61
62bool
63lint(line_type stone_a, line_type stone_b, point_type& cross_point)
64{
65 const auto p_1 = make_tuple(get<0>(stone_a), get<1>(stone_a));
66 const auto p_2 = make_tuple(get<0>(stone_a) + get<3>(stone_a), get<1>(stone_a) + get<4>(stone_a));
67
68 const auto p_3 = make_tuple(get<0>(stone_b), get<1>(stone_b));
69 const auto p_4 = make_tuple(get<0>(stone_b) + get<3>(stone_b), get<1>(stone_b) + get<4>(stone_b));
70
71 const auto a_1 = get<1>(p_2) - get<1>(p_1);
72 const auto b_1 = get<0>(p_1) - get<0>(p_2);
73 const auto c_1 = a_1 * (get<0>(p_1)) + b_1 * (get<1>(p_1));
74
75 const auto a_2 = get<1>(p_4) - get<1>(p_3);
76 const auto b_2 = get<0>(p_3) - get<0>(p_4);
77 const auto c_2 = a_2 * (get<0>(p_3)) + b_2 * (get<1>(p_3));
78
79 const auto determinant = a_1 * b_2 - a_2 * b_1;
80
81 if ( determinant == 0 ) {
82 return false;
83 }
84
85 auto p_x = (b_2 * c_1 - b_1 * c_2) / determinant;
86 auto p_y = (a_1 * c_2 - a_2 * c_1) / determinant;
87
88 cross_point = make_tuple(p_x, p_y);
89
90 return true;
91}
92
93void
94part1(const puzzle_type& input)
95{
96 const auto in_range = [](point_type point) -> bool {
97 static const auto lower_limit = 200000000000000.0;
98 static const auto upper_limit = 400000000000000.0;
99
100 const auto [x, y] = point;
101
102 return x > lower_limit && x < upper_limit && y > lower_limit && y < upper_limit;
103 };
104
105 const auto in_future = [](line_type stone, point_type point) -> bool {
106 const auto sgn_stone = get_direction(stone);
107 const auto sgn_point = get_direction(stone, point);
108
109 return sgn_stone == sgn_point;
110 };
111
112 long sum = 0;
113 for ( size_t idx = 0; idx != input.size(); ++idx ) {
114 const auto& stone_a = input[idx];
115
116 for ( size_t idx2 = idx + 1; idx2 < input.size(); ++idx2 ) {
117 const auto& stone_b = input[idx2];
118
119 point_type cross_point;
120 if ( lint(stone_a, stone_b, cross_point) && in_range(cross_point) && in_future(stone_a, cross_point) && in_future(stone_b, cross_point) ) {
121 ++sum;
122 }
123 }
124 }
125 cout << sum << endl;
126}
127
128void
129part2(const puzzle_type& input)
130{
131 auto config = z3::config();
132 auto context = z3::context(config);
133 auto solver = z3::solver(context);
134
135 const auto px = context.int_const("px");
136 const auto py = context.int_const("py");
137 const auto pz = context.int_const("pz");
138 const auto vx = context.int_const("vx");
139 const auto vy = context.int_const("vy");
140 const auto vz = context.int_const("vz");
141
142 for ( size_t i = 0; i != input.size(); ++i ) {
143 const auto& stone = input[i];
144
145 const auto pxn = context.int_val(int64_t(get<0>(stone)));
146 const auto pyn = context.int_val(int64_t(get<1>(stone)));
147 const auto pzn = context.int_val(int64_t(get<2>(stone)));
148 const auto vxn = context.int_val(int64_t(get<3>(stone)));
149 const auto vyn = context.int_val(int64_t(get<4>(stone)));
150 const auto vzn = context.int_val(int64_t(get<5>(stone)));
151 const auto tn = context.int_const(to_string(i+1).c_str());
152
153 solver.add(tn >= 0);
154 solver.add(pxn + vxn * tn == px + vx * tn);
155 solver.add(pyn + vyn * tn == py + vy * tn);
156 solver.add(pzn + vzn * tn == pz + vz * tn);
157 }
158
159 solver.check();
160
161 auto model = solver.get_model();
162
163 cout << model.eval(px).as_int64() + model.eval(py).as_int64() + model.eval(pz).as_int64() << endl;
164}
165
166int
167main()
168{
169 const auto input = read_file("data/day24.txt");
170
171 part1(input);
172 part2(input);
173}
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}