Advent of Code 2019 - Day 12

3 min read

Today's task was more about fun space shenanigans.

We had to simulate four moons and their positions and velocity and for part 1 needed to calculate how much total energy there was after 1000 steps. For part 2 we needed to find the step at which they first repeat constellation. This part quite difficult but in the end I found out that you can check when the velocity of each moon reaches the initial state of 0 again for each axis and then find the least common multiply of those three steps.

Code

use num_integer::lcm;
use regex::Regex;
use std::cmp::Ordering;

#[derive(Debug, PartialEq, Eq, Clone)]
struct Moon {
    x: i64,
    y: i64,
    z: i64,
    vx: i64,
    vy: i64,
    vz: i64,
}

impl Moon {
    fn get_kinetic_energy(&self) -> i64 {
        self.vx.abs() + self.vy.abs() + self.vz.abs()
    }

    fn get_potential_energy(&self) -> i64 {
        self.x.abs() + self.y.abs() + self.z.abs()
    }

    pub fn get_energy(&self) -> i64 {
        self.get_potential_energy() * self.get_kinetic_energy()
    }

    pub fn update_position(&mut self) {
        self.x += self.vx;
        self.y += self.vy;
        self.z += self.vz;
    }

    pub fn attract(&mut self, other: Moon) {
        if *self == other {
            return;
        }

        self.vx += Moon::apply_gravity(self.x, other.x);
        self.vy += Moon::apply_gravity(self.y, other.y);
        self.vz += Moon::apply_gravity(self.z, other.z);
    }

    fn apply_gravity(first: i64, second: i64) -> i64 {
        match first.cmp(&second) {
            Ordering::Less => 1,
            Ordering::Equal => 0,
            Ordering::Greater => -1,
        }
    }
}

impl From<&str> for Moon {
    fn from(input: &str) -> Self {
        let pattern = Regex::new(r"<x=(-?\d+), y=(-?\d+), z=(-?\d+)>").unwrap();
        let coordinates = pattern.captures(input).unwrap();

        Moon {
            x: coordinates[1].parse::<i64>().unwrap(),
            y: coordinates[2].parse::<i64>().unwrap(),
            z: coordinates[3].parse::<i64>().unwrap(),
            vx: 0,
            vy: 0,
            vz: 0,
        }
    }
}

fn get_moons(input: &str) -> Vec<Moon> {
    let mut moons = Vec::new();

    for line in input.trim().lines() {
        moons.push(Moon::from(line));
    }

    moons
}

fn simulate(moons: &mut Vec<Moon>, steps: i64) {
    for _ in 0..steps {
        for i in 0..moons.len() {
            for y in 0..moons.len() {
                let other = moons[y].clone();
                moons[i].attract(other);
            }
        }

        for moon in moons.iter_mut() {
            moon.update_position();
        }
    }
}

fn find_cycle_step(moons: &mut Vec<Moon>) -> i64 {
    let mut step = 1;
    let mut x_step = 0;
    let mut y_step = 0;
    let mut z_step = 0;

    loop {
        simulate(moons, 1);

        if x_step == 0 && moons.iter().all(|x| x.vx == 0) {
            x_step = step;
        }

        if y_step == 0 && moons.iter().all(|x| x.vy == 0) {
            y_step = step;
        }

        if z_step == 0 && moons.iter().all(|x| x.vz == 0) {
            z_step = step;
        }

        if vec![x_step, y_step, z_step].iter().all(|x| *x > 0) {
            break;
        }

        step += 1
    }

    lcm(x_step, lcm(y_step, z_step)) * 2
}

pub fn part_one(input: &str, steps: i64) -> i64 {
    let mut moons = get_moons(input);
    simulate(&mut moons, steps);
    moons.iter().map(Moon::get_energy).sum()
}

pub fn part_two(input: &str) -> i64 {
    let mut moons = get_moons(input);
    find_cycle_step(&mut moons)
}

Benchmarks

2019 - Day 12 - Part 1 time: 1.224197ms
2019 - Day 12 - Part 2 time: 11.938797ms

Feedback or Questions?

I don't have a direct way to leave comments on posts. But if you want to give some feedback or have some questions you can contact in other ways.