From 5fb7322acce0c09597c0648a6546ef1d52930893 Mon Sep 17 00:00:00 2001
From: Ummon <greg.burri@gmail.com>
Date: Sun, 15 Dec 2019 10:03:57 +0100
Subject: [PATCH] Day 12

---
 Cargo.toml   |   4 +-
 src/day12.rs | 137 +++++++++++++++++++++++++++++++++++++++++++++++++++
 src/main.rs  |   9 +++-
 3 files changed, 148 insertions(+), 2 deletions(-)
 create mode 100644 src/day12.rs

diff --git a/Cargo.toml b/Cargo.toml
index c456a17..1a85341 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -8,4 +8,6 @@ edition = "2018"
 
 [dependencies]
 itertools = "0.8"
-threadpool = "1.7"
\ No newline at end of file
+threadpool = "1.7"
+regex = "1"
+num = "0.2"
\ No newline at end of file
diff --git a/src/day12.rs b/src/day12.rs
new file mode 100644
index 0000000..162a57c
--- /dev/null
+++ b/src/day12.rs
@@ -0,0 +1,137 @@
+use std::ops::AddAssign;
+
+#[derive(Debug, Copy, Clone)]
+pub struct Vector3D {
+    x: i32,
+    y: i32,
+    z: i32
+}
+
+impl AddAssign for Vector3D {
+    fn add_assign(&mut self, other: Self) {
+        *self = Self {
+            x: self.x + other.x,
+            y: self.y + other.y,
+            z: self.z + other.z
+        };
+    }
+}
+
+#[derive(Debug, Copy, Clone)]
+pub struct Moon {
+    position: Vector3D,
+    velocity: Vector3D
+}
+
+impl Moon {
+    fn total_energy(&self) -> i32 {
+        (self.position.x.abs() + self.position.y.abs() + self.position.z.abs()) *
+        (self.velocity.x.abs() + self.velocity.y.abs() + self.velocity.z.abs())
+    }
+}
+
+fn next_step(moons: &mut Vec<Moon>) {
+    // Update velocities.
+    let moons_copy = moons.clone();
+    for m1 in moons.iter_mut() {
+        for m2 in &moons_copy {
+            m1.velocity.x += if m2.position.x > m1.position.x { 1 } else if m2.position.x < m1.position.x { -1 } else { 0 };
+            m1.velocity.y += if m2.position.y > m1.position.y { 1 } else if m2.position.y < m1.position.y { -1 } else { 0 };
+            m1.velocity.z += if m2.position.z > m1.position.z { 1 } else if m2.position.z < m1.position.z { -1 } else { 0 };
+        }
+    }
+
+    // Update positions.
+    for m in moons.iter_mut() {
+        m.position += m.velocity;
+    }
+}
+
+fn create_moons(moon_positions: &[Vector3D]) -> Vec<Moon> {
+    moon_positions.iter().map(|position| Moon { position: *position, velocity: Vector3D { x: 0, y: 0, z: 0 } }).collect()
+}
+
+pub fn final_energy(moon_positions: &[Vector3D], steps: u32) -> i32 {
+    let mut moons: Vec<Moon> = create_moons(moon_positions);
+
+    for _ in 0 .. steps {
+        next_step(&mut moons);
+    }
+
+    moons.iter().fold(0, |energy, moon| energy + moon.total_energy())
+}
+
+pub fn find_same_state(moon_positions: &[Vector3D]) -> i64 {
+    use num::Integer;
+
+    let mut moons: Vec<Moon> = create_moons(moon_positions);
+    let initial_state = moons.clone();
+    let mut nb_cycles = Vector3D { x: 0, y: 0, z: 0 };
+
+    let mut i = 0;
+    loop {
+        next_step(&mut moons);
+        i += 1;
+
+        if nb_cycles.x == 0 && initial_state.iter().zip(&moons).all(
+            |(m1, m2)| m1.position.x == m2.position.x && m1.velocity.x == m2.velocity.x
+        ) { nb_cycles.x = i; }
+
+        if nb_cycles.y == 0 && initial_state.iter().zip(&moons).all(
+            |(m1, m2)| m1.position.y == m2.position.y && m1.velocity.y == m2.velocity.y
+        ) { nb_cycles.y = i; }
+
+        if nb_cycles.z == 0 && initial_state.iter().zip(&moons).all(
+            |(m1, m2)| m1.position.z == m2.position.z && m1.velocity.z == m2.velocity.z
+        ) { nb_cycles.z = i; }
+
+        if nb_cycles.x != 0 && nb_cycles.y != 0 && nb_cycles.z != 0 {
+            return (nb_cycles.x as i64).lcm(&(nb_cycles.y as i64)).lcm(&(nb_cycles.z as i64))
+        }
+    }
+}
+
+pub fn parse_positions(input: &str) -> Vec<Vector3D> {
+    use regex::Regex;
+    fn build_pattern(var: &str) -> Regex { Regex::new(&format!(r".*{}\W*?=\W*?(-?.*?\d+).*", var)).unwrap() }
+    let rex = build_pattern("x");
+    let rey = build_pattern("y");
+    let rez = build_pattern("z");
+    input
+        .lines()
+        .map(|l|
+            Vector3D {
+                x: rex.captures(l).unwrap()[1].parse().unwrap(),
+                y: rey.captures(l).unwrap()[1].parse().unwrap(),
+                z: rez.captures(l).unwrap()[1].parse().unwrap()
+            }
+        )
+        .collect()
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn part1() {
+        let input =
+            "<x=-1, y=0, z=2>
+             <x=2, y=-10, z=-7>
+             <x=4, y=-8, z=8>
+             <x=3, y=5, z=-1>";
+        let coordinates = parse_positions(input);
+        assert_eq!(final_energy(&coordinates, 10), 179);
+    }
+
+    #[test]
+    fn part2() {
+        let input =
+            "<x=-8, y=-10, z=0>
+             <x=5, y=5, z=10>
+             <x=2, y=-7, z=3>
+             <x=9, y=-8, z=-3>";
+        let coordinates = parse_positions(input);
+        assert_eq!(find_same_state(&coordinates), 4686774924);
+    }
+}
\ No newline at end of file
diff --git a/src/main.rs b/src/main.rs
index e8266af..3b877e9 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -12,6 +12,7 @@ mod day07;
 mod day08;
 mod day10;
 mod day11;
+mod day12;
 
 fn day01() -> String {
     let masses = common::read_list_of_numbers("data/day01.input", "\n");
@@ -88,6 +89,11 @@ fn day11() -> String {
     format!("part1: {:?}, part2:\n{}", day11::run_robot(&code, 0).len(), common::layer_to_printable_string(&layer, width))
 }
 
+fn day12() -> String {
+    let coordinates = day12::parse_positions(&fs::read_to_string("data/day12.input").unwrap());
+    format!("part1: {}, part2: {}", day12::final_energy(&coordinates, 1000), day12::find_same_state(&coordinates))
+}
+
 fn format_micros(t: u128) -> String {
     if t < 10_000 {
         format!("{} μs", t)
@@ -117,7 +123,8 @@ fn main() {
         day08,
         day09,
         day10,
-        day11
+        day11,
+        day12
     );
 
     let args: Vec<String> = env::args().skip(1).collect();
-- 
2.45.2