year2018/
day23.rs

1use std::cmp::Ordering;
2use std::collections::BinaryHeap;
3use utils::geometry::Vec3;
4use utils::prelude::*;
5
6/// Finding the point in range of the most nodes.
7#[derive(Clone, Debug)]
8pub struct Day23 {
9    bots: Vec<Bot>,
10}
11
12#[derive(Clone, Debug)]
13struct Bot {
14    pos: Vec3<i32>,
15    r: u32,
16}
17
18// 2**29 seems to be the max range of the input, and 2**29 * 3 fits within i32 without overflow.
19const MAX_POW2: u32 = 29;
20const MIN: i32 = -(1 << MAX_POW2);
21const MAX: i32 = (1 << MAX_POW2) - 1;
22
23impl Day23 {
24    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
25        Ok(Self {
26            bots: parser::number_range(MIN..=MAX)
27                .repeat_n(b',')
28                .with_prefix("pos=<")
29                .with_suffix(">, r=")
30                .then(parser::u32())
31                .map(|(pos, r)| Bot { pos: pos.into(), r })
32                .parse_lines(input)?,
33        })
34    }
35
36    #[must_use]
37    pub fn part1(&self) -> usize {
38        let strongest = self.bots.iter().max_by_key(|b| b.r).unwrap();
39
40        self.bots
41            .iter()
42            .filter(|&b| b.pos.manhattan_distance_to(strongest.pos) <= strongest.r)
43            .count()
44    }
45
46    #[must_use]
47    pub fn part2(&self) -> u32 {
48        let initial = Subcube::new(Vec3::splat(MIN), Vec3::splat(MAX), &self.bots);
49
50        let mut heap = BinaryHeap::with_capacity(2048);
51        heap.push(initial);
52
53        while let Some(s) = heap.pop() {
54            if s.size == 1 {
55                return s.dist;
56            }
57            heap.extend(s.split(&self.bots));
58        }
59
60        unreachable!()
61    }
62}
63
64#[derive(Clone, Debug, Eq, PartialEq)]
65struct Subcube {
66    min: Vec3<i32>,
67    max: Vec3<i32>,
68    bot_count: usize,
69    dist: u32,
70    size: u32,
71}
72
73impl Subcube {
74    #[inline]
75    fn new(min: Vec3<i32>, max: Vec3<i32>, bots: &[Bot]) -> Self {
76        Self {
77            min,
78            max,
79            bot_count: bots
80                .iter()
81                .filter(|&bot| bot.pos.manhattan_distance_to_aabb(min, max) <= bot.r)
82                .count(),
83            dist: Vec3::ORIGIN.manhattan_distance_to_aabb(min, max),
84            size: max.x.abs_diff(min.x) + 1,
85        }
86    }
87
88    #[inline]
89    fn split(&self, bots: &[Bot]) -> [Self; 8] {
90        let half = (self.size / 2) as i32;
91        let xs = [
92            (self.min.x, self.min.x + half - 1),
93            (self.min.x + half, self.max.x),
94        ];
95        let ys = [
96            (self.min.y, self.min.y + half - 1),
97            (self.min.y + half, self.max.y),
98        ];
99        let zs = [
100            (self.min.z, self.min.z + half - 1),
101            (self.min.z + half, self.max.z),
102        ];
103
104        std::array::from_fn(|i| {
105            let (min_x, max_x) = xs[i >> 2];
106            let (min_y, max_y) = ys[(i >> 1) & 1];
107            let (min_z, max_z) = zs[i & 1];
108            Self::new(
109                Vec3::new(min_x, min_y, min_z),
110                Vec3::new(max_x, max_y, max_z),
111                bots,
112            )
113        })
114    }
115}
116
117impl Ord for Subcube {
118    #[inline]
119    fn cmp(&self, other: &Self) -> Ordering {
120        // Sort by bot count ascending, dist descending, size descending.
121        // When used inside a MaxHeap this will order entries by the reverse (bot count descending,
122        // dist ascending, size ascending), which ensures the first point visited is optimal.
123        self.bot_count
124            .cmp(&other.bot_count)
125            .then(self.dist.cmp(&other.dist).reverse())
126            .then(self.size.cmp(&other.size).reverse())
127    }
128}
129
130impl PartialOrd for Subcube {
131    #[inline]
132    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
133        Some(self.cmp(other))
134    }
135}
136
137examples!(Day23 -> (usize, u32) [
138    {
139        input: "pos=<0,0,0>, r=4\n\
140            pos=<1,0,0>, r=1\n\
141            pos=<4,0,0>, r=3\n\
142            pos=<0,2,0>, r=1\n\
143            pos=<0,5,0>, r=3\n\
144            pos=<0,0,3>, r=1\n\
145            pos=<1,1,1>, r=1\n\
146            pos=<1,1,2>, r=1\n\
147            pos=<1,3,1>, r=1",
148        part1: 7,
149    },
150    {
151        input: "pos=<10,12,12>, r=2\n\
152            pos=<12,14,12>, r=2\n\
153            pos=<16,12,12>, r=4\n\
154            pos=<14,14,14>, r=6\n\
155            pos=<50,50,50>, r=200\n\
156            pos=<10,10,10>, r=5",
157        part2: 36,
158    },
159]);
year2018/day23.rs

year2018/
day23.rs
