114 lines
2.9 KiB
C++
114 lines
2.9 KiB
C++
#include <algorithm>
|
|
#include <cstdint>
|
|
#include <iostream>
|
|
#include <sstream>
|
|
#include <string>
|
|
#include <vector>
|
|
|
|
#include <boost/phoenix.hpp>
|
|
#include <boost/spirit/include/qi.hpp>
|
|
|
|
#include <doctest.h>
|
|
|
|
#include <aocpp/Parsing.hpp>
|
|
#include <aocpp/Startup.hpp>
|
|
#include <aocpp/Counter.hpp>
|
|
|
|
namespace {
|
|
|
|
namespace qi = boost::spirit::qi;
|
|
namespace phx = boost::phoenix;
|
|
namespace ascii = boost::spirit::ascii;
|
|
|
|
struct Card
|
|
{
|
|
unsigned long long id;
|
|
std::vector<unsigned long long> mine;
|
|
std::vector<unsigned long long> winners;
|
|
};
|
|
|
|
struct Grammar : public qi::grammar<std::string::const_iterator, std::vector<Card>(), ascii::space_type> {
|
|
qi::rule<iterator_type, Card(), ascii::space_type> card;
|
|
qi::rule<iterator_type, std::vector<Card>(), ascii::space_type> cards;
|
|
|
|
Grammar() : base_type{cards} {
|
|
using namespace qi::labels;
|
|
cards = *card;
|
|
card =
|
|
"Card" >> qi::ulong_long [ phx::bind(&Card::id , _val) = _1] >>
|
|
":" >> (*qi::ulong_long) [ phx::bind(&Card::mine , _val) = _1] >>
|
|
"|" >> (*qi::ulong_long) [ phx::bind(&Card::winners, _val) = _1];
|
|
}
|
|
};
|
|
|
|
auto CountWins(std::vector<Card>& cards) -> std::vector<std::size_t>
|
|
{
|
|
std::vector<std::size_t> result;
|
|
result.reserve(cards.size());
|
|
|
|
for (auto& card : cards)
|
|
{
|
|
std::sort(card.mine .begin(), card.mine .end());
|
|
std::sort(card.winners.begin(), card.winners.end());
|
|
auto const counter =
|
|
std::set_intersection(
|
|
card.mine .begin(), card.mine .end(),
|
|
card.winners.begin(), card.winners.end(),
|
|
Counter{});
|
|
result.push_back(counter);
|
|
}
|
|
|
|
return result;
|
|
}
|
|
|
|
auto Part1(std::vector<std::size_t> const& wins) -> std::uint64_t
|
|
{
|
|
std::uint64_t result = 0;
|
|
for (auto const win : wins)
|
|
{
|
|
if (win > 0)
|
|
{
|
|
result += std::uint64_t{1} << (win - 1);
|
|
}
|
|
}
|
|
return result;
|
|
}
|
|
|
|
auto Part2(std::vector<std::size_t> const& wins) -> std::size_t
|
|
{
|
|
std::vector<std::size_t> psums(wins.size() + 1);
|
|
for (std::size_t i = wins.size(); i --> 0;)
|
|
{
|
|
psums[i] = 1 + 2 * psums[i + 1] - psums[i + 1 + wins[i]];
|
|
}
|
|
return psums.front();
|
|
}
|
|
|
|
} // namespace
|
|
|
|
TEST_SUITE("2023-04 examples") {
|
|
TEST_CASE("example") {
|
|
std::istringstream in {
|
|
R"(Card 1: 41 48 83 86 17 | 83 86 6 31 17 9 48 53
|
|
Card 2: 13 32 20 16 61 | 61 30 68 82 17 32 24 19
|
|
Card 3: 1 21 53 59 44 | 69 82 63 72 16 21 14 1
|
|
Card 4: 41 92 73 84 69 | 59 84 76 51 58 5 54 83
|
|
Card 5: 87 83 26 28 32 | 88 30 70 12 93 22 82 36
|
|
Card 6: 31 18 13 56 72 | 74 77 10 23 35 67 36 11
|
|
)"
|
|
};
|
|
auto input = aocpp::ParseGrammar_(Grammar{}, in);
|
|
auto const wins = CountWins(input);
|
|
CHECK(Part1(wins) == 13);
|
|
CHECK(Part2(wins) == 30);
|
|
}
|
|
}
|
|
|
|
auto Main(std::istream & in, std::ostream & out) -> void
|
|
{
|
|
auto input = aocpp::ParseGrammar_(Grammar{}, in);
|
|
auto const wins = CountWins(input);
|
|
out << "Part 1: " << Part1(wins) << std::endl;
|
|
out << "Part 2: " << Part2(wins) << std::endl;
|
|
}
|