From 2bbf25c80e80d6328f24f69a48be39c913f9f88b Mon Sep 17 00:00:00 2001 From: Thomas Schmucker Date: Tue, 19 Dec 2023 23:27:47 +0100 Subject: Lösungen für Tag 19, Teil 2 MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- src/day19.cpp | 179 +++++++++++++++++++++++++++++++++++++++++++--------------- 1 file changed, 132 insertions(+), 47 deletions(-) (limited to 'src') 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 +#include #include #include #include @@ -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>> 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> foo; + vector> 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]); - - string rule = "in"; - while ( rule != "A" && rule != "R" ) { - auto sub_rules = get<0>(rules[rule]); - auto next_rule = get<1>(rules[rule]); - - 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); - - 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; - } - } + if ( !regex_search(part, smatch, parts_pattern) ) { + continue; + } - rule = next_rule; - } - if (rule == "A") { - sum += xval; - sum += mval; - sum += aval; - sum += sval; + map values = { + { "x", stol(smatch[1]) }, + { "m", stol(smatch[2]) }, + { "a", stol(smatch[3]) }, + { "s", stol(smatch[4]) }, + }; + + string rule = "in"; + while ( rule != "A" && rule != "R" ) { + auto [sub_rules, next_rule] = rules[rule]; + + for ( const auto& sub_rule: sub_rules ) { + const auto [field, cmp, value, dest] = sub_rule; + + 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>> 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> 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>, string)> count = [&](map> 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 T; // NOLINT + pair 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(); } -- cgit v1.3