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::<usize>().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    for (i, j, ..) in flatten(buckets) {
54        let (i, j) = (i as usize, j as usize);
55
56        if union(&mut nodes, i, j) == boxes.len() {
57            return boxes[i][0] * boxes[j][0];
58        }
59    }
60
61    unreachable!()
62}
63
64fn worker(boxes: &[Box], iter: ParIter<'_, Box>) -> Vec<Vec<Pair>> {
65    let mut buckets = vec![Vec::new(); BUCKETS];
66
67    for v1 in iter {
68        let i = boxes.element_offset(v1).unwrap();
69
70        for (j, &v2) in boxes.iter().enumerate().skip(i + 1) {
71            let dx = v1[0].abs_diff(v2[0]);
72            let dy = v1[1].abs_diff(v2[1]);
73            let dz = v1[2].abs_diff(v2[2]);
74            let distance = dx * dx + dy * dy + dz * dz;
75
76            let index = distance / SIZE;
77            if index < BUCKETS {
78                buckets[index].push((i as u16, j as u16, distance));
79            }
80        }
81    }
82
83    buckets
84}
85
86fn flatten(buckets: &[Vec<Vec<Pair>>]) -> impl Iterator<Item = Pair> {
87    buckets.iter().flat_map(|pairs| {
88        let mut merged = pairs.concat();
89        merged.sort_unstable_by_key(|&(.., distance)| distance);
90        merged
91    })
92}
93
94fn find(set: &mut [Node], mut x: usize) -> usize {
95    while set[x].parent != x {
96        let parent = set[x].parent;
97        (x, set[x].parent) = (parent, set[parent].parent);
98    }
99
100    x
101}
102
103fn union(set: &mut [Node], mut x: usize, mut y: usize) -> usize {
104    x = find(set, x);
105    y = find(set, y);
106
107    if x != y {
108        if set[x].size < set[y].size {
109            (x, y) = (y, x);
110        }
111
112        set[y].parent = x;
113        set[x].size += set[y].size;
114    }
115
116    set[x].size
117}
aoc/year2025/day08.rs

aoc/year2025/
day08.rs
