1 files changed, 158 insertions, 0 deletions
diff --git a/2019/src/bin/day_10.rs b/2019/src/bin/day_10.rs
new file mode 100644
index 0000000..f25c3d2
--- /dev/null
+++ b/2019/src/bin/day_10.rs
@@ -0,0 +1,158 @@
+use aoc2019::*;
+use std::io;
+use std::io::prelude::*;
+use std::iter::FromIterator;
+use std::process;
+use structopt::StructOpt;
+
+#[derive(Debug, StructOpt)]
+#[structopt(name = "Day 10: Monitoring Station")]
+/// Finds the asteroid with the best view of the other asteroids. If
+/// an n is provided, then it will print the nth asteroid destroyed by
+/// a laser from the asteroid with the best view. Otherwise, it will
+/// print the number of asteroids visible.
+///
+/// Takes a map of asteroids in on stdin.
+///
+/// See https://adventofcode.com/2019/day/10 for details.
+struct Opt {
+    /// indexed from 0
+    #[structopt(short = "n")]
+    n: Option<usize>,
+}
+
+fn main() {
+    let opt = Opt::from_args();
+    let stdin = io::stdin();
+    let map: AsteroidMap = stdin
+        .lock()
+        .lines()
+        .map(|l| exit_on_failed_assertion(l, "Error reading input"))
+        .collect();
+
+    match opt.n {
+        Some(n) => println!("{:?}", map.nth_destroyed_asteroid(n)),
+        None => println!("{}", map.best_asteroid_line_of_sight_count()),
+    };
+}
+
+fn exit_on_failed_assertion<A, E: std::error::Error>(data: Result<A, E>, message: &str) -> A {
+    match data {
+        Ok(data) => data,
+        Err(e) => {
+            eprintln!("{}: {}", message, e);
+            process::exit(1);
+        }
+    }
+}
+
+#[derive(Debug)]
+struct AsteroidMap {
+    asteroids: Vec<Asteroid>,
+}
+
+impl FromIterator<String> for AsteroidMap {
+    fn from_iter<T: IntoIterator<Item = String>>(iter: T) -> Self {
+        AsteroidMap {
+            asteroids: iter
+                .into_iter()
+                .enumerate()
+                .flat_map(move |(y, line)| {
+                    line.chars()
+                        .enumerate()
+                        .map(move |(x, c)| (x, y, c))
+                        .collect::<Vec<_>>()
+                })
+                .filter(|(_x, _y, c)| *c == '#')
+                .map(|(x, y, _x)| Asteroid {
+                    x: x as i32,
+                    y: y as i32,
+                })
+                .collect(),
+        }
+    }
+}
+
+impl AsteroidMap {
+    fn best_asteroid_line_of_sight_count(&self) -> usize {
+        self.optimal_view_asteroid()
+            .map(|a| self.count_visible_from(&a))
+            .unwrap_or(0)
+    }
+
+    fn nth_destroyed_asteroid(&self, n: usize) -> Option<Asteroid> {
+        self.optimal_view_asteroid()
+            .and_then(|source| self.nth_destroyed_asteroid_from(&source, n))
+    }
+
+    fn nth_destroyed_asteroid_from(&self, source: &Asteroid, n: usize) -> Option<Asteroid> {
+        if self.asteroids.len() - 1 < n {
+            None
+        } else if self.count_visible_from(source) >= n {
+            sort_by_key(
+                self.asteroids
+                    .iter()
+                    .filter(|b| self.has_line_of_sight(source, b)),
+                |b| (source.angle_to(b) * 100000.) as i32,
+            )
+            .nth(n)
+            .cloned()
+        } else {
+            self.remove_visible_to(source)
+                .nth_destroyed_asteroid_from(source, n - self.count_visible_from(source))
+        }
+    }
+
+    fn optimal_view_asteroid(&self) -> Option<Asteroid> {
+        self.asteroids
+            .iter()
+            .max_by_key(|a| self.count_visible_from(a))
+            .cloned()
+    }
+
+    fn count_visible_from(&self, a: &Asteroid) -> usize {
+        self.asteroids
+            .iter()
+            .filter(|b| a != *b && self.has_line_of_sight(a, b))
+            .count()
+    }
+
+    fn remove_visible_to(&self, source: &Asteroid) -> AsteroidMap {
+        AsteroidMap {
+            asteroids: self
+                .asteroids
+                .iter()
+                .filter(|b| self.has_line_of_sight(source, b))
+                .cloned()
+                .collect(),
+        }
+    }
+
+    fn has_line_of_sight(&self, a: &Asteroid, b: &Asteroid) -> bool {
+        a != b
+            && !self.asteroids.iter().any(|c| {
+                a != c
+                    && b != c
+                    && a.angle_to(b) == a.angle_to(c)
+                    && a.distance_squared(b) > a.distance_squared(c)
+            })
+    }
+}
+
+#[derive(Debug, Clone, PartialEq, Eq)]
+struct Asteroid {
+    x: i32,
+    y: i32,
+}
+
+impl Asteroid {
+    fn angle_to(&self, other: &Asteroid) -> f32 {
+        ((self.x as f32 - other.x as f32).atan2(other.y as f32 - self.y as f32)
+            + std::f32::consts::PI)
+            % (2. * std::f32::consts::PI)
+    }
+
+    fn distance_squared(&self, other: &Asteroid) -> i32 {
+        (self.x - other.x).pow(2) + (self.y - other.y).pow(2)
+    }
+}