From e3c9f0c73077de51167491ca1ba4d5ccba005435 Mon Sep 17 00:00:00 2001 From: Federico Igne Date: Tue, 19 Dec 2023 02:06:02 +0100 Subject: aoc(2318): Lavaduct Lagoon --- 2023/18/Makefile | 19 ++++++++++++ 2023/18/resources/input_small.txt | 14 +++++++++ 2023/18/src/part1.cpp | 62 ++++++++++++++++++++++++++++++++++++++ 2023/18/src/part2.cpp | 63 +++++++++++++++++++++++++++++++++++++++ 2023/include/util.h | 39 ++++++++++++++++++++++++ 5 files changed, 197 insertions(+) create mode 100644 2023/18/Makefile create mode 100644 2023/18/resources/input_small.txt create mode 100644 2023/18/src/part1.cpp create mode 100644 2023/18/src/part2.cpp diff --git a/2023/18/Makefile b/2023/18/Makefile new file mode 100644 index 0000000..af6a294 --- /dev/null +++ b/2023/18/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/18/resources/input_small.txt b/2023/18/resources/input_small.txt new file mode 100644 index 0000000..fc7612e --- /dev/null +++ b/2023/18/resources/input_small.txt @@ -0,0 +1,14 @@ +R 6 (#70c710) +D 5 (#0dc571) +L 2 (#5713f0) +D 2 (#d2c081) +R 2 (#59c680) +D 2 (#411b91) +L 5 (#8ceee2) +U 2 (#caa173) +L 1 (#1b58a2) +U 2 (#caa171) +R 2 (#7807d2) +U 3 (#a77fa3) +L 2 (#015232) +U 2 (#7a21e3) diff --git a/2023/18/src/part1.cpp b/2023/18/src/part1.cpp new file mode 100644 index 0000000..b7c9e09 --- /dev/null +++ b/2023/18/src/part1.cpp @@ -0,0 +1,62 @@ +#include +#include +#include +#include +#include +#include + +#include "util.h" + +using Cmd = std::tuple; +using Pos = std::pair; +using Polygon = std::vector; + +std::vector parse(const char* file) +{ + std::vector cmds; + if (std::ifstream input{ file }; input.is_open()) + { + char dir; int steps; + std::string line; + while (not std::getline(input,line).eof()) + { + std::stringstream in{ line }; + in >> dir >> steps; + cmds.push_back({ dir, steps }); + } + } + return cmds; +} + +std::pair compute_border(Pos pos, const std::vector& cmds) +{ + Polygon poly; + int border{}; + auto [x, y] = pos; + for(const auto& cmd : cmds) + { + auto [dir, steps] = cmd; + switch (dir) + { + case 'R': y += steps; break; + case 'D': x += steps; break; + case 'L': y -= steps; break; + case 'U': x -= steps; + } + poly.push_back({ x, y }); + border += steps; + } + return { border, std::move(poly) }; +} + + + +int main(int argc, char* argv[]) +{ + auto cmds = parse(argv[1]); + auto [border, polygon] = compute_border({ 0, 0 }, cmds); + int area = util::shoelace(polygon.cbegin(), polygon.cend()); + + std::cout << border + util::pick(area, border) << std::endl; + return 0; +} diff --git a/2023/18/src/part2.cpp b/2023/18/src/part2.cpp new file mode 100644 index 0000000..e9b6c02 --- /dev/null +++ b/2023/18/src/part2.cpp @@ -0,0 +1,63 @@ +#include +#include +#include +#include +#include + +#include "util.h" + +enum Dir { R = 0, D, L, U }; +using Cmd = std::tuple; +using Pos = std::pair; +using Polygon = std::vector; + +std::vector parse(const char* file) +{ + std::vector cmds; + if (std::ifstream input{ file }; input.is_open()) + { + Dir dir; int steps; std::string color; + std::string line; + while (not std::getline(input,line).eof()) + { + std::stringstream in{ line }; + in >> util::skip >> util::skip >> color; + steps = std::stoi(color.substr(2, 5), nullptr, 16); + dir = static_cast(std::stoi(color.substr(7, 1))); + cmds.push_back({ dir, steps }); + } + } + return cmds; +} + +std::pair compute_border(Pos pos, const std::vector& cmds) +{ + Polygon poly; + long border{}; + auto [x, y] = pos; + for(const auto& cmd : cmds) + { + auto [dir, steps] = cmd; + switch (dir) + { + case R: y += steps; break; + case D: x += steps; break; + case L: y -= steps; break; + case U: x -= steps; + } + poly.push_back({ x, y }); + border += steps; + } + return { border, std::move(poly) }; +} + +int main(int argc, char* argv[]) +{ + auto cmds = parse(argv[1]); + auto [border, polygon] = compute_border({ 0, 0 }, cmds); + long area = util::shoelace(polygon.cbegin(), polygon.cend()); + + std::cout << border + util::pick(area, border) << std::endl; + return 0; +} + diff --git a/2023/include/util.h b/2023/include/util.h index e396e3c..3152719 100644 --- a/2023/include/util.h +++ b/2023/include/util.h @@ -6,6 +6,7 @@ #include #include #include +#include namespace util { @@ -119,6 +120,44 @@ std::basic_istream& skip(std::basic_istream& strea return stream; } +/* @brief Compute the area of a planar simple polygon. + * + * @tparam Int integral coordinate type. + * @param first start of an iterator over pairs of 'Int'. + * @param last end of an iterator over pairs of 'Int'. + * + * @see https://en.wikipedia.org/wiki/Shoelace_formula#Triangle_formula + */ +template,Int>> +Int shoelace(InputIt first, InputIt last) +{ + Int result{}; + auto [x1, y1] = *first; + while(first++ != last) + { + auto [x2, y2] = *first; + result += x1 * y2 - x2 * y1; + x1 = x2; y1 = y2; + } + return std::abs(result / 2); +} + +/* @brief Return the number of integral coordinates inside a planar + * simple polygon. + * + * @tparam Int integral return type. + * @param area the area of the polygon. + * @param border the number of integral coordinates on the polygon's + * boundary. + * + * @see https://en.wikipedia.org/wiki/Pick%27s_theorem#Formula + */ +template,Int>> +Int pick(Int area, Int border) +{ + return area - border / 2 + 1; +} + } // namespace util #endif //UTIL_H -- cgit v1.2.3