aboutsummaryrefslogtreecommitdiff
path: root/src/day14.cpp
diff options
context:
space:
mode:
authorThomas Schmucker <ts@its1.de>2024-01-03 23:35:54 +0100
committerThomas Schmucker <ts@its1.de>2024-01-03 23:35:54 +0100
commit56e890cec0a28c0a485212ccebfaf774235a79a2 (patch)
treed9c6241a1aa247e06ab5ba2f6f11967b77d458ec /src/day14.cpp
parente9a1cb0441d137d7a26cb303b7e72d3424b7392d (diff)
downloadadvent-of-code-56e890cec0a28c0a485212ccebfaf774235a79a2.tar.gz
advent-of-code-56e890cec0a28c0a485212ccebfaf774235a79a2.tar.bz2
advent-of-code-56e890cec0a28c0a485212ccebfaf774235a79a2.zip
prepare for more puzzles ... :)
Diffstat (limited to 'src/day14.cpp')
-rw-r--r--src/day14.cpp239
1 files changed, 0 insertions, 239 deletions
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}