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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132

//! # Experimental Emergency Teleportation
//!
//! Part two implements a 3D version of binary search. Starting with a single cube that encloses all
//! nanbots, each cube is further split into 8 smaller cubes until we find the answer.
//! Cubes are stored in a [`MinHeap`] ordered by:
//!
//! * Greatest number of nanobots in range.
//! * Least distance to origin.
//! * Least size.
//!
//! This means that when we encounter a cube of size 1 we can return the coordinates,
//! since we know that:
//!
//! * There are no cubes within range of more nanobots.
//! * There are no cubes that are closer.
//! * The coordinates cannot be refined any further.
//!
//! [`MinHeap`]: crate::util::heap
use crate::util::heap::*;
use crate::util::iter::*;
use crate::util::parse::*;

pub struct Nanobot {
    x: i32,
    y: i32,
    z: i32,
    r: i32,
}

impl Nanobot {
    fn from([x, y, z, r]: [i32; 4]) -> Nanobot {
        Nanobot { x, y, z, r }
    }

    fn manhattan(&self, other: &Nanobot) -> i32 {
        (self.x - other.x).abs() + (self.y - other.y).abs() + (self.z - other.z).abs()
    }
}

struct Cube {
    x1: i32,
    x2: i32,
    y1: i32,
    y2: i32,
    z1: i32,
    z2: i32,
}

impl Cube {
    fn new(x1: i32, x2: i32, y1: i32, y2: i32, z1: i32, z2: i32) -> Cube {
        Cube { x1, x2, y1, y2, z1, z2 }
    }

    /// Split the cube into 8 non-overlapping sub-cubes.
    /// Since each cube size is always of power of two, we can safely divide by 2.
    fn split(&self) -> [Cube; 8] {
        let Cube { x1, x2, y1, y2, z1, z2 } = *self;

        // Lower and upper halves of the new sub-cubes.
        let lx = (self.x1 + self.x2) / 2;
        let ly = (self.y1 + self.y2) / 2;
        let lz = (self.z1 + self.z2) / 2;
        let ux = lx + 1;
        let uy = ly + 1;
        let uz = lz + 1;

        // 8 possible permutations of lower and upper halves for each axis.
        [
            Cube::new(x1, lx, y1, ly, z1, lz),
            Cube::new(ux, x2, y1, ly, z1, lz),
            Cube::new(x1, lx, uy, y2, z1, lz),
            Cube::new(ux, x2, uy, y2, z1, lz),
            Cube::new(x1, lx, y1, ly, uz, z2),
            Cube::new(ux, x2, y1, ly, uz, z2),
            Cube::new(x1, lx, uy, y2, uz, z2),
            Cube::new(ux, x2, uy, y2, uz, z2),
        ]
    }

    // Compute the Manattan distance from the faces of the cube to the octohedron shaped region
    // within range of the Nanbot.
    fn in_range(&self, nb: &Nanobot) -> bool {
        let x = (self.x1 - nb.x).max(0) + (nb.x - self.x2).max(0);
        let y = (self.y1 - nb.y).max(0) + (nb.y - self.y2).max(0);
        let z = (self.z1 - nb.z).max(0) + (nb.z - self.z2).max(0);
        x + y + z <= nb.r
    }

    /// Find the corner closest to the origin, considering each axis independently.
    fn closest(&self) -> i32 {
        let x = self.x1.abs().min(self.x2.abs());
        let y = self.y1.abs().min(self.y2.abs());
        let z = self.z1.abs().min(self.z2.abs());
        x + y + z
    }

    /// All axes are the same same so choose `x` arbitrarily.
    fn size(&self) -> i32 {
        self.x2 - self.x1 + 1
    }
}

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

pub fn part1(input: &[Nanobot]) -> usize {
    let strongest = input.iter().max_by_key(|nb| nb.r).unwrap();
    input.iter().filter(|nb| strongest.manhattan(nb) <= strongest.r).count()
}

pub fn part2(input: &[Nanobot]) -> i32 {
    // Start with a single cube that encloses all nanobots. Cubes faces are aligned to powers of 2,
    // for example 0..4, 8..16, -32..0
    const SIZE: i32 = 1 << 29;
    let mut heap = MinHeap::with_capacity(1_000);
    heap.push((0, 0, 0), Cube::new(-SIZE, SIZE - 1, -SIZE, SIZE - 1, -SIZE, SIZE - 1));

    while let Some((_, cube)) = heap.pop() {
        if cube.size() == 1 {
            return cube.closest();
        }

        for next in cube.split() {
            let in_range = input.iter().filter(|nb| next.in_range(nb)).count();
            let key = (input.len() - in_range, next.closest(), next.size());
            heap.push(key, next);
        }
    }

    unreachable!()
}