From f7c0291770009bfd8d171727ff6f03b59aa8c644 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Kjetil=20=C3=98rbekk?= Date: Mon, 16 Dec 2019 10:15:21 -0500 Subject: AOC 12 part 2 --- advent/src/12_2.rs | 97 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 97 insertions(+) create mode 100644 advent/src/12_2.rs (limited to 'advent/src/12_2.rs') 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); + +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 { + let mut m : HashMap = 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"); + } +} + -- cgit v1.2.3