Day 12 part 2

1 files changed, 59 insertions, 10 deletions

diff --git a/src/bin/day_12.rs b/src/bin/day_12.rs
index 678653b..fa0db20 100644
--- a/src/bin/day_12.rs
+++ b/src/bin/day_12.rs
@@ -16,7 +16,7 @@ use structopt::StructOpt;
 /// See https://adventofcode.com/2019/day/12 for details.
 struct Opt {
     #[structopt(short = "n")]
-    n: usize,
+    n: Option<u64>,
 }
 
 fn main() {
@@ -30,7 +30,10 @@ fn main() {
         .map(|x| exit_on_failed_assertion(x.parse::<Planet>(), "Input was not a valid planet"))
         .collect();
 
-    println!("{}", energy(simulate_planets_n_iterations(planets, opt.n)));
+    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 {
@@ -47,13 +50,47 @@ fn energy(planets: Vec<Planet>) -> i32 {
     planets.into_iter().map(|p| p.energy()).sum()
 }
 
-fn simulate_planets_n_iterations(planets: Vec<Planet>, n: usize) -> Vec<Planet> {
-    iter::successors(Some((0, planets)), |(i, planets)| {
+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())))
     })
-    .find(|(i, _)| *i == n)
-    .unwrap()
-    .1
 }
 
 fn simulate_planets(planets: Vec<Planet>) -> Vec<Planet> {
@@ -68,7 +105,7 @@ fn simulate_gravity(planets: Vec<Planet>) -> Vec<Planet> {
             vel: planets
                 .iter()
                 .filter(|o| p != *o)
-                .map(|o| p.gravity_pull(o))
+                .map(|o| p.acc(o))
                 .fold(p.vel, |acc, next| acc + next),
         })
         .collect()
@@ -116,13 +153,13 @@ impl FromStr for Planet {
                 }),
                 _ => "wrong number of fields"
                     .parse::<i32>()
-                    .map(|x| Planet::default()),
+                    .map(|_x| Planet::default()),
             })
     }
 }
 
 impl Planet {
-    fn gravity_pull(&self, other: &Planet) -> Vec3d {
+    fn acc(&self, other: &Planet) -> Vec3d {
         Vec3d {
             x: gravity(self.pos.x, other.pos.x),
             y: gravity(self.pos.y, other.pos.y),
@@ -134,6 +171,18 @@ impl Planet {
         (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 {