Line data Source code
1 : #include "PuzzleImpl.h"
2 :
3 : #include "IntegerCast.h"
4 : #include "Vector.h"
5 : #include "Views.h"
6 :
7 : #include <re2/re2.h>
8 :
9 : #include <algorithm>
10 : #include <numeric>
11 : #include <queue>
12 : #include <string_view>
13 : #include <vector>
14 :
15 : namespace {
16 :
17 : using NodePos = Vector<3, int64_t>;
18 :
19 2995618 : int64_t sqDistance(NodePos const &a, NodePos const &b) {
20 2995618 : int64_t dist = 0;
21 11982472 : for (size_t i = 0; i < 3; ++i) {
22 8986854 : int64_t const diff = integerCast<int64_t>(a[i]) - integerCast<int64_t>(b[i]);
23 8986854 : dist += diff * diff;
24 8986854 : }
25 2995618 : return dist;
26 2995618 : }
27 :
28 2 : std::vector<NodePos> parseInput(std::string_view const input) {
29 2000 : return input | views::splitLines | std::views::transform([](std::string_view line) {
30 2000 : static RE2 const regex = R"((\d+),(\d+),(\d+))";
31 2000 : NodePos point;
32 2000 : ASSERT(RE2::FullMatch(line, regex, &point[0], &point[1], &point[2]));
33 2000 : return point;
34 2000 : }) |
35 2 : std::ranges::to<std::vector<NodePos>>();
36 2 : }
37 :
38 : using Edge = std::pair<unsigned, unsigned>;
39 :
40 2 : std::vector<Edge> buildEdges(size_t const numNodes) {
41 2 : std::vector<Edge> edges;
42 2 : edges.reserve(numNodes * (numNodes - 1) / 2);
43 2002 : for (unsigned i = 0; i < numNodes; ++i) {
44 1001000 : for (unsigned j = i + 1; j < numNodes; ++j) {
45 999000 : edges.emplace_back(i, j);
46 999000 : }
47 2000 : }
48 2 : return edges;
49 2 : }
50 :
51 : unsigned constexpr root = std::numeric_limits<unsigned>::max();
52 :
53 : struct Node {
54 1000 : [[nodiscard]] bool isRoot() const { return parent == root; }
55 :
56 : unsigned parent = root;
57 : unsigned size = 1;
58 : };
59 :
60 : class Forest {
61 : public:
62 2 : Forest(size_t numNodes) : _nodes(numNodes) {}
63 :
64 5933 : Node const &operator[](unsigned const i) const { return _nodes[i]; }
65 :
66 5660 : [[nodiscard]] unsigned size() const { return _nodes.size(); }
67 :
68 21515 : [[nodiscard]] unsigned find(unsigned const nodeIdx) {
69 21515 : if (_nodes[nodeIdx].parent == root) {
70 11314 : return nodeIdx;
71 11314 : }
72 10201 : unsigned const rootIdx = find(_nodes[nodeIdx].parent);
73 10201 : _nodes[nodeIdx].parent = rootIdx;
74 10201 : return rootIdx;
75 21515 : }
76 :
77 5657 : unsigned merge(unsigned const x, unsigned const y) {
78 5657 : unsigned const rootX = find(x);
79 5657 : unsigned const rootY = find(y);
80 5657 : if (rootX == rootY) {
81 3934 : return rootX;
82 3934 : }
83 1723 : if (_nodes[rootX].size >= _nodes[rootY].size) {
84 1132 : _nodes[rootY].parent = rootX;
85 1132 : _nodes[rootX].size += _nodes[rootY].size;
86 1132 : return rootX;
87 1132 : } else {
88 591 : _nodes[rootX].parent = rootY;
89 591 : _nodes[rootY].size += _nodes[rootX].size;
90 591 : return rootY;
91 591 : }
92 1723 : }
93 :
94 : private:
95 : std::vector<Node> _nodes;
96 : };
97 :
98 : } // namespace
99 :
100 1 : template <> std::string solvePart1<2025, 8>(std::string_view const input) {
101 1 : std::vector<NodePos> nodesPos = parseInput(input);
102 1 : Forest forest(nodesPos.size());
103 :
104 1 : std::vector<Edge> edges = buildEdges(forest.size());
105 :
106 582204 : auto edgeCompare = [&](Edge const &a, Edge const &b) {
107 582204 : return sqDistance(nodesPos[a.first], nodesPos[a.second]) <
108 582204 : sqDistance(nodesPos[b.first], nodesPos[b.second]);
109 582204 : };
110 :
111 1 : auto const first1000It =
112 1 : std::next(edges.begin(), integerCast<std::ptrdiff_t>(std::min(size_t{1000}, edges.size())));
113 1 : std::ranges::partial_sort(edges, first1000It, edgeCompare);
114 :
115 1001 : for (auto it = edges.begin(); it != first1000It; ++it) {
116 1000 : auto const &[u, v] = *it;
117 1000 : forest.merge(u, v);
118 1000 : }
119 :
120 1 : std::vector<unsigned> rootSizes;
121 1001 : for (unsigned i = 0; i < forest.size(); ++i) {
122 1000 : if (forest[i].isRoot()) {
123 276 : rootSizes.push_back(forest[i].size);
124 276 : }
125 1000 : }
126 :
127 1 : auto const top3It = std::next(rootSizes.begin(),
128 1 : integerCast<std::ptrdiff_t>(std::min(size_t{3}, rootSizes.size())));
129 1 : std::ranges::partial_sort(rootSizes, top3It, std::greater{});
130 :
131 1 : return std::to_string(std::accumulate(rootSizes.begin(), top3It, uint64_t{1}, std::multiplies{}));
132 1 : }
133 :
134 1 : template <> std::string solvePart2<2025, 8>(std::string_view const input) {
135 1 : std::vector<NodePos> nodesPos = parseInput(input);
136 1 : Forest forest(nodesPos.size());
137 :
138 915605 : auto edgeCompare = [&](Edge const &a, Edge const &b) {
139 915605 : return sqDistance(nodesPos[a.first], nodesPos[a.second]) >
140 915605 : sqDistance(nodesPos[b.first], nodesPos[b.second]);
141 915605 : };
142 :
143 1 : std::priority_queue<Edge, std::vector<Edge>, decltype(edgeCompare)> edges(
144 1 : edgeCompare, buildEdges(forest.size()));
145 :
146 4657 : while (!edges.empty()) {
147 4657 : auto const &[u, v] = edges.top();
148 4657 : edges.pop();
149 4657 : unsigned const newRoot = forest.merge(u, v);
150 4657 : if (forest[newRoot].size == forest.size()) {
151 1 : return std::to_string(nodesPos[u].x() * nodesPos[v].x());
152 1 : }
153 4657 : }
154 :
155 0 : return "";
156 1 : }
|
