aoc/year2018/
day25.rs

1//! # Four-Dimensional Adventure
2//!
3//! This problem is the classic [union find](https://en.wikipedia.org/wiki/Disjoint-set_data_structure).
4//! However since we only need the *count* of the distinct sets we can use a much simpler approach.
5//!
6//! Starting with an arbitrary point we find all other points within range, adding them to a
7//! todo list. We then transitively determine the neighbors of those points, and so on until
8//! all sets have been found.
9use crate::util::iter::*;
10use crate::util::parse::*;
11
12#[derive(Clone, Copy)]
13pub struct Point {
14    x: i32,
15    y: i32,
16    z: i32,
17    w: i32,
18}
19
20/// Simple 4D point implementation with Manhattan distance.
21impl Point {
22    fn from([x, y, z, w]: [i32; 4]) -> Self {
23        Point { x, y, z, w }
24    }
25
26    fn mahattan(&self, other: Self) -> i32 {
27        (self.x - other.x).abs()
28            + (self.y - other.y).abs()
29            + (self.z - other.z).abs()
30            + (self.w - other.w).abs()
31    }
32}
33
34pub fn parse(input: &str) -> Vec<Point> {
35    input.iter_signed::<i32>().chunk::<4>().map(Point::from).collect()
36}
37
38pub fn part1(input: &[Point]) -> usize {
39    let mut constellations = 0;
40    let mut remaining = input.to_vec();
41    let mut todo = Vec::with_capacity(input.len());
42
43    // Choose arbitrary point and start a new constellation.
44    while let Some(start) = remaining.pop() {
45        constellations += 1;
46        todo.push(start);
47
48        while let Some(point) = todo.pop() {
49            let mut i = 0;
50
51            // Find all neighbors, adding them to `todo` in order to transitively find all
52            // other points in the constellation.
53            while i < remaining.len() {
54                if point.mahattan(remaining[i]) <= 3 {
55                    todo.push(remaining.swap_remove(i));
56                } else {
57                    i += 1;
58                }
59            }
60        }
61    }
62
63    constellations
64}
65
66pub fn part2(_input: &[Point]) -> &'static str {
67    "n/a"
68}
aoc/year2018/day25.rs

aoc/year2018/
day25.rs
