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
|
#include <filesystem>
#include <fstream>
#include <iostream>
#include <map>
#include <string>
#include <unordered_set>
using namespace std;
namespace {
using Plants = unordered_set<long>;
using Rules = map<string, char>;
using Puzzle = tuple<Plants, Rules>;
Puzzle
read_file(const filesystem::path& filename)
{
fstream file{ filename };
string line;
getline(file, line);
line.erase(0, line.find(": ") + 2);
Plants plants;
for ( size_t idx = 0; idx != line.length(); ++idx ) {
if ( line.at(idx) == '#' ) {
plants.insert(static_cast<long>(idx));
}
}
getline(file, line);
Rules rules;
while ( getline(file, line) ) {
auto lhs = line.substr(0, 5);
auto rhs = line.substr(9);
rules[lhs] = rhs.at(0);
}
return { plants, rules };
}
Plants
update(const Plants& current, const Rules& rules)
{
auto [min, max] = ranges::minmax(current);
Plants next;
for ( auto i = min - 2; i <= max + 2; ++i ) {
string pattern;
pattern += current.contains(i - 2) ? '#' : '.';
pattern += current.contains(i - 1) ? '#' : '.';
pattern += current.contains(i) ? '#' : '.';
pattern += current.contains(i + 1) ? '#' : '.';
pattern += current.contains(i + 2) ? '#' : '.';
if ( rules.contains(pattern) && rules.at(pattern) == '#' ) {
next.insert(i);
}
}
return next;
}
void
part1(const Puzzle& puzzle)
{
auto [state, rules] = puzzle;
for ( int i = 0; i != 20; ++i ) {
state = update(state, rules);
}
long sum = 0;
for ( const auto pos: state ) {
sum += pos;
}
cout << "Part 1: " << sum << '\n';
}
void
part2(const Puzzle& puzzle)
{
auto [state, rules] = puzzle;
auto to_string = [&] {
string result;
auto [min, max] = ranges::minmax(state);
for ( auto pos = min; pos <= max; ++pos ) {
result += (state.contains(pos) ? '#' : '.');
}
return result;
};
unordered_set<string> seen;
for ( long shift = 50000000000;; --shift ) {
auto pattern = to_string();
if ( seen.contains(pattern) ) {
long sum = 0;
for ( const auto pos: state ) {
sum += pos + shift;
}
cout << "Part 2: " << sum << '\n';
return;
}
seen.insert(pattern);
state = update(state, rules);
}
}
} // namespace
int
main()
{
auto puzzle = read_file("data/day12.txt");
part1(puzzle);
part2(puzzle);
}
|
