1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
|
#include <array>
#include <filesystem>
#include <fstream>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <tuple>
using namespace std;
namespace {
using Pos = tuple<size_t, size_t>;
set<Pos>
read_file(const filesystem::path& filename)
{
ifstream file{ filename };
set<Pos> grid;
size_t row = 0;
for ( string line; getline(file, line); ) {
for ( size_t col = 0; col != line.length(); ++col ) {
if ( line[col] == '@' ) {
grid.emplace(col, row);
}
}
++row;
}
return grid;
}
array<Pos, 8>
get_neighbours(const Pos& pos)
{
auto [col, row] = pos;
return {
Pos{ col - 1, row },
Pos{ col - 1, row - 1 },
Pos{ col, row - 1 },
Pos{ col + 1, row - 1 },
Pos{ col + 1, row },
Pos{ col + 1, row + 1 },
Pos{ col, row + 1 },
Pos{ col - 1, row + 1 },
};
}
size_t
get_nneighbours(const set<Pos>& grid, const Pos& pos)
{
return (size_t) ranges::count_if(get_neighbours(pos), [&](const auto& neighbour) { return grid.contains(neighbour); });
}
bool
is_accessable(const set<Pos>& grid, const Pos& pos)
{
return get_nneighbours(grid, pos) < 4;
}
void
part1(const set<Pos>& grid)
{
auto count = ranges::count_if(grid, [&](const auto& pos) { return is_accessable(grid, pos); });
cout << "Part 1: " << count << '\n';
}
void
part2(set<Pos> grid)
{
const auto old_size = grid.size();
while ( true ) {
vector<Pos> remove;
for ( const auto& pos: grid ) {
if ( is_accessable(grid, pos) ) {
remove.emplace_back(pos);
}
}
if ( remove.empty() ) {
break;
}
for ( const auto& pos: remove ) {
grid.erase(pos);
}
}
cout << "Part 2: " << old_size - grid.size() << '\n';
}
void
part2_bfs(set<Pos> grid)
{
const auto old_size = grid.size();
map<Pos, size_t> counts;
for ( const auto& pos: grid ) {
counts[pos] = get_nneighbours(grid, pos);
}
queue<Pos> queue;
for ( const auto& [pos, count]: counts ) {
if ( count < 4 ) {
queue.emplace(pos);
}
}
while ( !queue.empty() ) {
const auto pos = queue.front();
queue.pop();
if ( !grid.contains(pos) ) {
continue;
}
grid.erase(pos);
for ( const auto& neighbour: get_neighbours(pos) ) {
if ( !grid.contains(neighbour) ) {
continue;
}
if ( --counts[neighbour] == 3 ) {
queue.emplace(neighbour);
}
}
}
cout << "Part 2: " << old_size - grid.size() << '\n';
}
} // namespace
int
main()
{
auto grid = read_file("data/day04.txt");
part1(grid);
part2(grid);
part2_bfs(grid);
}
|
