Day 23: Searching in a massive 3d space
[advent-of-code-2018.git] / src / bin / day_23.rs
1 extern crate advent_of_code_2018;
2 use advent_of_code_2018::*;
3
4 use std::error::Error;
5 use std::path::PathBuf;
6 use std::cmp;
7
8 // cargo watch -cs "cargo run --release --bin day_23"
9
10 #[derive(Debug, Clone)]
11 struct Bot {
12     radius: i64,
13     position: Position
14 }
15
16 #[derive(Debug, Clone)]
17 struct Position {
18     x: i64,
19     y: i64,
20     z: i64
21 }
22
23 impl Position {
24     fn distance(&self, other: &Position) -> i64 {
25         (other.z - self.z).abs() +
26             (other.y - self.y).abs() +
27             (other.x - self.x).abs()
28     }
29 }
30
31 fn main() -> Result<(), Box<Error>> {
32     let input = read_file(&PathBuf::from("inputs/23.txt"))?;
33
34     let mut bots: Vec<Bot> = input.iter().map(|line| {
35         let mut line_iter = line.split(|c: char| c != '-' && !c.is_numeric())
36             .filter(|s| !s.is_empty())
37             .map(|s| s.parse::<i64>().unwrap());
38         Bot {
39             position: Position {
40                 x: line_iter.next().unwrap(),
41                 y: line_iter.next().unwrap(),
42                 z: line_iter.next().unwrap()
43             },
44             radius: line_iter.next().unwrap()
45         }
46     }).collect();
47
48     let biggest_radius = bots.iter().max_by_key(|bot| bot.radius).unwrap();
49     let biggest_radius_in_range_count = bots.iter()
50         .filter(|bot| biggest_radius.position.distance(&bot.position) <= biggest_radius.radius)
51         .count();
52     debug!(biggest_radius);
53     debug!(biggest_radius_in_range_count);
54
55     
56     let min_x = bots.iter().min_by_key(|bot| bot.position.x).unwrap().position.x;
57     let max_x = bots.iter().max_by_key(|bot| bot.position.x).unwrap().position.x;
58     debug!(min_x);
59     debug!(max_x);
60     let min_y = bots.iter().min_by_key(|bot| bot.position.y).unwrap().position.y;
61     let max_y = bots.iter().max_by_key(|bot| bot.position.y).unwrap().position.y;
62     debug!(min_y);
63     debug!(max_y);
64     let min_z = bots.iter().min_by_key(|bot| bot.position.z).unwrap().position.z;
65     let max_z = bots.iter().max_by_key(|bot| bot.position.z).unwrap().position.z;
66     debug!(min_z);
67     debug!(max_z);
68
69     let origin = Position { x: 0, y: 0, z: 0 };
70     
71     let mut radius = cmp::max(max_x - min_x, cmp::max(max_y-min_y, max_z-min_z));
72     let mut center = origin.clone();
73     
74     while radius > 0 {
75         let delta = 0.8;
76         let new_radius = if radius == 1 { 0 } else { (radius as f32 * delta) as i64 };
77         let deltas = [-1.0, -0.8, -0.6, -0.4, -0.2, 0.0, 0.2, 0.4, 0.6, 0.8, 1.0];
78         let subs: Vec<Position> = deltas.iter().flat_map(|&dx| {
79             deltas.iter().flat_map(|&dy| {
80                 deltas.iter().map(|&dz| {
81                     Position {
82                         x: center.x + (radius as f32 * dx) as i64,
83                         y: center.y + (radius as f32 * dy) as i64,
84                         z: center.z + (radius as f32 * dz) as i64
85                     }
86                 }).collect::<Vec<_>>()
87             }).collect::<Vec<_>>()
88         }).collect();
89
90         center = subs.iter()
91             .map(|new_center| {
92                 (new_center, bots.iter()
93                     .filter(|bot| bot.position.distance(&new_center) <= bot.radius + new_radius)
94                     .count())
95             })
96             .max_by(|(a_center, a_bots), (b_center, b_bots)| {
97                 a_bots.cmp(&b_bots).then(b_center.distance(&origin).cmp(&a_center.distance(&origin)))
98             })
99             .map(|(center, _)| center)
100             .unwrap().clone();
101         
102         radius = new_radius;
103     }
104     
105     let connected_in_radius = bots.iter()
106         .filter(|bot| bot.position.distance(&center) <= bot.radius)
107         .count();
108     debug!(connected_in_radius);
109     debug!(center);
110     let distance_to_origin = center.distance(&origin);
111     debug!(distance_to_origin);
112
113     Ok(())
114 }