summaryrefslogtreecommitdiff
path: root/2019/src/bin
diff options
context:
space:
mode:
Diffstat (limited to '2019/src/bin')
-rw-r--r--2019/src/bin/day_1.rs93
-rw-r--r--2019/src/bin/day_10.rs158
-rw-r--r--2019/src/bin/day_11.rs205
-rw-r--r--2019/src/bin/day_12.rs205
-rw-r--r--2019/src/bin/day_13.rs149
-rw-r--r--2019/src/bin/day_14.rs221
-rw-r--r--2019/src/bin/day_15.rs183
-rw-r--r--2019/src/bin/day_16.rs112
-rw-r--r--2019/src/bin/day_17.rs78
-rw-r--r--2019/src/bin/day_18.rs365
-rw-r--r--2019/src/bin/day_19.rs102
-rw-r--r--2019/src/bin/day_2.rs96
-rw-r--r--2019/src/bin/day_20.rs310
-rw-r--r--2019/src/bin/day_21.rs109
-rw-r--r--2019/src/bin/day_22.rs325
-rw-r--r--2019/src/bin/day_23.rs211
-rw-r--r--2019/src/bin/day_24.rs239
-rw-r--r--2019/src/bin/day_25.dot43
-rw-r--r--2019/src/bin/day_25.rs110
-rw-r--r--2019/src/bin/day_3.rs333
-rw-r--r--2019/src/bin/day_4.rs55
-rw-r--r--2019/src/bin/day_5.rs45
-rw-r--r--2019/src/bin/day_6.rs251
-rw-r--r--2019/src/bin/day_7.rs175
-rw-r--r--2019/src/bin/day_8.rs135
-rw-r--r--2019/src/bin/day_9.rs1
26 files changed, 4309 insertions, 0 deletions
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::<Module>() {
+ 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<Item = Module>, 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<usize>,
+}
+
+fn main() {
+ let opt = Opt::from_args();
+ let stdin = io::stdin();
+ let map: AsteroidMap = stdin
+ .lock()
+ .lines()
+ .map(|l| exit_on_failed_assertion(l, "Error reading input"))
+ .collect();
+
+ match opt.n {
+ Some(n) => println!("{:?}", map.nth_destroyed_asteroid(n)),
+ None => println!("{}", map.best_asteroid_line_of_sight_count()),
+ };
+}
+
+fn exit_on_failed_assertion<A, E: std::error::Error>(data: Result<A, E>, message: &str) -> A {
+ match data {
+ Ok(data) => data,
+ Err(e) => {
+ eprintln!("{}: {}", message, e);
+ process::exit(1);
+ }
+ }
+}
+
+#[derive(Debug)]
+struct AsteroidMap {
+ asteroids: Vec<Asteroid>,
+}
+
+impl FromIterator<String> for AsteroidMap {
+ fn from_iter<T: IntoIterator<Item = String>>(iter: T) -> Self {
+ AsteroidMap {
+ asteroids: iter
+ .into_iter()
+ .enumerate()
+ .flat_map(move |(y, line)| {
+ line.chars()
+ .enumerate()
+ .map(move |(x, c)| (x, y, c))
+ .collect::<Vec<_>>()
+ })
+ .filter(|(_x, _y, c)| *c == '#')
+ .map(|(x, y, _x)| Asteroid {
+ x: x as i32,
+ y: y as i32,
+ })
+ .collect(),
+ }
+ }
+}
+
+impl AsteroidMap {
+ fn best_asteroid_line_of_sight_count(&self) -> usize {
+ self.optimal_view_asteroid()
+ .map(|a| self.count_visible_from(&a))
+ .unwrap_or(0)
+ }
+
+ fn nth_destroyed_asteroid(&self, n: usize) -> Option<Asteroid> {
+ self.optimal_view_asteroid()
+ .and_then(|source| self.nth_destroyed_asteroid_from(&source, n))
+ }
+
+ fn nth_destroyed_asteroid_from(&self, source: &Asteroid, n: usize) -> Option<Asteroid> {
+ if self.asteroids.len() - 1 < n {
+ None
+ } else if self.count_visible_from(source) >= n {
+ sort_by_key(
+ self.asteroids
+ .iter()
+ .filter(|b| self.has_line_of_sight(source, b)),
+ |b| (source.angle_to(b) * 100000.) as i32,
+ )
+ .nth(n)
+ .cloned()
+ } else {
+ self.remove_visible_to(source)
+ .nth_destroyed_asteroid_from(source, n - self.count_visible_from(source))
+ }
+ }
+
+ fn optimal_view_asteroid(&self) -> Option<Asteroid> {
+ self.asteroids
+ .iter()
+ .max_by_key(|a| self.count_visible_from(a))
+ .cloned()
+ }
+
+ fn count_visible_from(&self, a: &Asteroid) -> usize {
+ self.asteroids
+ .iter()
+ .filter(|b| a != *b && self.has_line_of_sight(a, b))
+ .count()
+ }
+
+ fn remove_visible_to(&self, source: &Asteroid) -> AsteroidMap {
+ AsteroidMap {
+ asteroids: self
+ .asteroids
+ .iter()
+ .filter(|b| self.has_line_of_sight(source, b))
+ .cloned()
+ .collect(),
+ }
+ }
+
+ fn has_line_of_sight(&self, a: &Asteroid, b: &Asteroid) -> bool {
+ a != b
+ && !self.asteroids.iter().any(|c| {
+ a != c
+ && b != c
+ && a.angle_to(b) == a.angle_to(c)
+ && a.distance_squared(b) > a.distance_squared(c)
+ })
+ }
+}
+
+#[derive(Debug, Clone, PartialEq, Eq)]
+struct Asteroid {
+ x: i32,
+ y: i32,
+}
+
+impl Asteroid {
+ fn angle_to(&self, other: &Asteroid) -> f32 {
+ ((self.x as f32 - other.x as f32).atan2(other.y as f32 - self.y as f32)
+ + std::f32::consts::PI)
+ % (2. * std::f32::consts::PI)
+ }
+
+ fn distance_squared(&self, other: &Asteroid) -> i32 {
+ (self.x - other.x).pow(2) + (self.y - other.y).pow(2)
+ }
+}
diff --git a/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::<Intcode>(), "Invalid number"))
+ .collect::<IntcodeProgram>();
+
+ let finished_robot = exit_on_failed_assertion(
+ Robot::new(program, !opt.debug).execute(),
+ "Robot encountered an error",
+ );
+ if opt.debug {
+ println!("{}", finished_robot.canvas.size());
+ } else {
+ println!("{}", finished_robot);
+ }
+}
+
+fn exit_on_failed_assertion<A, E: std::error::Error>(data: Result<A, E>, message: &str) -> A {
+ match data {
+ Ok(data) => data,
+ Err(e) => {
+ eprintln!("{}: {}", message, e);
+ process::exit(1);
+ }
+ }
+}
+
+#[derive(Debug, Clone)]
+struct Robot {
+ program: IntcodeProgram,
+ position: (i32, i32),
+ facing: Direction,
+ canvas: RedBlackTreeMap<(i32, i32), bool>,
+ background: bool,
+}
+
+impl fmt::Display for Robot {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ (self.min_white_y()..=self.max_white_y())
+ .map(move |y| {
+ (self.min_white_x()..=self.max_white_x())
+ .map(move |x| (x, y))
+ .map(|coord| self.canvas.get(&coord).cloned().unwrap_or(self.background))
+ .map(|c| write!(f, "{}", if c { '#' } else { ' ' }))
+ .collect::<fmt::Result>()
+ .and_then(|_| writeln!(f, ""))
+ })
+ .collect()
+ }
+}
+
+#[derive(Debug, Clone)]
+enum Direction {
+ Up,
+ Down,
+ Left,
+ Right,
+}
+
+impl Robot {
+ fn new(program: IntcodeProgram, background: bool) -> Robot {
+ Robot {
+ program: program.run_to_termination_or_input(),
+ position: (0, 0),
+ facing: Direction::Up,
+ canvas: RedBlackTreeMap::new(),
+ background,
+ }
+ }
+
+ fn execute(&self) -> Result<Robot, IntcodeProgramError> {
+ iter::successors(Some(self.clone()), |robot| Some(robot.next()))
+ .find(|robot| {
+ robot.program.error.is_some()
+ || (robot.program.halted && robot.program.output.is_empty())
+ })
+ .unwrap() // infinite iterator won't terminate unless this is Some
+ .as_result()
+ }
+
+ fn as_result(&self) -> Result<Robot, IntcodeProgramError> {
+ match self.program.error {
+ Some(ref error) => Err(error.clone()),
+ None => Ok(self.clone()),
+ }
+ }
+
+ fn next(&self) -> Robot {
+ match (
+ self.program.output.get(0).map(intcode_to_bool),
+ self.program.output.get(1).map(intcode_to_bool),
+ ) {
+ (Some(paint), Some(rot)) => Robot {
+ program: self
+ .program
+ .with_cleared_output()
+ .with_input(list![bool_to_intcode(
+ self.canvas
+ .get(&self.facing.rotate(rot).move_position(self.position))
+ .cloned()
+ .unwrap_or(self.background),
+ )])
+ .run_to_termination_or_input(),
+ position: self.facing.rotate(rot).move_position(self.position),
+ facing: self.facing.rotate(rot),
+ canvas: self.canvas.insert(self.position, paint),
+ background: self.background,
+ },
+ _ => Robot {
+ program: self
+ .program
+ .with_input(list![bool_to_intcode(
+ self.canvas
+ .get(&self.position)
+ .cloned()
+ .unwrap_or(self.background),
+ )])
+ .run_to_termination_or_input(),
+ ..self.clone()
+ },
+ }
+ }
+
+ fn min_white_x(&self) -> i32 {
+ self.white_blocks().map(|(x, _y)| x).min().unwrap_or(0)
+ }
+ fn min_white_y(&self) -> i32 {
+ self.white_blocks().map(|(_x, y)| y).min().unwrap_or(0)
+ }
+ fn max_white_x(&self) -> i32 {
+ self.white_blocks().map(|(x, _y)| x).max().unwrap_or(0)
+ }
+ fn max_white_y(&self) -> i32 {
+ self.white_blocks().map(|(_x, y)| y).max().unwrap_or(0)
+ }
+
+ fn white_blocks<'a>(&'a self) -> impl 'a + Iterator<Item = (i32, i32)> {
+ self.canvas
+ .iter()
+ .filter(|(_, val)| **val)
+ .map(|(coord, _)| coord)
+ .cloned()
+ }
+}
+
+impl Direction {
+ fn rotate(&self, clockwise: bool) -> Direction {
+ use Direction::*;
+
+ if clockwise {
+ match self {
+ Up => Right,
+ Right => Down,
+ Down => Left,
+ Left => Up,
+ }
+ } else {
+ match self {
+ Up => Left,
+ Left => Down,
+ Down => Right,
+ Right => Up,
+ }
+ }
+ }
+
+ fn move_position(&self, position: (i32, i32)) -> (i32, i32) {
+ use Direction::*;
+ match self {
+ Up => (position.0, position.1 + 1),
+ Down => (position.0, position.1 - 1),
+ Left => (position.0 - 1, position.1),
+ Right => (position.0 + 1, position.1),
+ }
+ }
+}
diff --git a/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<u64>,
+}
+
+fn main() {
+ let stdin = io::stdin();
+ let opt = Opt::from_args();
+
+ let planets: Vec<Planet> = stdin
+ .lock()
+ .lines()
+ .map(|x| exit_on_failed_assertion(x, "Error reading input"))
+ .map(|x| exit_on_failed_assertion(x.parse::<Planet>(), "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<A, E: std::error::Error>(data: Result<A, E>, message: &str) -> A {
+ match data {
+ Ok(data) => data,
+ Err(e) => {
+ eprintln!("{}: {}", message, e);
+ process::exit(1);
+ }
+ }
+}
+
+fn energy(planets: Vec<Planet>) -> i32 {
+ planets.into_iter().map(|p| p.energy()).sum()
+}
+
+fn simulate_planets_n_iterations(planets: Vec<Planet>, n: u64) -> Vec<Planet> {
+ simulate_planets_iter(planets)
+ .find(|(i, _)| *i == n)
+ .unwrap()
+ .1
+}
+
+fn simulate_planets_to_duplicate(planets: Vec<Planet>) -> 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<Planet>,
+ 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<Planet>) -> impl Iterator<Item = (u64, Vec<Planet>)> {
+ iter::successors(Some((0, planets.clone())), |(i, planets)| {
+ Some((i + 1, simulate_planets(planets.clone())))
+ })
+}
+
+fn simulate_planets(planets: Vec<Planet>) -> Vec<Planet> {
+ simulate_velocity(simulate_gravity(planets))
+}
+
+fn simulate_gravity(planets: Vec<Planet>) -> Vec<Planet> {
+ 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<Planet>) -> Vec<Planet> {
+ 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<Self, ParseIntError> {
+ s.replace(|c| "<>xyz= ".contains(c), "")
+ .split(',')
+ .map(|i| i.parse::<i32>())
+ .collect::<Result<Vec<_>, _>>()
+ .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::<i32>()
+ .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<Vec3d> 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<Intcode>,
+}
+
+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::<Intcode>(), "Invalid number"))
+ .collect::<IntcodeProgram>();
+
+ 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<A, E: std::error::Error>(data: Result<A, E>, message: &str) -> A {
+ match data {
+ Ok(data) => data,
+ Err(e) => {
+ eprintln!("{}: {}", message, e);
+ process::exit(1);
+ }
+ }
+}
+
+#[derive(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<Intcode>) -> 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<Intcode>) -> 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>) -> 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<i64>,
+}
+
+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::<Recipe>(), "Input was not a valid recipe"))
+ .collect::<Vec<_>>();
+
+ 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<A, E: std::error::Error>(data: Result<A, E>, message: &str) -> A {
+ match data {
+ Ok(data) => data,
+ Err(e) => {
+ eprintln!("{}: {}", message, e);
+ process::exit(1);
+ }
+ }
+}
+
+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<Chemical>,
+ 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<Self, Self::Err> {
+ // 2 XSNKB, 15 ZVMCB, 3 KDFNZ => 2 RFLX
+ s.replace(" => ", "=")
+ .replace(", ", ",")
+ .split(|c| c == ',' || c == '=')
+ .map(|chem| chem.parse::<Chemical>())
+ .collect::<Result<Vector<Chemical>, 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<Self, Self::Err> {
+ // 1 FUEL
+ match s.split(' ').collect::<Vec<_>>()[..] {
+ [quantity, name] => quantity
+ .parse::<i64>()
+ .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<String, i64>,
+}
+
+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::<Intcode>(), "Invalid number"))
+ .collect::<IntcodeProgram>();
+
+ if opt.find {
+ println!("{}", shortest_distance(program));
+ } else {
+ println!("{}", max_depth_from_oxygen(program));
+ }
+}
+
+fn exit_on_failed_assertion<A, E: std::error::Error>(data: Result<A, E>, message: &str) -> A {
+ match data {
+ Ok(data) => data,
+ Err(e) => {
+ eprintln!("{}: {}", message, e);
+ process::exit(1);
+ }
+ }
+}
+
+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::<String>()
+ );
+ });
+}
+
+fn exit_on_failed_assertion<A, E: std::error::Error>(data: Result<A, E>, message: &str) -> A {
+ match data {
+ Ok(data) => data,
+ Err(e) => {
+ eprintln!("{}: {}", message, e);
+ process::exit(1);
+ }
+ }
+}
+
+fn parse(s: &str) -> Result<Vec<i32>, ParseIntError> {
+ s.chars().map(|c| c.to_string().parse::<i32>()).collect()
+}
+
+fn transform(input: Vec<i32>, input_repeats: usize, fft_repeats: usize, offset: usize) -> Vec<i32> {
+ iter::successors(
+ Some(
+ input
+ .iter()
+ .cycle()
+ .take(input.len() * input_repeats)
+ .cloned()
+ .collect::<Vec<i32>>(),
+ ),
+ |input| Some(next_phase(input, offset)),
+ )
+ .nth(fft_repeats)
+ .unwrap()
+ .into_iter()
+ .skip(offset)
+ .take(8)
+ .collect()
+}
+
+fn next_phase(input: &Vec<i32>, offset: usize) -> Vec<i32> {
+ if offset > input.len() / 2 {
+ (0..input.len())
+ .into_par_iter()
+ .map(|digit| {
+ if digit < offset {
+ 0
+ } else {
+ input.iter().skip(digit).sum::<i32>().abs() % 10
+ }
+ })
+ .collect()
+ } else {
+ (0..input.len())
+ .into_par_iter()
+ .map(|digit| {
+ input
+ .iter()
+ .zip(pattern(digit))
+ .map(|(x, y)| x * y)
+ .sum::<i32>()
+ .abs()
+ % 10
+ })
+ .collect()
+ }
+}
+
+fn pattern(digit: usize) -> impl Iterator<Item = i32> {
+ 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::<Intcode>(), "Invalid number"))
+ .collect::<IntcodeProgram>();
+
+ 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::<String>()
+ );
+ println!("{}", result.last().unwrap());
+}
+
+fn exit_on_failed_assertion<A, E: std::error::Error>(data: Result<A, E>, message: &str) -> A {
+ match data {
+ Ok(data) => data,
+ Err(e) => {
+ eprintln!("{}: {}", message, e);
+ process::exit(1);
+ }
+ }
+}
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<A, E: std::error::Error>(data: Result<A, E>, message: &str) -> A {
+ match data {
+ Ok(data) => data,
+ Err(e) => {
+ eprintln!("{}: {}", message, e);
+ process::exit(1);
+ }
+ }
+}
+
+struct Maze {
+ blocks: Vec<Vec<char>>,
+ start: BoardState,
+ keys: KeySet,
+}
+
+impl FromIterator<String> for Maze {
+ fn from_iter<T: IntoIterator<Item = String>>(iter: T) -> Self {
+ Maze::from_blocks(
+ iter.into_iter()
+ .map(|line| line.chars().collect())
+ .collect(),
+ )
+ }
+}
+
+impl Maze {
+ fn from_blocks(blocks: Vec<Vec<char>>) -> 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<char> {
+ 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<BoardState>,
+ ) -> (ExploredStates, RedBlackTreeSet<BoardState>) {
+ (
+ locations
+ .iter()
+ .fold(explored, |acc, next| acc.insert(next)),
+ locations,
+ )
+ }
+
+ fn next_locations(
+ &self,
+ locations: &RedBlackTreeSet<BoardState>,
+ explored: &ExploredStates,
+ ) -> RedBlackTreeSet<BoardState> {
+ 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<KeySet, ExploredStatesForKey>,
+}
+
+#[derive(Default, Debug, Clone)]
+struct ExploredStatesForKey {
+ robots: Vector<RedBlackTreeSet<Location>>,
+}
+
+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<Location>,
+ 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<usize>,
+ /// The size of Santa's ship
+ #[structopt(long = "ship-size")]
+ ship_size: Option<usize>,
+}
+
+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::<Intcode>(), "Invalid number"))
+ .collect::<IntcodeProgram>();
+
+ 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<A, E: std::error::Error>(data: Result<A, E>, message: &str) -> A {
+ match data {
+ Ok(data) => data,
+ Err(e) => {
+ eprintln!("{}: {}", message, e);
+ process::exit(1);
+ }
+ }
+}
+
+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<Intcode>,
+ #[structopt(short = "v", long = "verb")]
+ verb: Option<Intcode>,
+ #[structopt(short = "o", long = "output")]
+ output: Option<Intcode>,
+}
+
+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::<Intcode>(), "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<A, E: std::error::Error>(data: Result<A, E>, message: &str) -> A {
+ match data {
+ Ok(data) => data,
+ Err(e) => {
+ eprintln!("{}: {}", message, e);
+ process::exit(1);
+ }
+ }
+}
+
+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::<MazeBuilder>()
+ .build();
+
+ println!("{}", maze.shortest_route(opt.include_depth));
+}
+
+fn exit_on_failed_assertion<A, E: std::error::Error>(data: Result<A, E>, message: &str) -> A {
+ match data {
+ Ok(data) => data,
+ Err(e) => {
+ eprintln!("{}: {}", message, e);
+ process::exit(1);
+ }
+ }
+}
+
+struct MazeBuilder {
+ map: Vector<Vector<char>>,
+}
+
+impl FromIterator<String> for MazeBuilder {
+ fn from_iter<T: IntoIterator<Item = String>>(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<Item = ([char; 2], Point)> + '_ {
+ 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<Item = ([char; 2], Point)> + '_ {
+ // .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<Item = ([char; 2], Point)> + '_ {
+ // 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<Item = ([char; 2], Point)> + '_ {
+ // .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<Item = ([char; 2], Point)> + '_ {
+ // 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<Vector<bool>>,
+ 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::<MazeBuilder>()
+ .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::<Intcode>(), "Invalid number"))
+ .collect::<IntcodeProgram>();
+
+ 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::<String>()
+ );
+ 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::<String>()
+ );
+ println!("{}", run_result.last().unwrap());
+}
+
+fn exit_on_failed_assertion<A, E: std::error::Error>(data: Result<A, E>, message: &str) -> A {
+ match data {
+ Ok(data) => data,
+ Err(e) => {
+ eprintln!("{}: {}", message, e);
+ process::exit(1);
+ }
+ }
+}
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::<Instruction>(), "Parse error"))
+ .collect::<Vec<Instruction>>();
+
+ //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<A, E: std::error::Error>(data: Result<A, E>, message: &str) -> A {
+ match data {
+ Ok(data) => data,
+ Err(e) => {
+ eprintln!("{}: {}", message, e);
+ process::exit(1);
+ }
+ }
+}
+
+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<Self, Self::Err> {
+ 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::<BigInt>()
+ .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::<BigInt>()
+ .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::<BigInt>()
+ .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::<Intcode>(), "Invalid number"))
+ .collect::<IntcodeProgram>();
+
+ 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<A, E: std::error::Error>(data: Result<A, E>, message: &str) -> A {
+ match data {
+ Ok(data) => data,
+ Err(e) => {
+ eprintln!("{}: {}", message, e);
+ process::exit(1);
+ }
+ }
+}
+
+#[derive(Debug, Clone)]
+struct Network {
+ computers: Vector<IntcodeProgram>,
+ nat: Option<Packet>,
+ 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<Item = Packet> + '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<Item = Packet> + 'a {
+ self.computers.iter().flat_map(|computer| {
+ computer
+ .output
+ .iter()
+ .cloned()
+ .collect::<Vec<Intcode>>()
+ .chunks_exact(3)
+ .map(|packet| Packet {
+ dest: packet[0].clone(),
+ x: packet[1].clone(),
+ y: packet[2].clone(),
+ })
+ .collect::<Vec<Packet>>()
+ })
+ }
+
+ fn pending_input<'a>(&'a self) -> impl Iterator<Item = Intcode> + 'a {
+ self.computers
+ .iter()
+ .flat_map(|computer| computer.input.iter().cloned().collect::<Vec<Intcode>>())
+ }
+
+ 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<usize>,
+ /// 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::<State>()
+ .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<A, E: std::error::Error>(data: Result<A, E>, message: &str) -> A {
+ match data {
+ Ok(data) => data,
+ Err(e) => {
+ eprintln!("{}: {}", message, e);
+ process::exit(1);
+ }
+ }
+}
+
+#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
+struct State {
+ alive: RedBlackTreeSet<Coordinate>,
+ fractal_mode: bool,
+}
+
+impl FromIterator<String> for State {
+ fn from_iter<T: IntoIterator<Item = String>>(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::<Vec<Coordinate>>()
+ })
+ .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<Item = Coordinate> + 'a {
+ self.alive
+ .iter()
+ .filter(move |coord| self.count_alive_neighbours(**coord) == 1)
+ .cloned()
+ }
+
+ fn comes_alive_next_round<'a>(&'a self) -> impl Iterator<Item = Coordinate> + '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<Coordinate> {
+ 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::<Vec<_>>()
+ .into_iter(),
+ (2, 1) => (0..5)
+ .map(|x| Coordinate {
+ x,
+ y: 0,
+ depth: coord.depth + 1,
+ })
+ .collect::<Vec<_>>()
+ .into_iter(),
+ (3, 2) => (0..5)
+ .map(|y| Coordinate {
+ x: 4,
+ y,
+ depth: coord.depth + 1,
+ })
+ .collect::<Vec<_>>()
+ .into_iter(),
+ (2, 3) => (0..5)
+ .map(|x| Coordinate {
+ x,
+ y: 4,
+ depth: coord.depth + 1,
+ })
+ .collect::<Vec<_>>()
+ .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::<Intcode>(), "Invalid number"))
+ .collect::<IntcodeProgram>();
+
+ 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::<String>()
+ );
+ println!("{}", result.last().unwrap());
+}
+
+fn exit_on_failed_assertion<A, E: std::error::Error>(data: Result<A, E>, message: &str) -> A {
+ match data {
+ Ok(data) => data,
+ Err(e) => {
+ eprintln!("{}: {}", message, e);
+ process::exit(1);
+ }
+ }
+}
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::<Wire>(), "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<A, E: std::error::Error>(data: Result<A, E>, message: &str) -> A {
+ match data {
+ Ok(data) => data,
+ Err(e) => {
+ eprintln!("{}: {}", message, e);
+ process::exit(1);
+ }
+ }
+}
+
+#[derive(Debug, Clone)]
+struct Wire {
+ segments: Vector<WireSegment>,
+}
+
+impl FromStr for Wire {
+ type Err = UnknownError;
+
+ fn from_str(s: &str) -> Result<Self, UnknownError> {
+ s.split(',')
+ .fold(
+ Ok(Vector::new()),
+ |acc: Result<Vector<WireSegment>, 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<Collision> {
+ 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<Item = Collision> + '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<Self, UnknownError> {
+ s.parse::<Direction>().and_then(|direction| {
+ WireSegment::length_from_str(s).map(|length| WireSegment {
+ start,
+ start_signal_distance,
+ direction,
+ length,
+ })
+ })
+ }
+
+ fn length_from_str(s: &str) -> Result<i32, UnknownError> {
+ s.chars()
+ .skip(1)
+ .collect::<String>()
+ .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<Collision> {
+ 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<Collision> {
+ 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<Self, UnknownError> {
+ 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<Intcode>,
+}
+
+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::<Intcode>(), "Invalid number"))
+ .collect::<IntcodeProgram>()
+ .with_input(opt.input.into_iter().collect());
+
+ let result = exit_on_failed_assertion(program.execute(), "Program errored");
+ println!("{}", result);
+}
+
+fn exit_on_failed_assertion<A, E: std::error::Error>(data: Result<A, E>, message: &str) -> A {
+ match data {
+ Ok(data) => data,
+ Err(e) => {
+ eprintln!("{}: {}", message, e);
+ process::exit(1);
+ }
+ }
+}
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::<Orbit>(), "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<A, E: std::error::Error>(data: Result<A, E>, message: &str) -> A {
+ match data {
+ Ok(data) => data,
+ Err(e) => {
+ eprintln!("{}: {}", message, e);
+ process::exit(1);
+ }
+ }
+}
+
+#[derive(Debug)]
+struct 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<Self, StrError> {
+ match s.split(')').collect::<Vec<_>>()[..] {
+ [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<OrbitalMap>,
+}
+
+struct OrbitalMapBuilder {
+ orbiters: Vector<OrbitalMap>,
+ inserted_orbits: Vector<String>,
+ pending_orbits: Vector<Orbit>,
+}
+
+impl FromIterator<Orbit> for OrbitalMap {
+ fn from_iter<T: IntoIterator<Item = Orbit>>(iter: T) -> Self {
+ iter.into_iter().collect::<OrbitalMapBuilder>().build()
+ }
+}
+
+impl FromIterator<Orbit> for OrbitalMapBuilder {
+ fn from_iter<T: IntoIterator<Item = Orbit>>(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::<usize>()
+ }
+
+ fn total_orbits(&self) -> usize {
+ self.count_orbits()
+ + self
+ .orbiters
+ .iter()
+ .map(|o| o.total_orbits())
+ .sum::<usize>()
+ }
+
+ 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<OrbitalMap> {
+ 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::<Intcode>(), "Invalid number"))
+ .collect::<IntcodeProgram>();
+
+ let result = exit_on_failed_assertion(
+ find_max_power(&program, opt.feedback_loop_mode),
+ "Program errored",
+ );
+ println!("{}", result);
+}
+
+fn exit_on_failed_assertion<A, E: std::error::Error>(data: Result<A, E>, message: &str) -> A {
+ match data {
+ Ok(data) => data,
+ Err(e) => {
+ eprintln!("{}: {}", message, e);
+ process::exit(1);
+ }
+ }
+}
+
+fn find_max_power(
+ program: &IntcodeProgram,
+ feedback_loop_mode: bool,
+) -> Result<Intcode, IntcodeProgramError> {
+ PhaseSetting::all(feedback_loop_mode)
+ .map(|phase| AmplifierArray::new(program, &phase).execute())
+ .collect::<Result<Vec<Intcode>, _>>()
+ .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<Item = PhaseSetting> {
+ if feedback_loop_mode {
+ PhaseSetting::permute(5, 10)
+ } else {
+ PhaseSetting::permute(0, 5)
+ }
+ }
+
+ fn permute(min: i32, max: i32) -> impl Iterator<Item = PhaseSetting> {
+ // 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<IntcodeProgram>,
+}
+
+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<Intcode, IntcodeProgramError> {
+ 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<Intcode, IntcodeProgramError> {
+ 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::<List<Intcode>>())
+ .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::<List<Intcode>>(),
+ )
+ },
+ )
+ .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<A, E: std::error::Error>(data: Result<A, E>, message: &str) -> A {
+ match data {
+ Ok(data) => data,
+ Err(e) => {
+ eprintln!("{}: {}", message, e);
+ process::exit(1);
+ }
+ }
+}
+
+#[derive(Debug)]
+struct Image {
+ width: u32,
+ height: u32,
+ layers: Vec<ImageLayer>,
+}
+
+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::<fmt::Result>()
+ .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<u8>,
+}
+
+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