AOC 12 part 2

2 files changed, 102 insertions, 0 deletions

diff --git a/advent/Cargo.toml b/advent/Cargo.toml
index 46c4fb0..775e2c8 100644
--- a/advent/Cargo.toml
+++ b/advent/Cargo.toml
@@ -8,4 +8,9 @@ edition = "2018"
 name = "12"
 path = "src/12.rs"
 
+[[bin]]
+name = "12_2"
+path = "src/12_2.rs"
+
 [dependencies]
+num = "0.1"
diff --git a/advent/src/12_2.rs b/advent/src/12_2.rs
new file mode 100644
index 0000000..403e2e4
--- /dev/null
+++ b/advent/src/12_2.rs
@@ -0,0 +1,97 @@
+extern crate num;
+use std::cmp;
+use std::collections::HashMap;
+use num::integer;
+
+#[derive(Debug, PartialEq, Eq, Hash, Clone)]
+struct Moon {
+    pos: i64,
+    vel: i64
+}
+
+fn sign(x: i64) -> i64 {
+    if x < 0 {
+        -1
+    } else if x > 0 {
+        1
+    } else {
+        0
+    }
+}
+
+impl Moon {
+    fn new(pos: i64) -> Moon {
+        Moon { pos: pos, vel: 0 }
+    }
+
+    fn step(&self, moons: &[Moon]) -> Moon {
+        let mut vel = self.vel;
+        for moon in moons {
+            vel += sign(moon.pos - self.pos);
+        }
+        Moon { pos: self.pos + vel, vel: vel }
+    }
+}
+
+#[derive(Debug, PartialEq, Eq, Hash, Clone)]
+struct Moons(Vec<Moon>);
+
+impl Moons {
+    fn step(&self) -> Moons {
+        Moons(self.0.iter().map(|m| m.step(&self.0)).collect())
+    }
+}
+
+fn run_steps(mut m: Moons, steps: i64, debug: bool) {
+    for i in 0..steps {
+        if debug {
+            println!("After {} steps:", i);
+            println!("{:?}", m);
+        }
+        m = m.step()
+    }
+    println!("After {} steps:", steps);
+    println!("{:?}", m);
+}
+
+#[derive(Debug)]
+struct Cycle {
+    start: i64,
+    length: i64,
+    moons: Moons,
+}
+
+fn find_cycle(mut moons: Moons, limit: i64) -> Option<Cycle> {
+    let mut m : HashMap<Moons, i64> = HashMap::new();
+    for i in 0..limit {
+        if m.contains_key(&moons) {
+            let start = m[&moons];
+            return Some(Cycle { start: start, length: i - start, moons: moons.clone() });
+        } else {
+            m.insert(moons.clone(), i);
+            moons = moons.step();
+        }
+    }
+    println!("Giving up after {} steps", limit);
+    None
+}
+
+fn main() {
+    let moon_x = Moons(vec!(-8, 5, 2, 9).into_iter().map(Moon::new).collect());
+    let moon_y = Moons(vec!(-10, 5, -7, -8).into_iter().map(Moon::new).collect());
+    let moon_z = Moons(vec!(0, 10, 3, -3).into_iter().map(Moon::new).collect());
+
+    let cycle_x = find_cycle(moon_x, 1 << 30);
+    let cycle_y = find_cycle(moon_y, 1 << 30);
+    let cycle_z = find_cycle(moon_z, 1 << 30);
+
+    if let (Some(cx), Some(cy), Some(cz)) = (cycle_x, cycle_y, cycle_z) {
+        println!("cycles:\n{:?}\n{:?}\n{:?}", cx, cy, cz);
+        let start = cmp::max(cx.start, cmp::max(cy.start, cz.start));
+        let length = integer::lcm(cx.length, integer::lcm(cy.length, cz.length));
+        println!("common cycle: start={} length={}", start, length);
+    } else {
+        println!("failed");
+    }
+}
+