From 9d38545ad4014569537579afb99516f879b17dc2 Mon Sep 17 00:00:00 2001
From: Ummon <greg.burri@gmail.com>
Date: Sun, 8 Dec 2019 19:59:49 +0100
Subject: [PATCH] Day 6

---
 src/day06.rs | 88 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 src/main.rs  | 11 ++++++-
 2 files changed, 98 insertions(+), 1 deletion(-)
 create mode 100644 src/day06.rs

diff --git a/src/day06.rs b/src/day06.rs
new file mode 100644
index 0000000..1923336
--- /dev/null
+++ b/src/day06.rs
@@ -0,0 +1,88 @@
+use std::collections::HashMap;
+use std::cmp;
+
+// All planets indexing their parent (planet -> parent).
+type Orbits = HashMap<String, String>;
+
+pub fn build_orbits(orbits_str: &[&str]) -> Orbits {
+    let mut orbits = Orbits::new();
+    for orbit in orbits_str {
+        let planets: Vec<&str> = orbit.trim().split(')').collect();
+        orbits.insert(String::from(planets[1]), String::from(planets[0]));
+    }
+    orbits
+}
+
+fn parents<'a>(orbits: &'a Orbits, planet: &str) -> Vec<&'a str> {
+    let mut parents = Vec::<&str>::new();
+    let mut current_planet = planet;
+
+    loop {
+        match orbits.get(current_planet) {
+            Some (parent) => { parents.insert(0, parent); current_planet = parent; },
+            None => break
+        }
+    }
+
+    parents
+}
+
+pub fn total_direct_and_indirect_orbits(orbits: &Orbits) -> usize {
+    orbits.keys().fold(0, |sum, planet| { sum + parents(orbits, &planet).len() })
+}
+
+pub fn nb_orbital_transfers(orbits: &Orbits, loc1: &str, loc2: &str) -> usize {
+    let parents_loc1 = parents(orbits, loc1);
+    let parents_loc2 = parents(orbits, loc2);
+    for i in 0..cmp::min(parents_loc1.len(), parents_loc2.len()) {
+        if parents_loc1[i] != parents_loc2[i] {
+            return parents_loc1.len() + parents_loc2.len() - 2 * i
+        }
+    }
+    0
+}
+
+#[cfg(test)]
+mod test {
+    use super::*;
+
+    #[test]
+    fn part1() {
+        let lines: Vec<&str> =
+            "COM)B
+                B)C
+                C)D
+                D)E
+                E)F
+                B)G
+                G)H
+                D)I
+                E)J
+                J)K
+                K)L".lines().collect();
+
+        let n = total_direct_and_indirect_orbits(&build_orbits(&lines));
+        assert_eq!(n, 42);
+    }
+
+    #[test]
+    fn part2() {
+        let lines: Vec<&str> =
+            "COM)B
+                B)C
+                C)D
+                D)E
+                E)F
+                B)G
+                G)H
+                D)I
+                E)J
+                J)K
+                K)L
+                K)YOU
+                I)SAN".lines().collect();
+
+        let n = nb_orbital_transfers(&build_orbits(&lines), "SAN", "YOU");
+        assert_eq!(n, 4);
+    }
+}
\ No newline at end of file
diff --git a/src/main.rs b/src/main.rs
index 56fefeb..1c320c5 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -5,6 +5,7 @@ use std::time::Instant;
 mod day01;
 mod day02;
 mod day03;
+mod day06;
 mod common;
 
 fn day01() -> String {
@@ -27,6 +28,13 @@ fn day03() -> String {
     )
 }
 
+fn day06() -> String {
+    let file_content = fs::read_to_string("data/day06.input").unwrap();
+    let lines: Vec<&str> = file_content.lines().collect();
+    let orbits = day06::build_orbits(&lines);
+    format!("part1: {}, part2: {}", day06::total_direct_and_indirect_orbits(&orbits), day06::nb_orbital_transfers(&orbits, "SAN", "YOU"))
+}
+
 fn format_micros(t: u128) -> String {
     if t < 10_000 {
         format!("{} μs", t)
@@ -48,7 +56,8 @@ fn main() {
     let days: Vec<fn() -> String> = vec!(
         day01,
         day02,
-        day03
+        day03,
+        day06
     );
 
     let args: Vec<String> = env::args().skip(1).collect();
-- 
2.45.2