111 lines
2.2 KiB
C++
111 lines
2.2 KiB
C++
#include <algorithm>
|
|
#include <concepts>
|
|
#include <cstdint>
|
|
#include <iostream>
|
|
#include <set>
|
|
#include <sstream>
|
|
#include <stack>
|
|
#include <stdexcept>
|
|
#include <string>
|
|
#include <tuple>
|
|
#include <utility>
|
|
#include <vector>
|
|
|
|
#include <doctest.h>
|
|
|
|
#include <aocpp/Startup.hpp>
|
|
#include <aocpp/Vec.hpp>
|
|
|
|
namespace {
|
|
|
|
using Coord = aocpp::Vec<std::int64_t, 3>;
|
|
|
|
/// @brief Parse an input stream
|
|
/// @param in white-space delimited, comma-separated coordinates
|
|
/// @return set of coordinates
|
|
auto Parse(std::istream & in) -> std::set<Coord>
|
|
{
|
|
auto result = std::set<Coord>{};
|
|
auto line = std::string{};
|
|
|
|
while (in >> line) {
|
|
auto x = Coord{};
|
|
if (3 != std::sscanf(line.c_str(), "%lld,%lld,%lld\n", &x[0], &x[1], &x[2])) {
|
|
throw std::runtime_error{"bad input line"};
|
|
}
|
|
result.insert(x);
|
|
}
|
|
return result;
|
|
}
|
|
|
|
auto Part1(std::set<Coord> const& obj) -> std::size_t
|
|
{
|
|
auto result = std::size_t{0};
|
|
for (auto const& x : obj) {
|
|
x.EachNeighbor([&](Coord const& y) {
|
|
if (!obj.contains(y)) result++;
|
|
});
|
|
}
|
|
return result;
|
|
}
|
|
|
|
auto Part2(std::set<Coord> const& obj) -> std::size_t
|
|
{
|
|
auto [lo, hi] = Coord::BoundingBox(obj.begin(), obj.end());
|
|
lo -= Coord{1};
|
|
hi += Coord{1};
|
|
|
|
auto seen = std::set<Coord>{};
|
|
auto work = std::stack<Coord>{};
|
|
auto result = std::size_t{0};
|
|
|
|
work.push(lo);
|
|
seen.insert(lo);
|
|
|
|
while (!work.empty()) {
|
|
auto const x = work.top();
|
|
work.pop();
|
|
x.EachNeighbor([&, lo=lo, hi=hi](Coord const& y) {
|
|
if (obj.contains(y)) {
|
|
result++;
|
|
} else if (y.InRange(lo, hi) && seen.insert(y).second) {
|
|
work.push(y);
|
|
}
|
|
});
|
|
}
|
|
|
|
return result;
|
|
}
|
|
|
|
} // namespace
|
|
|
|
TEST_SUITE("2022-12 examples") {
|
|
TEST_CASE("documented example") {
|
|
std::istringstream in {
|
|
"2,2,2\n"
|
|
"1,2,2\n"
|
|
"3,2,2\n"
|
|
"2,1,2\n"
|
|
"2,3,2\n"
|
|
"2,2,1\n"
|
|
"2,2,3\n"
|
|
"2,2,4\n"
|
|
"2,2,6\n"
|
|
"1,2,5\n"
|
|
"3,2,5\n"
|
|
"2,1,5\n"
|
|
"2,3,5\n"
|
|
};
|
|
auto obj = Parse(in);
|
|
CHECK(64 == Part1(obj));
|
|
CHECK(58 == Part2(obj));
|
|
}
|
|
}
|
|
|
|
auto Main(std::istream & in, std::ostream & out) -> void
|
|
{
|
|
auto const obj = Parse(in);
|
|
out << "Part 1: " << Part1(obj) << std::endl;
|
|
out << "Part 2: " << Part2(obj) << std::endl;
|
|
}
|