summaryrefslogtreecommitdiff
path: root/2023/19/src/part2.cpp
diff options
context:
space:
mode:
authorFederico Igne <undyamon@disroot.org>2023-12-20 00:54:49 +0100
committerFederico Igne <undyamon@disroot.org>2023-12-20 00:54:49 +0100
commit95afbe5174be402b681cd98ea83cc063cd23f5c0 (patch)
treefe7790f346e99e4e661723b568ff2be3ba6f8891 /2023/19/src/part2.cpp
parente3c9f0c73077de51167491ca1ba4d5ccba005435 (diff)
downloadaoc-95afbe5174be402b681cd98ea83cc063cd23f5c0.tar.gz
aoc-95afbe5174be402b681cd98ea83cc063cd23f5c0.zip
aoc(2319): AplentyHEADmaster
Diffstat (limited to '2023/19/src/part2.cpp')
-rw-r--r--2023/19/src/part2.cpp149
1 files changed, 149 insertions, 0 deletions
diff --git a/2023/19/src/part2.cpp b/2023/19/src/part2.cpp
new file mode 100644
index 0000000..93bfd65
--- /dev/null
+++ b/2023/19/src/part2.cpp
@@ -0,0 +1,149 @@
1#include <iostream>
2#include <fstream>
3#include <array>
4#include <vector>
5#include <unordered_map>
6
7#include "util.h"
8
9constexpr int FEATS = 4;
10constexpr int MIN = 1 - 1;
11constexpr int MAX = 4000 + 1;
12
13using Name = std::string;
14using Cond = std::tuple<char,char,int>;
15using Rule = std::pair<std::vector<Cond>,Name>;
16using Bounds = std::array<int,2*FEATS>;
17using Workflows = std::unordered_map<Name,Rule>;
18
19const std::unordered_map<char,int> fields{ {'x', 0}, {'m', 2}, {'a', 4}, {'s', 6} };
20
21Cond neg(const Cond& cond)
22{
23 auto [f,o,v] = cond;
24 return { f, (o == '<') ? '>' : '<', v + ((o == '<') ? -1 : 1) };
25}
26
27std::pair<std::vector<Rule>,Workflows> parse(const char* file)
28{
29 using namespace util::separators;
30
31 Workflows workflows;
32 std::vector<Rule> arules;
33
34 if (std::ifstream input{ file }; input.is_open())
35 {
36 std::string line;
37 std::getline(input,line);
38 while (not line.empty())
39 {
40 auto bw = line.find('{');
41 Name next = line.substr(0, bw);
42
43 std::vector<std::pair<Cond,Name>> conds;
44 line = line.substr(bw + 1, line.size() - bw - 2);
45 for (auto srule : util::split<COMMA>(std::string_view{ line }))
46 {
47 auto tokens = util::split<COLON>(srule);
48 if (tokens.size() > 1)
49 {
50 int val = std::stoi(std::string(tokens[0].substr(2)));
51 conds.push_back({ { tokens[0][0], tokens[0][1], val }, Name{ tokens[1] } });
52 }
53 else
54 {
55 conds.push_back({ { 0, 0, 0 }, Name{ tokens[0] } });
56 }
57 }
58
59 for (int i = 0; i < conds.size(); ++i)
60 {
61 auto [cond, name] = conds[i];
62 if (name == "R") continue;
63
64 int j{ i - 1 };
65 auto [f,o,v] = cond;
66 std::vector<Cond> nconds;
67 nconds.push_back(f ? cond : neg(std::get<0>(conds[j--])));
68 for (; j >= 0; --j)
69 {
70 nconds.push_back(neg(std::get<0>(conds[j])));
71 }
72
73 if (name == "A")
74 {
75 arules.push_back({ std::move(nconds), next });
76 }
77 else
78 {
79 workflows.insert({ name, { std::move(nconds), next } });
80 }
81 }
82 std::getline(input,line);
83 }
84 }
85
86 return { std::move(arules), std::move(workflows) };
87}
88
89Bounds operator&&(const Bounds& a, const Bounds& b)
90{
91 Bounds c;
92 for (int i = 0; i < FEATS; ++i)
93 {
94 c[2*i] = std::max(a[2*i], b[2*i]);
95 c[2*i+1] = std::min(a[2*i+1], b[2*i+1]);
96 }
97 return c;
98}
99
100void operator+=(Bounds& b, const Cond& c)
101{
102 auto [f,o,v] = c;
103 int i{ fields.at(f) };
104 if (o == '>')
105 {
106 b[i] = std::max(b[i],v);
107 }
108 else
109 {
110 b[i + 1] = std::min(b[i + 1],v);
111 }
112}
113
114Bounds compute_bounds(const Workflows& wfs, const Rule& rule)
115{
116 Bounds bounds{ MIN, MAX, MIN, MAX, MIN, MAX, MIN, MAX };
117 auto [conds, next] = rule;
118 for (const auto& cond : conds)
119 {
120 bounds += cond;
121 }
122 if (next == "in") return { bounds };
123 return bounds && compute_bounds(wfs, wfs.at(next));
124}
125
126long long combinations(const Bounds& bounds)
127{
128 long long res{ 1 };
129 for (int i = 0; i < FEATS; ++i)
130 {
131 if (bounds[2*i] >= bounds[2*i+1]) return 0;
132 res *= bounds[2*i+1] - bounds[2*i] - 1;
133 }
134 return res;
135}
136
137int main(int argc, char* argv[])
138{
139 long answer{};
140
141 auto [arules, workflows] = parse(argv[1]);
142 for (const auto& rule : arules)
143 {
144 answer += combinations(compute_bounds(workflows, rule));
145 }
146
147 std::cout << answer<< std::endl;
148 return 0;
149}