aoc/year2025/
day08.rs

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

aoc/year2025/
day08.rs
