aoc(2319): AplentyHEADmaster

5 files changed, 331 insertions, 1 deletions

diff --git a/2023/19/Makefile b/2023/19/Makefile
new file mode 100644
index 0000000..af6a294
--- /dev/null
+++ b/2023/19/Makefile
@@ -0,0 +1,19 @@
+CXXFLAGS := -std=c++17
+CPPFLAGS := -I../include
+EXE := part1 part2
+
+.PHONY: all clean configure
+
+all: $(EXE)
+
+configure:
+        bear -- $(MAKE) all
+
+%.o: %.cpp
+        $(CXX) -c $(CPPFLAGS) $(CXXFLAGS) $< -o $@
+
+clean:
+        rm -rf $(EXE) src/*.o compile_commands.json
+
+%: src/%.o
+        $(CXX) $^ -o $@
diff --git a/2023/19/resources/input_small.txt b/2023/19/resources/input_small.txt
new file mode 100644
index 0000000..e5b5d64
--- /dev/null
+++ b/2023/19/resources/input_small.txt
@@ -0,0 +1,17 @@
+px{a<2006:qkq,m>2090:A,rfg}
+pv{a>1716:R,A}
+lnx{m>1548:A,A}
+rfg{s<537:gd,x>2440:R,A}
+qs{s>3448:A,lnx}
+qkq{x<1416:A,crn}
+crn{x>2662:A,R}
+in{s<1351:px,qqz}
+qqz{s>2770:qs,m<1801:hdj,R}
+gd{a>3333:R,R}
+hdj{m>838:A,pv}
+
+{x=787,m=2655,a=1222,s=2876}
+{x=1679,m=44,a=2067,s=496}
+{x=2036,m=264,a=79,s=2244}
+{x=2461,m=1339,a=466,s=291}
+{x=2127,m=1623,a=2188,s=1013}
diff --git a/2023/19/src/part1.cpp b/2023/19/src/part1.cpp
new file mode 100644
index 0000000..b63f05d
--- /dev/null
+++ b/2023/19/src/part1.cpp
@@ -0,0 +1,125 @@
+#include <iostream>
+#include <fstream>
+#include <array>
+#include <vector>
+#include <unordered_map>
+#include <functional>
+
+#include "util.h"
+
+using Name = std::string;
+using Part = std::array<int,4>;
+using Cond = std::function<bool(const Part&)>;
+using Rule = std::pair<Cond,Name>;
+using Workflow = std::vector<Rule>;
+using Workflows = std::unordered_map<Name,Workflow>;
+
+const std::unordered_map<char,int> fields{ {'x', 0}, {'m', 1}, {'a', 2}, {'s', 3} };
+
+std::pair<std::vector<Part>,Workflows> parse(const char* file)
+{
+    using namespace util::separators;
+
+    Workflows wfs;
+    std::vector<Part> parts;
+
+    if (std::ifstream input{ file }; input.is_open())
+    {
+        std::string line;
+        std::getline(input,line);
+        while (not line.empty())
+        {
+            auto bw = line.find('{');
+            Name name = line.substr(0, bw);
+
+            std::vector<Rule> rules;
+            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 f = fields.at(tokens[0][0]);
+                    int v = std::stoi(std::string(tokens[0].substr(2)));
+                    switch (tokens[0][1])
+                    {
+                        case '<':
+                            rules.push_back({
+                                [f,v](const Part& p) { return p[f] < v; },
+                                Name{ tokens[1] }
+                            });
+                            break;
+                        default:
+                            rules.push_back({
+                                [f,v](const Part& p) { return p[f] > v; },
+                                Name{ tokens[1] }
+                            });
+                    };
+                }
+                else
+                {
+                    rules.push_back({
+                        [](const Part& p) { return true; },
+                        Name{ tokens[0] }
+                    });
+                }
+            }
+            wfs.insert({ name, std::move(rules) });
+            std::getline(input,line);
+        }
+
+        while (not std::getline(input,line).eof())
+        {
+            Part part; int i{};
+            util::accumulate<COMMA>(std::string_view{ line }.substr(1, line.size() - 2),
+                [&part,&i](std::string_view& v)
+                {
+                    part[i++] = std::stoi(std::string{ v.substr(2) });
+                }
+            );
+            parts.push_back(std::move(part));
+        }
+    }
+    return { std::move(parts), std::move(wfs) };
+}
+
+Name apply_workflow(const Workflow& wf, const Part& p)
+{
+    for (const auto& rule : wf)
+    {
+        auto [cond, name] = rule;
+        if (cond(p)) return name;
+    }
+    return "R";
+}
+
+int value(const Part& p)
+{
+    return p[0] + p[1] + p[2] + p[3];
+}
+
+int process(const Part& p, const Workflows& wfs)
+{
+    Name wname = "in";
+    while (wname != "A")
+    {
+        if (wname == "R") return 0;
+        wname = apply_workflow(wfs.at(wname), p);
+    }
+    return value(p);
+}
+
+int main(int argc, char* argv[])
+{
+    int answer{};
+
+    auto [parts, workflows] = parse(argv[1]);
+
+    for (const auto& part : parts)
+    {
+        answer += process(part, workflows);
+    }
+
+    std::cout << answer << std::endl;
+    return 0;
+}
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;
+}
diff --git a/2023/include/util.h b/2023/include/util.h
index 3152719..100c9ed 100644
--- a/2023/include/util.h
+++ b/2023/include/util.h
@@ -7,6 +7,7 @@
 #include <string>
 #include <string_view>
 #include <type_traits>
+#include <vector>
 
 namespace util
 {
@@ -49,7 +50,7 @@ inline void trim(std::string_view& view)
  * @param the callable object.
  */
 template<const char* delim, typename Accumulate>
-void accumulate(std::string_view& view, Accumulate acc)
+void accumulate(std::string_view view, Accumulate acc)
 {
     size_t from{}, to;
     std::string elem;
@@ -68,6 +69,25 @@ void accumulate(std::string_view& view, Accumulate acc)
     }
 }
 
+/** @brief Split a string view according to a delimiter.
+ *
+ * Specialized version of `util::accumulate` collecting the split
+ * `std::string_view` in a `std::vector`.
+ *
+ * @tparam delim the delimiter to split the string view.
+ * @param view the string view.
+ *
+ * @see util::accumulate;
+ */
+template<const char* delim>
+std::vector<std::string_view> split(std::string_view view)
+{
+    std::vector<std::string_view> v;
+    auto callback = [&v](const std::string_view& s) { v.push_back(s); };
+    accumulate<delim>(view, callback);
+    return v;
+}
+
 /** @brief Discard element from stream by type.
  *
  * @tparam T the type of the element to discard.