Line data Source code
1 : #include "LinewiseInput.h"
2 : #include "Parsing.h"
3 : #include "PuzzleImpl.h"
4 :
5 : #include <absl/container/flat_hash_map.h>
6 : #include <libassert/assert.hpp>
7 : #include <memory>
8 : #include <numeric>
9 : #include <re2/re2.h>
10 :
11 : #include <array>
12 : #include <span>
13 : #include <string_view>
14 : #include <tuple>
15 :
16 : namespace {
17 :
18 0 : constexpr std::array<unsigned, 128u> makeCategoryIndexMap() {
19 0 : std::array<unsigned, 128u> map{};
20 0 : map['x'] = 0;
21 0 : map['m'] = 1;
22 0 : map['a'] = 2;
23 0 : map['s'] = 3;
24 0 : return map;
25 0 : }
26 : constexpr std::array<unsigned, 128u> categoryIndexMap = makeCategoryIndexMap();
27 :
28 : using PartRatings = std::array<unsigned, 4u>;
29 :
30 : struct Rule {
31 2112 : Rule(std::string_view const ruleStr) {
32 2112 : static const RE2 pattern = R"(([xmas])([<>])(\d+)\:([a-zAR]+))";
33 :
34 2112 : char category = 0;
35 2112 : ASSUME(RE2::FullMatch(ruleStr, pattern, &category, &op, &threshold, &acceptedWorkflow));
36 :
37 2112 : idx = categoryIndexMap[category];
38 2112 : }
39 :
40 : unsigned idx = 0;
41 : unsigned threshold = 0;
42 : char op = 0;
43 : std::string_view acceptedWorkflow;
44 : };
45 :
46 : struct Workflow {
47 1052 : Workflow(std::string_view const workflowStr) {
48 1052 : auto parts = split(workflowStr);
49 1052 : defaultWorkflow = parts.back();
50 1052 : parts.pop_back();
51 1052 : rules.assign(parts.begin(), parts.end());
52 1052 : }
53 :
54 : std::vector<Rule> rules;
55 : std::string_view defaultWorkflow;
56 : };
57 :
58 : using Workflows = absl::flat_hash_map<std::string_view, Workflow>;
59 :
60 : class Node {
61 : public:
62 4226 : virtual ~Node() = default;
63 : [[nodiscard]] virtual bool accept(PartRatings const &p) const = 0;
64 : [[nodiscard]] virtual size_t acceptedCombinations(PartRatings const &min,
65 : PartRatings const &max) const = 0;
66 : };
67 :
68 : std::unique_ptr<Node> makeNode(Workflows const &wfs, std::string_view const wf);
69 : std::unique_ptr<Node> makeNode(Workflows const &wfs, Workflow const &wf, auto it);
70 :
71 : class AcceptingNode final : public Node {
72 : public:
73 94 : [[nodiscard]] bool accept(PartRatings const &) const final { return true; }
74 :
75 : [[nodiscard]] size_t acceptedCombinations(PartRatings const &min,
76 542 : PartRatings const &max) const final {
77 542 : return size_t(max[0] - min[0] + 1) * size_t(max[1] - min[1] + 1) * size_t(max[2] - min[2] + 1) *
78 542 : size_t(max[3] - min[3] + 1);
79 542 : }
80 : };
81 :
82 : class RejectingNode final : public Node {
83 : public:
84 106 : [[nodiscard]] bool accept(PartRatings const &) const final { return false; }
85 :
86 515 : [[nodiscard]] size_t acceptedCombinations(PartRatings const &, PartRatings const &) const final {
87 515 : return 0;
88 515 : };
89 : };
90 :
91 : class LessThanNode final : public Node {
92 : public:
93 : LessThanNode(Workflows const &wfs, Workflow const &wf, auto it)
94 1080 : : _idx(it->idx), _threshold(it->threshold) {
95 :
96 1080 : ASSUME(it->op == '<');
97 :
98 1080 : _ltNode = makeNode(wfs, it->acceptedWorkflow);
99 :
100 1080 : if (std::next(it) == wf.rules.end())
101 528 : _geNode = makeNode(wfs, wf.defaultWorkflow);
102 552 : else {
103 552 : _geNode = makeNode(wfs, wf, std::next(it));
104 552 : }
105 1080 : }
106 :
107 990 : [[nodiscard]] bool accept(PartRatings const &p) const final {
108 990 : return p[_idx] < _threshold ? _ltNode->accept(p) : _geNode->accept(p);
109 990 : }
110 :
111 : [[nodiscard]] size_t acceptedCombinations(PartRatings const &min,
112 540 : PartRatings const &max) const final {
113 :
114 540 : PartRatings newMax = max;
115 540 : newMax[_idx] = _threshold - 1;
116 540 : PartRatings newMin = min;
117 540 : newMin[_idx] = _threshold;
118 :
119 540 : return _ltNode->acceptedCombinations(min, newMax) + _geNode->acceptedCombinations(newMin, max);
120 540 : }
121 :
122 : private:
123 : unsigned _idx;
124 : unsigned _threshold;
125 : std::unique_ptr<Node> _ltNode;
126 : std::unique_ptr<Node> _geNode;
127 : };
128 :
129 : class GreaterThanNode final : public Node {
130 : public:
131 : GreaterThanNode(Workflows const &wfs, Workflow const &wf, auto it)
132 1032 : : _idx(it->idx), _threshold(it->threshold) {
133 :
134 1032 : ASSUME(it->op == '>');
135 :
136 1032 : _gtNode = makeNode(wfs, it->acceptedWorkflow);
137 :
138 1032 : if (std::next(it) == wf.rules.end())
139 524 : _leNode = makeNode(wfs, wf.defaultWorkflow);
140 508 : else {
141 508 : _leNode = makeNode(wfs, wf, std::next(it));
142 508 : }
143 1032 : }
144 :
145 829 : [[nodiscard]] bool accept(PartRatings const &p) const final {
146 829 : return p[_idx] > _threshold ? _gtNode->accept(p) : _leNode->accept(p);
147 829 : }
148 :
149 : [[nodiscard]] size_t acceptedCombinations(PartRatings const &min,
150 516 : PartRatings const &max) const final {
151 :
152 516 : PartRatings newMax = max;
153 516 : newMax[_idx] = _threshold;
154 516 : PartRatings newMin = min;
155 516 : newMin[_idx] = _threshold + 1;
156 :
157 516 : return _gtNode->acceptedCombinations(newMin, max) + _leNode->acceptedCombinations(min, newMax);
158 516 : }
159 :
160 : private:
161 : unsigned _idx;
162 : unsigned _threshold;
163 : std::unique_ptr<Node> _gtNode;
164 : std::unique_ptr<Node> _leNode;
165 : };
166 :
167 3166 : std::unique_ptr<Node> makeNode(Workflows const &wfs, std::string_view const wf) {
168 :
169 3166 : if (wf == "A")
170 1084 : return std::make_unique<AcceptingNode>();
171 2082 : else if (wf == "R")
172 1030 : return std::make_unique<RejectingNode>();
173 1052 : else {
174 1052 : auto it = wfs.find(wf);
175 1052 : ASSUME(it != wfs.end());
176 1052 : return makeNode(wfs, it->second, it->second.rules.begin());
177 1052 : }
178 3166 : }
179 :
180 2112 : std::unique_ptr<Node> makeNode(Workflows const &wfs, Workflow const &wf, auto it) {
181 2112 : if (it->op == '<')
182 1080 : return std::make_unique<LessThanNode>(wfs, wf, it);
183 1032 : else
184 1032 : return std::make_unique<GreaterThanNode>(wfs, wf, it);
185 2112 : }
186 :
187 2 : std::unique_ptr<Node> parseWorkflows(std::span<std::string_view const> const input) {
188 2 : static const RE2 pattern = R"(([a-z]+){(.*)})";
189 :
190 2 : absl::flat_hash_map<std::string_view, Workflow> workflows;
191 :
192 1052 : for (std::string_view const line : input) {
193 1052 : std::string_view name, ruleStr;
194 1052 : ASSUME(RE2::FullMatch(line, pattern, &name, &ruleStr));
195 1052 : workflows.emplace(name, Workflow(ruleStr));
196 1052 : }
197 :
198 2 : return makeNode(workflows, "in");
199 2 : }
200 :
201 1 : std::vector<PartRatings> parsePartRatings(std::span<std::string_view const> const input) {
202 1 : static const RE2 pattern = R"({x=(\d+),m=(\d+),a=(\d+),s=(\d+)})";
203 :
204 1 : std::vector<PartRatings> result;
205 1 : result.reserve(input.size());
206 :
207 200 : for (std::string_view const line : input) {
208 200 : PartRatings r;
209 200 : ASSUME(RE2::FullMatch(line, pattern, &r[0], &r[1], &r[2], &r[3]));
210 200 : result.push_back(r);
211 200 : }
212 :
213 1 : return result;
214 1 : }
215 :
216 1 : auto parse(std::string_view const input) {
217 1 : LinewiseInput lines(input);
218 1 : std::vector<std::span<std::string_view const>> splitLines = lines.splitOnEmptyLines();
219 1 : ASSUME(splitLines.size() == 2u);
220 1 : return std::make_tuple(parseWorkflows(splitLines[0]), parsePartRatings(splitLines[1]));
221 1 : }
222 :
223 : } // namespace
224 :
225 1 : template <> size_t part1<2023, 19>(std::string_view const input) {
226 1 : auto [workflows, parts] = parse(input);
227 1 : size_t sum = 0;
228 200 : for (auto const &part : parts) {
229 200 : if (workflows->accept(part)) {
230 94 : sum += std::reduce(part.begin(), part.end());
231 94 : }
232 200 : }
233 :
234 1 : return sum;
235 1 : }
236 :
237 1 : template <> size_t part2<2023, 19>(std::string_view const input) {
238 1 : LinewiseInput lines(input);
239 1 : std::vector<std::span<std::string_view const>> splitLines = lines.splitOnEmptyLines();
240 1 : auto workflows = parseWorkflows(splitLines[0]);
241 1 : return workflows->acceptedCombinations({1, 1, 1, 1}, {4000, 4000, 4000, 4000});
242 1 : }
|
