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
15const BUCKETS: usize = 5;
16const SIZE: usize = 10_000 * 10_000;
17
18pub fn parse(input: &str) -> Input {
19    let boxes: Vec<_> = input.iter_unsigned::<usize>().chunk::<3>().collect();
20    let items: Vec<_> = (0..boxes.len()).collect();
21    let mut buckets = vec![vec![]; BUCKETS];
22
23    for result in spawn_parallel_iterator(&items, |iter| worker(&boxes, iter)) {
24        for (bucket, pairs) in buckets.iter_mut().zip(result) {
25            bucket.push(pairs);
26        }
27    }
28
29    (boxes, buckets)
30}
31
32pub fn part1(input: &Input) -> usize {
33    part1_testable(input, 1000)
34}
35
36pub fn part1_testable(input: &Input, limit: usize) -> usize {
37    let (boxes, buckets) = input;
38    let mut nodes: Vec<_> = (0..boxes.len()).map(|i| Node { parent: i, size: 1 }).collect();
39
40    for (i, j, ..) in flatten(buckets).take(limit) {
41        union(&mut nodes, i as usize, j as usize);
42    }
43
44    nodes.sort_unstable_by_key(|node| node.size);
45    nodes.iter().rev().take(3).map(|node| node.size).product()
46}
47
48pub fn part2(input: &Input) -> usize {
49    let (boxes, buckets) = input;
50    let mut nodes: Vec<_> = (0..boxes.len()).map(|i| Node { parent: i, size: 1 }).collect();
51
52    for (i, j, ..) in flatten(buckets) {
53        let (i, j) = (i as usize, j as usize);
54
55        if union(&mut nodes, i, j) == boxes.len() {
56            return boxes[i][0] * boxes[j][0];
57        }
58    }
59
60    unreachable!()
61}
62
63fn worker(boxes: &[Box], iter: ParIter<'_, usize>) -> Vec<Vec<Pair>> {
64    let mut buckets = vec![vec![]; BUCKETS];
65
66    for &i in iter {
67        let v1 = boxes[i];
68
69        for (j, &v2) in boxes.iter().enumerate().skip(i + 1) {
70            let dx = v1[0].abs_diff(v2[0]);
71            let dy = v1[1].abs_diff(v2[1]);
72            let dz = v1[2].abs_diff(v2[2]);
73            let distance = dx * dx + dy * dy + dz * dz;
74
75            let index = (distance / SIZE).min(BUCKETS - 1);
76            buckets[index].push((i as u16, j as u16, distance));
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
