aoc/year2025/
day08.rs

1//! # Playground
2use crate::util::iter::*;
3use crate::util::parse::*;
4use crate::util::thread::*;
5
6type Box = [usize; 3];
7type Pair = (u16, u16, usize);
8type Input = (Vec<Box>, Vec<Vec<Vec<Pair>>>);
9
10struct Node {
11    parent: usize,
12    size: usize,
13}
14
15/// Since the input is rather uniformly spaced, we assume that any two points further apart
16/// than 4*size will eventually be connected by some point in between.
17const BUCKETS: usize = 4;
18const SIZE: usize = 10_000 * 10_000;
19
20pub fn parse(input: &str) -> Input {
21    let boxes: Vec<_> = input.iter_unsigned::<usize>().chunk::<3>().collect();
22    let items: Vec<_> = (0..boxes.len()).collect();
23    let mut buckets = vec![vec![]; BUCKETS];
24
25    for result in spawn_parallel_iterator(&items, |iter| worker(&boxes, iter)) {
26        for (bucket, pairs) in buckets.iter_mut().zip(result) {
27            bucket.push(pairs);
28        }
29    }
30
31    (boxes, buckets)
32}
33
34pub fn part1(input: &Input) -> usize {
35    part1_testable(input, 1000)
36}
37
38pub fn part1_testable(input: &Input, limit: usize) -> usize {
39    let (boxes, buckets) = input;
40    let mut nodes: Vec<_> = (0..boxes.len()).map(|i| Node { parent: i, size: 1 }).collect();
41
42    for (i, j, ..) in flatten(buckets).take(limit) {
43        union(&mut nodes, i as usize, j as usize);
44    }
45
46    nodes.sort_unstable_by_key(|node| node.size);
47    nodes.iter().rev().take(3).map(|node| node.size).product()
48}
49
50pub fn part2(input: &Input) -> usize {
51    let (boxes, buckets) = input;
52    let mut nodes: Vec<_> = (0..boxes.len()).map(|i| Node { parent: i, size: 1 }).collect();
53
54    for (i, j, ..) in flatten(buckets) {
55        let (i, j) = (i as usize, j as usize);
56
57        if union(&mut nodes, i, j) == boxes.len() {
58            return boxes[i][0] * boxes[j][0];
59        }
60    }
61
62    unreachable!()
63}
64
65fn worker(boxes: &[Box], iter: ParIter<'_, usize>) -> Vec<Vec<Pair>> {
66    let mut buckets = vec![vec![]; BUCKETS];
67
68    for &i in iter {
69        let v1 = boxes[i];
70
71        for (j, &v2) in boxes.iter().enumerate().skip(i + 1) {
72            let dx = v1[0].abs_diff(v2[0]);
73            let dy = v1[1].abs_diff(v2[1]);
74            let dz = v1[2].abs_diff(v2[2]);
75            let distance = dx * dx + dy * dy + dz * dz;
76
77            let index = distance / SIZE;
78            if index < BUCKETS {
79                buckets[index].push((i as u16, j as u16, distance));
80            }
81        }
82    }
83
84    buckets
85}
86
87fn flatten(buckets: &[Vec<Vec<Pair>>]) -> impl Iterator<Item = Pair> {
88    buckets.iter().flat_map(|pairs| {
89        let mut merged = pairs.concat();
90        merged.sort_unstable_by_key(|&(.., distance)| distance);
91        merged
92    })
93}
94
95fn find(set: &mut [Node], mut x: usize) -> usize {
96    while set[x].parent != x {
97        let parent = set[x].parent;
98        (x, set[x].parent) = (parent, set[parent].parent);
99    }
100
101    x
102}
103
104fn union(set: &mut [Node], mut x: usize, mut y: usize) -> usize {
105    x = find(set, x);
106    y = find(set, y);
107
108    if x != y {
109        if set[x].size < set[y].size {
110            (x, y) = (y, x);
111        }
112
113        set[y].parent = x;
114        set[x].size += set[y].size;
115    }
116
117    set[x].size
118}
aoc/year2025/day08.rs

aoc/year2025/
day08.rs
