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)
    }
}