diff options
Diffstat (limited to 'src')
-rw-r--r-- | src/bin/day_10.rs | 158 | ||||
-rw-r--r-- | src/bin/day_11.rs | 205 | ||||
-rw-r--r-- | src/bin/day_9.rs | 1 | ||||
-rw-r--r-- | src/lib.rs | 22 |
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 @@ -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() +} |