Day 10 and 11! Yay!

4 files changed, 386 insertions, 0 deletions

diff --git a/src/bin/day_10.rs b/src/bin/day_10.rs
new file mode 100644
index 0000000..f25c3d2
--- /dev/null
+++ b/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)
+    }
+}
diff --git a/src/bin/day_11.rs b/src/bin/day_11.rs
new file mode 100644
index 0000000..da3e1fd
--- /dev/null
+++ b/src/bin/day_11.rs
@@ -0,0 +1,205 @@
+use aoc2019::*;
+use rpds::list;
+use rpds::list::List;
+use rpds::RedBlackTreeMap;
+use std::fmt;
+use std::io;
+use std::io::prelude::*;
+use std::iter;
+use std::process;
+use structopt::StructOpt;
+
+#[derive(Debug, StructOpt)]
+#[structopt(name = "Day 11: Space Police")]
+/// Calculates how many blocks a painting robot would paint.
+///
+/// Takes the program to run on the robot in on stdin.
+///
+/// See https://adventofcode.com/2019/day/11 for details.
+struct Opt {
+    /// debug mode prints the size of the painted area on a black background
+    #[structopt(short = "d", long = "debug")]
+    debug: bool,
+}
+
+fn main() {
+    let opt = Opt::from_args();
+    let stdin = io::stdin();
+    let program: IntcodeProgram = stdin
+        .lock()
+        .split(b',')
+        .map(|x| exit_on_failed_assertion(x, "Error reading input"))
+        .map(|x| exit_on_failed_assertion(String::from_utf8(x), "Input was not valid UTF-8"))
+        .map(|x| exit_on_failed_assertion(x.trim().parse::<Intcode>(), "Invalid number"))
+        .collect::<IntcodeProgram>();
+
+    let finished_robot = exit_on_failed_assertion(
+        Robot::new(program, !opt.debug).execute(),
+        "Robot encountered an error",
+    );
+    if opt.debug {
+        println!("{}", finished_robot.canvas.size());
+    } else {
+        println!("{}", finished_robot);
+    }
+}
+
+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, Clone)]
+struct Robot {
+    program: IntcodeProgram,
+    position: (i32, i32),
+    facing: Direction,
+    canvas: RedBlackTreeMap<(i32, i32), bool>,
+    background: bool,
+}
+
+impl fmt::Display for Robot {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        (self.min_white_y()..=self.max_white_y())
+            .map(move |y| {
+                (self.min_white_x()..=self.max_white_x())
+                    .map(move |x| (x, y))
+                    .map(|coord| self.canvas.get(&coord).cloned().unwrap_or(self.background))
+                    .map(|c| write!(f, "{}", if c { '#' } else { ' ' }))
+                    .collect::<fmt::Result>()
+                    .and_then(|_| writeln!(f, ""))
+            })
+            .collect()
+    }
+}
+
+#[derive(Debug, Clone)]
+enum Direction {
+    Up,
+    Down,
+    Left,
+    Right,
+}
+
+impl Robot {
+    fn new(program: IntcodeProgram, background: bool) -> Robot {
+        Robot {
+            program: program.run_to_termination_or_input(),
+            position: (0, 0),
+            facing: Direction::Up,
+            canvas: RedBlackTreeMap::new(),
+            background,
+        }
+    }
+
+    fn execute(&self) -> Result<Robot, IntcodeProgramError> {
+        iter::successors(Some(self.clone()), |robot| Some(robot.next()))
+            .find(|robot| {
+                robot.program.error.is_some()
+                    || (robot.program.halted && robot.program.output.is_empty())
+            })
+            .unwrap() // infinite iterator won't terminate unless this is Some
+            .as_result()
+    }
+
+    fn as_result(&self) -> Result<Robot, IntcodeProgramError> {
+        match self.program.error {
+            Some(ref error) => Err(error.clone()),
+            None => Ok(self.clone()),
+        }
+    }
+
+    fn next(&self) -> Robot {
+        match (
+            self.program.output.get(0).map(intcode_to_bool),
+            self.program.output.get(1).map(intcode_to_bool),
+        ) {
+            (Some(paint), Some(rot)) => Robot {
+                program: self
+                    .program
+                    .with_cleared_output()
+                    .with_input(list![bool_to_intcode(
+                        self.canvas
+                            .get(&self.facing.rotate(rot).move_position(self.position))
+                            .cloned()
+                            .unwrap_or(self.background),
+                    )])
+                    .run_to_termination_or_input(),
+                position: self.facing.rotate(rot).move_position(self.position),
+                facing: self.facing.rotate(rot),
+                canvas: self.canvas.insert(self.position, paint),
+                background: self.background,
+            },
+            _ => Robot {
+                program: self
+                    .program
+                    .with_input(list![bool_to_intcode(
+                        self.canvas
+                            .get(&self.position)
+                            .cloned()
+                            .unwrap_or(self.background),
+                    )])
+                    .run_to_termination_or_input(),
+                ..self.clone()
+            },
+        }
+    }
+
+    fn min_white_x(&self) -> i32 {
+        self.white_blocks().map(|(x, _y)| x).min().unwrap_or(0)
+    }
+    fn min_white_y(&self) -> i32 {
+        self.white_blocks().map(|(_x, y)| y).min().unwrap_or(0)
+    }
+    fn max_white_x(&self) -> i32 {
+        self.white_blocks().map(|(x, _y)| x).max().unwrap_or(0)
+    }
+    fn max_white_y(&self) -> i32 {
+        self.white_blocks().map(|(_x, y)| y).max().unwrap_or(0)
+    }
+
+    fn white_blocks<'a>(&'a self) -> impl 'a + Iterator<Item = (i32, i32)> {
+        self.canvas
+            .iter()
+            .filter(|(_, val)| **val)
+            .map(|(coord, _)| coord)
+            .cloned()
+    }
+}
+
+impl Direction {
+    fn rotate(&self, clockwise: bool) -> Direction {
+        use Direction::*;
+
+        if clockwise {
+            match self {
+                Up => Right,
+                Right => Down,
+                Down => Left,
+                Left => Up,
+            }
+        } else {
+            match self {
+                Up => Left,
+                Left => Down,
+                Down => Right,
+                Right => Up,
+            }
+        }
+    }
+
+    fn move_position(&self, position: (i32, i32)) -> (i32, i32) {
+        use Direction::*;
+        match self {
+            Up => (position.0, position.1 + 1),
+            Down => (position.0, position.1 - 1),
+            Left => (position.0 - 1, position.1),
+            Right => (position.0 + 1, position.1),
+        }
+    }
+}
diff --git a/src/bin/day_9.rs b/src/bin/day_9.rs
new file mode 100644
index 0000000..7f9b4aa
--- /dev/null
+++ b/src/bin/day_9.rs
@@ -0,0 +1 @@
+// Run the day 5 binary for this
diff --git a/src/lib.rs b/src/lib.rs
index 39966e6..6be1aba 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -6,6 +6,7 @@ use std::fmt;
 use std::iter;
 use std::iter::FromIterator;
 use std::iter::IntoIterator;
+use std::iter::Iterator;
 
 pub type Intcode = BigInt;
 
@@ -57,6 +58,18 @@ impl fmt::Debug for IntcodeProgram {
     }
 }
 
+pub fn intcode_to_bool(i: &Intcode) -> bool {
+    *i != Intcode::from(0)
+}
+
+pub fn bool_to_intcode(i: bool) -> Intcode {
+    if i {
+        Intcode::from(1)
+    } else {
+        Intcode::from(0)
+    }
+}
+
 impl IntcodeProgram {
     pub fn with_noun_verb_input(&self, noun: Intcode, verb: Intcode) -> IntcodeProgram {
         self.with_memory_set(1.into(), noun)
@@ -444,3 +457,12 @@ mod tests {
         assert_eq!(program.output, i32_vec_to_intcode_vec(quine));
     }
 }
+
+pub fn sort_by_key<T, K: Ord>(
+    iter: impl IntoIterator<Item = T>,
+    f: impl FnMut(&T) -> K,
+) -> impl Iterator<Item = T> {
+    let mut tmp: Vec<T> = iter.into_iter().collect();
+    tmp.sort_by_key(f);
+    tmp.into_iter()
+}