aoc/year2018/
day23.rs

1//! # Experimental Emergency Teleportation
2//!
3//! Part two implements a 3D version of binary search. Starting with a single cube that encloses all
4//! nanbots, each cube is further split into 8 smaller cubes until we find the answer.
5//! Cubes are stored in a [`MinHeap`] ordered by:
6//!
7//! * Greatest number of nanobots in range.
8//! * Least distance to origin.
9//! * Least size.
10//!
11//! This means that when we encounter a cube of size 1 we can return the coordinates,
12//! since we know that:
13//!
14//! * There are no cubes within range of more nanobots.
15//! * There are no cubes that are closer.
16//! * The coordinates cannot be refined any further.
17//!
18//! [`MinHeap`]: crate::util::heap
19use crate::util::heap::*;
20use crate::util::iter::*;
21use crate::util::parse::*;
22
23pub struct Nanobot {
24    x: i32,
25    y: i32,
26    z: i32,
27    r: i32,
28}
29
30impl Nanobot {
31    fn from([x, y, z, r]: [i32; 4]) -> Nanobot {
32        Nanobot { x, y, z, r }
33    }
34
35    fn manhattan(&self, other: &Nanobot) -> i32 {
36        (self.x - other.x).abs() + (self.y - other.y).abs() + (self.z - other.z).abs()
37    }
38}
39
40struct Cube {
41    x1: i32,
42    x2: i32,
43    y1: i32,
44    y2: i32,
45    z1: i32,
46    z2: i32,
47}
48
49impl Cube {
50    fn new(x1: i32, x2: i32, y1: i32, y2: i32, z1: i32, z2: i32) -> Cube {
51        Cube { x1, x2, y1, y2, z1, z2 }
52    }
53
54    /// Split the cube into 8 non-overlapping sub-cubes.
55    /// Since each cube size is always of power of two, we can safely divide by 2.
56    fn split(&self) -> [Cube; 8] {
57        let Cube { x1, x2, y1, y2, z1, z2 } = *self;
58
59        // Lower and upper halves of the new sub-cubes.
60        let lx = (self.x1 + self.x2) / 2;
61        let ly = (self.y1 + self.y2) / 2;
62        let lz = (self.z1 + self.z2) / 2;
63        let ux = lx + 1;
64        let uy = ly + 1;
65        let uz = lz + 1;
66
67        // 8 possible permutations of lower and upper halves for each axis.
68        [
69            Cube::new(x1, lx, y1, ly, z1, lz),
70            Cube::new(ux, x2, y1, ly, z1, lz),
71            Cube::new(x1, lx, uy, y2, z1, lz),
72            Cube::new(ux, x2, uy, y2, z1, lz),
73            Cube::new(x1, lx, y1, ly, uz, z2),
74            Cube::new(ux, x2, y1, ly, uz, z2),
75            Cube::new(x1, lx, uy, y2, uz, z2),
76            Cube::new(ux, x2, uy, y2, uz, z2),
77        ]
78    }
79
80    // Compute the Manattan distance from the faces of the cube to the octohedron shaped region
81    // within range of the Nanbot.
82    fn in_range(&self, nb: &Nanobot) -> bool {
83        let x = (self.x1 - nb.x).max(0) + (nb.x - self.x2).max(0);
84        let y = (self.y1 - nb.y).max(0) + (nb.y - self.y2).max(0);
85        let z = (self.z1 - nb.z).max(0) + (nb.z - self.z2).max(0);
86        x + y + z <= nb.r
87    }
88
89    /// Find the corner closest to the origin, considering each axis independently.
90    fn closest(&self) -> i32 {
91        let x = self.x1.abs().min(self.x2.abs());
92        let y = self.y1.abs().min(self.y2.abs());
93        let z = self.z1.abs().min(self.z2.abs());
94        x + y + z
95    }
96
97    /// All axes are the same same so choose `x` arbitrarily.
98    fn size(&self) -> i32 {
99        self.x2 - self.x1 + 1
100    }
101}
102
103pub fn parse(input: &str) -> Vec<Nanobot> {
104    input.iter_signed().chunk::<4>().map(Nanobot::from).collect()
105}
106
107pub fn part1(input: &[Nanobot]) -> usize {
108    let strongest = input.iter().max_by_key(|nb| nb.r).unwrap();
109    input.iter().filter(|nb| strongest.manhattan(nb) <= strongest.r).count()
110}
111
112pub fn part2(input: &[Nanobot]) -> i32 {
113    // Start with a single cube that encloses all nanobots. Cubes faces are aligned to powers of 2,
114    // for example 0..4, 8..16, -32..0
115    const SIZE: i32 = 1 << 29;
116    let mut heap = MinHeap::with_capacity(1_000);
117    heap.push((0, 0, 0), Cube::new(-SIZE, SIZE - 1, -SIZE, SIZE - 1, -SIZE, SIZE - 1));
118
119    while let Some((_, cube)) = heap.pop() {
120        if cube.size() == 1 {
121            return cube.closest();
122        }
123
124        for next in cube.split() {
125            let in_range = input.iter().filter(|nb| next.in_range(nb)).count();
126            let key = (input.len() - in_range, next.closest(), next.size());
127            heap.push(key, next);
128        }
129    }
130
131    unreachable!()
132}
aoc/year2018/day23.rs

aoc/year2018/
day23.rs
