year2025/
day08.rs

1use std::ops::ControlFlow;
2use utils::disjoint_set::Dsu;
3use utils::geometry::Vec3;
4use utils::prelude::*;
5
6/// Connecting the nearest 3D points to form a connected graph.
7#[derive(Clone, Debug)]
8pub struct Day08 {
9    points: Vec<Vec3<u32>>,
10    subdivisions: Vec<Vec<u32>>,
11    part1_limit: usize,
12}
13
14const MAX_COORD: u32 = 99999;
15const SUBDIVISIONS: usize = 6;
16const TOTAL_SUBDIVISIONS: usize = SUBDIVISIONS * SUBDIVISIONS * SUBDIVISIONS;
17const SUBDIVISION_WIDTH: usize = (MAX_COORD as usize + 1).div_ceil(SUBDIVISIONS);
18const SUBDIVISION_WIDTH2: usize = SUBDIVISION_WIDTH * SUBDIVISION_WIDTH;
19
20// [(min euclidian distance between subdivisions, slice of subdivision offsets)]
21const DISTANCE_TIER_OFFSETS: &[(usize, &[Vec3<i8>])] = {
22    const fn compute_offsets<const N: usize>(tier: u32) -> [Vec3<i8>; N] {
23        let max_abs = (tier.isqrt() + 1) as i8;
24
25        let mut result = [Vec3::ORIGIN; N];
26        let mut i = 0usize;
27
28        // Only generate offsets where the second subdivision has a greater index, so that each
29        // subdivision pair is only checked once
30        let mut dz = 0;
31        while dz <= max_abs {
32            let mut dy = if dz == 0 { 0 } else { -max_abs };
33            while dy <= max_abs {
34                let mut dx = if dz == 0 && dy == 0 { 1 } else { -max_abs };
35                while dx <= max_abs {
36                    let min_dist_x = dx.unsigned_abs().saturating_sub(1) as u32;
37                    let min_dist_y = dy.unsigned_abs().saturating_sub(1) as u32;
38                    let min_dist_z = dz.unsigned_abs().saturating_sub(1) as u32;
39                    let min_dist2 =
40                        min_dist_x * min_dist_x + min_dist_y * min_dist_y + min_dist_z * min_dist_z;
41
42                    if tier == min_dist2 {
43                        result[i] = Vec3::new(dx, dy, dz);
44                        i += 1;
45                    }
46                    dx += 1;
47                }
48                dy += 1;
49            }
50            dz += 1;
51        }
52
53        assert!(i == N);
54        result
55    }
56
57    &[
58        // 3x |d|<=1
59        (0, &compute_offsets::<13>(0)),
60        // 1x |d|=2, 2x |d|<=1
61        (SUBDIVISION_WIDTH2, &compute_offsets::<27>(1)),
62        // 2x |d|=2, 1x |d|<=1
63        (2 * SUBDIVISION_WIDTH2, &compute_offsets::<18>(2)),
64        // 3x |d|=2
65        (3 * SUBDIVISION_WIDTH2, &compute_offsets::<4>(3)),
66        // 1x |d|=3, 2x |d|<=1
67        (4 * SUBDIVISION_WIDTH2, &compute_offsets::<27>(4)),
68        // 1x |d|=3, 1x |d|=2, 1x |d|<=1
69        (5 * SUBDIVISION_WIDTH2, &compute_offsets::<36>(5)),
70        // 1x |d|=3, 2x |d|=2
71        (6 * SUBDIVISION_WIDTH2, &compute_offsets::<12>(6)),
72        // Impossible
73        (7 * SUBDIVISION_WIDTH2, &compute_offsets::<0>(7)),
74        // 2x |d|=3, 1x |d|<=1
75        (8 * SUBDIVISION_WIDTH2, &compute_offsets::<18>(8)),
76        // 2x |d|=3, 1x |d|=2 OR 1x |d|=4, 2x |d|<=1
77        (9 * SUBDIVISION_WIDTH2, &compute_offsets::<39>(9)),
78        // 1x |d|=4, 1x |d|=2, 1x |d|<=1
79        (10 * SUBDIVISION_WIDTH2, &compute_offsets::<36>(10)),
80        // 1x |d|=4, 2x |d|=2
81        (11 * SUBDIVISION_WIDTH2, &compute_offsets::<12>(11)),
82        // 3x |d|=3
83        (12 * SUBDIVISION_WIDTH2, &compute_offsets::<4>(12)),
84    ]
85};
86
87// DISTANCE_TIER_OFFSETS is truncated and doesn't include every possible distance/subdivision offset
88const MAX_DISTANCE_CHECKED: usize = (DISTANCE_TIER_OFFSETS.len() * SUBDIVISION_WIDTH2).isqrt();
89
90impl Day08 {
91    pub fn new(input: &str, input_type: InputType) -> Result<Self, InputError> {
92        let points = parser::number_range(0..=MAX_COORD)
93            .repeat_n(b',')
94            .map(Vec3::from)
95            .parse_lines(input)?;
96
97        if points.len() > u32::MAX as usize {
98            return Err(InputError::new(input, 0, "too many points"));
99        }
100
101        let mut subdivisions = vec![Vec::new(); TOTAL_SUBDIVISIONS];
102        for (i, p) in points.iter().enumerate() {
103            let sub_coords = p.map(|x| x as usize / SUBDIVISION_WIDTH);
104            subdivisions[Self::subdivision_index(sub_coords)].push(i as u32);
105        }
106
107        Ok(Self {
108            points,
109            subdivisions,
110            part1_limit: match input_type {
111                InputType::Example => 10,
112                InputType::Real => 1000,
113            },
114        })
115    }
116
117    #[must_use]
118    pub fn part1(&self) -> u64 {
119        let mut dsu = Dsu::new(self.points.len());
120        let mut remaining_edges = self.part1_limit;
121        self.for_each_sorted_edge(
122            |_, i, j| {
123                let _ = dsu.union(i, j);
124                remaining_edges -= 1;
125                if remaining_edges == 0 {
126                    ControlFlow::Break(())
127                } else {
128                    ControlFlow::Continue(())
129                }
130            },
131            self.part1_limit,
132        );
133
134        let mut component_sizes: Vec<_> = dsu.roots().map(|x| dsu.root_size(x) as u64).collect();
135        component_sizes.select_nth_unstable_by(2, |a, b| b.cmp(a));
136        component_sizes.iter().take(3).product()
137    }
138
139    #[must_use]
140    pub fn part2(&self) -> u64 {
141        let mut dsu = Dsu::new(self.points.len());
142        let mut remaining_merges = self.points.len() - 1;
143
144        self.for_each_sorted_edge(
145            |_, i, j| {
146                if dsu.union(i, j) {
147                    remaining_merges -= 1;
148                    if remaining_merges == 0 {
149                        return ControlFlow::Break(
150                            self.points[i].x as u64 * self.points[j].x as u64,
151                        );
152                    }
153                }
154                ControlFlow::Continue(())
155            },
156            usize::MAX,
157        )
158    }
159
160    #[inline]
161    fn for_each_sorted_edge<T>(
162        &self,
163        mut f: impl FnMut(i64, usize, usize) -> ControlFlow<T>,
164        mut limit: usize,
165    ) -> T {
166        let mut edges = Vec::new();
167        let mut next_edges = Vec::new();
168
169        for &(min_dist2, offsets) in DISTANCE_TIER_OFFSETS.iter() {
170            let max_dist2 = min_dist2 + SUBDIVISION_WIDTH2;
171
172            // Move edges now below max_dist2 from next_edges to edges
173            next_edges.retain(|&(dist2, i, j)| {
174                if dist2 < max_dist2 as i64 {
175                    edges.push((dist2, i, j));
176                    false
177                } else {
178                    true
179                }
180            });
181
182            // Push the pair to edges if its distance is within the current tier
183            let mut process_pair = |i: u32, j: u32| {
184                let dist2 = self.points[i as usize]
185                    .cast::<i64>()
186                    .squared_euclidean_distance_to(self.points[j as usize].cast());
187
188                if dist2 < max_dist2 as i64 {
189                    edges.push((dist2, i, j));
190                } else if edges.len() < limit {
191                    // Only store pairs for the next tier if the current tier hasn't already reached
192                    // the provided limit
193                    next_edges.push((dist2, i, j));
194                }
195            };
196
197            // Check all point pairs within subdivision pairs at the current tier
198            for sub1 in 0..self.subdivisions.len() {
199                if min_dist2 == 0 {
200                    // Try pairs within the current subdivision
201                    for (n, &i) in self.subdivisions[sub1].iter().enumerate() {
202                        for &j in self.subdivisions[sub1].iter().skip(n + 1) {
203                            process_pair(i, j);
204                        }
205                    }
206                }
207
208                let sub1_coords = Self::subdivision_coords(sub1);
209                for offset in offsets.iter() {
210                    let sub2_coords = sub1_coords.wrapping_add_signed(offset.cast());
211                    if sub2_coords.x >= SUBDIVISIONS
212                        || sub2_coords.y >= SUBDIVISIONS
213                        || sub2_coords.z >= SUBDIVISIONS
214                    {
215                        continue;
216                    }
217
218                    let sub2 = Self::subdivision_index(sub2_coords);
219
220                    for &i in self.subdivisions[sub1].iter() {
221                        for &j in self.subdivisions[sub2].iter() {
222                            process_pair(i, j);
223                        }
224                    }
225                }
226            }
227
228            if edges.len() > limit {
229                edges.select_nth_unstable_by(limit - 1, |(a, _, _), (b, _, _)| a.cmp(b));
230                edges.truncate(limit);
231            }
232
233            edges.sort_unstable_by_key(|(a, _, _)| *a);
234            limit -= edges.len();
235
236            for &(d, i, j) in edges.iter() {
237                if let ControlFlow::Break(result) = f(d, i as usize, j as usize) {
238                    return result;
239                }
240            }
241
242            assert!(
243                limit > 0,
244                "f should return break at or before the provided limit"
245            );
246            edges.clear();
247        }
248
249        panic!("no solution found after checking all pairs within {MAX_DISTANCE_CHECKED} distance");
250    }
251
252    #[inline]
253    fn subdivision_index(c: Vec3<usize>) -> usize {
254        c.x + c.y * SUBDIVISIONS + c.z * SUBDIVISIONS * SUBDIVISIONS
255    }
256
257    #[inline]
258    fn subdivision_coords(i: usize) -> Vec3<usize> {
259        let x = i % SUBDIVISIONS;
260        let y = (i / SUBDIVISIONS) % SUBDIVISIONS;
261        let z = i / SUBDIVISIONS / SUBDIVISIONS;
262        Vec3::new(x, y, z)
263    }
264}
265
266examples!(Day08 -> (u64, u64) [
267    {file: "day08_example0.txt", part1: 40, part2: 25272},
268]);
year2025/day08.rs

year2025/
day08.rs
