year2018/
day25.rs

1use utils::geometry::Vec4;
2use utils::prelude::*;
3
4/// Clustering points within Manhattan distance.
5#[derive(Clone, Debug)]
6pub struct Day25 {
7    points: Vec<Vec4<i32>>,
8}
9
10impl Day25 {
11    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
12        let mut points = parser::i32()
13            .repeat_n(b',')
14            .map(Vec4::from)
15            .parse_lines(input)?;
16
17        points.sort_unstable_by_key(|p| p.x);
18
19        Ok(Self { points })
20    }
21
22    #[must_use]
23    pub fn part1(&self) -> u32 {
24        let mut remaining = self.points.clone();
25        let mut to_visit = Vec::with_capacity(remaining.len());
26        let mut constellations = 0;
27        while let Some(start) = remaining.pop() {
28            to_visit.push(start);
29            while let Some(point) = to_visit.pop() {
30                // Use binary search to only check points in range on the x-axis.
31                // This requires keeping the remaining points sorted (instead of using swap_remove)
32                let start = remaining.partition_point(|p| p.x < point.x - 3);
33                let end = remaining.partition_point(|p| p.x <= point.x + 3);
34
35                to_visit.extend(
36                    remaining.extract_if(start..end, |p| p.manhattan_distance_to(point) <= 3),
37                );
38            }
39            constellations += 1;
40        }
41        constellations
42    }
43
44    #[must_use]
45    pub fn part2(&self) -> &'static str {
46        "🎄"
47    }
48}
49
50examples!(Day25 -> (u32, &'static str) [
51    {file: "day25_example0.txt", part1: 4},
52    {file: "day25_example1.txt", part1: 3},
53    {file: "day25_example2.txt", part1: 8},
54]);
year2018/day25.rs

year2018/
day25.rs
