Day 23: Searching in a massive 3d space
[advent-of-code-2018.git] / src / bin / day_23.rs
index 6f60dbf..463f3d3 100644 (file)
@@ -3,16 +3,112 @@ use advent_of_code_2018::*;
 
 use std::error::Error;
 use std::path::PathBuf;
+use std::cmp;
 
 // cargo watch -cs "cargo run --release --bin day_23"
 
+#[derive(Debug, Clone)]
+struct Bot {
+    radius: i64,
+    position: Position
+}
+
+#[derive(Debug, Clone)]
+struct Position {
+    x: i64,
+    y: i64,
+    z: i64
+}
+
+impl Position {
+    fn distance(&self, other: &Position) -> i64 {
+        (other.z - self.z).abs() +
+            (other.y - self.y).abs() +
+            (other.x - self.x).abs()
+    }
+}
+
 fn main() -> Result<(), Box<Error>> {
     let input = read_file(&PathBuf::from("inputs/23.txt"))?;
 
-    println!("Input: {:?}", input);
+    let mut bots: Vec<Bot> = input.iter().map(|line| {
+        let mut line_iter = line.split(|c: char| c != '-' && !c.is_numeric())
+            .filter(|s| !s.is_empty())
+            .map(|s| s.parse::<i64>().unwrap());
+        Bot {
+            position: Position {
+                x: line_iter.next().unwrap(),
+                y: line_iter.next().unwrap(),
+                z: line_iter.next().unwrap()
+            },
+            radius: line_iter.next().unwrap()
+        }
+    }).collect();
+
+    let biggest_radius = bots.iter().max_by_key(|bot| bot.radius).unwrap();
+    let biggest_radius_in_range_count = bots.iter()
+        .filter(|bot| biggest_radius.position.distance(&bot.position) <= biggest_radius.radius)
+        .count();
+    debug!(biggest_radius);
+    debug!(biggest_radius_in_range_count);
 
+    
+    let min_x = bots.iter().min_by_key(|bot| bot.position.x).unwrap().position.x;
+    let max_x = bots.iter().max_by_key(|bot| bot.position.x).unwrap().position.x;
+    debug!(min_x);
+    debug!(max_x);
+    let min_y = bots.iter().min_by_key(|bot| bot.position.y).unwrap().position.y;
+    let max_y = bots.iter().max_by_key(|bot| bot.position.y).unwrap().position.y;
+    debug!(min_y);
+    debug!(max_y);
+    let min_z = bots.iter().min_by_key(|bot| bot.position.z).unwrap().position.z;
+    let max_z = bots.iter().max_by_key(|bot| bot.position.z).unwrap().position.z;
+    debug!(min_z);
+    debug!(max_z);
 
+    let origin = Position { x: 0, y: 0, z: 0 };
+    
+    let mut radius = cmp::max(max_x - min_x, cmp::max(max_y-min_y, max_z-min_z));
+    let mut center = origin.clone();
+    
+    while radius > 0 {
+        let delta = 0.8;
+        let new_radius = if radius == 1 { 0 } else { (radius as f32 * delta) as i64 };
+        let deltas = [-1.0, -0.8, -0.6, -0.4, -0.2, 0.0, 0.2, 0.4, 0.6, 0.8, 1.0];
+        let subs: Vec<Position> = deltas.iter().flat_map(|&dx| {
+            deltas.iter().flat_map(|&dy| {
+                deltas.iter().map(|&dz| {
+                    Position {
+                        x: center.x + (radius as f32 * dx) as i64,
+                        y: center.y + (radius as f32 * dy) as i64,
+                        z: center.z + (radius as f32 * dz) as i64
+                    }
+                }).collect::<Vec<_>>()
+            }).collect::<Vec<_>>()
+        }).collect();
 
+        center = subs.iter()
+            .map(|new_center| {
+                (new_center, bots.iter()
+                    .filter(|bot| bot.position.distance(&new_center) <= bot.radius + new_radius)
+                    .count())
+            })
+            .max_by(|(a_center, a_bots), (b_center, b_bots)| {
+                a_bots.cmp(&b_bots).then(b_center.distance(&origin).cmp(&a_center.distance(&origin)))
+            })
+            .map(|(center, _)| center)
+            .unwrap().clone();
+        
+        radius = new_radius;
+    }
+    
+    let connected_in_radius = bots.iter()
+        .filter(|bot| bot.position.distance(&center) <= bot.radius)
+        .count();
+    debug!(connected_in_radius);
+    debug!(center);
+    let distance_to_origin = center.distance(&origin);
+    debug!(distance_to_origin);
 
     Ok(())
 }