From 9892e3ebde304726903a1e5c358d05c2e343ea5e Mon Sep 17 00:00:00 2001 From: Justin Wernick Date: Tue, 19 Apr 2022 20:26:36 +0200 Subject: Refile for merging repos --- 2019/src/bin/day_1.rs | 93 ++++++++++++ 2019/src/bin/day_10.rs | 158 +++++++++++++++++++++ 2019/src/bin/day_11.rs | 205 +++++++++++++++++++++++++++ 2019/src/bin/day_12.rs | 205 +++++++++++++++++++++++++++ 2019/src/bin/day_13.rs | 149 ++++++++++++++++++++ 2019/src/bin/day_14.rs | 221 +++++++++++++++++++++++++++++ 2019/src/bin/day_15.rs | 183 ++++++++++++++++++++++++ 2019/src/bin/day_16.rs | 112 +++++++++++++++ 2019/src/bin/day_17.rs | 78 +++++++++++ 2019/src/bin/day_18.rs | 365 ++++++++++++++++++++++++++++++++++++++++++++++++ 2019/src/bin/day_19.rs | 102 ++++++++++++++ 2019/src/bin/day_2.rs | 96 +++++++++++++ 2019/src/bin/day_20.rs | 310 ++++++++++++++++++++++++++++++++++++++++ 2019/src/bin/day_21.rs | 109 +++++++++++++++ 2019/src/bin/day_22.rs | 325 ++++++++++++++++++++++++++++++++++++++++++ 2019/src/bin/day_23.rs | 211 ++++++++++++++++++++++++++++ 2019/src/bin/day_24.rs | 239 +++++++++++++++++++++++++++++++ 2019/src/bin/day_25.dot | 43 ++++++ 2019/src/bin/day_25.rs | 110 +++++++++++++++ 2019/src/bin/day_3.rs | 333 +++++++++++++++++++++++++++++++++++++++++++ 2019/src/bin/day_4.rs | 55 ++++++++ 2019/src/bin/day_5.rs | 45 ++++++ 2019/src/bin/day_6.rs | 251 +++++++++++++++++++++++++++++++++ 2019/src/bin/day_7.rs | 175 +++++++++++++++++++++++ 2019/src/bin/day_8.rs | 135 ++++++++++++++++++ 2019/src/bin/day_9.rs | 1 + 26 files changed, 4309 insertions(+) create mode 100644 2019/src/bin/day_1.rs create mode 100644 2019/src/bin/day_10.rs create mode 100644 2019/src/bin/day_11.rs create mode 100644 2019/src/bin/day_12.rs create mode 100644 2019/src/bin/day_13.rs create mode 100644 2019/src/bin/day_14.rs create mode 100644 2019/src/bin/day_15.rs create mode 100644 2019/src/bin/day_16.rs create mode 100644 2019/src/bin/day_17.rs create mode 100644 2019/src/bin/day_18.rs create mode 100644 2019/src/bin/day_19.rs create mode 100644 2019/src/bin/day_2.rs create mode 100644 2019/src/bin/day_20.rs create mode 100644 2019/src/bin/day_21.rs create mode 100644 2019/src/bin/day_22.rs create mode 100644 2019/src/bin/day_23.rs create mode 100644 2019/src/bin/day_24.rs create mode 100644 2019/src/bin/day_25.dot create mode 100644 2019/src/bin/day_25.rs create mode 100644 2019/src/bin/day_3.rs create mode 100644 2019/src/bin/day_4.rs create mode 100644 2019/src/bin/day_5.rs create mode 100644 2019/src/bin/day_6.rs create mode 100644 2019/src/bin/day_7.rs create mode 100644 2019/src/bin/day_8.rs create mode 100644 2019/src/bin/day_9.rs (limited to '2019/src/bin') diff --git a/2019/src/bin/day_1.rs b/2019/src/bin/day_1.rs new file mode 100644 index 0000000..572d287 --- /dev/null +++ b/2019/src/bin/day_1.rs @@ -0,0 +1,93 @@ +use derive_more; +use std::io; +use std::io::prelude::*; +use std::iter; +use std::process; + +use structopt::StructOpt; + +#[derive(Debug, StructOpt)] +#[structopt(name = "Day 1: The Tyranny of the Rocket Equation")] +/// Calculates the fuel needed for your rocket to save Santa. +/// +/// The weight of each module is read from stdin, one module weight +/// per line. See https://adventofcode.com/2019/day/1 for details. +struct Opt { + /// Includes the weight of fuel + #[structopt(short = "i", long = "include-fuel-weight")] + include_fuel_weight: bool, +} + +fn main() { + let stdin = io::stdin(); + let opt = Opt::from_args(); + + let input = stdin.lock().lines().map(|l| match l { + Ok(s) => match s.parse::() { + Ok(module) => module, + Err(e) => { + eprintln!("Invalid input \"{}\": {}", s, e); + process::exit(1); + } + }, + Err(e) => { + eprintln!("Error reading input: {}", e); + process::exit(1); + } + }); + + println!("{}", fuel_required(input, opt.include_fuel_weight)) +} + +fn fuel_required(it: impl Iterator, include_fuel_weight: bool) -> Fuel { + it.map(if include_fuel_weight { + Module::fuel_including_fuel_weight + } else { + Module::fuel_excluding_fuel_weight + }) + .sum() +} + +#[derive(Debug, derive_more::FromStr, Clone, Copy)] +struct Module { + weight: Weight, +} + +impl Module { + fn fuel_excluding_fuel_weight(self) -> Fuel { + self.weight.required_fuel() + } + + fn fuel_including_fuel_weight(self) -> Fuel { + iter::successors(Some(self.weight.required_fuel()), |fuel| { + if fuel.is_zero() { + None + } else { + Some(fuel.weight().required_fuel()) + } + }) + .sum() + } +} + +#[derive(Debug, derive_more::FromStr, Clone, Copy)] +struct Weight(u32); + +impl Weight { + fn required_fuel(self) -> Fuel { + Fuel((self.0 / 3).saturating_sub(2)) + } +} + +#[derive(Debug, derive_more::Add, derive_more::Sum, Clone, Copy, derive_more::Display)] +struct Fuel(u32); + +impl Fuel { + fn weight(self) -> Weight { + Weight(self.0) + } + + fn is_zero(self) -> bool { + self.0 == 0 + } +} 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, +} + +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(data: Result, message: &str) -> A { + match data { + Ok(data) => data, + Err(e) => { + eprintln!("{}: {}", message, e); + process::exit(1); + } + } +} + +#[derive(Debug)] +struct AsteroidMap { + asteroids: Vec, +} + +impl FromIterator for AsteroidMap { + fn from_iter>(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::>() + }) + .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 { + 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 { + 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 { + 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/2019/src/bin/day_11.rs b/2019/src/bin/day_11.rs new file mode 100644 index 0000000..da3e1fd --- /dev/null +++ b/2019/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::(), "Invalid number")) + .collect::(); + + 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(data: Result, 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::() + .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 { + 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 { + 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 { + 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/2019/src/bin/day_12.rs b/2019/src/bin/day_12.rs new file mode 100644 index 0000000..7e42f4c --- /dev/null +++ b/2019/src/bin/day_12.rs @@ -0,0 +1,205 @@ +use std::io; +use std::io::prelude::*; +use std::iter; +use std::num::ParseIntError; +use std::ops; +use std::process; +use std::str::FromStr; +use structopt::StructOpt; + +#[derive(Debug, StructOpt)] +#[structopt(name = "Day 12: The N-Body Problem")] +/// Simulates N bodies, physically interacting +/// +/// See https://adventofcode.com/2019/day/12 for details. +struct Opt { + #[structopt(short = "n")] + n: Option, +} + +fn main() { + let stdin = io::stdin(); + let opt = Opt::from_args(); + + let planets: Vec = stdin + .lock() + .lines() + .map(|x| exit_on_failed_assertion(x, "Error reading input")) + .map(|x| exit_on_failed_assertion(x.parse::(), "Input was not a valid planet")) + .collect(); + + match opt.n { + Some(n) => println!("{}", energy(simulate_planets_n_iterations(planets, n))), + None => println!("{}", simulate_planets_to_duplicate(planets)), + }; +} + +fn exit_on_failed_assertion(data: Result, message: &str) -> A { + match data { + Ok(data) => data, + Err(e) => { + eprintln!("{}: {}", message, e); + process::exit(1); + } + } +} + +fn energy(planets: Vec) -> i32 { + planets.into_iter().map(|p| p.energy()).sum() +} + +fn simulate_planets_n_iterations(planets: Vec, n: u64) -> Vec { + simulate_planets_iter(planets) + .find(|(i, _)| *i == n) + .unwrap() + .1 +} + +fn simulate_planets_to_duplicate(planets: Vec) -> u64 { + lowest_common_multiple( + simulate_planets_to_duplicate_1d(planets.clone(), |(p, o)| p.equal_x(o)), + simulate_planets_to_duplicate_1d(planets.clone(), |(p, o)| p.equal_y(o)), + simulate_planets_to_duplicate_1d(planets.clone(), |(p, o)| p.equal_z(o)), + ) +} + +fn simulate_planets_to_duplicate_1d( + planets: Vec, + eq: impl FnMut((&Planet, &Planet)) -> bool + Copy, +) -> u64 { + simulate_planets_iter(planets.clone()) + .skip(1) + .find(|(_i, ps)| ps.iter().zip(planets.iter()).all(eq)) + .unwrap() + .0 +} + +fn lowest_common_multiple(x: u64, y: u64, z: u64) -> u64 { + (1..) + .map(|i| x * i) + .find(|mx| multiples(y, *mx) && multiples(z, *mx)) + .unwrap() +} + +fn multiples(x: u64, target: u64) -> bool { + target % x == 0 +} + +fn simulate_planets_iter(planets: Vec) -> impl Iterator)> { + iter::successors(Some((0, planets.clone())), |(i, planets)| { + Some((i + 1, simulate_planets(planets.clone()))) + }) +} + +fn simulate_planets(planets: Vec) -> Vec { + simulate_velocity(simulate_gravity(planets)) +} + +fn simulate_gravity(planets: Vec) -> Vec { + planets + .iter() + .map(|p| Planet { + pos: p.pos.clone(), + vel: planets + .iter() + .filter(|o| p != *o) + .map(|o| p.acc(o)) + .fold(p.vel, |acc, next| acc + next), + }) + .collect() +} + +fn simulate_velocity(planets: Vec) -> Vec { + planets + .into_iter() + .map(|p| Planet { + pos: p.pos + p.vel, + vel: p.vel, + }) + .collect() +} + +#[derive(Debug, Default, Clone, PartialEq)] +struct Planet { + pos: Vec3d, + vel: Vec3d, +} + +#[derive(Debug, Default, Clone, Copy, PartialEq)] +struct Vec3d { + x: i32, + y: i32, + z: i32, +} + +impl FromStr for Planet { + type Err = ParseIntError; + + fn from_str(s: &str) -> Result { + s.replace(|c| "<>xyz= ".contains(c), "") + .split(',') + .map(|i| i.parse::()) + .collect::, _>>() + .and_then(|v| match &v[..] { + [x, y, z] => Ok(Planet { + pos: Vec3d { + x: *x, + y: *y, + z: *z, + }, + vel: Vec3d::default(), + }), + _ => "wrong number of fields" + .parse::() + .map(|_x| Planet::default()), + }) + } +} + +impl Planet { + fn acc(&self, other: &Planet) -> Vec3d { + Vec3d { + x: gravity(self.pos.x, other.pos.x), + y: gravity(self.pos.y, other.pos.y), + z: gravity(self.pos.z, other.pos.z), + } + } + + fn energy(&self) -> i32 { + (self.pos.x.abs() + self.pos.y.abs() + self.pos.z.abs()) + * (self.vel.x.abs() + self.vel.y.abs() + self.vel.z.abs()) + } + + fn equal_x(&self, other: &Planet) -> bool { + self.pos.x == other.pos.x && self.vel.x == other.vel.x + } + + fn equal_y(&self, other: &Planet) -> bool { + self.pos.y == other.pos.y && self.vel.y == other.vel.y + } + + fn equal_z(&self, other: &Planet) -> bool { + self.pos.z == other.pos.z && self.vel.z == other.vel.z + } +} + +fn gravity(this: i32, that: i32) -> i32 { + if that > this { + 1 + } else if this > that { + -1 + } else { + 0 + } +} + +impl ops::Add for Vec3d { + type Output = Vec3d; + fn add(self, rhs: Vec3d) -> Self::Output { + Vec3d { + x: self.x + rhs.x, + y: self.y + rhs.y, + z: self.z + rhs.z, + } + } +} diff --git a/2019/src/bin/day_13.rs b/2019/src/bin/day_13.rs new file mode 100644 index 0000000..ac1c478 --- /dev/null +++ b/2019/src/bin/day_13.rs @@ -0,0 +1,149 @@ +use aoc2019::*; +use rpds::list; +use rpds::list::List; +use rpds::vector::Vector; +use rpds::RedBlackTreeMap; +use std::cmp::Ordering; +use std::io; +use std::io::prelude::*; +use std::iter; +use std::process; +use structopt::StructOpt; + +#[derive(Debug, StructOpt)] +#[structopt(name = "Day 13: Care Package")] +/// Executes an Intcode game +/// +/// The program is read from stdin as a series of comma-separated +/// values. Newlines are ignored. +/// +/// See https://adventofcode.com/2019/day/13 for details. +struct Opt { + #[structopt(short = "q", long = "quarters")] + quarters: Option, +} + +fn main() { + let stdin = io::stdin(); + let opt = Opt::from_args(); + + 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::(), "Invalid number")) + .collect::(); + + match opt.quarters { + Some(quarters) => { + let result = score_on_won_game(program.with_mem_0(quarters)); + println!("{}", result); + } + None => { + let result = exit_on_failed_assertion(program.execute(), "Program errored"); + println!("{}", count_blocks(&result)); + } + } +} + +fn exit_on_failed_assertion(data: Result, message: &str) -> A { + match data { + Ok(data) => data, + Err(e) => { + eprintln!("{}: {}", message, e); + process::exit(1); + } + } +} + +#[derive(Default, Clone)] +struct Screen { + screen: RedBlackTreeMap<(Intcode, Intcode), Intcode>, + previous_ball: (Intcode, Intcode), + ball: (Intcode, Intcode), + paddle: (Intcode, Intcode), + score: Intcode, +} + +impl Screen { + fn render(output: &Vector) -> Screen { + (0..output.len() / 3) + .map(|i| i * 3) + .map(|i| { + ( + output[i].clone(), + output[i + 1].clone(), + output[i + 2].clone(), + ) + }) + .fold(Screen::default(), |acc, (x, y, tile)| { + if x == Intcode::from(-1) && y == Intcode::from(0) { + Screen { score: tile, ..acc } + } else if tile == Intcode::from(4) { + Screen { + ball: (x, y), + previous_ball: acc.ball, + ..acc + } + } else if tile == Intcode::from(3) { + Screen { + paddle: (x.clone(), y.clone()), + screen: acc.screen.insert((x, y), tile), + ..acc + } + } else if tile == Intcode::from(0) { + Screen { + screen: acc.screen.remove(&(x, y)), + ..acc + } + } else { + Screen { + screen: acc.screen.insert((x, y), tile), + ..acc + } + } + }) + } + + fn paddle_required_direction(&self) -> Intcode { + match self.paddle.0.cmp(&self.ball.0) { + Ordering::Less => Intcode::from(1), + Ordering::Equal => Intcode::from(0), + Ordering::Greater => Intcode::from(-1), + } + } +} + +fn count_blocks(output: &Vector) -> usize { + Screen::render(output) + .screen + .values() + .filter(|val| **val == Intcode::from(2)) + .count() +} + +fn score_on_won_game(program: IntcodeProgram) -> Intcode { + Screen::render( + &iter::successors(Some(program.run_to_termination_or_input()), |program| { + Some(next_game_state(program.clone())) + }) + .take_while(|program| !program.halted) + .find(|program| count_blocks(&program.output) == 0) + .unwrap() + .output, + ) + .score +} + +fn next_game_state(program: IntcodeProgram) -> IntcodeProgram { + program_with_next_input(program.run_to_termination_or_input()) +} + +fn program_with_next_input(program: IntcodeProgram) -> IntcodeProgram { + program.with_input(list![next_input(&program.output)]) +} + +fn next_input(output: &Vector) -> Intcode { + Screen::render(output).paddle_required_direction() +} diff --git a/2019/src/bin/day_14.rs b/2019/src/bin/day_14.rs new file mode 100644 index 0000000..0532f5f --- /dev/null +++ b/2019/src/bin/day_14.rs @@ -0,0 +1,221 @@ +use rpds::map::red_black_tree_map::RedBlackTreeMap; +use rpds::rbt_map; +use rpds::vector::Vector; +use std::fmt; +use std::io; +use std::io::prelude::*; +use std::iter; +use std::process; +use std::str::FromStr; +use structopt::StructOpt; + +#[derive(Debug, StructOpt)] +#[structopt(name = "Day 14: Space Stoichiometry")] +/// Finds how much ore you need to produce one fuel. +/// +/// Recipes are passed in on stdin, one per line. +/// +/// See https://adventofcode.com/2019/day/14 for details. +struct Opt { + #[structopt(long = "available-ore")] + available_ore: Option, +} + +fn main() { + let stdin = io::stdin(); + let opt = Opt::from_args(); + + let recipes = stdin + .lock() + .lines() + .map(|x| exit_on_failed_assertion(x, "Error reading input")) + .map(|x| exit_on_failed_assertion(x.parse::(), "Input was not a valid recipe")) + .collect::>(); + + match opt.available_ore { + Some(ore) => println!("{}", max_fuel_production(ore, &recipes)), + None => println!("{}", Desires::new(1).min_ore_required(&recipes)), + } +} + +fn exit_on_failed_assertion(data: Result, message: &str) -> A { + match data { + Ok(data) => data, + Err(e) => { + eprintln!("{}: {}", message, e); + process::exit(1); + } + } +} + +fn max_fuel_production(ore_max: i64, recipes: &[Recipe]) -> i64 { + binary_search_max_fuel_production( + ore_max / Desires::new(1).min_ore_required(&recipes), + 2 * ore_max / Desires::new(1).min_ore_required(&recipes), + ore_max, + recipes, + ) +} + +fn binary_search_max_fuel_production( + fuel_min: i64, + fuel_max: i64, + ore_max: i64, + recipes: &[Recipe], +) -> i64 { + if fuel_max - fuel_min <= 1 { + fuel_min + } else if Desires::new((fuel_min + fuel_max) / 2).min_ore_required(recipes) <= ore_max { + binary_search_max_fuel_production((fuel_min + fuel_max) / 2, fuel_max, ore_max, recipes) + } else { + binary_search_max_fuel_production(fuel_min, (fuel_min + fuel_max) / 2, ore_max, recipes) + } +} + +#[derive(Debug, Clone)] +struct Recipe { + ingredients: Vector, + output: Chemical, +} + +#[derive(Default, Debug, Clone)] +struct Chemical { + name: String, + quantity: i64, +} + +impl FromStr for Recipe { + type Err = ParseErr; + fn from_str(s: &str) -> Result { + // 2 XSNKB, 15 ZVMCB, 3 KDFNZ => 2 RFLX + s.replace(" => ", "=") + .replace(", ", ",") + .split(|c| c == ',' || c == '=') + .map(|chem| chem.parse::()) + .collect::, ParseErr>>() + .map(|chemicals| Recipe { + ingredients: chemicals + .drop_last() + .expect("Assertion failed: line did not have any chemicals"), + output: chemicals + .last() + .cloned() + .expect("Assertion failed: line did not have any chemicals"), + }) + } +} + +impl Recipe { + fn required_scale(&self, desired_quantity: i64) -> i64 { + (desired_quantity + self.output.quantity - 1) / self.output.quantity + } +} + +impl FromStr for Chemical { + type Err = ParseErr; + fn from_str(s: &str) -> Result { + // 1 FUEL + match s.split(' ').collect::>()[..] { + [quantity, name] => quantity + .parse::() + .map_err(|_| ParseErr) + .map(|q| Chemical { + name: name.to_string(), + quantity: q, + }), + _ => Err(ParseErr), + } + } +} + +impl Chemical { + fn scale(&self, scale: i64) -> Chemical { + Chemical { + name: self.name.clone(), + quantity: self.quantity * scale, + } + } +} + +#[derive(Debug, Clone, Copy)] +struct ParseErr; + +impl fmt::Display for ParseErr { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!(f, "Error parsing input") + } +} + +impl std::error::Error for ParseErr {} + +#[derive(Debug, Clone)] +struct Desires { + chemicals: RedBlackTreeMap, +} + +impl Desires { + fn new(fuel: i64) -> Desires { + Desires { + chemicals: rbt_map!["FUEL".to_string() => fuel, "ORE".to_string() => 0], + } + } + + fn min_ore_required(&self, recipes: &[Recipe]) -> i64 { + iter::successors(Some(self.clone()), |prev| Some(prev.next(recipes))) + .find(|desires| desires.is_only_ore()) + .unwrap() + .chemicals + .get("ORE") + .cloned() + .unwrap() + } + + fn is_only_ore(&self) -> bool { + !self + .chemicals + .iter() + .any(|(name, quantity)| *quantity > 0 && name != "ORE") + } + + fn next(&self, recipes: &[Recipe]) -> Desires { + self.chemicals + .iter() + .find(|(name, quantity)| **quantity > 0 && *name != "ORE") + .map(|(mixing, quantity)| { + self.with_mixed_recipe( + recipes + .iter() + .find(|recipe| recipe.output.name == *mixing) + .expect("Required chemical without a recipe"), + *quantity, + ) + }) + .unwrap_or(self.clone()) + } + + fn with_mixed_recipe(&self, recipe: &Recipe, desired_quantity: i64) -> Desires { + recipe.ingredients.iter().fold( + self.with_chemical( + recipe + .output + .scale(-1 * recipe.required_scale(desired_quantity)), + ), + |acc, next_ingredient| { + acc.with_chemical(next_ingredient.scale(recipe.required_scale(desired_quantity))) + }, + ) + } + + fn with_chemical(&self, chemical: Chemical) -> Desires { + Desires { + chemicals: match self.chemicals.get(&chemical.name) { + Some(existing_quantity) => self + .chemicals + .insert(chemical.name.clone(), existing_quantity + chemical.quantity), + None => self + .chemicals + .insert(chemical.name.clone(), chemical.quantity), + }, + } + } +} diff --git a/2019/src/bin/day_15.rs b/2019/src/bin/day_15.rs new file mode 100644 index 0000000..b2205bb --- /dev/null +++ b/2019/src/bin/day_15.rs @@ -0,0 +1,183 @@ +use aoc2019::*; +use rpds::list; +use rpds::list::List; +use rpds::rbt_set; +use rpds::set::red_black_tree_set::RedBlackTreeSet; +use rpds::vector; +use rpds::vector::Vector; +use std::io; +use std::io::prelude::*; +use std::iter; +use std::process; +use structopt::StructOpt; + +#[derive(Debug, StructOpt)] +#[structopt(name = "Day 15: Oxygen System")] +/// Executes an Intcode robot that's searching a map. Prints the +/// time taken for oxygen to propagate to the whole area. +/// +/// See https://adventofcode.com/2019/day/15 for details. +struct Opt { + /// Run in 'find' mode, find the oxygen tank but don't see how long it takes the oxygen to propagate + #[structopt(short = "f")] + find: bool, +} + +fn main() { + let stdin = io::stdin(); + let opt = Opt::from_args(); + + 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::(), "Invalid number")) + .collect::(); + + if opt.find { + println!("{}", shortest_distance(program)); + } else { + println!("{}", max_depth_from_oxygen(program)); + } +} + +fn exit_on_failed_assertion(data: Result, message: &str) -> A { + match data { + Ok(data) => data, + Err(e) => { + eprintln!("{}: {}", message, e); + process::exit(1); + } + } +} + +fn shortest_distance(program: IntcodeProgram) -> usize { + iter::successors( + Some(( + rbt_set![(0, 0)], + vector![((0, 0), program.run_to_termination_or_input())], + )), + |(visited, programs)| { + Some(next_depth_states( + visited.clone(), + next_program_states(programs, visited), + )) + }, + ) + .enumerate() + .find(|(_i, (_visited, programs))| { + programs + .iter() + .any(|(_location, program)| program.output == vector![2.into()]) + }) + .unwrap() + .0 +} + +fn max_depth_from_oxygen(program: IntcodeProgram) -> usize { + max_depth( + iter::successors( + Some(( + rbt_set![(0, 0)], + vector![((0, 0), program.run_to_termination_or_input())], + )), + |(visited, programs)| { + Some(next_depth_states( + visited.clone(), + next_program_states(programs, visited), + )) + }, + ) + .find(|(_visited, programs)| { + programs + .iter() + .any(|(_location, program)| program.output == vector![2.into()]) + }) + .unwrap() + .1 + .iter() + .find(|(_location, program)| program.output == vector![2.into()]) + .cloned() + .unwrap() + .1, + ) +} + +fn max_depth(program: IntcodeProgram) -> usize { + iter::successors( + Some(( + rbt_set![(0, 0)], + vector![((0, 0), program.run_to_termination_or_input())], + )), + |(visited, programs)| { + Some(next_depth_states( + visited.clone(), + next_program_states(programs, visited), + )) + }, + ) + .take_while(|(_visited, programs)| programs.len() > 0) + .count() + - 1 +} + +fn inputs() -> [((i32, i32), Intcode); 4] { + [ + ((0, 1), Intcode::from(1)), + ((0, -1), Intcode::from(2)), + ((1, 0), Intcode::from(3)), + ((-1, 0), Intcode::from(4)), + ] +} + +fn next_program_states( + programs: &Vector<((i32, i32), IntcodeProgram)>, + visited: &RedBlackTreeSet<(i32, i32)>, +) -> Vector<((i32, i32), IntcodeProgram)> { + let inputs = inputs(); + programs + .iter() + .flat_map(|(location, program)| { + inputs.iter().map(move |(vec, input)| { + ( + (location.0 + vec.0, location.1 + vec.1), + program + .with_cleared_output() + .with_input(list![input.clone()]) + .run_to_termination_or_input(), + ) + }) + }) + .filter(|(location, program)| { + !visited.contains(location) && program.output != vector![0.into()] + }) + .collect() +} + +fn next_depth_states( + previous_visited: RedBlackTreeSet<(i32, i32)>, + programs: Vector<((i32, i32), IntcodeProgram)>, +) -> ( + RedBlackTreeSet<(i32, i32)>, + Vector<((i32, i32), IntcodeProgram)>, +) { + ( + programs + .iter() + .fold(previous_visited, |acc, (next, _)| acc.insert(*next)), + dedup_locations(programs), + ) +} + +fn dedup_locations( + programs: Vector<((i32, i32), IntcodeProgram)>, +) -> Vector<((i32, i32), IntcodeProgram)> { + programs.iter().fold(Vector::new(), |acc, next| { + if acc.iter().any(|(loc, _)| *loc == next.0) { + acc + } else { + acc.push_back(next.clone()) + } + }) +} diff --git a/2019/src/bin/day_16.rs b/2019/src/bin/day_16.rs new file mode 100644 index 0000000..aa53127 --- /dev/null +++ b/2019/src/bin/day_16.rs @@ -0,0 +1,112 @@ +use rayon::prelude::*; +use std::io; +use std::io::prelude::*; +use std::iter; +use std::num::ParseIntError; +use std::process; +use structopt::StructOpt; + +#[derive(Debug, StructOpt)] +#[structopt(name = "Day 16: Flawed Frequency Transmission")] +/// Performs the flawed frequency transform of a number. +/// +/// See https://adventofcode.com/2019/day/16 for details. +struct Opt { + /// the offset after which you start reading output + #[structopt(short = "o", long = "offset", default_value = "0")] + offset: usize, + input_repeats: usize, + fft_repeats: usize, +} + +fn main() { + let stdin = io::stdin(); + let opt = Opt::from_args(); + + stdin + .lock() + .lines() + .map(|x| exit_on_failed_assertion(x, "Error reading input")) + .map(|x| exit_on_failed_assertion(parse(&x), "Input was not a valid recipe")) + .for_each(|input| { + println!( + "{}", + transform(input, opt.input_repeats, opt.fft_repeats, opt.offset) + .into_iter() + .map(|c| c.to_string()) + .collect::() + ); + }); +} + +fn exit_on_failed_assertion(data: Result, message: &str) -> A { + match data { + Ok(data) => data, + Err(e) => { + eprintln!("{}: {}", message, e); + process::exit(1); + } + } +} + +fn parse(s: &str) -> Result, ParseIntError> { + s.chars().map(|c| c.to_string().parse::()).collect() +} + +fn transform(input: Vec, input_repeats: usize, fft_repeats: usize, offset: usize) -> Vec { + iter::successors( + Some( + input + .iter() + .cycle() + .take(input.len() * input_repeats) + .cloned() + .collect::>(), + ), + |input| Some(next_phase(input, offset)), + ) + .nth(fft_repeats) + .unwrap() + .into_iter() + .skip(offset) + .take(8) + .collect() +} + +fn next_phase(input: &Vec, offset: usize) -> Vec { + if offset > input.len() / 2 { + (0..input.len()) + .into_par_iter() + .map(|digit| { + if digit < offset { + 0 + } else { + input.iter().skip(digit).sum::().abs() % 10 + } + }) + .collect() + } else { + (0..input.len()) + .into_par_iter() + .map(|digit| { + input + .iter() + .zip(pattern(digit)) + .map(|(x, y)| x * y) + .sum::() + .abs() + % 10 + }) + .collect() + } +} + +fn pattern(digit: usize) -> impl Iterator { + iter::repeat(0) + .take(digit + 1) + .chain(iter::repeat(1).take(digit + 1)) + .chain(iter::repeat(0).take(digit + 1)) + .chain(iter::repeat(-1).take(digit + 1)) + .cycle() + .skip(1) +} diff --git a/2019/src/bin/day_17.rs b/2019/src/bin/day_17.rs new file mode 100644 index 0000000..e85373c --- /dev/null +++ b/2019/src/bin/day_17.rs @@ -0,0 +1,78 @@ +use aoc2019::*; +use std::io; +use std::io::prelude::*; +use std::process; +use structopt::StructOpt; + +#[derive(Debug, StructOpt)] +#[structopt(name = "Day 17: Set and Forget")] +/// Pilots a vacuum robot around on a scaffold. What could go wrong? +/// +/// See https://adventofcode.com/2019/day/17 for details. +struct Opt { + /// Draw the map and exit + #[structopt(short = "d")] + draw_map: bool, +} + +fn main() { + let stdin = io::stdin(); + let opt = Opt::from_args(); + + 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::(), "Invalid number")) + .collect::(); + + let result = exit_on_failed_assertion( + if opt.draw_map { + program.execute() + } else { + // L,12,L,8,R,10,R,10,L,6,L,4,L,12,L,12,L,8,R,10,R,10,L,6,L,4,L,12,R,10,L,8,L,4,R,10,L,6,L,4,L,12,L,12,L,8,R,10,R,10,R,10,L,8,L,4,R,10,L,6,L,4,L,12,R,10,L,8,L,4,R,10 + // | | || + + let input = vec![ + "A,B,A,B,C,B,A,C,B,C\n", + "L,12,L,8,R,10,R,10\n", + "L,6,L,4,L,12\n", + "R,10,L,8,L,4,R,10\n", + "y\n", + ]; + program + .with_mem_0(Intcode::from(2)) + .with_input( + input + .iter() + .flat_map(|line| line.chars().map(|c| Intcode::from(c as u8))) + .collect(), + ) + .execute() + }, + "Program failed", + ); + + println!( + "{}", + result + .drop_last() + .unwrap() + .iter() + .flat_map(|c| c.to_signed_bytes_be()) + .map(|c| c as char) + .collect::() + ); + println!("{}", result.last().unwrap()); +} + +fn exit_on_failed_assertion(data: Result, message: &str) -> A { + match data { + Ok(data) => data, + Err(e) => { + eprintln!("{}: {}", message, e); + process::exit(1); + } + } +} diff --git a/2019/src/bin/day_18.rs b/2019/src/bin/day_18.rs new file mode 100644 index 0000000..255baa0 --- /dev/null +++ b/2019/src/bin/day_18.rs @@ -0,0 +1,365 @@ +use rpds::rbt_set; +use rpds::vector::Vector; +use rpds::RedBlackTreeMap; +use rpds::RedBlackTreeSet; +use std::io; +use std::io::prelude::*; +use std::iter; +use std::iter::FromIterator; +use std::process; +use structopt::StructOpt; + +#[derive(Debug, StructOpt)] +#[structopt(name = "Day 18: Many-Worlds Interpretation")] +/// Finds the shortest path through a maze with keys +/// +/// See https://adventofcode.com/2019/day/18 for details. +struct Opt {} + +fn main() { + let stdin = io::stdin(); + let _opt = Opt::from_args(); + + let maze: Maze = stdin + .lock() + .lines() + .map(|x| exit_on_failed_assertion(x, "Error reading input")) + .collect(); + + println!("{}", maze.shortest_route()); +} + +fn exit_on_failed_assertion(data: Result, message: &str) -> A { + match data { + Ok(data) => data, + Err(e) => { + eprintln!("{}: {}", message, e); + process::exit(1); + } + } +} + +struct Maze { + blocks: Vec>, + start: BoardState, + keys: KeySet, +} + +impl FromIterator for Maze { + fn from_iter>(iter: T) -> Self { + Maze::from_blocks( + iter.into_iter() + .map(|line| line.chars().collect()) + .collect(), + ) + } +} + +impl Maze { + fn from_blocks(blocks: Vec>) -> Maze { + Maze { + start: BoardState { + robots: blocks + .iter() + .enumerate() + .flat_map(|(y, line)| { + line.iter() + .enumerate() + .filter(|(_x, ch)| **ch == '@') + .map(move |(x, _ch)| Location { x, y }) + }) + .collect(), + keys: KeySet::default(), + }, + keys: blocks + .iter() + .flat_map(|line| line.iter()) + .fold(KeySet::default(), |acc, next| acc.add_key(*next)), + blocks, + } + } + + fn block_at(&self, location: &Location) -> Option { + self.blocks + .get(location.y) + .and_then(|line| line.get(location.x)) + .cloned() + } + + fn shortest_route(&self) -> usize { + iter::successors( + Some(( + ExploredStates::default().insert(&self.start), + rbt_set![self.start.clone()], + )), + |(explored, locations)| { + Some(Maze::next_depth_states( + explored.clone(), + self.next_locations(locations, explored), + )) + }, + ) + // .inspect(|(explored, states)| eprintln!("{:?}", states)) + .take_while(|(_explored, states)| states.size() > 0) + .enumerate() + .find(|(_i, (_explored, states))| states.iter().any(|state| state.keys == self.keys)) + .unwrap() + .0 + } + + fn next_depth_states( + explored: ExploredStates, + locations: RedBlackTreeSet, + ) -> (ExploredStates, RedBlackTreeSet) { + ( + locations + .iter() + .fold(explored, |acc, next| acc.insert(next)), + locations, + ) + } + + fn next_locations( + &self, + locations: &RedBlackTreeSet, + explored: &ExploredStates, + ) -> RedBlackTreeSet { + locations + .iter() + .flat_map(|current| { + (0..current.robots.len()).flat_map(move |i_robot| { + [(-1, 0), (1, 0), (0, -1), (0, 1)] + .iter() + .map(move |(dx, dy)| current.next(i_robot, *dx, *dy)) + .map(move |(state, new_location)| { + self.block_at(&new_location) + .map(|c| state.with_key(c)) + .unwrap_or(state) + }) + }) + }) + .filter(|state| self.is_open(state)) + .filter(|state| !explored.contains(state)) + .collect() + } + + fn is_open(&self, state: &BoardState) -> bool { + state.robots.iter().all(|location| { + self.block_at(location) + .map(|c| Maze::char_is_open(c, state.keys)) + .unwrap_or(false) + }) + } + + fn char_is_open(c: char, keys: KeySet) -> bool { + c != '#' && !keys.door_is_locked(c) + } +} + +#[derive(Default, Debug, Clone)] +struct ExploredStates { + for_key: RedBlackTreeMap, +} + +#[derive(Default, Debug, Clone)] +struct ExploredStatesForKey { + robots: Vector>, +} + +impl ExploredStates { + fn insert(&self, new: &BoardState) -> ExploredStates { + ExploredStates { + for_key: self.for_key.insert( + new.keys.clone(), + self.for_key + .get(&new.keys) + .map(|current| ExploredStatesForKey { + robots: current + .robots + .iter() + .zip(new.robots.iter()) + .map(|(current_explored, robot)| current_explored.insert(robot.clone())) + .collect(), + }) + .unwrap_or_else(|| ExploredStatesForKey { + robots: new + .robots + .iter() + .map(|robot| RedBlackTreeSet::new().insert(robot.clone())) + .collect(), + }), + ), + } + } + + fn contains(&self, state: &BoardState) -> bool { + self.for_key + .get(&state.keys) + .filter(|for_key| { + state + .robots + .iter() + .zip(for_key.robots.iter()) + .all(|(r_state, r_explored)| r_explored.contains(r_state)) + }) + .is_some() + } +} + +#[derive(Default, Debug, Clone, PartialEq, Eq, PartialOrd, Ord)] +struct BoardState { + robots: Vector, + keys: KeySet, +} + +impl BoardState { + fn next(&self, i_robot: usize, dx: isize, dy: isize) -> (BoardState, Location) { + ( + BoardState { + robots: self + .robots + .set(i_robot, self.robots[i_robot].next(dx, dy)) + .unwrap(), + ..self.clone() + }, + self.robots[i_robot].next(dx, dy), + ) + } + + fn with_key(&self, c: char) -> BoardState { + BoardState { + keys: self.keys.add_key(c), + ..self.clone() + } + } +} + +#[derive(Default, Debug, Clone, PartialEq, Eq, PartialOrd, Ord)] +struct Location { + x: usize, + y: usize, +} + +impl Location { + fn next(&self, dx: isize, dy: isize) -> Location { + Location { + x: (self.x as isize + dx) as usize, + y: (self.y as isize + dy) as usize, + } + } +} + +#[derive(Default, Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)] +struct KeySet { + bitset: u32, +} + +impl KeySet { + fn add_key(self, key: char) -> KeySet { + KeySet { + bitset: self.bitset | KeySet::key_to_bitset(key), + } + } + + fn door_is_locked(self, door: char) -> bool { + KeySet::door_to_bitset(door) & (!self.bitset) > 0 + } + + fn key_to_bitset(key: char) -> u32 { + if key.is_ascii_alphabetic() && key.is_ascii_lowercase() { + 1 << (key as u8 - b'a') + } else { + 0 + } + } + + fn door_to_bitset(door: char) -> u32 { + if door.is_ascii_alphabetic() && door.is_ascii_uppercase() { + 1 << (door as u8 - b'A') + } else { + 0 + } + } +} + +#[test] +fn doors_are_locked_without_key() { + assert_eq!(true, KeySet::default().door_is_locked('A')) +} + +#[test] +fn doors_are_unlocked_with_key() { + assert_eq!(false, KeySet::default().add_key('a').door_is_locked('A')) +} + +#[test] +fn example_1() { + let maze: Maze = r" +######### +#b.A.@.a# +######### +" + .split('\n') + .map(|s| s.to_string()) + .collect(); + + assert_eq!(maze.shortest_route(), 8); +} + +#[test] +fn example_2() { + let maze: Maze = r" +################# +#i.G..c...e..H.p# +########.######## +#j.A..b...f..D.o# +########@######## +#k.E..a...g..B.n# +########.######## +#l.F..d...h..C.m# +################# +" + .split('\n') + .map(|s| s.to_string()) + .collect(); + + assert_eq!(maze.shortest_route(), 136); +} + +#[test] +fn example_3() { + let maze: Maze = r" +############# +#DcBa.#.GhKl# +#.###@#@#I### +#e#d#####j#k# +###C#@#@###J# +#fEbA.#.FgHi# +############# +" + .split('\n') + .map(|s| s.to_string()) + .collect(); + + assert_eq!(maze.shortest_route(), 32); +} + +#[test] +fn example_4() { + let maze: Maze = r" +############# +#g#f.D#..h#l# +#F###e#E###.# +#dCba@#@BcIJ# +############# +#nK.L@#@G...# +#M###N#H###.# +#o#m..#i#jk.# +############# +" + .split('\n') + .map(|s| s.to_string()) + .collect(); + + assert_eq!(maze.shortest_route(), 74); +} diff --git a/2019/src/bin/day_19.rs b/2019/src/bin/day_19.rs new file mode 100644 index 0000000..73c8374 --- /dev/null +++ b/2019/src/bin/day_19.rs @@ -0,0 +1,102 @@ +use aoc2019::*; +use cached::cached_key; +use cached::UnboundCache; +use rpds::list; +use rpds::list::List; +use rpds::vector; +use std::io; +use std::io::prelude::*; +use std::process; +use structopt::StructOpt; + +#[derive(Debug, StructOpt)] +#[structopt(name = "Day 19: Tractor Beam")] +/// Finds the effective area of a tractor beam in an n x n square, and +/// how far away you need to be to capture Santa's ship. +/// +/// See https://adventofcode.com/2019/day/19 for details. +struct Opt { + /// The size for a diagnostics scan. + #[structopt(long = "diagnostics-size")] + diagnostics_size: Option, + /// The size of Santa's ship + #[structopt(long = "ship-size")] + ship_size: Option, +} + +fn main() { + let stdin = io::stdin(); + let opt = Opt::from_args(); + + 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::(), "Invalid number")) + .collect::(); + + if let Some(size) = opt.diagnostics_size { + println!("{}", count_active_in_area(program.clone(), 0, 0, size)); + } + if let Some(size) = opt.ship_size { + println!("{:?}", find_closest_ship_space(program, size)) + } +} + +fn exit_on_failed_assertion(data: Result, message: &str) -> A { + match data { + Ok(data) => data, + Err(e) => { + eprintln!("{}: {}", message, e); + process::exit(1); + } + } +} + +fn count_active_in_area(program: IntcodeProgram, left: usize, top: usize, size: usize) -> usize { + (left..left + size) + .flat_map(|x| (top..top + size).map(move |y| (x, y))) + .filter(|(x, y)| tractor_beam_is_active(program.clone(), *x, *y)) + .count() +} + +fn area_is_all_full(program: IntcodeProgram, left: usize, top: usize, size: usize) -> bool { + // This check with a grid that's aligned to 10 gives an early exit + // for most, that will have the program executions shared. This + // makes the memoized tractor function more effective at cutting + // down on execution, even though you need to do the whole lot + // again to verify if this passes. + (left..left + size) + .flat_map(|x| (top..top + size).map(move |y| (x, y))) + .filter(|(x, y)| x % 10 == 0 && y % 10 == 0) + .all(|(x, y)| tractor_beam_is_active(program.clone(), x, y)) + && (left..left + size) + .flat_map(|x| (top..top + size).map(move |y| (x, y))) + .all(|(x, y)| tractor_beam_is_active(program.clone(), x, y)) +} + +fn find_closest_ship_space(program: IntcodeProgram, size: usize) -> (usize, usize) { + (0..) + .flat_map(|radius| { + (0..radius) + .flat_map(move |x| (0..radius).map(move |y| (x, y))) + .filter(move |(x, y)| { + (radius - 1) * (radius - 1) < x * x + y * y && x * x + y * y <= radius * radius + }) + }) + .find(|(x, y)| area_is_all_full(program.clone(), *x, *y, size)) + .unwrap() +} + +cached_key! { + TRACTOR_BEAM_IS_ACTIVE: UnboundCache<(usize, usize), bool> = UnboundCache::new(); + Key = { (x, y) }; + fn tractor_beam_is_active(program: IntcodeProgram, x: usize, y: usize) -> bool = { + program + .with_input(list![Intcode::from(x), Intcode::from(y)]) + .execute() + == Ok(vector![Intcode::from(1)]) + + } +} diff --git a/2019/src/bin/day_2.rs b/2019/src/bin/day_2.rs new file mode 100644 index 0000000..ba9e189 --- /dev/null +++ b/2019/src/bin/day_2.rs @@ -0,0 +1,96 @@ +use aoc2019::*; +use std::io; +use std::io::prelude::*; +use std::process; +use structopt::StructOpt; + +#[derive(Debug, StructOpt)] +#[structopt(name = "Day 2: 1202 Program Alarm")] +/// Executes an Intcode program +/// +/// The program is read from stdin as a series of comma-separated +/// values. Newlines are ignored. When the program halts, the value at +/// position 0 is returned. +/// +/// If an output is provided, all possible inputs are tried to find +/// the input that results in the desired output. In this case, the +/// inputs are returned in the format (noun, verb). +/// +///See https://adventofcode.com/2019/day/2 for details. +struct Opt { + #[structopt(short = "n", long = "noun")] + noun: Option, + #[structopt(short = "v", long = "verb")] + verb: Option, + #[structopt(short = "o", long = "output")] + output: Option, +} + +fn main() { + let stdin = io::stdin(); + let opt = Opt::from_args(); + + 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::(), "Invalid number")) + .collect(); + + match (opt.noun, opt.verb, opt.output) { + (Some(noun), Some(verb), _) => { + let result = exit_on_failed_assertion( + program + .with_noun_verb_input(noun, verb) + .execute_returning_memory_0(), + "Program errored", + ); + println!("{}", result); + } + (_, _, Some(output)) => { + let (noun, verb) = + exit_on_failed_assertion(find_input(&program, output), "Program errored"); + println!("({}, {})", noun, verb); + } + (None, None, None) => { + let result = + exit_on_failed_assertion(program.execute_returning_memory_0(), "Program errored"); + println!("{}", result); + } + _ => { + eprintln!("Either a noun and verb or an expected output must be provided"); + process::exit(1); + } + } +} + +fn exit_on_failed_assertion(data: Result, message: &str) -> A { + match data { + Ok(data) => data, + Err(e) => { + eprintln!("{}: {}", message, e); + process::exit(1); + } + } +} + +fn find_input( + program: &IntcodeProgram, + output: Intcode, +) -> Result<(Intcode, Intcode), IntcodeProgramError> { + (0..99) + .flat_map(|noun| (0..99).map(move |verb| (Intcode::from(noun), Intcode::from(verb)))) + .map(|(noun, verb)| { + ( + noun.clone(), + verb.clone(), + program + .with_noun_verb_input(noun, verb) + .execute_returning_memory_0(), + ) + }) + .find(|(_noun, _verb, out)| *out == Ok(output.clone())) + .map(|(noun, verb, _out)| Ok((noun, verb))) + .unwrap_or(Err(IntcodeProgramError::Unknown)) +} diff --git a/2019/src/bin/day_20.rs b/2019/src/bin/day_20.rs new file mode 100644 index 0000000..953df75 --- /dev/null +++ b/2019/src/bin/day_20.rs @@ -0,0 +1,310 @@ +use rpds::rbt_set; +use rpds::vector::Vector; +use rpds::RedBlackTreeMap; +use rpds::RedBlackTreeSet; +use std::io; +use std::io::prelude::*; +use std::iter; +use std::iter::FromIterator; +use std::process; +use structopt::StructOpt; + +#[derive(Debug, StructOpt)] +#[structopt(name = "Day 20: Donut Maze")] +/// Finds the shortest path through a maze with portals. +/// +/// See https://adventofcode.com/2019/day/20 for details. +struct Opt { + /// include the rule that going through portals changes your depth + #[structopt(short = "d")] + include_depth: bool, +} + +fn main() { + let stdin = io::stdin(); + let opt = Opt::from_args(); + + let maze = stdin + .lock() + .lines() + .map(|x| exit_on_failed_assertion(x, "Error reading input")) + .collect::() + .build(); + + println!("{}", maze.shortest_route(opt.include_depth)); +} + +fn exit_on_failed_assertion(data: Result, message: &str) -> A { + match data { + Ok(data) => data, + Err(e) => { + eprintln!("{}: {}", message, e); + process::exit(1); + } + } +} + +struct MazeBuilder { + map: Vector>, +} + +impl FromIterator for MazeBuilder { + fn from_iter>(iter: T) -> Self { + MazeBuilder { + map: iter + .into_iter() + .map(|line| line.chars().collect()) + .collect(), + } + } +} + +impl MazeBuilder { + fn build(self) -> Maze { + Maze { + walls: self + .map + .iter() + .map(|line| line.iter().map(|ch| *ch != '.').collect()) + .collect(), + portals: self.grouped_portals(), + entrance: self + .all_portals() + .find(|(id, _)| *id == ['A', 'A']) + .unwrap() + .1, + exit: self + .all_portals() + .find(|(id, _)| *id == ['Z', 'Z']) + .unwrap() + .1, + } + } + + fn grouped_portals(&self) -> Vector<(Point, Point)> { + self.all_portals() + .fold( + (Vector::new(), RedBlackTreeMap::new()), + |(matched, unmatched): ( + Vector<(Point, Point)>, + RedBlackTreeMap<[char; 2], Point>, + ), + (next_id, next_p)| match unmatched.get(&next_id) { + Some(pair) => ( + matched.push_back(pair.clone().inside_out( + next_p, + self.map[0].len(), + self.map.len(), + )), + unmatched.remove(&next_id), + ), + None => (matched, unmatched.insert(next_id, next_p)), + }, + ) + .0 + } + + fn all_portals(&self) -> impl Iterator + '_ { + self.horizontal_trailing_portals() + .chain(self.horizontal_leading_portals()) + .chain(self.vertical_trailing_portals()) + .chain(self.vertical_leading_portals()) + } + + fn horizontal_trailing_portals(&self) -> impl Iterator + '_ { + // .XX + (0..self.map.len()) + .flat_map(move |y| (0..self.map[y].len() - 2).map(move |x| Point { x, y })) + .filter(move |p| { + self.map[p.y][p.x] == '.' + && self.map[p.y][p.x + 1].is_alphabetic() + && self.map[p.y][p.x + 2].is_alphabetic() + }) + .map(move |p| ([self.map[p.y][p.x + 1], self.map[p.y][p.x + 2]], p)) + } + + fn horizontal_leading_portals(&self) -> impl Iterator + '_ { + // XX. + (0..self.map.len()) + .flat_map(move |y| (0..self.map[y].len() - 2).map(move |x| Point { x, y })) + .filter(move |p| { + self.map[p.y][p.x + 2] == '.' + && self.map[p.y][p.x + 1].is_alphabetic() + && self.map[p.y][p.x].is_alphabetic() + }) + .map(move |p| { + ( + [self.map[p.y][p.x], self.map[p.y][p.x + 1]], + Point { x: p.x + 2, y: p.y }, + ) + }) + } + + fn vertical_trailing_portals(&self) -> impl Iterator + '_ { + // .XX + (0..self.map[0].len()) + .flat_map(move |x| (0..self.map.len() - 2).map(move |y| Point { x, y })) + .filter(move |p| { + self.map[p.y][p.x] == '.' + && self.map[p.y + 1][p.x].is_alphabetic() + && self.map[p.y + 2][p.x].is_alphabetic() + }) + .map(move |p| ([self.map[p.y + 1][p.x], self.map[p.y + 2][p.x]], p)) + } + + fn vertical_leading_portals(&self) -> impl Iterator + '_ { + // XX. + (0..self.map[0].len()) + .flat_map(move |x| (0..self.map.len() - 2).map(move |y| Point { x, y })) + .filter(move |p| { + self.map[p.y + 2][p.x] == '.' + && self.map[p.y + 1][p.x].is_alphabetic() + && self.map[p.y][p.x].is_alphabetic() + }) + .map(move |p| { + ( + [self.map[p.y][p.x], self.map[p.y + 1][p.x]], + Point { x: p.x, y: p.y + 2 }, + ) + }) + } +} + +#[derive(Debug)] +struct Maze { + walls: Vector>, + portals: Vector<(Point, Point)>, + entrance: Point, // AA + exit: Point, // ZZ +} + +#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)] +struct Point { + x: usize, + y: usize, +} + +impl Point { + fn add(&self, x: isize, y: isize) -> Point { + Point { + x: (self.x as isize + x) as usize, + y: (self.y as isize + y) as usize, + } + } + + fn inside_out(self, other: Point, width: usize, height: usize) -> (Point, Point) { + if self.closest_side(width, height) > other.closest_side(width, height) { + (self, other) + } else { + (other, self) + } + } + + fn closest_side(&self, width: usize, height: usize) -> usize { + self.x.min(width - self.x).min(self.y).min(height - self.y) + } +} + +impl Maze { + fn shortest_route(&self, include_depth: bool) -> usize { + iter::successors( + Some(( + rbt_set![(self.entrance.clone(), 0)], + rbt_set![(self.entrance.clone(), 0)], + )), + |(explored, locations)| { + Some(Maze::next_depth_states( + explored.clone(), + self.next_locations(locations, explored, include_depth), + )) + }, + ) + // .inspect(|(explored, states)| eprintln!("{:?}", states)) + .take_while(|(_explored, states)| states.size() > 0) + .enumerate() + .find(|(_i, (_explored, states))| { + states + .iter() + .any(|(p_state, depth)| *p_state == self.exit && (!include_depth || *depth == 0)) + }) + .unwrap() + .0 + } + + fn next_depth_states( + explored: RedBlackTreeSet<(Point, isize)>, + locations: RedBlackTreeSet<(Point, isize)>, + ) -> ( + RedBlackTreeSet<(Point, isize)>, + RedBlackTreeSet<(Point, isize)>, + ) { + ( + locations + .iter() + .fold(explored, |acc, next| acc.insert(next.clone())), + locations, + ) + } + + fn next_locations( + &self, + locations: &RedBlackTreeSet<(Point, isize)>, + explored: &RedBlackTreeSet<(Point, isize)>, + include_depth: bool, + ) -> RedBlackTreeSet<(Point, isize)> { + locations + .iter() + .flat_map(|(p, depth)| { + [(-1, 0), (1, 0), (0, -1), (0, 1)] + .iter() + .map(move |(dx, dy)| (p.add(*dx, *dy), *depth)) + .chain( + self.portals + .iter() + .filter(move |(from, _to)| p == from) + .map(move |(_from, to)| (to.clone(), depth + 1)), + ) + .chain( + self.portals + .iter() + .filter(move |(_to, from)| p == from) + .map(move |(to, _from)| (to.clone(), depth - 1)), + ) + }) + .filter(|(p_next, depth)| { + !self.walls[p_next.y][p_next.x] && (!include_depth || *depth >= 0) + }) + .filter(|state| !explored.contains(state)) + .collect() + } +} + +#[test] +fn portal_maze_example_1() { + let maze: Maze = r" A + A + #######.######### + #######.........# + #######.#######.# + #######.#######.# + #######.#######.# + ##### B ###.# +BC...## C ###.# + ##.## ###.# + ##...DE F ###.# + ##### G ###.# + #########.#####.# +DE..#######...###.# + #.#########.###.# +FG..#########.....# + ###########.##### + Z + Z " + .split('\n') + .map(|s| s.to_string()) + .collect::() + .build(); + + assert_eq!(maze.shortest_route(false), 23); + assert_eq!(maze.shortest_route(true), 26); +} diff --git a/2019/src/bin/day_21.rs b/2019/src/bin/day_21.rs new file mode 100644 index 0000000..7fa781c --- /dev/null +++ b/2019/src/bin/day_21.rs @@ -0,0 +1,109 @@ +use aoc2019::*; +use std::io; +use std::io::prelude::*; +use std::process; +use structopt::StructOpt; + +#[derive(Debug, StructOpt)] +#[structopt(name = "Day 21: Springdroid Adventure")] +/// Pilots a springdroid around! +/// +/// See https://adventofcode.com/2019/day/21 for details. +struct Opt {} + +fn main() { + let stdin = io::stdin(); + let _opt = Opt::from_args(); + + 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::(), "Invalid number")) + .collect::(); + + let walk_result = exit_on_failed_assertion( + { + let input = vec![ + "NOT T T\n", + "AND A T\n", + "AND B T\n", + "AND C T\n", + "NOT T J\n", + "AND D J\n", + "WALK\n", + ]; + program + .with_input( + input + .iter() + .flat_map(|line| line.chars().map(|c| Intcode::from(c as u8))) + .collect(), + ) + .execute() + }, + "Program failed", + ); + + println!( + "{}", + walk_result + .drop_last() + .unwrap() + .iter() + .flat_map(|c| c.to_signed_bytes_be()) + .map(|c| c as char) + .collect::() + ); + println!("{}", walk_result.last().unwrap()); + + let run_result = exit_on_failed_assertion( + { + // (!A || !B || !C) && D && (E || H) + let input = vec![ + "OR E J\n", + "OR H J\n", + "AND D J\n", + "NOT T T\n", + "AND A T\n", + "AND B T\n", + "AND C T\n", + "NOT T T\n", + "AND T J\n", + "RUN\n", + ]; + program + .with_input( + input + .iter() + .flat_map(|line| line.chars().map(|c| Intcode::from(c as u8))) + .collect(), + ) + .execute() + }, + "Program failed", + ); + + println!( + "{}", + run_result + .drop_last() + .unwrap() + .iter() + .flat_map(|c| c.to_signed_bytes_be()) + .map(|c| c as char) + .collect::() + ); + println!("{}", run_result.last().unwrap()); +} + +fn exit_on_failed_assertion(data: Result, message: &str) -> A { + match data { + Ok(data) => data, + Err(e) => { + eprintln!("{}: {}", message, e); + process::exit(1); + } + } +} diff --git a/2019/src/bin/day_22.rs b/2019/src/bin/day_22.rs new file mode 100644 index 0000000..5b999a6 --- /dev/null +++ b/2019/src/bin/day_22.rs @@ -0,0 +1,325 @@ +use derive_more::Display; +use num::bigint::BigInt; +use num::traits::identities::Zero; +use num::traits::sign::abs; +use num::traits::Signed; +use std::fmt; +use std::io; +use std::io::prelude::*; +use std::process; +use std::str::FromStr; +use structopt::StructOpt; + +#[derive(Debug, StructOpt)] +#[structopt(name = "Day 22: Slam Shuffle")] +/// Shuffles some cards. +/// +/// See https://adventofcode.com/2019/day/22 for details. +struct Opt { + /// The size of the deck + deck_size: BigInt, + /// At the end, query the position of card + card: BigInt, + /// Number of repetitions + repetitions: BigInt, + + /// Prints the card in position n, rather than the position of card n + #[structopt(short = "p")] + position_mode: bool, +} + +fn main() { + let stdin = io::stdin(); + let opt = Opt::from_args(); + + let instructions = stdin + .lock() + .lines() + .map(|x| exit_on_failed_assertion(x, "Error reading input")) + .map(|x| exit_on_failed_assertion(x.parse::(), "Parse error")) + .collect::>(); + + //eprintln!("{:?}", instructions); + + if opt.position_mode { + println!( + "{}", + instructions + .iter() + .rev() + .fold( + StandardisedInstruction::identity(opt.deck_size.clone()), + |acc, next| acc.then(&(next.clone(), opt.deck_size.clone(), false).into()) + ) + .repeat(opt.repetitions) + .apply(opt.card.clone()) + ); + } else { + println!( + "{}", + instructions + .iter() + .fold( + StandardisedInstruction::identity(opt.deck_size.clone()), + |acc, next| { + eprintln!("{}", acc); + acc.then(&(next.clone(), opt.deck_size.clone(), true).into()) + } + ) + .repeat(opt.repetitions) + .apply(opt.card.clone()) + ); + } +} + +fn exit_on_failed_assertion(data: Result, message: &str) -> A { + match data { + Ok(data) => data, + Err(e) => { + eprintln!("{}: {}", message, e); + process::exit(1); + } + } +} + +fn mod_plus(a: BigInt, b: BigInt, modulus: BigInt) -> BigInt { + mod_normalize(a + b, modulus) +} + +fn mod_sub(a: BigInt, b: BigInt, modulus: BigInt) -> BigInt { + mod_normalize(a - b, modulus) +} + +fn mod_times(a: BigInt, b: BigInt, modulus: BigInt) -> BigInt { + mod_normalize(a * b, modulus) +} + +fn mod_divide(a: BigInt, b: BigInt, modulus: BigInt) -> BigInt { + mod_times(a, mod_inverse(b, modulus.clone()), modulus) +} + +fn mod_pow(a: BigInt, b: BigInt, modulus: BigInt) -> BigInt { + a.modpow(&b, &modulus) +} + +fn mod_normalize(a: BigInt, modulus: BigInt) -> BigInt { + if a.is_negative() { + a.clone() + modulus.clone() * (1 + abs(a) / modulus) + } else { + a % modulus + } +} + +// NB: This may give nonsense if modulus isn't coprime with a +fn mod_inverse(a: BigInt, modulus: BigInt) -> BigInt { + mod_normalize(euclid_gcd_coefficients(a, modulus.clone()).0, modulus) +} + +fn euclid_gcd_coefficients(a: BigInt, b: BigInt) -> (BigInt, BigInt) { + fn euclid_gcd_coefficients_inner( + r: BigInt, + old_r: BigInt, + s: BigInt, + old_s: BigInt, + t: BigInt, + old_t: BigInt, + ) -> (BigInt, BigInt) { + if r.is_zero() { + (old_s, old_t) + } else { + euclid_gcd_coefficients_inner( + old_r.clone() - (old_r.clone() / r.clone()) * r.clone(), + r.clone(), + old_s - (old_r.clone() / r.clone()) * s.clone(), + s, + old_t - (old_r.clone() / r) * t.clone(), + t, + ) + } + } + + assert!(a < b); + + euclid_gcd_coefficients_inner(b, a, 0.into(), 1.into(), 1.into(), 0.into()) +} + +#[derive(Debug, Clone)] +enum Instruction { + DealIntoNewStack, + Cut(BigInt), + ReverseCut(BigInt), + DealWithIncrement(BigInt), +} + +impl FromStr for Instruction { + type Err = ParseErr; + fn from_str(s: &str) -> Result { + if s.starts_with("deal into new stack") { + Ok(Instruction::DealIntoNewStack) + } else if s.starts_with("cut -") { + s.split(' ') + .nth(1) + .map(|val| { + val.parse::() + .map_err(|_| ParseErr) + .map(|parsed| Instruction::ReverseCut(abs(parsed))) + }) + .unwrap_or(Err(ParseErr)) + } else if s.starts_with("cut") { + s.split(' ') + .nth(1) + .map(|val| { + val.parse::() + .map_err(|_| ParseErr) + .map(|parsed| Instruction::Cut(parsed)) + }) + .unwrap_or(Err(ParseErr)) + } else if s.starts_with("deal with increment") { + s.split(' ') + .nth(3) + .map(|val| { + val.parse::() + .map_err(|_| ParseErr) + .map(|parsed| Instruction::DealWithIncrement(parsed)) + }) + .unwrap_or(Err(ParseErr)) + } else { + Err(ParseErr) + } + } +} + +// f(x) = ax + b mod c +#[derive(Display, Clone)] +#[display(fmt = "f(x) = {} x + {} % {}", a, b, modulus)] +struct StandardisedInstruction { + a: BigInt, + b: BigInt, + modulus: BigInt, +} + +impl From<(Instruction, BigInt, bool)> for StandardisedInstruction { + fn from((instruction, modulus, forward): (Instruction, BigInt, bool)) -> Self { + match (instruction, forward) { + (Instruction::DealIntoNewStack, _) => StandardisedInstruction { + a: BigInt::from(-1), + b: BigInt::from(-1), + modulus: modulus, + }, + (Instruction::Cut(n), true) => StandardisedInstruction { + a: BigInt::from(1), + b: BigInt::from(-n), + modulus: modulus, + }, + (Instruction::Cut(n), false) => StandardisedInstruction { + a: BigInt::from(1), + b: BigInt::from(n), + modulus: modulus, + }, + (Instruction::ReverseCut(n), true) => StandardisedInstruction { + a: BigInt::from(1), + b: BigInt::from(n), + modulus: modulus, + }, + (Instruction::ReverseCut(n), false) => StandardisedInstruction { + a: BigInt::from(1), + b: BigInt::from(-n), + modulus: modulus, + }, + (Instruction::DealWithIncrement(n), true) => StandardisedInstruction { + a: BigInt::from(n), + b: BigInt::from(0), + modulus: modulus, + }, + (Instruction::DealWithIncrement(n), false) => StandardisedInstruction { + a: BigInt::from(mod_inverse(n, modulus.clone())), + b: BigInt::from(0), + modulus: modulus, + }, + } + .normalise() + } +} + +impl StandardisedInstruction { + fn identity(modulus: BigInt) -> StandardisedInstruction { + StandardisedInstruction { + a: BigInt::from(1), + b: BigInt::from(0), + modulus, + } + } + fn normalise(&self) -> StandardisedInstruction { + StandardisedInstruction { + a: mod_normalize(self.a.clone(), self.modulus.clone()), + b: mod_normalize(self.b.clone(), self.modulus.clone()), + modulus: self.modulus.clone(), + } + } + fn then(&self, other: &StandardisedInstruction) -> StandardisedInstruction { + // g(f(x)) = ga (fa x + fb) + gb = + StandardisedInstruction { + a: mod_times(self.a.clone(), other.a.clone(), self.modulus.clone()), + b: mod_plus( + mod_times(self.b.clone(), other.a.clone(), self.modulus.clone()), + other.b.clone(), + self.modulus.clone(), + ), + modulus: self.modulus.clone(), + } + } + fn repeat(&self, repetitions: BigInt) -> StandardisedInstruction { + StandardisedInstruction { + a: mod_pow(self.a.clone(), repetitions.clone(), self.modulus.clone()), + b: mod_divide( + mod_times( + self.b.clone(), + mod_sub( + BigInt::from(1), + mod_pow(self.a.clone(), repetitions.clone(), self.modulus.clone()), + self.modulus.clone(), + ), + self.modulus.clone(), + ), + mod_sub(BigInt::from(1), self.a.clone(), self.modulus.clone()), + self.modulus.clone(), + ), + modulus: self.modulus.clone(), + } + } + + fn apply(&self, x: BigInt) -> BigInt { + mod_plus( + mod_times(self.a.clone(), x, self.modulus.clone()), + self.b.clone(), + self.modulus.clone(), + ) + } +} + +#[derive(Debug, Clone, Copy)] +struct ParseErr; + +impl fmt::Display for ParseErr { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!(f, "Error parsing input") + } +} + +impl std::error::Error for ParseErr {} + +#[test] +fn mod_inverse_of_13() { + assert_eq!(mod_inverse(1.into(), 13.into()), 1.into()); + assert_eq!(mod_inverse(2.into(), 13.into()), 7.into()); + assert_eq!(mod_inverse(3.into(), 13.into()), 9.into()); + assert_eq!(mod_inverse(4.into(), 13.into()), 10.into()); + assert_eq!(mod_inverse(5.into(), 13.into()), 8.into()); + assert_eq!(mod_inverse(6.into(), 13.into()), 11.into()); + assert_eq!(mod_inverse(7.into(), 13.into()), 2.into()); + assert_eq!(mod_inverse(8.into(), 13.into()), 5.into()); + assert_eq!(mod_inverse(9.into(), 13.into()), 3.into()); + assert_eq!(mod_inverse(10.into(), 13.into()), 4.into()); + assert_eq!(mod_inverse(11.into(), 13.into()), 6.into()); + assert_eq!(mod_inverse(12.into(), 13.into()), 12.into()); +} diff --git a/2019/src/bin/day_23.rs b/2019/src/bin/day_23.rs new file mode 100644 index 0000000..e074cf4 --- /dev/null +++ b/2019/src/bin/day_23.rs @@ -0,0 +1,211 @@ +use aoc2019::*; +use rpds::list; +use rpds::list::List; +use rpds::vector::Vector; +use std::io; +use std::io::prelude::*; +use std::iter; +use std::process; +use structopt::StructOpt; + +#[derive(Debug, StructOpt)] +#[structopt(name = "Day 23: Category Six")] +/// Executes an Intcode program on a network of computers +/// +/// See https://adventofcode.com/2019/day/23 for details. +struct Opt { + #[structopt(short = "n", long = "network-size")] + network_size: usize, + #[structopt(long = "nat")] + send_nat: bool, +} + +fn main() { + let stdin = io::stdin(); + let opt = Opt::from_args(); + + 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::(), "Invalid number")) + .collect::(); + + let network = Network::new(program, opt.network_size); + + if opt.send_nat { + println!("{}", network.first_repeated_nat_packet().y); + } else { + println!("{}", network.first_nat_packet().y); + } +} + +fn exit_on_failed_assertion(data: Result, message: &str) -> A { + match data { + Ok(data) => data, + Err(e) => { + eprintln!("{}: {}", message, e); + process::exit(1); + } + } +} + +#[derive(Debug, Clone)] +struct Network { + computers: Vector, + nat: Option, + is_potentially_idle: bool, + is_idle: bool, +} + +impl Network { + fn new(program: IntcodeProgram, network_size: usize) -> Network { + Network { + computers: (0..network_size) + .map(|ip| program.with_input(list![ip.into(), Intcode::from(-1)])) + .collect(), + nat: None, + is_potentially_idle: false, + is_idle: false, + } + } + + fn first_nat_packet(&self) -> Packet { + iter::successors(Some(self.clone()), |network| Some(network.next())) + .filter_map(|network| network.nat) + .next() + .unwrap() + } + + fn first_repeated_nat_packet(&self) -> Packet { + self.sent_nat_packets() + .zip(self.sent_nat_packets().skip(1)) + // .inspect(|(nat, _p2)| eprintln!("{}", nat.y)) + .find(|(p1, p2)| p1.y == p2.y) + .unwrap() + .0 + } + + fn sent_nat_packets<'a>(&'a self) -> impl Iterator + 'a { + iter::successors(Some(self.clone()), |network| { + Some(network.with_nat_packet_sent().run_to_network_idle()) + }) + .filter_map(|network| network.nat) + } + + fn run_to_network_idle(&self) -> Network { + iter::successors(Some(self.clone()), |network| Some(network.next())) + .find(|network| network.is_idle) + .unwrap() + } + + fn with_nat_packet_sent(&self) -> Network { + if self.nat.is_some() { + Network { + computers: self + .computers + .iter() + .enumerate() + .map(|(ip, computer)| { + computer + .with_additional_input( + self.nat + .iter() + .filter(|packet| packet.dest == Intcode::from(ip)) + .flat_map(|packet| vec![packet.x.clone(), packet.y.clone()]) + .collect(), + ) + .run_to_termination_or_input() + }) + .collect(), + nat: self.nat.clone(), + is_potentially_idle: false, + is_idle: false, + } + } else { + self.clone() + } + } + + fn next(&self) -> Network { + Network { + computers: self + .computers + .iter() + .enumerate() + .map(|(ip, computer)| { + computer + .with_cleared_output() + .with_additional_input(if self.empty_queues() { + list![Intcode::from(-1)] + } else { + list![] + }) + .with_additional_input( + self.pending_packets() + .filter(|packet| packet.dest == Intcode::from(ip)) + .flat_map(|packet| vec![packet.x, packet.y]) + .collect(), + ) + .run_to_termination_or_input() + }) + .collect(), + nat: self + .pending_packets() + .filter(|packet| packet.is_nat()) + .map(|packet| packet.with_dest(0.into())) + .last() + .or_else(|| self.nat.clone()), + is_potentially_idle: self.empty_queues(), + is_idle: self.is_potentially_idle && self.empty_queues(), + } + } + + fn pending_packets<'a>(&'a self) -> impl Iterator + 'a { + self.computers.iter().flat_map(|computer| { + computer + .output + .iter() + .cloned() + .collect::>() + .chunks_exact(3) + .map(|packet| Packet { + dest: packet[0].clone(), + x: packet[1].clone(), + y: packet[2].clone(), + }) + .collect::>() + }) + } + + fn pending_input<'a>(&'a self) -> impl Iterator + 'a { + self.computers + .iter() + .flat_map(|computer| computer.input.iter().cloned().collect::>()) + } + + fn empty_queues(&self) -> bool { + self.pending_packets().count() == 0 && self.pending_input().count() == 0 + } +} + +#[derive(Debug, Clone)] +struct Packet { + dest: Intcode, + x: Intcode, + y: Intcode, +} + +impl Packet { + fn is_nat(&self) -> bool { + self.dest == 255.into() + } + + fn with_dest(&self, dest: Intcode) -> Packet { + Packet { + dest, + ..self.clone() + } + } +} diff --git a/2019/src/bin/day_24.rs b/2019/src/bin/day_24.rs new file mode 100644 index 0000000..ebc6a1b --- /dev/null +++ b/2019/src/bin/day_24.rs @@ -0,0 +1,239 @@ +use rpds::RedBlackTreeSet; +use std::io; +use std::io::prelude::*; +use std::iter; +use std::iter::FromIterator; +use std::process; +use structopt::StructOpt; + +#[derive(Debug, StructOpt)] +#[structopt(name = "Day 24: Planet of Discord")] +/// Simulates the life and death of Eris bugs +/// +/// See https://adventofcode.com/2019/day/24 for details. +struct Opt { + /// How many iterations of the game of life should be run + /// If not provided, runs until a state appears twice. + #[structopt(short = "n")] + depth: Option, + /// Interprets the map as being one part of an infinite fractal map + #[structopt(short = "f")] + fractal: bool, +} + +fn main() { + let stdin = io::stdin(); + let opt = Opt::from_args(); + + let initial_state: State = stdin + .lock() + .lines() + .map(|x| exit_on_failed_assertion(x, "Error reading input")) + .collect::() + .with_fractal_mode(opt.fractal); + + let final_state = match opt.depth { + Some(depth) => initial_state.n_steps_forward(depth), + None => initial_state.first_repeated_state(), + }; + + println!("Bugs: {}", final_state.alive.size()); + println!("Biodiversity: {}", final_state.biodiversity_rating()); +} + +fn exit_on_failed_assertion(data: Result, message: &str) -> A { + match data { + Ok(data) => data, + Err(e) => { + eprintln!("{}: {}", message, e); + process::exit(1); + } + } +} + +#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)] +struct State { + alive: RedBlackTreeSet, + fractal_mode: bool, +} + +impl FromIterator for State { + fn from_iter>(iter: T) -> Self { + State { + alive: iter + .into_iter() + .enumerate() + .flat_map(move |(y, line)| { + line.chars() + .enumerate() + .filter(move |(_x, c)| *c == '#') + .map(move |(x, _c)| Coordinate { + x: x as isize, + y: y as isize, + depth: 0, + }) + .collect::>() + }) + .collect(), + fractal_mode: false, + } + } +} + +impl State { + fn with_fractal_mode(&self, fractal_mode: bool) -> State { + State { + fractal_mode, + ..self.clone() + } + } + + fn n_steps_forward(&self, n: usize) -> Self { + iter::successors(Some(self.clone()), |state| Some(state.next())) + .nth(n) + .unwrap() + } + + fn first_repeated_state(&self) -> State { + iter::successors( + Some((RedBlackTreeSet::new(), self.clone())), + |(seen, state)| Some((seen.insert(state.clone()), state.next())), + ) + .find(|(seen, state)| seen.contains(state)) + .unwrap() + .1 + } + + fn next(&self) -> State { + State { + alive: self + .still_alive_next_round() + .chain(self.comes_alive_next_round()) + .collect(), + ..self.clone() + } + } + + fn biodiversity_rating(&self) -> usize { + self.alive + .iter() + .map(|coord| 2_usize.pow((coord.y * 5 + coord.x) as u32)) + .sum() + } + + fn still_alive_next_round<'a>(&'a self) -> impl Iterator + 'a { + self.alive + .iter() + .filter(move |coord| self.count_alive_neighbours(**coord) == 1) + .cloned() + } + + fn comes_alive_next_round<'a>(&'a self) -> impl Iterator + 'a { + self.alive + .iter() + .flat_map(move |coord| self.neighbours(*coord)) + .filter(move |coord| !self.alive.contains(coord)) + .filter(move |coord| { + self.count_alive_neighbours(*coord) == 1 || self.count_alive_neighbours(*coord) == 2 + }) + } + + fn count_alive_neighbours(&self, coordinate: Coordinate) -> usize { + self.neighbours(coordinate) + .into_iter() + .filter(|coord| self.alive.contains(coord)) + .count() + } + + fn neighbours(&self, coordinate: Coordinate) -> Vec { + if self.fractal_mode { + [(-1, 0), (1, 0), (0, -1), (0, 1)] + .into_iter() + .map(|(dx, dy)| Coordinate { + x: coordinate.x + dx, + y: coordinate.y + dy, + depth: coordinate.depth, + }) + .flat_map(move |coord| match (coord.x, coord.y) { + (x, _y) if x < 0 => vec![Coordinate { + x: 1, + y: 2, + depth: coord.depth - 1, + }] + .into_iter(), + (_x, y) if y < 0 => vec![Coordinate { + x: 2, + y: 1, + depth: coord.depth - 1, + }] + .into_iter(), + (x, _y) if x >= 5 => vec![Coordinate { + x: 3, + y: 2, + depth: coord.depth - 1, + }] + .into_iter(), + (_x, y) if y >= 5 => vec![Coordinate { + x: 2, + y: 3, + depth: coord.depth - 1, + }] + .into_iter(), + (2, 2) => match (coordinate.x, coordinate.y) { + (1, 2) => (0..5) + .map(|y| Coordinate { + x: 0, + y, + depth: coord.depth + 1, + }) + .collect::>() + .into_iter(), + (2, 1) => (0..5) + .map(|x| Coordinate { + x, + y: 0, + depth: coord.depth + 1, + }) + .collect::>() + .into_iter(), + (3, 2) => (0..5) + .map(|y| Coordinate { + x: 4, + y, + depth: coord.depth + 1, + }) + .collect::>() + .into_iter(), + (2, 3) => (0..5) + .map(|x| Coordinate { + x, + y: 4, + depth: coord.depth + 1, + }) + .collect::>() + .into_iter(), + (_, _) => vec![].into_iter(), + }, + _ => vec![coord.clone()].into_iter(), + }) + .collect() + } else { + [(-1, 0), (1, 0), (0, -1), (0, 1)] + .into_iter() + .map(|(dx, dy)| Coordinate { + x: coordinate.x + dx, + y: coordinate.y + dy, + depth: coordinate.depth, + }) + .filter(|coord| coord.x >= 0 && coord.x < 5 && coord.y >= 0 && coord.y < 5) + .collect() + } + } +} + +#[derive(Debug, Clone, Copy, PartialOrd, Ord, PartialEq, Eq)] +struct Coordinate { + x: isize, + y: isize, + depth: isize, +} diff --git a/2019/src/bin/day_25.dot b/2019/src/bin/day_25.dot new file mode 100644 index 0000000..58dc131 --- /dev/null +++ b/2019/src/bin/day_25.dot @@ -0,0 +1,43 @@ +digraph { + Breach [label="Hull Breach"] + Crew [label="Crew Quarters (antenna)"] + Hallway [label="Hallway (weather machine)"] + Storage [label="Storage (klein bottle)"] + Stables [label="Stables (spool of cat6)"] + Warp [label="Warp Drive Maintenance"] + Security [label="Security Checkpoint"] + Pressure [label="Pressure-Sensitive Floor"] + Gift [label="Gift Wrapping Center"] + Sick [label="Sick Bay (infinite loop X)"] + Chocolate [label="Hot Chocolate Fountain (giant electromagnet X)"] + Observatory [label="Observatory (cake)"] + Navigation [label="Navigation (escape pod XX)"] + Corridor [label="Corridor"] + Holodeck [label="Holodeck (molten lava X)"] + Science [label="Science Lab (tambourine)"] + Passages [label="Passages (shell)"] + Engineering [label="Engineering"] + Arcade [label="Arcade (photons X)"] + Kitchen [label="Kitchen (mug)"] + + + Breach -> Crew [label=East] + Breach -> Hallway [label=North] + Hallway -> Storage [label=North] + Storage -> Stables [label=East] + Stables -> Warp [label=South] + Warp -> Security [label=South] + Security -> Pressure [label=East] + Stables -> Gift [label=East] + Gift -> Sick [label=North] + Sick -> Chocolate [label=West] + Chocolate -> Observatory [label=North] + Chocolate -> Navigation [label=West] + Corridor -> Holodeck [label=North] + Holodeck -> Science [label=North] + Sick -> Corridor [label=East] + Corridor -> Passages [label=South] + Passages -> Engineering [label=East] + Engineering -> Arcade [label=South] + Gift -> Kitchen [label=South] +} diff --git a/2019/src/bin/day_25.rs b/2019/src/bin/day_25.rs new file mode 100644 index 0000000..522789e --- /dev/null +++ b/2019/src/bin/day_25.rs @@ -0,0 +1,110 @@ +use aoc2019::*; +use std::io; +use std::io::prelude::*; +use std::process; +use structopt::StructOpt; + +#[derive(Debug, StructOpt)] +#[structopt(name = "Day 25: Cryostasis")] +/// Pilots a robot to save Santa! +/// +/// See https://adventofcode.com/2019/day/25 for details. +struct Opt {} + +fn main() { + let stdin = io::stdin(); + let _opt = Opt::from_args(); + + 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::(), "Invalid number")) + .collect::(); + + let input = vec![ + "east", + "take antenna", + "west", + "north", + "take weather machine", + "north", + "take klein bottle", + "east", + "take spool of cat6", + "east", + "south", + "take mug", + "north", + "north", + "west", + "north", + "take cake", + "south", + "east", + "east", + "north", + "north", + "take tambourine", + "south", + "south", + "south", + "take shell", + "north", + "west", + "south", + "west", + "south", + "south", + "inv", + //"drop mug", + //"drop weather machine", + "drop cake", + "drop shell", + "drop klein bottle", + "drop tambourine", + //"drop antenna", + //"drop spool of cat6", + "east", + ]; + + let result = exit_on_failed_assertion( + program + .with_input( + input + .iter() + .flat_map(|line| { + line.chars() + .map(|c| Intcode::from(c as u8)) + .chain(vec![Intcode::from(10)].into_iter()) + }) + .collect(), + ) + .run_to_termination_or_input() + .output_into_result(), + "Program failed", + ); + + println!( + "{}", + result + .drop_last() + .unwrap() + .iter() + .flat_map(|c| c.to_signed_bytes_be()) + .map(|c| c as char) + .collect::() + ); + println!("{}", result.last().unwrap()); +} + +fn exit_on_failed_assertion(data: Result, message: &str) -> A { + match data { + Ok(data) => data, + Err(e) => { + eprintln!("{}: {}", message, e); + process::exit(1); + } + } +} diff --git a/2019/src/bin/day_3.rs b/2019/src/bin/day_3.rs new file mode 100644 index 0000000..f4163bd --- /dev/null +++ b/2019/src/bin/day_3.rs @@ -0,0 +1,333 @@ +use rpds::vector::Vector; +use std::fmt; +use std::io; +use std::io::prelude::*; +use std::process; +use std::str::FromStr; +use structopt::StructOpt; + +#[derive(Debug, StructOpt)] +#[structopt(name = "Day 3: Crossed Wires")] +/// Finds the closest intersection between two wires. By default, +/// 'closest' is defined as closest in terms of Manhattan distance. If +/// --signal-distance is set, distance is defined in terms of the +/// total distance along the wire. +/// +/// See https://adventofcode.com/2019/day/3 for details. +struct Opt { + #[structopt(short = "s", long = "signal-distance")] + /// returns the closest intersection by signal distance. + signal_distance: bool, +} + +fn main() { + let stdin = io::stdin(); + let opt = Opt::from_args(); + + let mut input = stdin + .lock() + .lines() + .map(|x| exit_on_failed_assertion(x, "Error reading input")) + .map(|x| exit_on_failed_assertion(x.parse::(), "Input was not a valid wire")); + + let (wire1, wire2) = match (input.next(), input.next()) { + (Some(w1), Some(w2)) => (w1, w2), + _ => { + eprintln!("Input must have two wires"); + process::exit(1); + } + }; + + match wire1.closest_collision(&wire2, opt.signal_distance) { + Some(c) => println!( + "{}", + if opt.signal_distance { + c.signal_distance + } else { + c.manhattan_distance() + } + ), + None => { + eprintln!("No collisions"); + process::exit(1); + } + } +} + +fn exit_on_failed_assertion(data: Result, message: &str) -> A { + match data { + Ok(data) => data, + Err(e) => { + eprintln!("{}: {}", message, e); + process::exit(1); + } + } +} + +#[derive(Debug, Clone)] +struct Wire { + segments: Vector, +} + +impl FromStr for Wire { + type Err = UnknownError; + + fn from_str(s: &str) -> Result { + s.split(',') + .fold( + Ok(Vector::new()), + |acc: Result, UnknownError>, next_str| { + acc.and_then(|previous_segments| { + WireSegment::from_str( + previous_segments.last().map(|l| l.end()).unwrap_or((0, 0)), + previous_segments + .last() + .map(|l| l.end_signal_distance()) + .unwrap_or(0), + next_str, + ) + .map(|seg| previous_segments.push_back(seg)) + }) + }, + ) + .map(|segments| Wire { segments }) + } +} + +impl Wire { + fn closest_collision(&self, other: &Wire, use_signal_distance: bool) -> Option { + self.collisions(other).min_by_key(|c| { + if use_signal_distance { + c.signal_distance + } else { + c.manhattan_distance() + } + }) + } + + fn collisions<'a>(&'a self, other: &'a Wire) -> impl Iterator + 'a { + self.segments + .iter() + .flat_map(move |seg1| other.segments.iter().map(move |seg2| (seg1, seg2))) + .flat_map(|(seg1, seg2)| seg1.collisions(seg2)) + .filter(|c| !(c.x == 0 && c.y == 0)) + } +} + +#[derive(Debug, Clone)] +struct WireSegment { + start: (i32, i32), + start_signal_distance: i32, + direction: Direction, + length: i32, +} + +impl WireSegment { + fn from_str( + start: (i32, i32), + start_signal_distance: i32, + s: &str, + ) -> Result { + s.parse::().and_then(|direction| { + WireSegment::length_from_str(s).map(|length| WireSegment { + start, + start_signal_distance, + direction, + length, + }) + }) + } + + fn length_from_str(s: &str) -> Result { + s.chars() + .skip(1) + .collect::() + .parse() + .map_err(|_| UnknownError) + } + + fn end(&self) -> (i32, i32) { + ( + self.start.0 + self.direction.as_vec().0 * self.length, + self.start.1 + self.direction.as_vec().1 * self.length, + ) + } + + fn end_signal_distance(&self) -> i32 { + self.start_signal_distance + self.length + } + + fn collisions(&self, other: &WireSegment) -> Option { + use Direction::*; + + match (self.direction, other.direction) { + (Left, Left) | (Right, Right) | (Up, Up) | (Down, Down) => None, + (Left, Right) | (Right, Left) | (Up, Down) | (Down, Up) => None, + (Left, Up) => collisions( + self.end(), + self.end_signal_distance(), + self.length, + -1, + other.start, + other.start_signal_distance, + other.length, + 1, + ), + (Left, Down) => collisions( + self.end(), + self.end_signal_distance(), + self.length, + -1, + other.end(), + other.end_signal_distance(), + other.length, + -1, + ), + (Right, Up) => collisions( + self.start, + self.start_signal_distance, + self.length, + 1, + other.start, + other.start_signal_distance, + other.length, + 1, + ), + (Right, Down) => collisions( + self.start, + self.start_signal_distance, + self.length, + 1, + other.end(), + other.end_signal_distance(), + other.length, + -1, + ), + (Down, Right) => collisions( + other.start, + other.start_signal_distance, + other.length, + 1, + self.end(), + self.end_signal_distance(), + self.length, + -1, + ), + (Down, Left) => collisions( + other.end(), + other.end_signal_distance(), + other.length, + -1, + self.end(), + self.end_signal_distance(), + self.length, + -1, + ), + (Up, Right) => collisions( + other.start, + other.start_signal_distance, + other.length, + 1, + self.start, + self.start_signal_distance, + self.length, + 1, + ), + (Up, Left) => collisions( + other.end(), + other.end_signal_distance(), + other.length, + -1, + self.start, + self.start_signal_distance, + self.length, + 1, + ), + } + } +} + +fn collisions( + horizontal_start: (i32, i32), + horizontal_start_signal_distance: i32, + horizontal_length: i32, + horizontal_signal_distance_multiplier: i32, + vertical_start: (i32, i32), + vertical_start_signal_distance: i32, + vertical_length: i32, + vertical_signal_distance_multiplier: i32, +) -> Option { + if horizontal_start.1 >= vertical_start.1 + && horizontal_start.1 <= vertical_start.1 + vertical_length + && vertical_start.0 >= horizontal_start.0 + && vertical_start.0 <= horizontal_start.0 + horizontal_length + { + Some(Collision { + x: vertical_start.0, + y: horizontal_start.1, + signal_distance: horizontal_start_signal_distance + + (vertical_start.0 - horizontal_start.0) * horizontal_signal_distance_multiplier + + vertical_start_signal_distance + + (horizontal_start.1 - vertical_start.1) * vertical_signal_distance_multiplier, + }) + } else { + None + } +} + +#[derive(Debug, Clone, Copy)] +enum Direction { + Up, + Down, + Left, + Right, +} + +impl FromStr for Direction { + type Err = UnknownError; + + fn from_str(s: &str) -> Result { + use Direction::*; + match s.chars().next() { + Some('L') => Ok(Left), + Some('R') => Ok(Right), + Some('U') => Ok(Up), + Some('D') => Ok(Down), + Some(_) => Err(UnknownError), + None => Err(UnknownError), + } + } +} +impl Direction { + fn as_vec(&self) -> (i32, i32) { + use Direction::*; + match self { + Up => (0, 1), + Down => (0, -1), + Left => (-1, 0), + Right => (1, 0), + } + } +} + +struct Collision { + x: i32, + y: i32, + signal_distance: i32, +} + +impl Collision { + fn manhattan_distance(&self) -> i32 { + self.x.abs() + self.y.abs() + } +} + +#[derive(Debug, PartialEq)] +struct UnknownError; + +impl fmt::Display for UnknownError { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!(f, "Unknown error") + } +} +impl std::error::Error for UnknownError {} diff --git a/2019/src/bin/day_4.rs b/2019/src/bin/day_4.rs new file mode 100644 index 0000000..d7d6b69 --- /dev/null +++ b/2019/src/bin/day_4.rs @@ -0,0 +1,55 @@ +use structopt::StructOpt; + +#[derive(Debug, StructOpt)] +#[structopt(name = "Day 4: Secure Container")] +/// Calculates how many possible lock values there are +/// +/// See https://adventofcode.com/2019/day/4 for details. +struct Opt { + /// Repeated digits must be exactly 2 long + #[structopt(long = "larger-range-rule")] + larger_range_rule: bool, + min: u32, + max: u32, +} + +fn main() { + let opt = Opt::from_args(); + + println!( + "{}", + valid_combinations(opt.min, opt.max, opt.larger_range_rule) + ) +} + +fn valid_combinations(min: u32, max: u32, larger_range_rule: bool) -> u32 { + (min..max) + .filter(|x| { + two_adjacent_identical_digits(*x, larger_range_rule) && digits_never_decrease(*x) + }) + .count() as u32 +} + +fn two_adjacent_identical_digits(x: u32, larger_range_rule: bool) -> bool { + if larger_range_rule { + (0..5).any(|d| { + digit(x, d) == digit(x, d + 1) + && digit(x, d) != digit(x, d + 2) + && digit(x, d) != digit(x, d - 1) + }) + } else { + (0..5).any(|d| digit(x, d) == digit(x, d + 1)) + } +} + +fn digits_never_decrease(x: u32) -> bool { + (0..5).all(|d| digit(x, d) >= digit(x, d + 1)) +} + +fn digit(x: u32, digit: i32) -> u32 { + if digit < 0 { + 0 + } else { + (x / 10u32.pow(digit as u32)) % 10 + } +} diff --git a/2019/src/bin/day_5.rs b/2019/src/bin/day_5.rs new file mode 100644 index 0000000..07f7af8 --- /dev/null +++ b/2019/src/bin/day_5.rs @@ -0,0 +1,45 @@ +use aoc2019::*; +use std::io; +use std::io::prelude::*; +use std::process; +use structopt::StructOpt; + +#[derive(Debug, StructOpt)] +#[structopt(name = "Day 5: Sunny with a Chance of Asteroids")] +/// Executes an Intcode program +/// +/// The program is read from stdin as a series of comma-separated +/// values. Newlines are ignored. +/// +/// See https://adventofcode.com/2019/day/5 for details. +struct Opt { + #[structopt(short = "i", long = "input")] + input: Vec, +} + +fn main() { + let stdin = io::stdin(); + let opt = Opt::from_args(); + + 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::(), "Invalid number")) + .collect::() + .with_input(opt.input.into_iter().collect()); + + let result = exit_on_failed_assertion(program.execute(), "Program errored"); + println!("{}", result); +} + +fn exit_on_failed_assertion(data: Result, message: &str) -> A { + match data { + Ok(data) => data, + Err(e) => { + eprintln!("{}: {}", message, e); + process::exit(1); + } + } +} diff --git a/2019/src/bin/day_6.rs b/2019/src/bin/day_6.rs new file mode 100644 index 0000000..2af272c --- /dev/null +++ b/2019/src/bin/day_6.rs @@ -0,0 +1,251 @@ +use rpds::vector::Vector; +use std::fmt; +use std::io; +use std::io::prelude::*; +use std::iter::FromIterator; +use std::process; +use std::str::FromStr; +use structopt::StructOpt; + +#[derive(Debug, StructOpt)] +#[structopt(name = "Day 6: Universal Orbit Map")] +/// Finds the minumum number of orbital transfers between two points. +/// +/// Input is read from stdin, one direct orbit per line, in the format +/// `A)B` (B is orbiting A). +/// +/// See https://adventofcode.com/2019/day/6 for details. +struct Opt { + /// Debug checksum: Counts the total orbits + #[structopt(short = "d", long = "debug")] + debug: bool, +} + +fn main() { + let stdin = io::stdin(); + let opt = Opt::from_args(); + + let orbits: OrbitalMap = stdin + .lock() + .lines() + .map(|x| exit_on_failed_assertion(x, "Error reading input")) + .map(|x| exit_on_failed_assertion(x.parse::(), "Input was not a valid orbit")) + .collect(); + + // eprintln!("{:#?}", orbits); + + if opt.debug { + println!("{}", orbits.total_orbits()); + } else { + println!("{}", orbits.orbital_transfers("YOU", "SAN")); + } +} + +fn exit_on_failed_assertion(data: Result, message: &str) -> A { + match data { + Ok(data) => data, + Err(e) => { + eprintln!("{}: {}", message, e); + process::exit(1); + } + } +} + +#[derive(Debug)] +struct StrError { + str: String, +} + +impl fmt::Display for StrError { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!(f, "{}", self.str) + } +} +impl std::error::Error for StrError {} + +#[derive(Debug, Clone)] +struct Orbit { + a: String, + b: String, +} + +impl FromStr for Orbit { + type Err = StrError; + + fn from_str(s: &str) -> Result { + match s.split(')').collect::>()[..] { + [a, b] => Ok(Orbit { + a: a.to_string(), + b: b.to_string(), + }), + _ => Err(StrError { + str: format!("{} is not a valid orbit description", s), + }), + } + } +} + +#[derive(Clone, Debug)] +struct OrbitalMap { + id: String, + depth: usize, + orbiters: Vector, +} + +struct OrbitalMapBuilder { + orbiters: Vector, + inserted_orbits: Vector, + pending_orbits: Vector, +} + +impl FromIterator for OrbitalMap { + fn from_iter>(iter: T) -> Self { + iter.into_iter().collect::().build() + } +} + +impl FromIterator for OrbitalMapBuilder { + fn from_iter>(iter: T) -> Self { + OrbitalMapBuilder { + orbiters: Vector::new(), + inserted_orbits: Vector::new(), + pending_orbits: iter.into_iter().collect(), + } + } +} + +impl OrbitalMapBuilder { + fn build(self) -> OrbitalMap { + if self.pending_orbits.is_empty() { + OrbitalMap { + id: ROOT.into(), + depth: 0, + orbiters: self.orbiters, + } + } else { + self.pending_orbits + .into_iter() + .fold( + OrbitalMapBuilder { + pending_orbits: Vector::new(), + ..self + }, + |acc, next| acc.insert(&next), + ) + .build() + } + } + + fn insert(self, orbit: &Orbit) -> OrbitalMapBuilder { + if orbit.a == ROOT { + OrbitalMapBuilder { + orbiters: self.orbiters.push_back(OrbitalMap::new(orbit.b.clone(), 1)), + inserted_orbits: self.inserted_orbits.push_back(orbit.b.clone()), + ..self + } + } else if self.inserted_orbits.iter().any(|o| *o == orbit.a) { + OrbitalMapBuilder { + orbiters: self + .orbiters + .into_iter() + .map(|map| OrbitalMap::insert(map.clone(), orbit)) + .collect(), + inserted_orbits: self.inserted_orbits.push_back(orbit.b.clone()), + ..self + } + } else { + OrbitalMapBuilder { + pending_orbits: self.pending_orbits.push_back(orbit.clone()), + ..self + } + } + } +} + +const ROOT: &str = "COM"; + +impl OrbitalMap { + fn new(id: String, depth: usize) -> OrbitalMap { + OrbitalMap { + id, + depth, + orbiters: Vector::new(), + } + } + + fn insert(self, orbit: &Orbit) -> OrbitalMap { + if orbit.a == self.id { + if self.orbiters.iter().any(|o| o.id == orbit.b) { + self + } else { + OrbitalMap { + orbiters: self + .orbiters + .push_back(OrbitalMap::new(orbit.b.clone(), self.depth + 1)), + ..self + } + } + } else { + OrbitalMap { + orbiters: self + .orbiters + .into_iter() + .map(|map| OrbitalMap::insert(map.clone(), orbit)) + .collect(), + ..self + } + } + } + + fn count_orbits(&self) -> usize { + self.orbiters.len() + + self + .orbiters + .iter() + .map(|o| o.count_orbits()) + .sum::() + } + + fn total_orbits(&self) -> usize { + self.count_orbits() + + self + .orbiters + .iter() + .map(|o| o.total_orbits()) + .sum::() + } + + fn find_depth(&self, id: &str) -> usize { + if self.id == id { + self.depth + } else { + // only the actual one will return non-zero from this + self.orbiters.iter().map(|o| o.find_depth(id)).sum() + } + } + + fn contains(&self, id: &str) -> bool { + self.id == id || self.orbiters.iter().any(|o| o.contains(id)) + } + + fn find_common_ancestor(&self, a: &str, b: &str) -> Option { + if !self.contains(a) || !self.contains(b) { + None + } else { + self.orbiters + .iter() + .flat_map(|o| o.find_common_ancestor(a, b)) + .next() + .or(Some(self.clone())) + } + } + + fn orbital_transfers(&self, from: &str, to: &str) -> usize { + self.find_depth(from) + self.find_depth(to) + - 2 * self + .find_common_ancestor(from, to) + .map(|o| o.depth) + .unwrap_or(0) + - 2 + } +} diff --git a/2019/src/bin/day_7.rs b/2019/src/bin/day_7.rs new file mode 100644 index 0000000..9b9177a --- /dev/null +++ b/2019/src/bin/day_7.rs @@ -0,0 +1,175 @@ +use aoc2019::*; +use rpds::list; +use rpds::list::List; +use rpds::vector::Vector; +use std::io; +use std::io::prelude::*; +use std::iter; +use std::process; +use structopt::StructOpt; + +#[derive(Debug, StructOpt)] +#[structopt(name = "Day 7: Amplification Circuit")] +/// Executes an Intcode program on 5 amplifiers, and finds the input that gives the max output +/// +/// See https://adventofcode.com/2019/day/7 for details. +struct Opt { + #[structopt(short = "f", long = "feedback-loop")] + feedback_loop_mode: bool, +} + +fn main() { + let stdin = io::stdin(); + let opt = Opt::from_args(); + + 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::(), "Invalid number")) + .collect::(); + + let result = exit_on_failed_assertion( + find_max_power(&program, opt.feedback_loop_mode), + "Program errored", + ); + println!("{}", result); +} + +fn exit_on_failed_assertion(data: Result, message: &str) -> A { + match data { + Ok(data) => data, + Err(e) => { + eprintln!("{}: {}", message, e); + process::exit(1); + } + } +} + +fn find_max_power( + program: &IntcodeProgram, + feedback_loop_mode: bool, +) -> Result { + PhaseSetting::all(feedback_loop_mode) + .map(|phase| AmplifierArray::new(program, &phase).execute()) + .collect::, _>>() + .map(|powers| powers.into_iter().max().unwrap_or(Intcode::from(0))) +} + +#[derive(Debug, Clone)] +struct PhaseSetting([Intcode; 5]); + +impl PhaseSetting { + fn all(feedback_loop_mode: bool) -> impl Iterator { + if feedback_loop_mode { + PhaseSetting::permute(5, 10) + } else { + PhaseSetting::permute(0, 5) + } + } + + fn permute(min: i32, max: i32) -> impl Iterator { + // This is an absolutely atrocious way to do the permutation, + // but luckily it's only 5 elements long. + (min..max) + .flat_map(move |a| { + (min..max).flat_map(move |b| { + (min..max).flat_map(move |c| { + (min..max).flat_map(move |d| { + (min..max).map(move |e| { + PhaseSetting([a.into(), b.into(), c.into(), d.into(), e.into()]) + }) + }) + }) + }) + }) + .filter(move |phase| (min..max).all(|x| phase.0.contains(&x.into()))) + } +} + +#[derive(Debug, Clone)] +struct AmplifierArray { + amplifiers: Vector, +} + +impl AmplifierArray { + fn new(program: &IntcodeProgram, phase: &PhaseSetting) -> AmplifierArray { + AmplifierArray { + amplifiers: (0..5) + .map(|n| AmplifierArray::new_amp(program, phase, n)) + .collect(), + } + } + + fn new_amp(program: &IntcodeProgram, phase: &PhaseSetting, n: usize) -> IntcodeProgram { + if n == 0 { + program.with_input(list![phase.0[n].clone(), Intcode::from(0)]) + } else { + program.with_input(list![phase.0[n].clone()]) + } + } + + fn execute(&self) -> Result { + self.run_to_termination().output_into_result() + } + + fn run_to_termination(&self) -> AmplifierArray { + iter::successors(Some(self.clone()), |p| Some(p.next())) + .find(|p| p.is_terminated()) + .unwrap() // successors doesn't terminate, so this will never be none. + } + + fn output_into_result(&self) -> Result { + self.amplifiers + .first() + .and_then(|amp| amp.input.first().cloned()) + .ok_or(IntcodeProgramError::Unknown) + } + + fn is_terminated(&self) -> bool { + self.amplifiers.last().map(|amp| amp.halted).unwrap_or(true) + } + + fn next(&self) -> AmplifierArray { + self.run_amplifiers().update_inputs() + } + + fn run_amplifiers(&self) -> AmplifierArray { + AmplifierArray { + amplifiers: self + .amplifiers + .iter() + .map(|amp| amp.run_to_termination_or_input()) + .collect(), + } + } + + fn update_inputs(&self) -> AmplifierArray { + AmplifierArray { + amplifiers: self + .amplifiers + .iter() + .fold( + ( + Vector::new(), + self.amplifiers + .last() + .map(|a| a.output.iter().cloned().collect::>()) + .unwrap_or(List::new()), + ), + |(amps, piped_input), next_amp| { + ( + amps.push_back( + next_amp + .with_additional_input(piped_input) + .with_cleared_output(), + ), + next_amp.output.iter().cloned().collect::>(), + ) + }, + ) + .0, + } + } +} diff --git a/2019/src/bin/day_8.rs b/2019/src/bin/day_8.rs new file mode 100644 index 0000000..0508e7c --- /dev/null +++ b/2019/src/bin/day_8.rs @@ -0,0 +1,135 @@ +use std::fmt; +use std::io; +use std::io::prelude::*; +use std::process; +use structopt::StructOpt; + +#[derive(Debug, StructOpt)] +#[structopt(name = "Day 8: Space Image Format")] +/// Executes an Intcode program on 5 amplifiers, and finds the input that gives the max output +/// +/// See https://adventofcode.com/2019/day/8 for details. +struct Opt { + /// Rather than rendering the image, calculate and print its checksum + #[structopt(short = "c", long = "checksum")] + checksum_mode: bool, + #[structopt(short = "w", long = "width")] + width: u32, + #[structopt(short = "h", long = "height")] + height: u32, +} + +fn main() { + let opt = Opt::from_args(); + + let image: Image = { + let mut buffer = String::new(); + exit_on_failed_assertion( + io::stdin().read_to_string(&mut buffer), + "Error reading input", + ); + + Image::from_str(&buffer.trim(), opt.width, opt.height) + }; + + if opt.checksum_mode { + println!("{}", image.checksum()); + } else { + println!("{}", image); + } +} + +fn exit_on_failed_assertion(data: Result, message: &str) -> A { + match data { + Ok(data) => data, + Err(e) => { + eprintln!("{}: {}", message, e); + process::exit(1); + } + } +} + +#[derive(Debug)] +struct Image { + width: u32, + height: u32, + layers: Vec, +} + +impl fmt::Display for Image { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + self.flatten() + .pixels + .chunks(self.width as usize) + .map(|line| { + line.iter() + .map(|c| write!(f, "{}", if *c == 0 { ' ' } else { '1' })) + .collect::() + .and_then(|_| writeln!(f)) + }) + .collect() + } +} + +impl Image { + fn from_str(s: &str, width: u32, height: u32) -> Image { + Image { + width, + height, + layers: s + .as_bytes() + .chunks((width * height) as usize) + .map(|chunk| ImageLayer::new(chunk)) + .collect(), + } + } + + fn checksum(&self) -> usize { + self.layers + .iter() + .min_by_key(|layer| layer.pixel_count(0)) + .map(|layer| layer.pixel_count(1) * layer.pixel_count(2)) + .unwrap_or(0) + } + + fn flatten(&self) -> ImageLayer { + self.layers + .iter() + .fold(ImageLayer::empty(self.width, self.height), |acc, next| { + ImageLayer { + pixels: acc + .pixels + .iter() + .zip(next.pixels.iter()) + .map(|(a, b)| if *a == 2 { *b } else { *a }) + .collect(), + } + }) + } +} + +#[derive(Debug)] +struct ImageLayer { + pixels: Vec, +} + +impl ImageLayer { + fn new(char_pixels: &[u8]) -> ImageLayer { + ImageLayer { + pixels: char_pixels + .iter() + .map(|c| c.overflowing_sub(b'0').0) + .collect(), + } + } + + fn empty(width: u32, height: u32) -> ImageLayer { + ImageLayer { + pixels: vec![2; (width * height) as usize], + } + } + + fn pixel_count(&self, value: u8) -> usize { + self.pixels.iter().filter(|p| **p == value).count() + } +} diff --git a/2019/src/bin/day_9.rs b/2019/src/bin/day_9.rs new file mode 100644 index 0000000..7f9b4aa --- /dev/null +++ b/2019/src/bin/day_9.rs @@ -0,0 +1 @@ +// Run the day 5 binary for this -- cgit v1.2.3