day12.rs

//
//  It was maybe not such a great idea (code-length wise) to represent
//  MoonSystem, Moon, Coordinates and so on with explicit structs. Could probably be done
//  in 1/4 of the lines with Vecs.
//

use std::collections::HashSet;

fn main() {
    let mut moons = MoonSystem {
        io: Moon {
            position: Position { x: -3, y: 10, z: -1},
            velocity: Velocity { x: 0, y: 0, z: 0}    
        },
        europa: Moon {
            position: Position { x: -12, y: -10, z: -5},
            velocity: Velocity { x: 0, y: 0, z: 0}    
        },
        ganymede: Moon {
            position: Position { x: -9, y: 0, z: 10},
            velocity: Velocity { x: 0, y: 0, z: 0}    
        },
        callisto: Moon {
            position: Position { x: 7, y: -5, z: -3},
            velocity: Velocity { x: 0, y: 0, z: 0}    
        }
    };

    let mut x_cycle: Option<u64> = None;
    let mut y_cycle: Option<u64> = None;
    let mut z_cycle: Option<u64> = None;
    let mut n_step: u64 = 0;
    let m_start = moons.clone();
    loop {
        moons.update_velocities();
        moons.update_positions();
        n_step += 1;
        if moons.equal_x(&m_start) && x_cycle == None {
            x_cycle = Some(n_step)
        }
        if moons.equal_y(&m_start) && y_cycle == None {
            y_cycle = Some(n_step)
        }
        if moons.equal_z(&m_start) && z_cycle == None {
            z_cycle = Some(n_step)
        }

        if  x_cycle != None && y_cycle != None && z_cycle != None {
            break
        }
    }
    // Correct is: 484244804958744
    println!("And the world starts again at step: {}", calculate_steps(vec!(x_cycle.unwrap(), y_cycle.unwrap(), z_cycle.unwrap())))
}

fn calculate_steps(v: Vec<u64>) -> u64 {
    let factors_per_dim: Vec<Vec<u64>> = v.iter().map(|n| prime_factors(*n)).collect();
    let mut all_primes: HashSet<u64> = HashSet::new();
    factors_per_dim.iter().flatten().for_each( |p| {all_primes.insert(*p);});
    let mut lcm: u64 = 1;    
    for prime in all_primes {
        let amount: u64 = (0..3).fold(0, |acc, dim| acc.max(factors_per_dim[dim].iter().filter(|n| **n == prime).count() as u64));
        let c = prime.pow(amount as u32);
        lcm *= c
    }
    lcm
}

fn prime_factors(n_in: u64) -> Vec<u64> {
    let mut factors: Vec<u64> = vec!();
    let mut i: u64 = 2;
    let mut n: u64 = n_in;
    while i * i <= n {
        if n % i != 0 {
            i += 1
        } else {
            n /= i;
            factors.push(i)
        }
    }
    if n > 1 {
        factors.push(n)
    }
    factors
}


fn accumulate_gravity(acc: &(i64, i64, i64), contrib: &(i64, i64, i64)) -> (i64, i64, i64) {
    (acc.0 + contrib.0, acc.1 + contrib.1, acc.2 + contrib.2)
}

fn gravity_contribution(moon: &Moon, other_moon: &Moon) -> (i64, i64, i64) {
    (gravity_coord_contribution(moon.position.x, other_moon.position.x),
    gravity_coord_contribution(moon.position.y, other_moon.position.y),
    gravity_coord_contribution(moon.position.z, other_moon.position.z))
}

fn gravity_coord_contribution(coord: i64, other_coord: i64) -> i64 {
    if coord < other_coord {
        1
    } else if coord > other_coord {
        -1
    } else {
        0
    }
}

#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)]
struct Position {
    x: i64,
    y: i64,
    z: i64
}

#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)]
struct Velocity {
    x: i64,
    y: i64,
    z: i64
}

#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)]
struct MoonSystem {
    io: Moon,
    europa: Moon,
    ganymede: Moon,
    callisto: Moon
}

impl MoonSystem {
    fn equal_x(&self, other: &MoonSystem) -> bool {
        self.europa.position.x == other.europa.position.x &&
        self.io.position.x == other.io.position.x &&
        self.ganymede.position.x == other.ganymede.position.x &&
        self.callisto.position.x == other.callisto.position.x &&
        self.europa.velocity.x == other.europa.velocity.x &&
        self.io.velocity.x == other.io.velocity.x &&
        self.ganymede.velocity.x == other.ganymede.velocity.x &&
        self.callisto.velocity.x == other.callisto.velocity.x
    }

    fn equal_y(&self, other: &MoonSystem) -> bool {
        self.europa.position.y == other.europa.position.y &&
        self.io.position.y == other.io.position.y &&
        self.ganymede.position.y == other.ganymede.position.y &&
        self.callisto.position.y == other.callisto.position.y &&
        self.europa.velocity.y == other.europa.velocity.y &&
        self.io.velocity.y == other.io.velocity.y &&
        self.ganymede.velocity.y == other.ganymede.velocity.y &&
        self.callisto.velocity.y == other.callisto.velocity.y
    }

    fn equal_z(&self, other: &MoonSystem) -> bool {
        self.europa.position.z == other.europa.position.z &&
        self.io.position.z == other.io.position.z &&
        self.ganymede.position.z == other.ganymede.position.z &&
        self.callisto.position.z == other.callisto.position.z &&
        self.europa.velocity.z == other.europa.velocity.z &&
        self.io.velocity.z == other.io.velocity.z &&
        self.ganymede.velocity.z == other.ganymede.velocity.z &&
        self.callisto.velocity.z == other.callisto.velocity.z
    }

    fn moons(&self) -> Vec<&Moon> {
        vec!(&self.io, &self.europa, &self.ganymede, &self.callisto)
    }
    fn update_positions(&mut self) {
        self.europa.update_position();
        self.io.update_position();
        self.ganymede.update_position();
        self.callisto.update_position();
    }

    fn update_velocities(&mut self) {
        let io_gravity = self.moons().iter().filter(|x| *x != &&self.io).fold((0, 0, 0), |acc, o| accumulate_gravity(&acc, &gravity_contribution(&self.io, o)));
        let europa_gravity = self.moons().iter().filter(|x| *x != &&self.europa).fold((0, 0, 0), |acc, o| accumulate_gravity(&acc, &gravity_contribution(&self.europa, o)));
        let ganymede_gravity = self.moons().iter().filter(|x| *x != &&self.ganymede).fold((0, 0, 0), |acc, o| accumulate_gravity(&acc, &gravity_contribution(&self.ganymede, o)));
        let callisto_gravity = self.moons().iter().filter(|x| *x != &&self.callisto).fold((0, 0, 0), |acc, o| accumulate_gravity(&acc, &gravity_contribution(&self.callisto, o)));
        self.europa.update_velocity(&europa_gravity);
        self.io.update_velocity(&io_gravity);
        self.ganymede.update_velocity(&ganymede_gravity);
        self.callisto.update_velocity(&callisto_gravity);
    }

}

#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)]
struct Moon {
    position: Position,
    velocity: Velocity
}

impl Moon {
    fn update_position(&mut self) {
        self.position.x += self.velocity.x;
        self.position.y += self.velocity.y;
        self.position.z += self.velocity.z;
    }

    fn update_velocity(&mut self, gravity: &(i64, i64, i64)) {
        self.velocity.x += gravity.0;
        self.velocity.y += gravity.1;
        self.velocity.z += gravity.2;
    }    
}

#[cfg(test)]
mod test {

    #[test]
    fn basic() {
        assert!(true);
    }
}