84 lines
2.0 KiB
C++
84 lines
2.0 KiB
C++
#include <algorithm>
|
|
#include <cctype>
|
|
#include <cstdint>
|
|
#include <iostream>
|
|
#include <string_view>
|
|
#include <string>
|
|
#include <tuple>
|
|
#include <tuple>
|
|
#include <vector>
|
|
#include <numeric>
|
|
#include <functional>
|
|
|
|
#include <aocpp/Startup.hpp>
|
|
|
|
namespace {
|
|
|
|
using Input = std::vector<std::uint32_t>;
|
|
|
|
auto Parse(std::istream & in) -> Input
|
|
{
|
|
Input results {};
|
|
std::for_each(
|
|
std::istream_iterator<std::string>{in},
|
|
std::istream_iterator<std::string>{},
|
|
[&](std::string line) {
|
|
results.push_back(std::stoul(line));
|
|
}
|
|
);
|
|
return results;
|
|
}
|
|
|
|
auto Next(std::uint32_t x) -> std::uint32_t
|
|
{
|
|
x = (x ^ (x << 6)) & 0xffffff;
|
|
x = (x ^ (x >> 5)) & 0xffffff;
|
|
x = (x ^ (x << 11)) & 0xffffff;
|
|
return x;
|
|
}
|
|
|
|
auto Solve(Input entries) -> std::pair<std::uint64_t, std::uint64_t>
|
|
{
|
|
std::vector<std::uint32_t> patterns(std::size(entries));
|
|
std::vector<std::uint64_t> counts(19*19*19*19);
|
|
std::vector<bool> seen(std::size(entries)*19*19*19*19);
|
|
|
|
for (std::size_t i = 0; i < 3; ++i) {
|
|
for (std::size_t j = 0; j < entries.size(); ++j) {
|
|
auto const x = entries[j];
|
|
auto const y = Next(x);
|
|
entries[j] = y;
|
|
patterns[j] = patterns[j] * 19 + y%10 + 9 - x%10;
|
|
}
|
|
}
|
|
|
|
for (std::size_t i = 3; i < 2'000; ++i) {
|
|
for (std::size_t j = 0; j < entries.size(); ++j) {
|
|
auto const x = entries[j];
|
|
auto const y = Next(x);
|
|
entries[j] = y;
|
|
auto const p = patterns[j] % (19 * 19 * 19) * 19 + y%10 + 9 - x%10;
|
|
patterns[j] = p;
|
|
if (!seen[j * 19 * 19 * 19 * 19 + p]) {
|
|
seen[j * 19 * 19 * 19 * 19 + p] = true;
|
|
counts[p] += y%10;
|
|
}
|
|
}
|
|
}
|
|
|
|
auto const p1 = std::accumulate(begin(entries), end(entries), std::uint64_t{0});
|
|
auto const p2 = *std::max_element(begin(counts), end(counts));
|
|
return {p1, p2};
|
|
}
|
|
|
|
|
|
} // namespace
|
|
|
|
auto Main(std::istream & in, std::ostream & out) -> void
|
|
{
|
|
auto entries = Parse(in);
|
|
auto const [p1, p2] = Solve(std::move(entries));
|
|
out << "Part 1: " << p1 << "\n"
|
|
<< "Part 2: " << p2 << "\n";
|
|
}
|