From 95afbe5174be402b681cd98ea83cc063cd23f5c0 Mon Sep 17 00:00:00 2001 From: Federico Igne Date: Wed, 20 Dec 2023 00:54:49 +0100 Subject: aoc(2319): Aplenty --- 2023/19/Makefile | 19 +++++ 2023/19/resources/input_small.txt | 17 +++++ 2023/19/src/part1.cpp | 125 ++++++++++++++++++++++++++++++++ 2023/19/src/part2.cpp | 149 ++++++++++++++++++++++++++++++++++++++ 2023/include/util.h | 22 +++++- 5 files changed, 331 insertions(+), 1 deletion(-) create mode 100644 2023/19/Makefile create mode 100644 2023/19/resources/input_small.txt create mode 100644 2023/19/src/part1.cpp create mode 100644 2023/19/src/part2.cpp (limited to '2023') 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 +#include +#include +#include +#include +#include + +#include "util.h" + +using Name = std::string; +using Part = std::array; +using Cond = std::function; +using Rule = std::pair; +using Workflow = std::vector; +using Workflows = std::unordered_map; + +const std::unordered_map fields{ {'x', 0}, {'m', 1}, {'a', 2}, {'s', 3} }; + +std::pair,Workflows> parse(const char* file) +{ + using namespace util::separators; + + Workflows wfs; + std::vector 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 rules; + line = line.substr(bw + 1, line.size() - bw - 2); + for (auto srule : util::split(std::string_view{ line })) + { + auto tokens = util::split(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(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 +#include +#include +#include +#include + +#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; +using Rule = std::pair,Name>; +using Bounds = std::array; +using Workflows = std::unordered_map; + +const std::unordered_map 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,Workflows> parse(const char* file) +{ + using namespace util::separators; + + Workflows workflows; + std::vector 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> conds; + line = line.substr(bw + 1, line.size() - bw - 2); + for (auto srule : util::split(std::string_view{ line })) + { + auto tokens = util::split(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 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 #include #include +#include namespace util { @@ -49,7 +50,7 @@ inline void trim(std::string_view& view) * @param the callable object. */ template -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 +std::vector split(std::string_view view) +{ + std::vector v; + auto callback = [&v](const std::string_view& s) { v.push_back(s); }; + accumulate(view, callback); + return v; +} + /** @brief Discard element from stream by type. * * @tparam T the type of the element to discard. -- cgit v1.2.3