bpavuk.neocities.org
Advent of Code 2025, done in C++
1#include <algorithm>
2#include <cmath>
3#include <fstream>
4#include <iterator>
5#include <map>
6#include <print>
7#include <ranges>
8#include <set>
9#include <vector>
10
11#include "common/getinputpath.h"
12#include "common/istest.h"
13
14const int STEPS = is_test() ? 10 : 1000;
15
16struct Box {
17 int x;
18 int y;
19 int z;
20
21 float euclidean(Box& other) {
22 return std::sqrt(std::pow((other.x - this->x), 2) +
23 std::pow((other.y - this->y), 2) +
24 std::pow((other.z - this->z), 2));
25 }
26
27 bool operator==(const Box other) const {
28 return this->x == other.x && this->y == other.y && this->z == other.z;
29 }
30
31 bool operator<(const Box other) const {
32 return this->x < other.x || (this->x == other.x && this->y < other.y) ||
33 (this->x == other.x && this->y == other.y && this->z < other.z);
34 }
35
36 std::string to_string() { return std::format("{} {} {}", x, y, z); }
37};
38
39struct Connection {
40 Box a;
41 Box b;
42 float distance;
43
44 bool operator==(const Connection& other) const {
45 return (other.a == this->a && other.b == this->b) ||
46 (other.a == this->b && other.b == this->a);
47 }
48
49 bool contains(Box box) { return this->a == box || this->b == box; }
50
51 bool connected(Connection connection) {
52 return this->contains(connection.a) || this->contains(connection.b);
53 }
54
55 bool operator<(const Connection other) const {
56 return this->distance < other.distance;
57 }
58};
59
60Connection make_connection(Box& one, Box& other) {
61 return Connection{.a = one, .b = other, .distance = one.euclidean(other)};
62}
63
64// standard DSU
65class DSU {
66 std::vector<int> size{};
67 std::vector<int> parent{};
68
69 public:
70 DSU(int n) {
71 parent.resize(n);
72 size.resize(n);
73
74 for (int i = 0; i < n; ++i) {
75 parent[i] = i;
76 size[i] = 1;
77 }
78 }
79
80 int find(int i) {
81 return (parent[i] == i) ? i : (parent[i] = find(parent[i]));
82 }
83
84 void unite(int x, int y) {
85 int s1 = find(x);
86 int s2 = find(y);
87
88 if (s1 == s2) {
89 return;
90 }
91 if (size[s1] < size[s2]) {
92 parent[s1] = s2;
93 size[s2] += size[s1];
94 } else if (size[s1] > size[s2]) {
95 parent[s2] = s1;
96 size[s1] += size[s2];
97 } else {
98 parent[s2] = s1;
99 size[s1] += size[s2];
100 }
101 }
102
103 std::vector<int> sizes() { return size; }
104};
105
106int main() {
107 auto path = get_input_path(DATA_FOLDER);
108 std::ifstream data_ifstream(path);
109 if (!data_ifstream.is_open()) {
110 std::println("Cannot open the file at {}", path.string());
111 return 1;
112 }
113
114 std::vector<Box> data{};
115 for (std::string t; std::getline(data_ifstream, t);) {
116 int x{};
117 int y{};
118 int z{};
119
120 auto first_comma_idx = t.find_first_of(',');
121 auto x_str = t.substr(0, first_comma_idx);
122 auto yz_str = t.substr(first_comma_idx + 1);
123 auto second_comma_idx = yz_str.find_first_of(',');
124 auto y_str = yz_str.substr(0, second_comma_idx);
125 auto z_str = yz_str.substr(second_comma_idx + 1);
126
127 x = std::stoi(x_str);
128 y = std::stoi(y_str);
129 z = std::stoi(z_str);
130
131 data.push_back(Box{.x = x, .y = y, .z = z});
132 }
133
134 long long estimated_conns = data.size() * data.size() - data.size();
135 std::print("Generating connections... est. {}", estimated_conns);
136
137 // replacing this with an unordered set would make things faster
138 std::set<Connection> connections{};
139 for (auto box1 : data) {
140 for (auto box2 : data) {
141 if (box1 == box2) {
142 continue;
143 }
144
145 Connection conn = make_connection(box1, box2);
146 if (connections.contains(conn)) { // connection already exists
147 continue;
148 }
149 connections.insert(conn);
150 std::print("\r");
151 }
152 }
153 std::println();
154
155 std::println("Sorting connections...");
156 std::vector<Connection> connections_vec =
157 connections | std::ranges::to<std::vector<Connection>>();
158 std::ranges::sort(connections_vec, [](Connection one, Connection other) {
159 return one.distance < other.distance;
160 });
161
162 std::println("Calculating three largest connected components...");
163 DSU dsu(data.size());
164
165 std::map<Box, size_t> data_idxs{};
166 for (auto [idx, box] : data | std::ranges::views::enumerate) {
167 data_idxs[box] = idx;
168 }
169
170 long long counter = 0;
171 Connection last_connected;
172 long long password_part_1;
173 for (auto conn : connections_vec) {
174 counter += 1;
175 if (dsu.find(data_idxs[conn.a]) != dsu.find(data_idxs[conn.b])) {
176 dsu.unite(data_idxs[conn.a], data_idxs[conn.b]);
177 last_connected = conn;
178 }
179 if (counter == STEPS) {
180 auto sizes = dsu.sizes();
181 std::ranges::sort(sizes);
182 std::ranges::reverse(sizes);
183
184 std::println("Three biggest: {}, {}, {}", sizes[0], sizes[1],
185 sizes[2]);
186 int s1 = sizes[0];
187 int s2 = sizes[1];
188 int s3 = sizes[2];
189 password_part_1 = s1 * s2 * s3;
190 }
191 }
192
193 long long password_part_2 = last_connected.a.x * last_connected.b.x;
194
195 std::println();
196 std::println("Eureka! {} / {}", password_part_1, password_part_2);
197
198 return 0;
199}