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