1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

//! # Four-Dimensional Adventure
//!
//! This problem is the classic [union find](https://en.wikipedia.org/wiki/Disjoint-set_data_structure).
//! However since we only need the *count* of the distinct sets we can use a much simpler approach.
//!
//! Starting with an arbitrary point we find all other points within range, adding them to a
//! todo list. We then transitively determine the neighbors of those points, and so on until
//! all sets have been found.
use crate::util::iter::*;
use crate::util::parse::*;

#[derive(Clone, Copy)]
pub struct Point {
    x: i32,
    y: i32,
    z: i32,
    w: i32,
}

/// Simple 4D point implementation with Manhattan distance.
impl Point {
    fn from([x, y, z, w]: [i32; 4]) -> Self {
        Point { x, y, z, w }
    }

    fn mahattan(&self, other: Self) -> i32 {
        (self.x - other.x).abs()
            + (self.y - other.y).abs()
            + (self.z - other.z).abs()
            + (self.w - other.w).abs()
    }
}

pub fn parse(input: &str) -> Vec<Point> {
    input.iter_signed::<i32>().chunk::<4>().map(Point::from).collect()
}

pub fn part1(input: &[Point]) -> usize {
    let mut constellations = 0;
    let mut remaining = input.to_vec();
    let mut todo = Vec::with_capacity(input.len());

    // Choose arbitrary point and start a new constellation.
    while let Some(start) = remaining.pop() {
        constellations += 1;
        todo.push(start);

        while let Some(point) = todo.pop() {
            let mut i = 0;

            // Find all neighbors, adding them to `todo` in order to transitively find all
            // other points in the constellation.
            while i < remaining.len() {
                if point.mahattan(remaining[i]) <= 3 {
                    todo.push(remaining.swap_remove(i));
                } else {
                    i += 1;
                }
            }
        }
    }

    constellations
}

pub fn part2(_input: &[Point]) -> &'static str {
    "n/a"
}