aboutsummaryrefslogtreecommitdiff
path: root/src/day21.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/day21.cpp')
-rw-r--r--src/day21.cpp148
1 files changed, 0 insertions, 148 deletions
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}