aoc/year2018/
day23.rs

1//! # Experimental Emergency Teleportation
2//!
3//! A generic solution to part two would be a 3D version of binary search. Starting with a single
4//! cube that encloses all nanobots, each cube is further split into 8 smaller cubes until we find
5//! the answer. Cubes can be stored in a
6//! [min-heap](https://en.wikipedia.org/wiki/Heap_(data_structure)) ordered by:
7//!
8//! * Greatest number of nanobots in range.
9//! * Least distance to origin.
10//! * Least size.
11//!
12//! This means that when we encounter a cube of size 1, we can return the coordinates,
13//! since we know that:
14//!
15//! * There are no cubes within range of more nanobots.
16//! * There are no cubes that are closer.
17//! * The coordinates cannot be refined any further.
18//!
19//! However, the actual input files lend themselves to an even faster answer. At a high level,
20//! we can determine a one-dimensional range of Manhattan distances at which we are in range of
21//! a given nanobot. By sorting the points at which ranges begin and end, we can determine the
22//! maximum number of nanobots that can possibly be in range at once. In the generic case,
23//! two nanobots may have the same Manhattan distance but be non-overlapping in distinct
24//! octants of 3D space, so the actual best point may have fewer than the maximum determined in
25//! this manner. But for our input files, it so happens that there is exactly one range that has
26//! a higher potential than any other, and the low end of this range happens to be the Manhattan
27//! distance we are after, without actually having to find the point with that distance.
28use crate::util::iter::*;
29use crate::util::parse::*;
30
31pub struct Nanobot {
32    x: i32,
33    y: i32,
34    z: i32,
35    r: i32,
36}
37
38impl Nanobot {
39    fn from([x, y, z, r]: [i32; 4]) -> Nanobot {
40        Nanobot { x, y, z, r }
41    }
42
43    fn manhattan(&self, other: &Nanobot) -> i32 {
44        (self.x - other.x).abs() + (self.y - other.y).abs() + (self.z - other.z).abs()
45    }
46}
47
48pub fn parse(input: &str) -> Vec<Nanobot> {
49    input.iter_signed().chunk::<4>().map(Nanobot::from).collect()
50}
51
52pub fn part1(input: &[Nanobot]) -> usize {
53    let strongest = input.iter().max_by_key(|nb| nb.r).unwrap();
54    input.iter().filter(|nb| strongest.manhattan(nb) <= strongest.r).count()
55}
56
57pub fn part2(input: &[Nanobot]) -> i32 {
58    // Start by populating the possible distances that can reach each nanobot.
59    let origin = Nanobot::from([0, 0, 0, 0]);
60    let mut endpoints = Vec::with_capacity(2_000);
61
62    for bot in input {
63        let dist = bot.manhattan(&origin);
64        let low = (dist - bot.r).max(0);
65        endpoints.push((low, 1));
66        endpoints.push((dist + bot.r + 1, -1));
67    }
68
69    endpoints.sort_unstable();
70
71    // Determine the distance that has the maximum overlap in ranges.
72    let mut best_dist = 0;
73    let mut best_total = 0;
74    let mut total = 0;
75
76    for (dist, delta) in endpoints {
77        total += delta;
78        if total > best_total {
79            best_total = total;
80            best_dist = dist;
81        }
82    }
83
84    // In the generic case, the actual answer might be a lower number of overlapping nanobots at a
85    // different distance, but for our input files, the maximum overlap gives the distance we want.
86    best_dist
87}
aoc/year2018/day23.rs

aoc/year2018/
day23.rs
