1 files changed, 129 insertions, 44 deletions

diff --git a/src/day19.cpp b/src/day19.cpp
index 3dbae22..c991d6d 100644
--- a/src/day19.cpp
+++ b/src/day19.cpp
@@ -1,4 +1,5 @@
 #include <fstream>
+#include <functional>
 #include <iostream>
 #include <map>
 #include <regex>
@@ -41,83 +42,167 @@ part1()
         const auto rules_string = split(input[0], "\n");
         const auto parts        = split(input[1], "\n");
 
-        const regex rules_pattern{ R"((.*)\{(.*),(.*)\})" };
-        const regex sub_rules_pattern{ R"((.)(.)(\d*):(.*))" };
-
         map<string, tuple<vector<tuple<string, string, long, string>>, string>> rules;
 
         for ( const auto& rule: rules_string ) {
+                static const regex rules_pattern{ R"((.*)\{(.*),(.*)\})" };
+
                 smatch smatch;
                 if ( regex_search(rule, smatch, rules_pattern) ) {
                         string rule_name    = smatch[1];
                         string default_dest = smatch[3];
 
-                        vector<tuple<string, string, long, string>> foo;
+                        vector<tuple<string, string, long, string>> sub_rules;
 
                         for ( const auto& sub_rule: split(smatch[2].str(), ",") ) {
+                                static const regex sub_rules_pattern{ R"((.)(.)(\d*):(.*))" };
+
                                 std::smatch smatch2;
                                 if ( regex_search(sub_rule, smatch2, sub_rules_pattern) ) {
-                                        foo.emplace_back(smatch2[1], smatch2[2], stol(smatch2[3]), smatch2[4]);
+                                        sub_rules.emplace_back(smatch2[1], smatch2[2], stol(smatch2[3]), smatch2[4]);
                                 }
                         }
 
-                        rules[rule_name] = make_tuple(foo, default_dest);
+                        rules[rule_name] = make_tuple(sub_rules, default_dest);
                 }
         }
 
         long sum = 0;
-        const regex parts_pattern{ R"(\{x=(\d*),m=(\d*),a=(\d*),s=(\d*)\})" };
         for ( const auto& part: parts ) {
+                static const regex parts_pattern{ R"(\{x=(\d*),m=(\d*),a=(\d*),s=(\d*)\})" };
+
                 smatch smatch;
-                if ( regex_search(part, smatch, parts_pattern) ) {
-                        const auto xval = stol(smatch[1]);
-                        const auto mval = stol(smatch[2]);
-                        const auto aval = stol(smatch[3]);
-                        const auto sval = stol(smatch[4]);
+                if ( !regex_search(part, smatch, parts_pattern) ) {
+                        continue;
+                }
 
-                        string rule = "in";
-                        while ( rule != "A" && rule != "R" ) {
-                                auto sub_rules = get<0>(rules[rule]);
-                                auto next_rule = get<1>(rules[rule]);
+                map<string, long> values = {
+                        { "x", stol(smatch[1]) },
+                        { "m", stol(smatch[2]) },
+                        { "a", stol(smatch[3]) },
+                        { "s", stol(smatch[4]) },
+                };
 
-                                for ( auto sub_rule: sub_rules ) {
-                                        const auto field = get<0>(sub_rule);
-                                        const auto cmp   = get<1>(sub_rule);
-                                        const auto value = get<2>(sub_rule);
+                string rule = "in";
+                while ( rule != "A" && rule != "R" ) {
+                        auto [sub_rules, next_rule] = rules[rule];
 
-                                        if ( field == "x" && ((cmp == ">" && xval > value) || (cmp == "<" && xval < value)) ) {
-                                                next_rule = get<3>(sub_rule);
-                                                break;
-                                        }
-                                        if ( field == "m" && ((cmp == ">" && mval > value) || (cmp == "<" && mval < value)) ) {
-                                                next_rule = get<3>(sub_rule);
-                                                break;
-                                        }
-                                        if ( field == "a" && ((cmp == ">" && aval > value) || (cmp == "<" && aval < value)) ) {
-                                                next_rule = get<3>(sub_rule);
-                                                break;
-                                        }
-                                        if ( field == "s" && ((cmp == ">" && sval > value) || (cmp == "<" && sval < value)) ) {
-                                                next_rule = get<3>(sub_rule);
-                                                break;
-                                        }
-                                }
+                        for ( const auto& sub_rule: sub_rules ) {
+                                const auto [field, cmp, value, dest] = sub_rule;
 
-                                rule = next_rule;
-                        }
-                        if (rule == "A") {
-                                sum += xval;
-                                sum += mval;
-                                sum += aval;
-                                sum += sval;
+                                if ( values.contains(field) && ((cmp == ">" && values[field] > value) || (cmp == "<" && values[field] < value)) ) {
+                                        next_rule = dest;
+                                        break;
+                                }
                         }
+
+                        rule = next_rule;
+                }
+
+                if ( rule == "A" ) {
+                        sum += values["x"];
+                        sum += values["m"];
+                        sum += values["a"];
+                        sum += values["s"];
                 }
         }
         cout << sum << endl;
 }
 
+void
+part2()
+{
+        const auto input        = split(read_file("data/day19.txt"), "\n\n");
+        const auto rules_string = split(input[0], "\n");
+
+        const regex rules_pattern{ R"((.*)\{(.*),(.*)\})" };
+        const regex sub_rules_pattern{ R"((.)(.)(\d*):(.*))" };
+
+        map<string, tuple<vector<tuple<string, string, long, string>>, string>> rules;
+
+        for ( const auto& rule: rules_string ) {
+                smatch smatch;
+                if ( regex_search(rule, smatch, rules_pattern) ) {
+                        string rule_name    = smatch[1];
+                        string default_dest = smatch[3];
+
+                        vector<tuple<string, string, long, string>> sub_rules;
+
+                        for ( const auto& sub_rule: split(smatch[2].str(), ",") ) {
+                                std::smatch smatch2;
+                                if ( regex_search(sub_rule, smatch2, sub_rules_pattern) ) {
+                                        sub_rules.emplace_back(smatch2[1], smatch2[2], stol(smatch2[3]), smatch2[4]);
+                                }
+                        }
+
+                        rules[rule_name] = make_tuple(sub_rules, default_dest);
+                }
+        }
+
+        function<long(map<string, tuple<long, long>>, string)> count = [&](map<string, tuple<long, long>> ranges, string name) -> long {
+                if ( name == "R" ) {
+                        return 0;
+                }
+
+                if ( name == "A" ) {
+                        long result = 1;
+                        for ( const auto& range: ranges ) {
+                                const auto [lo, hi] = range.second;
+                                result *= hi - lo + 1;
+                        }
+                        return result;
+                }
+
+                const auto [sub_rules, fallback] = rules[name];
+
+                long result = 0;
+
+                bool run_trough = true;
+                for ( const auto& [key, cmp, value, target]: sub_rules ) {
+                        const auto [lo, hi] = ranges[key];
+                        pair<long, long> T; // NOLINT
+                        pair<long, long> F; // NOLINT
+                        if ( cmp == "<" ) {
+                                T = { lo, min(value - 1, hi) };
+                                F = { max(value, lo), hi };
+                        }
+                        else {
+                                T = { max(value + 1, lo), hi };
+                                F = { lo, min(value, hi) };
+                        }
+                        if ( T.first <= T.second ) {
+                                auto copy = ranges;
+                                copy[key] = T;
+                                result += count(copy, target);
+                        }
+                        if ( F.first <= F.second ) {
+                                ranges[key] = F;
+                        }
+                        else {
+                                run_trough = false;
+                                break;
+                        }
+                }
+                if ( run_trough ) {
+                        result += count(ranges, fallback);
+                }
+
+                return result;
+        };
+
+        cout << count({
+                          { "x", { 1, 4000 } },
+                          { "m", { 1, 4000 } },
+                          { "a", { 1, 4000 } },
+                          { "s", { 1, 4000 } },
+                      },
+                      "in")
+             << endl;
+}
+
 int
 main()
 {
         part1();
+        part2();
 }