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");
    }
}