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 ++++++++++++++++++++++++++++++++++++++ 4 files changed, 310 insertions(+) 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/19') 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; +} -- cgit v1.2.3