aboutsummaryrefslogtreecommitdiff
path: root/2018
diff options
context:
space:
mode:
Diffstat (limited to '2018')
-rw-r--r--2018/data/.gitkeep0
-rw-r--r--2018/src/day01.cpp58
-rw-r--r--2018/src/day02.cpp87
-rw-r--r--2018/src/day03.cpp95
-rw-r--r--2018/src/day04.cpp135
-rw-r--r--2018/src/day05.cpp101
-rw-r--r--2018/src/day06.cpp152
-rw-r--r--2018/src/day07.cpp194
-rw-r--r--2018/src/day08.cpp88
-rw-r--r--2018/src/day09.cpp113
-rw-r--r--2018/src/day10.cpp137
-rw-r--r--2018/src/day11.cpp143
12 files changed, 1303 insertions, 0 deletions
diff --git a/2018/data/.gitkeep b/2018/data/.gitkeep
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/2018/data/.gitkeep
diff --git a/2018/src/day01.cpp b/2018/src/day01.cpp
new file mode 100644
index 0000000..d57a187
--- /dev/null
+++ b/2018/src/day01.cpp
@@ -0,0 +1,58 @@
1#include <filesystem>
2#include <fstream>
3#include <iostream>
4#include <numeric>
5#include <unordered_set>
6#include <vector>
7
8using namespace std;
9
10namespace {
11
12vector<long>
13read_file(const filesystem::path& filename)
14{
15 ifstream file{ filename };
16 vector<long> values;
17
18 for ( long value = 0; file >> value; ) {
19 values.emplace_back(value);
20 }
21
22 return values;
23}
24
25void
26part1(const vector<long>& values)
27{
28 auto sum = accumulate(values.begin(), values.end(), 0L);
29 cout << "Part1: " << sum << '\n';
30}
31
32void
33part2(const vector<long>& values)
34{
35 unordered_set<long> seen;
36
37 long sum = 0;
38 for ( size_t idx = 0;; ++idx ) {
39 sum += values.at(idx % values.size());
40
41 if ( seen.contains(sum) ) {
42 cout << "Part2: " << sum << '\n';
43 return;
44 }
45
46 seen.emplace(sum);
47 }
48}
49
50} // namespace
51
52int
53main()
54{
55 auto values = read_file("data/day01.txt");
56 part1(values);
57 part2(values);
58}
diff --git a/2018/src/day02.cpp b/2018/src/day02.cpp
new file mode 100644
index 0000000..5dc6c7f
--- /dev/null
+++ b/2018/src/day02.cpp
@@ -0,0 +1,87 @@
1#include <filesystem>
2#include <fstream>
3#include <iostream>
4#include <map>
5#include <set>
6#include <string>
7#include <vector>
8
9using namespace std;
10
11namespace {
12
13vector<string>
14read_lines(const filesystem::path& filename)
15{
16 ifstream file{ filename };
17 vector<string> lines;
18
19 for ( string line; getline(file, line); ) {
20 lines.emplace_back(line);
21 }
22
23 return lines;
24}
25
26void
27part1(const vector<string>& lines)
28{
29 int twos = 0;
30 int threes = 0;
31 for ( const auto& line: lines ) {
32 map<char, int> foo;
33 for ( const auto chr: line ) {
34 foo[chr]++;
35 }
36
37 set<int> counts;
38 for ( const auto& [chr, count]: foo ) {
39 counts.insert(count);
40 }
41
42 if ( counts.contains(2) ) {
43 ++twos;
44 }
45 if ( counts.contains(3) ) {
46 ++threes;
47 }
48 }
49 cout << "Part 1: " << twos * threes << '\n';
50}
51
52void
53part2(const vector<string>& lines)
54{
55 for ( size_t i = 0; i != lines.size(); ++i ) {
56 for ( size_t j = i + 1; j != lines.size(); ++j ) {
57 const auto& lhs = lines.at(i);
58 const auto& rhs = lines.at(j);
59
60 if ( lhs.length() != rhs.length() ) {
61 throw runtime_error("invalid data");
62 }
63
64 string result;
65 for ( size_t k = 0; k != lhs.length(); ++k ) {
66 if ( lhs[k] == rhs[k] ) {
67 result += lhs[k];
68 }
69 }
70
71 if ( result.length() + 1 == lhs.length() ) {
72 cout << "Part 2: " << result << '\n';
73 return;
74 }
75 }
76 }
77}
78
79} // namespace
80
81int
82main()
83{
84 auto lines = read_lines("data/day02.txt");
85 part1(lines);
86 part2(lines);
87}
diff --git a/2018/src/day03.cpp b/2018/src/day03.cpp
new file mode 100644
index 0000000..bed3acb
--- /dev/null
+++ b/2018/src/day03.cpp
@@ -0,0 +1,95 @@
1#include <filesystem>
2#include <fstream>
3#include <iostream>
4#include <map>
5#include <regex>
6#include <set>
7#include <tuple>
8#include <vector>
9
10using namespace std;
11
12namespace {
13
14struct Claim {
15 int id;
16 int left;
17 int top;
18 int width;
19 int height;
20};
21
22#if 0
23ostream&
24operator<<(ostream& ostrm, const Claim& claim)
25{
26 ostrm << "id: " << claim.id
27 << " (" << claim.left << ", " << claim.top << ": " << claim.width << "x" << claim.height;
28 return ostrm;
29}
30#endif
31
32vector<Claim>
33read_file(const filesystem::path& filename)
34{
35 ifstream file{ filename };
36 vector<Claim> claims;
37
38 regex pattern(R"#((\d+) @ (\d+),(\d+): (\d+)x(\d+))#");
39 smatch match;
40
41 for ( string line; getline(file, line); ) {
42 if ( !regex_search(line, match, pattern) ) {
43 continue;
44 }
45
46 Claim claim{};
47 claim.id = stoi(match[1]);
48 claim.left = stoi(match[2]);
49 claim.top = stoi(match[3]);
50 claim.width = stoi(match[4]);
51 claim.height = stoi(match[5]);
52
53 claims.emplace_back(claim);
54 }
55
56 return claims;
57}
58
59void
60solve(const vector<Claim>& claims)
61{
62 map<tuple<int, int>, vector<int>> fabric;
63 set<int> allIds;
64
65 for ( const auto& claim: claims ) {
66 for ( int x = claim.left; x < claim.left + claim.width; ++x ) {
67 for ( int y = claim.top; y < claim.top + claim.height; ++y ) {
68 fabric[{ x, y }].emplace_back(claim.id);
69 }
70 }
71 allIds.emplace(claim.id);
72 }
73
74 int overlapCount = 0;
75 for ( const auto& [pos, ids]: fabric ) {
76 if ( ids.size() > 1 ) {
77 ++overlapCount;
78 for ( const auto& id: ids ) {
79 allIds.erase(id);
80 }
81 }
82 }
83
84 cout << "Part 1: " << overlapCount << '\n';
85 cout << "Part 2: " << *allIds.begin() << '\n';
86}
87
88} // namespace
89
90int
91main()
92{
93 auto claims = read_file("data/day03.txt");
94 solve(claims);
95}
diff --git a/2018/src/day04.cpp b/2018/src/day04.cpp
new file mode 100644
index 0000000..ea3c69f
--- /dev/null
+++ b/2018/src/day04.cpp
@@ -0,0 +1,135 @@
1#include <algorithm>
2#include <filesystem>
3#include <fstream>
4#include <iostream>
5#include <map>
6#include <string>
7#include <vector>
8
9using namespace std;
10
11namespace {
12
13struct Record {
14 int guard_id;
15 long start_sleep;
16 long stop_sleep;
17};
18
19long
20to_timestamp(const string& line)
21{
22 long year = stol(line.substr(1, 4));
23 long mon = stol(line.substr(6, 2));
24 long day = stol(line.substr(9, 2));
25 long hour = stol(line.substr(12, 2));
26 long min = stol(line.substr(15, 2));
27
28 auto timestamp = (year * 100'000'000) + (mon * 1'000'000) + (day * 10'000) + (hour * 100) + min; // NOLINT
29
30 return timestamp;
31}
32
33vector<Record>
34read_file(const filesystem::path& filename)
35{
36 ifstream file{ filename };
37 vector<string> lines;
38
39 for ( string line; getline(file, line); ) {
40 lines.emplace_back(line);
41 }
42
43 ranges::sort(lines);
44
45 vector<Record> records;
46
47 int guard = -1;
48 long start_sleep = -1;
49 long stop_sleep = -1;
50 for ( const auto& line: lines ) {
51 if ( line.find(" Guard #") != string::npos ) {
52 guard = stoi(line.substr(26));
53 }
54 else if ( line.find(" falls asleep") != string::npos ) {
55 start_sleep = to_timestamp(line);
56 }
57 else if ( line.find(" wakes up") != string::npos ) {
58 stop_sleep = to_timestamp(line);
59 records.emplace_back(guard, start_sleep, stop_sleep);
60 }
61 }
62
63 return records;
64}
65
66void
67part1(const vector<Record>& records)
68{
69 map<int, long> sleep_amounts;
70
71 for ( const auto& record: records ) {
72 sleep_amounts[record.guard_id] += record.stop_sleep - record.start_sleep;
73 }
74
75 auto max_amount = ranges::max_element(sleep_amounts,
76 [](const auto& lhs, const auto& rhs) {
77 return lhs.second < rhs.second;
78 });
79
80 map<long, unsigned> sleep_counts;
81
82 for ( const auto& record: records ) {
83 if ( record.guard_id != max_amount->first ) {
84 continue;
85 }
86
87 for ( auto timestamp = record.start_sleep; timestamp != record.stop_sleep; ++timestamp ) {
88 sleep_counts[timestamp % 10'000]++;
89 }
90 }
91
92 auto max_count = ranges::max_element(sleep_counts,
93 [](const auto& lhs, const auto& rhs) {
94 return lhs.second < rhs.second;
95 });
96
97 cout << "Part 1: " << max_amount->first * (max_count->first % 100) << '\n';
98}
99
100void
101part2(const vector<Record>& records)
102{
103 map<int, map<long, unsigned>> sleep_counts;
104
105 for ( const auto& record: records ) {
106 for ( auto timestamp = record.start_sleep; timestamp != record.stop_sleep; ++timestamp ) {
107 sleep_counts[record.guard_id][timestamp % 10'000]++;
108 }
109 }
110
111 int found_guard = -1;
112 long found_min = -1;
113 unsigned max_count = 0;
114 for ( const auto& [id, times]: sleep_counts ) {
115 for ( const auto& [min, count]: times ) {
116 if ( count > max_count ) {
117 max_count = count;
118 found_guard = id;
119 found_min = min % 100;
120 }
121 }
122 }
123
124 cout << "Part 2: " << found_guard * found_min << '\n';
125}
126
127} // namespace
128
129int
130main()
131{
132 auto records = read_file("data/day04.txt");
133 part1(records);
134 part2(records);
135}
diff --git a/2018/src/day05.cpp b/2018/src/day05.cpp
new file mode 100644
index 0000000..9de484d
--- /dev/null
+++ b/2018/src/day05.cpp
@@ -0,0 +1,101 @@
1#include <filesystem>
2#include <fstream>
3#include <iostream>
4#include <string>
5
6using namespace std;
7
8namespace {
9
10string
11read_line(const filesystem::path& filename)
12{
13 ifstream file{ filename };
14 string line;
15 getline(file, line);
16 return line;
17}
18
19bool
20xorEqual(char lhs, char rhs)
21{
22 return (lhs ^ (1 << 5)) == rhs;
23}
24
25#if 0
26void
27part1(string str)
28{
29 size_t idx = 1;
30 while ( idx < str.length() ) {
31 if ( xorEqual(str[idx - 1], str[idx]) ) {
32 str.erase(idx - 1, 2);
33 idx = 1;
34 }
35 else {
36 ++idx;
37 }
38 }
39
40 cout << "Part 1: " << str.length() << '\n';
41}
42#endif
43
44void
45part1_opti(string_view str)
46{
47 string result;
48
49 for ( const auto chr: str ) {
50 if ( !result.empty() && xorEqual(result.back(), chr) ) {
51 result.pop_back();
52 }
53 else {
54 result.push_back(chr);
55 }
56 }
57
58 cout << "Part 1: " << result.length() << '\n';
59}
60
61void
62part2(string_view str)
63{
64 size_t min_length = str.size();
65 for ( auto ch = 'a'; ch != 'z'; ++ch ) {
66 string result;
67
68 for ( const auto chr: str ) {
69 if ( tolower(chr) == ch ) {
70 // nichts
71 }
72 else if ( !result.empty() && xorEqual(result.back(), chr) ) {
73 result.pop_back();
74 }
75 else {
76 result.push_back(chr);
77 }
78 }
79 min_length = min(min_length, result.length());
80 }
81
82 cout << "Part 2: " << min_length << '\n';
83}
84
85} // namespace
86
87int
88main()
89{
90 auto line = read_line("data/day05.txt");
91 // part1(line);
92 part1_opti(line);
93 part2(line);
94 /*
95 cout << reduce("aA") << '\n';
96 cout << reduce("abBA") << '\n';
97 cout << reduce("abAB") << '\n';
98 cout << reduce("aabAAB") << '\n';
99 cout << reduce("dabAcCaCBAcCcaDA") << '\n';
100 */
101}
diff --git a/2018/src/day06.cpp b/2018/src/day06.cpp
new file mode 100644
index 0000000..8701cbe
--- /dev/null
+++ b/2018/src/day06.cpp
@@ -0,0 +1,152 @@
1#include <filesystem>
2#include <fstream>
3#include <iostream>
4#include <map>
5#include <set>
6#include <tuple>
7
8using namespace std;
9
10namespace {
11
12using Point = tuple<int, int>;
13
14set<Point>
15read_file(const filesystem::path& filename)
16{
17 ifstream file{ filename };
18 set<Point> points;
19
20 int x{};
21 int y{};
22 char sep{};
23
24 while ( file >> x >> sep >> y ) {
25 points.insert({ x, y });
26 }
27
28 return points;
29}
30
31void
32getBoundingBox(const set<Point>& points, Point& topLeft, Point& bottomRight)
33{
34 auto minX = numeric_limits<int>::max();
35 auto minY = numeric_limits<int>::max();
36 auto maxX = numeric_limits<int>::min();
37 auto maxY = numeric_limits<int>::min();
38
39 for ( const auto [x, y]: points ) {
40 minX = min(minX, x);
41 minY = min(minY, y);
42 maxX = max(maxX, x);
43 maxY = max(maxY, y);
44 }
45
46 topLeft = { minX, minY };
47 bottomRight = { maxX, maxY };
48}
49
50int
51manhattanDistance(const Point& lhs, const Point& rhs)
52{
53 int distance = abs(get<0>(lhs) - get<0>(rhs)) + abs(get<1>(lhs) - get<1>(rhs));
54
55 return distance;
56}
57
58void
59part1(const set<Point>& points)
60{
61 Point topLeft{};
62 Point bottomRight{};
63 getBoundingBox(points, topLeft, bottomRight);
64
65 const auto [minX, minY] = topLeft;
66 const auto [maxX, maxY] = bottomRight;
67
68 map<Point, int> areaCount;
69 set<Point> infinite;
70
71 static const int offset = 1;
72
73 for ( auto posX = minX - offset; posX <= maxX + offset; ++posX ) {
74 for ( auto posY = minY - offset; posY <= maxY + offset; ++posY ) {
75 int bestDistance = numeric_limits<int>::max();
76 Point bestPoint{};
77 bool tie = false;
78
79 for ( const auto& point: points ) {
80 int distance = manhattanDistance(point, { posX, posY });
81 if ( distance < bestDistance ) {
82 bestDistance = distance;
83 bestPoint = point;
84 tie = false;
85 }
86 else if ( distance == bestDistance ) {
87 tie = true;
88 }
89 }
90
91 if ( !tie ) {
92 areaCount[bestPoint]++;
93
94 if ( posX < minX || posX > maxX || posY < minY || posY > maxY ) {
95 infinite.insert(bestPoint);
96 }
97 }
98 }
99 }
100
101 int maxSize = 0;
102 for ( const auto& [point, size]: areaCount ) {
103 if ( infinite.contains(point) ) {
104 continue;
105 }
106 maxSize = max(maxSize, size);
107 }
108
109 cout << "Part 1: " << maxSize << '\n';
110}
111
112void
113part2(const set<Point>& points, const int threshold)
114{
115 Point topLeft{};
116 Point bottomRight{};
117 getBoundingBox(points, topLeft, bottomRight);
118
119 const auto [minX, minY] = topLeft;
120 const auto [maxX, maxY] = bottomRight;
121
122 static const int offset = 100;
123
124 unsigned int regionSize = 0;
125
126 for ( auto posX = minX - offset; posX <= maxX + offset; ++posX ) {
127 for ( auto posY = minY - offset; posY <= maxY + offset; ++posY ) {
128 int sum = 0;
129
130 for ( const auto& point: points ) {
131 int distance = manhattanDistance(point, { posX, posY });
132 sum += distance;
133 }
134
135 if ( sum < threshold ) {
136 ++regionSize;
137 }
138 }
139 }
140
141 cout << "Part 2: " << regionSize << '\n';
142}
143
144} // namespace
145
146int
147main()
148{
149 auto points = read_file("data/day06.txt");
150 part1(points);
151 part2(points, 10000);
152}
diff --git a/2018/src/day07.cpp b/2018/src/day07.cpp
new file mode 100644
index 0000000..e6147d6
--- /dev/null
+++ b/2018/src/day07.cpp
@@ -0,0 +1,194 @@
1#include <filesystem>
2#include <fstream>
3#include <iostream>
4#include <map>
5#include <set>
6#include <sstream>
7#include <string>
8#include <vector>
9
10using namespace std;
11
12namespace {
13
14vector<string>
15split(const string& line)
16{
17 stringstream strm{ line };
18 vector<string> words;
19
20 for ( string word; getline(strm, word, ' '); ) {
21 words.emplace_back(word);
22 }
23
24 return words;
25}
26
27map<string, set<string>>
28read_file(const filesystem::path& filename)
29{
30 ifstream file{ filename };
31 map<string, set<string>> graph;
32
33 for ( string line; getline(file, line); ) {
34 auto words = split(line);
35 graph[words.at(1)].emplace(words.at(7));
36 }
37
38 return graph;
39}
40
41vector<string>
42topologicalSort(const map<string, set<string>>& graph)
43{
44 map<string, int> indegree;
45
46 // Eingangsgrade initialisieren
47 for ( const auto& [node, neighbors]: graph ) {
48 if ( !indegree.contains(node) ) {
49 indegree[node] = 0;
50 }
51 for ( const auto& neighbor: neighbors ) {
52 indegree[neighbor]++;
53 }
54 }
55
56 // Queue mit Knoten, deren Eingangsgrad 0 ist
57 priority_queue<string, vector<string>, greater<>> queue;
58 for ( const auto& [node, deg]: indegree ) {
59 if ( deg == 0 ) {
60 queue.push(node);
61 }
62 }
63
64 vector<string> sorted;
65
66 // Kahn's Algorithmus
67 while ( !queue.empty() ) {
68 string node = queue.top();
69 queue.pop();
70
71 sorted.push_back(node);
72
73 if ( !graph.contains(node) ) {
74 continue;
75 }
76
77 for ( const auto& neighbor: graph.at(node) ) {
78 indegree[neighbor]--;
79 if ( indegree[neighbor] == 0 ) {
80 queue.push(neighbor);
81 }
82 }
83 }
84
85 // Prüfen auf Zyklus
86 if ( sorted.size() != indegree.size() ) {
87 throw runtime_error("Zyklus im Graph gefunden! Keine topologische Sortierung möglich.");
88 }
89
90 return sorted;
91}
92
93void
94part1(const map<string, set<string>>& graph)
95{
96 auto sorted = topologicalSort(graph);
97
98 cout << "Part 1: ";
99 ranges::copy(sorted, ostream_iterator<string>(cout));
100 cout << '\n';
101}
102
103void
104part2(const map<string, set<string>>& graph, const int workers, const int base)
105{
106 map<string, int> indegree;
107
108 // Eingangsgrade initialisieren
109 for ( const auto& [node, neighbors]: graph ) {
110 if ( !indegree.contains(node) ) {
111 indegree[node] = 0;
112 }
113 for ( const auto& neighbor: neighbors ) {
114 indegree[neighbor]++;
115 }
116 }
117
118 set<string> available;
119 for ( const auto& [node, deg]: indegree ) {
120 if ( deg == 0 ) {
121 available.insert(node);
122 }
123 }
124
125 set<pair<int, string>> finishing;
126
127 int active_workers = 0;
128 int time = 0;
129
130 while ( !indegree.empty() ) {
131 while ( !finishing.empty() && finishing.begin()->first == time ) {
132 auto [finish_time, node] = *finishing.begin();
133 finishing.erase(finishing.begin());
134
135 active_workers--;
136
137 indegree.erase(node);
138
139 if ( !graph.contains(node) ) {
140 continue;
141 }
142
143 for ( const auto& neighbor: graph.at(node) ) {
144 indegree[neighbor]--;
145 if ( indegree[neighbor] == 0 ) {
146 available.insert(neighbor);
147 }
148 }
149 }
150
151 while ( active_workers < workers && !available.empty() ) {
152 auto node = *available.begin();
153 available.erase(available.begin());
154
155 int duration = base + (node.at(0) - 'A' + 1);
156 int finish_time = time + duration;
157
158 finishing.emplace(finish_time, node);
159 active_workers++;
160 }
161
162 if ( finishing.empty() ) {
163 if ( available.empty() ) {
164 break;
165 }
166 else {
167 time++;
168 }
169 }
170 else {
171 time = finishing.begin()->first;
172 }
173 }
174
175 cout << "Part 2: " << time << '\n';
176}
177
178} // namespace
179
180int
181main()
182{
183 auto graph = read_file("data/day07.txt");
184 try {
185 part1(graph);
186
187 static const int WORKERS = 5;
188 static const int BASE = 60;
189 part2(graph, WORKERS, BASE);
190 }
191 catch ( exception& e ) {
192 cerr << "Fehler: " << e.what() << '\n';
193 }
194}
diff --git a/2018/src/day08.cpp b/2018/src/day08.cpp
new file mode 100644
index 0000000..9c2a093
--- /dev/null
+++ b/2018/src/day08.cpp
@@ -0,0 +1,88 @@
1#include <filesystem>
2#include <fstream>
3#include <iostream>
4#include <vector>
5
6using namespace std;
7
8namespace {
9
10vector<int>
11read_file(const filesystem::path& filename)
12{
13 ifstream file{ filename };
14 vector<int> data;
15
16 for ( int number{}; file >> number; ) {
17 data.emplace_back(number);
18 }
19
20 return data;
21}
22
23void
24part1(const vector<int>& data)
25{
26 size_t idx = 0;
27 int sum = 0;
28
29 function<void()> func = [&] {
30 auto count_child = data.at(idx++);
31 auto count_meta = data.at(idx++);
32
33 while ( count_child-- > 0 ) {
34 func();
35 }
36
37 while ( count_meta-- > 0 ) {
38 sum += data.at(idx++);
39 }
40 };
41
42 func();
43
44 cout << "Part 1: " << sum << '\n';
45}
46
47void
48part2(const vector<int>& data)
49{
50 size_t idx = 0;
51
52 function<int()> func = [&] {
53 const auto count_child = data.at(idx++);
54 const auto count_meta = data.at(idx++);
55
56 vector<int> child_values;
57 for ( int i = 0; i != count_child; ++i ) {
58 child_values.emplace_back(func());
59 }
60
61 int value = 0;
62 for ( int i = 0; i != count_meta; ++i ) {
63 auto meta = data.at(idx++);
64 if ( count_child == 0 ) {
65 value += meta;
66 }
67 else {
68 meta--;
69 if ( meta >= 0 && meta < count_child ) {
70 value += child_values[static_cast<size_t>(meta)];
71 }
72 }
73 }
74 return value;
75 };
76
77 cout << "Part 2: " << func() << '\n';
78}
79
80} // namespace
81
82int
83main()
84{
85 auto data = read_file("data/day08.txt");
86 part1(data);
87 part2(data);
88}
diff --git a/2018/src/day09.cpp b/2018/src/day09.cpp
new file mode 100644
index 0000000..d1b4eb0
--- /dev/null
+++ b/2018/src/day09.cpp
@@ -0,0 +1,113 @@
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6namespace {
7
8struct Marble {
9 explicit Marble(long score)
10 : score{ score }
11 {
12 }
13
14 Marble(long score, Marble* prev, Marble* next)
15 : score{ score }
16 , prev{ prev }
17 , next{ next }
18 {
19 }
20
21 [[nodiscard]]
22 Marble* insert_after_two(long value) const
23 {
24 auto* insert_after = this->next;
25
26 auto* new_marble = new Marble(value, insert_after, insert_after->next); // NOLINT
27
28 insert_after->next->prev = new_marble;
29 insert_after->next = new_marble;
30
31 return new_marble;
32 }
33
34 [[nodiscard]]
35 pair<Marble*, long> remove_seventh_back()
36 {
37 auto* to_remove = this;
38 for ( int i = 0; i != 7; ++i ) {
39 to_remove = to_remove->prev;
40 }
41
42 to_remove->prev->next = to_remove->next;
43 to_remove->next->prev = to_remove->prev;
44
45 auto* new_current = to_remove->next;
46 auto score = to_remove->score;
47
48 delete to_remove; // NOLINT
49
50 return { new_current, score };
51 }
52
53 long score;
54 Marble* prev{ this };
55 Marble* next{ this };
56};
57
58long
59solve(const size_t players, const long last_marble)
60{
61 auto current = new Marble(0); // NOLINT
62
63 vector<long> scores(players, 0);
64 size_t player = 0;
65
66 for ( long marble = 1; marble <= last_marble; ++marble ) {
67 if ( marble % 23 != 0 ) {
68 current = current->insert_after_two(marble);
69 }
70 else {
71 auto [new_current, removed_score] = current->remove_seventh_back();
72
73 scores[player] += marble + removed_score;
74 current = new_current;
75 }
76
77 player += 1;
78 player %= players;
79 }
80
81 Marble* start = current;
82 do {
83 Marble* next = start->next;
84 delete start; // NOLINT
85 start = next;
86 } while ( start != current );
87
88 return ranges::max(scores);
89}
90
91void
92part1(const size_t players, const long last_marble)
93{
94 cout << "Part 1: " << solve(players, last_marble) << '\n';
95}
96
97void
98part2(const size_t players, const long last_marble)
99{
100 cout << "Part 2: " << solve(players, last_marble * 100) << '\n';
101}
102
103} // namespace
104
105int
106main()
107{
108 static const size_t players = 400;
109 static const long points = 71864;
110
111 part1(players, points);
112 part2(players, points);
113}
diff --git a/2018/src/day10.cpp b/2018/src/day10.cpp
new file mode 100644
index 0000000..43de95c
--- /dev/null
+++ b/2018/src/day10.cpp
@@ -0,0 +1,137 @@
1#include <filesystem>
2#include <fstream>
3#include <iostream>
4#include <regex>
5#include <set>
6#include <tuple>
7#include <vector>
8
9using namespace std;
10
11namespace {
12
13struct Point {
14 long x;
15 long y;
16 long vx;
17 long vy;
18};
19
20vector<Point>
21read_file(const filesystem::path& filename)
22{
23 ifstream file{ filename };
24
25 static const regex pattern{ R"(position=<\s*(-?\d+)\s*,\s*(-?\d+)\s*>\s*velocity=<\s*(-?\d+)\s*,\s*(-?\d+)\s*>)" };
26
27 vector<Point> data;
28 for ( string line; getline(file, line); ) {
29 smatch match;
30 if ( regex_match(line, match, pattern) ) {
31 auto x = stol(match[1]);
32 auto y = stol(match[2]);
33 auto vx = stol(match[3]);
34 auto vy = stol(match[4]);
35
36 data.emplace_back(x, y, vx, vy);
37 }
38 }
39
40 return data;
41}
42
43void
44get_bounding_box(const vector<Point>& points, long& min_x, long& min_y, long& max_x, long& max_y)
45{
46 min_x = numeric_limits<long>::max();
47 min_y = numeric_limits<long>::max();
48 max_x = numeric_limits<long>::min();
49 max_y = numeric_limits<long>::min();
50
51 for ( const auto& point: points ) {
52 min_x = min(min_x, point.x);
53 min_y = min(min_y, point.y);
54 max_x = max(max_x, point.x);
55 max_y = max(max_y, point.y);
56 }
57}
58
59long
60bounding_area(const vector<Point>& points)
61{
62 long min_x = 0;
63 long min_y = 0;
64 long max_x = 0;
65 long max_y = 0;
66 get_bounding_box(points, min_x, min_y, max_x, max_y);
67 return 1L * (max_x - min_x + 1) * (max_y - min_y + 1);
68}
69
70void
71update(vector<Point>& points)
72{
73 for ( auto& point: points ) {
74 point.x += point.vx;
75 point.y += point.vy;
76 }
77}
78
79tuple<int, vector<Point>>
80get_best(vector<Point> points)
81{
82 auto best_area = numeric_limits<long>::max();
83
84 vector<Point> best;
85 int best_t = 0;
86
87 for ( int i = 0; i != 100'000; ++i ) {
88 update(points);
89
90 auto area = bounding_area(points);
91 if ( area < best_area ) {
92 best_area = area;
93 best = points;
94 best_t = i + 1;
95 }
96 }
97 return { best_t, best };
98}
99
100void
101print(const vector<Point>& points)
102{
103 set<tuple<long, long>> grid;
104 for ( const auto [x, y, vx, vy]: points ) {
105 grid.emplace(x, y);
106 }
107
108 long min_x = 0;
109 long min_y = 0;
110 long max_x = 0;
111 long max_y = 0;
112 get_bounding_box(points, min_x, min_y, max_x, max_y);
113
114 for ( long y = min_y; y <= max_y; ++y ) {
115 for ( long x = min_x; x <= max_x; ++x ) {
116 cout << (grid.contains({ x, y }) ? '#' : ' ');
117 }
118 cout << '\n';
119 }
120}
121
122void
123solve(const vector<Point>& points)
124{
125 auto [time, best_points] = get_best(points);
126 print(best_points);
127 cout << "Part 2: " << time << '\n';
128}
129
130} // namespace
131
132int
133main()
134{
135 auto data = read_file("data/day10.txt");
136 solve(data);
137}
diff --git a/2018/src/day11.cpp b/2018/src/day11.cpp
new file mode 100644
index 0000000..1f8f9e2
--- /dev/null
+++ b/2018/src/day11.cpp
@@ -0,0 +1,143 @@
1#include <iostream>
2#include <map>
3
4using namespace std;
5
6namespace {
7
8const int WIDTH = 300;
9const int HEIGHT = 300;
10
11using Grid = map<tuple<int, int>, int>;
12
13int
14power_level(int x, int y, int serial)
15{
16 auto rack_id = x + 10;
17 auto level = rack_id * y;
18 level += serial;
19 level *= rack_id;
20 level /= 100;
21 level %= 10;
22 level -= 5;
23 return level;
24}
25
26Grid
27build_grid(int serial)
28{
29 Grid grid;
30 for ( int x = 1; x <= WIDTH; ++x ) {
31 for ( int y = 1; y <= HEIGHT; ++y ) {
32 grid[{ x, y }] = power_level(x, y, serial);
33 }
34 }
35 return grid;
36}
37
38int
39sum3x3(const Grid& grid, int x, int y)
40{
41 auto sum = 0;
42 for ( int dx = 0; dx != 3; ++dx ) {
43 for ( int dy = 0; dy != 3; ++dy ) {
44 sum += grid.at({ x + dx, y + dy });
45 }
46 }
47 return sum;
48}
49
50void
51part1(const int serial)
52{
53 auto grid = build_grid(serial);
54
55 auto best_sum = numeric_limits<int>::min();
56 auto best_x = 0;
57 auto best_y = 0;
58
59 for ( int x = 1; x <= WIDTH - 2; ++x ) {
60 for ( int y = 1; y <= HEIGHT - 2; ++y ) {
61 if ( auto sum = sum3x3(grid, x, y); sum > best_sum ) {
62 best_sum = sum;
63 best_x = x;
64 best_y = y;
65 }
66 }
67 }
68
69 cout << "Part 1: " << best_x << ',' << best_y << '\n';
70}
71
72Grid
73pre_process(const Grid& grid)
74{
75 Grid sat;
76
77 for ( int y = 1; y <= HEIGHT; ++y ) {
78 for ( int x = 1; x <= WIDTH; ++x ) {
79 const auto a = grid.at({ x, y });
80 const auto b = (x > 1) ? sat.at({ x - 1, y }) : 0;
81 const auto c = (y > 1) ? sat.at({ x, y - 1 }) : 0;
82 const auto d = (x > 1 && y > 1) ? sat.at({ x - 1, y - 1 }) : 0;
83
84 sat[{ x, y }] = a + b + c - d;
85 }
86 }
87
88 return sat;
89}
90
91int
92get_safe(const Grid& grid, int x, int y)
93{
94 return (x < 1 || y < 1) ? 0 : grid.at({ x, y });
95}
96
97int
98square_sum(const Grid& grid, int x, int y, int s)
99{
100 int x2 = x + s - 1;
101 int y2 = y + s - 1;
102
103 return get_safe(grid, x2, y2) - get_safe(grid, x - 1, y2) - get_safe(grid, x2, y - 1) + get_safe(grid, x - 1, y - 1);
104}
105
106void
107part2(const int serial)
108{
109 static const int MAX_SIZE = 100;
110
111 auto grid = pre_process(build_grid(serial));
112
113 auto best_sum = numeric_limits<int>::min();
114 auto best_x = 0;
115 auto best_y = 0;
116 auto best_s = 0;
117
118 for ( int s = 1; s <= MAX_SIZE; ++s ) {
119 for ( int x = 1; x <= WIDTH - s + 1; ++x ) {
120 for ( int y = 1; y <= HEIGHT - s + 1; ++y ) {
121 if ( auto sum = square_sum(grid, x, y, s); sum > best_sum ) {
122 best_sum = sum;
123 best_x = x;
124 best_y = y;
125 best_s = s;
126 }
127 }
128 }
129 }
130
131 cout << "Part 2: " << best_x << ',' << best_y << "," << best_s << '\n';
132}
133
134} // namespace
135
136int
137main()
138{
139 static const int SERIAL = 7989;
140
141 part1(SERIAL);
142 part2(SERIAL);
143}