1 files changed, 205 insertions, 0 deletions
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,
+        }
+    }
+}