Add day10, 2019

4 files changed, 176 insertions, 0 deletions

diff --git a/2019/rust/Cargo.toml b/2019/rust/Cargo.toml
index 420d5ab..0f57bd0 100644
--- a/2019/rust/Cargo.toml
+++ b/2019/rust/Cargo.toml
@@ -9,4 +9,5 @@ members = [
     "day07",
     "day08",
     "day09",
+    "day10",
 ]
diff --git a/2019/rust/day10/Cargo.toml b/2019/rust/day10/Cargo.toml
new file mode 100644
index 0000000..a9c1d17
--- /dev/null
+++ b/2019/rust/day10/Cargo.toml
@@ -0,0 +1,8 @@
+[package]
+name = "day10"
+version = "0.1.0"
+authors = ["cos <cos>"]
+edition = "2018"
+
+[dependencies]
+itertools = "0"
diff --git a/2019/rust/day10/both_parts.sh b/2019/rust/day10/both_parts.sh
new file mode 100755
index 0000000..68b03ce
--- /dev/null
+++ b/2019/rust/day10/both_parts.sh
@@ -0,0 +1,2 @@
+../target/release/day10 < input
+
diff --git a/2019/rust/day10/src/main.rs b/2019/rust/day10/src/main.rs
new file mode 100644
index 0000000..40091fb
--- /dev/null
+++ b/2019/rust/day10/src/main.rs
@@ -0,0 +1,165 @@
+use std::io::{self, BufRead};
+use std::collections::BTreeMap;
+
+#[derive(Clone, Copy, Debug, PartialEq)]
+struct Asteroid {
+    x: f64,
+    y: f64,
+}
+
+impl Asteroid {
+    fn new(x: f64, y: f64) -> Asteroid {
+        Asteroid {
+            x,
+            y,
+        }
+    }
+}
+
+#[derive(Clone, Copy, Debug)]
+struct Pair<'a> {
+    first: &'a Asteroid,
+    second: &'a Asteroid,
+}
+
+type Asteroids = Vec<Asteroid>;
+
+fn read_map() -> Asteroids {
+    let mut asteroids: Asteroids = Vec::new();
+    let stdin = io::stdin();
+
+    for (y, line) in stdin.lock().lines().enumerate() {
+        match line {
+            Ok(s) => {
+                for (x, byte) in s.as_bytes().iter().enumerate() {
+                  if *byte == b'#' {
+//                      println!("Asteroid found at {}, {}.", x, y);
+                      asteroids.push(Asteroid::new(x as f64, y as f64));
+                  }
+                }
+            },
+            _ => eprintln!("Failed to parse input at row {}.", y),
+        }
+    }
+
+    asteroids
+}
+
+fn calc_distance_angle(observer: &Asteroid, observee: &Asteroid) -> (f64, f64)
+{
+    let xdiff = observee.x - observer.x;
+    let ydiff = observer.y - observee.y;
+
+    let distance = f64::sqrt(xdiff.powf(2.0) + ydiff.powf(2.0));
+    let mut angle = f64::atan2(xdiff,ydiff);
+    if angle.is_sign_negative() {
+        angle += std::f64::consts::PI*2.0;
+    }
+
+    (distance, angle)
+}
+
+fn float_encode(f: f64) -> i128 {
+    (f * f64::powf(10.0, 37.0)) as i128
+}
+
+fn float_decode(i: i128) -> f64 {
+    (i as f64 / i128::pow(10, 37) as f64)
+}
+
+fn main() {
+    println!("Reading map");
+    let asteroids = read_map();
+
+    let mut angles = BTreeMap::new();
+    println!("Calculating distances between all asteroids");
+    for observer in &asteroids {
+        for observee in &asteroids {
+            if observer == observee { continue; }
+
+            let ( distance, angle ) = calc_distance_angle(observer, observee);
+            let dist_int = float_encode(distance);
+            let ang_int = float_encode(angle);
+
+            let pair = Pair {first: observer, second: observee};
+            let distances:&mut BTreeMap<i128, Vec<Pair>> =
+                angles.entry(ang_int).or_insert(BTreeMap::new());
+            distances.entry(dist_int).or_insert(Vec::new()).push(pair);
+        }
+    }
+
+    println!("Building huge angle and distance sorted datastructure of all asteroids.");
+    let mut huge:Vec<Vec<(Asteroid, f64, f64, Asteroid)>> = asteroids.iter()
+        .map(|asteroid| { let a:Vec<(Asteroid, f64, f64, Asteroid)> = angles.iter()
+            .map(|(angle, distances)| {
+                let a:Vec<(Asteroid, f64, f64, Asteroid)> = distances.iter()
+                .map(|(distance, pairs)| pairs.iter()
+                    .filter(|pair| if asteroid == pair.first {
+                        true
+                    } else {
+                        false
+                    })
+                    .map(move |pair| { (
+                        *asteroid,
+                        float_decode(*angle),
+                        float_decode(distance.clone()),
+                        *pair.second
+                    )})
+                ).flatten().collect(); a
+            }).flatten().collect() ; a
+        }).collect();
+
+    println!("Creating vector merely containing visible asteroids");
+    let visible_asteroids:Vec<usize> = huge.iter()
+        .map(|i| { let (_, n) = i.iter()
+             .fold((std::f64::consts::PI*3.0, 0),
+                  |( ang, res ), (_asteroid, angle, _distance, _other)|
+             {
+                 if f64::abs(ang - *angle) < 0.00000001 {
+                     ( *angle, res )
+                 } else {
+                     ( *angle, res + 1)
+             } }); n
+        }
+        ).collect();
+
+    let highest_no_visible_asteroids = visible_asteroids.iter().max().unwrap();
+
+    let mut best_asteroid = 0;
+    for ( which, val ) in visible_asteroids.iter().enumerate() {
+        if val == highest_no_visible_asteroids {
+            best_asteroid = which;
+        }
+    }
+    println!("Found out that {} other asteroids can be seen from the best asteroid.",
+        visible_asteroids[best_asteroid]);
+
+    let mut no_zapped = 0;
+    let mut index = 0;
+    let mut last_angle = -1.0;
+    println!("Powering up lazer...");
+    loop {
+        if index >= huge[best_asteroid].len() {
+            if index == 1 {
+                eprintln!("Not enough asteroids to zap!");
+                break;
+            }
+            index = 0;
+        }
+
+        let short = huge[best_asteroid][index];
+        if short.1 != last_angle {
+            let (_, angle, _, zapped_asteroid) = huge[best_asteroid].remove(index);
+            last_angle = angle;
+            no_zapped += 1;
+            if no_zapped == 200 {
+                println!("\rLast asteroid zapped was at {:?} {:?}",
+                    zapped_asteroid.x, zapped_asteroid.y);
+                break;
+            }
+        } else {
+            index += 1;
+        }
+    }
+
+}