diff options
author | Federico Igne <undyamon@disroot.org> | 2023-12-20 00:54:49 +0100 |
---|---|---|
committer | Federico Igne <undyamon@disroot.org> | 2023-12-20 00:54:49 +0100 |
commit | 95afbe5174be402b681cd98ea83cc063cd23f5c0 (patch) | |
tree | fe7790f346e99e4e661723b568ff2be3ba6f8891 /2023/19/src/part2.cpp | |
parent | e3c9f0c73077de51167491ca1ba4d5ccba005435 (diff) | |
download | aoc-95afbe5174be402b681cd98ea83cc063cd23f5c0.tar.gz aoc-95afbe5174be402b681cd98ea83cc063cd23f5c0.zip |
Diffstat (limited to '2023/19/src/part2.cpp')
-rw-r--r-- | 2023/19/src/part2.cpp | 149 |
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 | |||
9 | constexpr int FEATS = 4; | ||
10 | constexpr int MIN = 1 - 1; | ||
11 | constexpr int MAX = 4000 + 1; | ||
12 | |||
13 | using Name = std::string; | ||
14 | using Cond = std::tuple<char,char,int>; | ||
15 | using Rule = std::pair<std::vector<Cond>,Name>; | ||
16 | using Bounds = std::array<int,2*FEATS>; | ||
17 | using Workflows = std::unordered_map<Name,Rule>; | ||
18 | |||
19 | const std::unordered_map<char,int> fields{ {'x', 0}, {'m', 2}, {'a', 4}, {'s', 6} }; | ||
20 | |||
21 | Cond neg(const Cond& cond) | ||
22 | { | ||
23 | auto [f,o,v] = cond; | ||
24 | return { f, (o == '<') ? '>' : '<', v + ((o == '<') ? -1 : 1) }; | ||
25 | } | ||
26 | |||
27 | std::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 | |||
89 | Bounds 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 | |||
100 | void 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 | |||
114 | Bounds 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 | |||
126 | long 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 | |||
137 | int 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 | } | ||