From 95afbe5174be402b681cd98ea83cc063cd23f5c0 Mon Sep 17 00:00:00 2001
From: Federico Igne <undyamon@disroot.org>
Date: Wed, 20 Dec 2023 00:54:49 +0100
Subject: aoc(2319): Aplenty

---
 2023/19/src/part2.cpp | 149 ++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 149 insertions(+)
 create mode 100644 2023/19/src/part2.cpp

(limited to '2023/19/src/part2.cpp')

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 @@
+#include <iostream>
+#include <fstream>
+#include <array>
+#include <vector>
+#include <unordered_map>
+
+#include "util.h"
+
+constexpr int FEATS = 4;
+constexpr int MIN = 1 - 1;
+constexpr int MAX = 4000 + 1;
+
+using Name = std::string;
+using Cond = std::tuple<char,char,int>;
+using Rule = std::pair<std::vector<Cond>,Name>;
+using Bounds = std::array<int,2*FEATS>;
+using Workflows = std::unordered_map<Name,Rule>;
+
+const std::unordered_map<char,int> fields{ {'x', 0}, {'m', 2}, {'a', 4}, {'s', 6} };
+
+Cond neg(const Cond& cond)
+{
+    auto [f,o,v] = cond;
+    return { f, (o == '<') ? '>' : '<', v + ((o == '<') ? -1 : 1) };
+}
+
+std::pair<std::vector<Rule>,Workflows> parse(const char* file)
+{
+    using namespace util::separators;
+
+    Workflows workflows;
+    std::vector<Rule> arules;
+
+    if (std::ifstream input{ file }; input.is_open())
+    {
+        std::string line;
+        std::getline(input,line);
+        while (not line.empty())
+        {
+            auto bw = line.find('{');
+            Name next = line.substr(0, bw);
+
+            std::vector<std::pair<Cond,Name>> conds;
+            line = line.substr(bw + 1, line.size() - bw - 2);
+            for (auto srule : util::split<COMMA>(std::string_view{ line }))
+            {
+                auto tokens = util::split<COLON>(srule);
+                if (tokens.size() > 1)
+                {
+                    int val = std::stoi(std::string(tokens[0].substr(2)));
+                    conds.push_back({ { tokens[0][0], tokens[0][1], val }, Name{ tokens[1] } });
+                }
+                else
+                {
+                    conds.push_back({ { 0, 0, 0 }, Name{ tokens[0] } });
+                }
+            }
+
+            for (int i = 0; i < conds.size(); ++i)
+            {
+                auto [cond, name] = conds[i];
+                if (name == "R") continue;
+
+                int j{ i - 1 };
+                auto [f,o,v] = cond;
+                std::vector<Cond> nconds;
+                nconds.push_back(f ? cond : neg(std::get<0>(conds[j--])));
+                for (; j >= 0; --j)
+                {
+                    nconds.push_back(neg(std::get<0>(conds[j])));
+                }
+
+                if (name == "A")
+                {
+                    arules.push_back({ std::move(nconds), next });
+                }
+                else
+                {
+                    workflows.insert({ name, { std::move(nconds), next } });
+                }
+            }
+            std::getline(input,line);
+        }
+    }
+
+    return { std::move(arules), std::move(workflows) };
+}
+
+Bounds operator&&(const Bounds& a, const Bounds& b)
+{
+    Bounds c;
+    for (int i = 0; i < FEATS; ++i)
+    {
+        c[2*i] = std::max(a[2*i], b[2*i]);
+        c[2*i+1] = std::min(a[2*i+1], b[2*i+1]);
+    }
+    return c;
+}
+
+void operator+=(Bounds& b, const Cond& c)
+{
+    auto [f,o,v] = c;
+    int i{ fields.at(f) };
+    if (o == '>')
+    {
+        b[i] = std::max(b[i],v);
+    }
+    else
+    {
+        b[i + 1] = std::min(b[i + 1],v);
+    }
+}
+
+Bounds compute_bounds(const Workflows& wfs, const Rule& rule)
+{
+    Bounds bounds{ MIN, MAX, MIN, MAX, MIN, MAX, MIN, MAX };
+    auto [conds, next] = rule;
+    for (const auto& cond : conds)
+    {
+        bounds += cond;
+    }
+    if (next == "in") return { bounds };
+    return bounds && compute_bounds(wfs, wfs.at(next));
+}
+
+long long combinations(const Bounds& bounds)
+{
+    long long res{ 1 };
+    for (int i = 0; i < FEATS; ++i)
+    {
+        if (bounds[2*i] >= bounds[2*i+1]) return 0;
+        res *= bounds[2*i+1] - bounds[2*i] - 1;
+    }
+    return res;
+}
+
+int main(int argc, char* argv[])
+{
+    long answer{};
+
+    auto [arules, workflows] = parse(argv[1]);
+    for (const auto& rule : arules)
+    {
+        answer += combinations(compute_bounds(workflows, rule));
+    }
+
+    std::cout << answer<< std::endl;
+    return 0;
+}
-- 
cgit v1.2.3