aboutsummaryrefslogtreecommitdiff
path: root/src/day12.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/day12.cpp')
-rw-r--r--src/day12.cpp182
1 files changed, 0 insertions, 182 deletions
diff --git a/src/day12.cpp b/src/day12.cpp
deleted file mode 100644
index 11bd80b..0000000
--- a/src/day12.cpp
+++ /dev/null
@@ -1,182 +0,0 @@
1#include <fstream>
2#include <iostream>
3#include <map>
4#include <sstream>
5#include <string>
6#include <vector>
7using namespace std;
8
9vector<string>
10read_file(string_view filename)
11{
12 fstream input{ filename };
13 vector<string> data;
14
15 for ( string line; getline(input, line); ) {
16 data.emplace_back(line);
17 }
18
19 return data;
20}
21
22vector<string>
23split(const string& line, char sep)
24{
25 vector<string> parts{};
26 stringstream input{ line };
27
28 for ( string part; getline(input, part, sep); ) {
29 parts.emplace_back(part);
30 }
31
32 return parts;
33}
34
35template<typename T = long>
36vector<T>
37read_ints(const string& line)
38{
39 vector<T> parts{};
40 stringstream input{ line };
41
42 for ( string part; getline(input, part, ','); ) {
43 parts.emplace_back(stol(part));
44 }
45
46 return parts;
47}
48
49vector<long>
50count_groups(string_view str)
51{
52 vector<long> groups;
53
54 size_t idx = 0U;
55 while ( idx != str.length() ) {
56 while ( idx != str.length() && str[idx] == '.' ) {
57 ++idx;
58 }
59 if ( idx != str.length() && str[idx] == '#' ) {
60 auto num = 0L;
61 while ( idx != str.length() && str[idx] == '#' ) {
62 ++num;
63 ++idx;
64 }
65 groups.emplace_back(num);
66 }
67 }
68
69 return groups;
70}
71
72long
73brute_force(string_view springs, const vector<long>& groups)
74{
75 long counts = count_if(springs.begin(), springs.end(), [](char chr) { return chr == '?'; });
76
77 string test_pattern;
78
79 auto arrangements = 0L;
80 for ( size_t counter = 0; counter != (1U << size_t(counts)); ++counter ) {
81 auto bit_pattern = counter;
82
83 for ( char chr: springs ) {
84 if ( chr == '?' ) {
85 if ( (bit_pattern & 1U) != 0U ) {
86 test_pattern += '.';
87 }
88 else {
89 test_pattern += '#';
90 }
91 bit_pattern >>= 1U;
92 }
93 else {
94 test_pattern += chr;
95 }
96 }
97 if ( groups == count_groups(test_pattern) ) {
98 arrangements++;
99 }
100
101 test_pattern.clear();
102 }
103
104 return arrangements;
105}
106
107long
108count(const string& springs, const vector<long>& groups)
109{
110 map<tuple<string, vector<long>>, long> cache;
111
112 function<long(string, const vector<long>&)> count_rec = [&](string springs, const vector<long>& groups) -> long {
113 auto cached_value = cache.find(make_tuple(springs, groups));
114 if ( cached_value != cache.end() ) {
115 return cached_value->second;
116 }
117
118 springs.erase(0, springs.find_first_not_of('.'));
119
120 if ( springs.empty() ) {
121 return groups.empty() ? 1 : 0;
122 }
123
124 if ( groups.empty() ) {
125 return springs.find('#') == string_view::npos ? 1 : 0;
126 }
127
128 if ( springs[0] == '#' ) {
129 auto gidx = size_t(groups[0]);
130 if ( springs.length() < gidx || springs.substr(0, gidx).find('.') != string_view::npos || springs[gidx] == '#' ) {
131 return 0;
132 }
133
134 return count_rec(springs.substr(gidx + 1), { groups.begin() + 1, groups.end() });
135 }
136
137 auto value = count_rec(string("#") + springs.substr(1), groups) + count_rec(springs.substr(1), groups);
138
139 cache[make_tuple(springs, groups)] = value;
140
141 return value;
142 };
143
144 return count_rec(springs + ".", groups);
145}
146
147void
148part1(const vector<string>& input)
149{
150 auto sum = 0L;
151 for ( const auto& line: input ) {
152 auto parts = split(line, ' ');
153 auto springs = parts[0];
154 auto groups = read_ints(parts[1]);
155
156 sum += brute_force(springs, groups);
157 // sum += count(springs, groups);
158 }
159 cout << sum << endl;
160}
161
162void
163part2(const vector<string>& input)
164{
165 auto sum = 0L;
166 for ( const auto& line: input ) {
167 auto parts = split(line, ' ');
168 auto springs = parts[0] + "?" + parts[0] + "?" + parts[0] + "?" + parts[0] + "?" + parts[0];
169 auto groups = read_ints(parts[1] + "," + parts[1] + "," + parts[1] + "," + parts[1] + "," + parts[1]);
170
171 sum += count(springs, groups);
172 }
173 cout << sum << endl;
174}
175
176int
177main()
178{
179 const auto input = read_file("data/day12.txt");
180 part1(input);
181 part2(input);
182}