Add day06, 2019

3 files changed, 205 insertions, 0 deletions

diff --git a/2019/rust/Cargo.toml b/2019/rust/Cargo.toml
index acbc8bb..cd02164 100644
--- a/2019/rust/Cargo.toml
+++ b/2019/rust/Cargo.toml
@@ -5,4 +5,5 @@ members = [
     "day03",
     "day04",
     "day05",
+    "day06",
 ]
diff --git a/2019/rust/day06/Cargo.toml b/2019/rust/day06/Cargo.toml
new file mode 100644
index 0000000..1da4ea0
--- /dev/null
+++ b/2019/rust/day06/Cargo.toml
@@ -0,0 +1,10 @@
+[package]
+name = "day06"
+version = "0.1.0"
+authors = ["cos <cos>"]
+edition = "2018"
+
+# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
+
+[dependencies]
+itertools = "0"
diff --git a/2019/rust/day06/src/main.rs b/2019/rust/day06/src/main.rs
new file mode 100644
index 0000000..1de9e38
--- /dev/null
+++ b/2019/rust/day06/src/main.rs
@@ -0,0 +1,194 @@
+use std::io::{self, BufRead};
+use itertools::Itertools;
+
+fn read_input() -> Vec<(String, String)> {
+    let stdin = io::stdin();
+
+    stdin.lock().lines()
+        .map(|line| line.unwrap().split(')').map(|s| s.to_string())
+             .next_tuple().unwrap()
+        ).collect()
+}
+
+#[derive(Clone, Debug)]
+struct Tree {
+    name: String,
+    children: Vec<Tree>,
+}
+
+impl Tree {
+    fn new(name: &str) -> Self {
+        Tree {
+            name: name.to_string(),
+            children: Vec::new(),
+        }
+    }
+
+    fn new_with_one(name: &str, tree: Tree) -> Self {
+        Tree {
+            name: name.to_string(),
+            children: vec![tree],
+        }
+    }
+
+    fn join(&mut self, mut tree:Tree) -> bool {
+        if self.name == tree.name {
+            self.children.append(&mut tree.children);
+            true
+        } else {
+            for c in &mut self.children {
+                if c.contains(&tree.name) {
+                    c.join(tree);
+                    return true;
+                }
+            }
+            false
+        }
+    }
+
+    fn contains(&self, needle:&str) -> bool {
+        if &self.name == needle {
+            return true;
+        }
+
+        for c in &self.children {
+            if c.contains(needle) {
+                return true;
+            }
+        }
+
+        false
+    }
+
+    fn orbit_count(&self) -> usize {
+        fn orbit_count_internal(t: &Tree, s:usize) -> usize {
+            let mut n = s;
+                for c in &t.children {
+                    n += orbit_count_internal(c, s + 1);
+                }
+            n
+        }
+
+        orbit_count_internal(self, 0)
+    }
+
+    fn find_distance(&self, to: &str) -> Option<usize> {
+        fn find_distance_internal(t:&Tree, p: &str, s:usize) -> usize {
+            for c in &t.children {
+                if c.contains(p) {
+                    return find_distance_internal(c, p, s + 1);
+                }
+            }
+
+            s
+        }
+
+        if self.contains(to) {
+            Some(find_distance_internal(self, to , 0))
+        } else {
+            None
+        }
+    }
+
+    fn last_common_ancestor(&self, from: &str, to: &str) -> Option<Tree> {
+        fn ancestor_internal(t: &Tree, from: &str, to: &str) -> Option<Tree> {
+            if t.contains(from) && t.contains(to) {
+                for c in &t.children {
+                    if c.contains(from) && c.contains(to) {
+                        return ancestor_internal(c, from, to);
+                    }
+                }
+                Some(t.clone())
+            } else {
+                None
+            }
+        }
+
+        ancestor_internal(self, from, to)
+    }
+}
+
+fn build_tree(orbit_map: Vec<(String, String)>) -> Option<Tree> {
+    let mut trees:Vec<Tree> = Vec::new();
+
+    for (parent, child) in &orbit_map {
+        let mut found = false;
+
+        for t in &mut trees {
+            if t.contains(parent) {
+                let newtree = Tree::new_with_one(parent, Tree::new(child));
+                found = t.join(newtree);
+                break;
+            }
+        }
+
+        if ! found {
+            let newtree = Tree::new_with_one(parent, Tree::new(child));
+            trees.push(newtree);
+        }
+    }
+
+    while {
+        let last_len = trees.len();
+
+        let mut i = 0;
+        while i < trees.len() {
+            let mut one = trees.remove(i);
+            let mut j = 0;
+            while j < trees.len() {
+                let mut two = trees.remove(j);
+                if one.contains(&two.name) {
+                    one.join(two);
+                } else if two.contains(&one.name) {
+                    two.join(one);
+                    one = two;
+                } else {
+                    trees.push(two);
+                }
+                j += 1;
+            }
+            trees.push(one);
+            i += 1;
+        }
+        trees.len() != last_len
+    } {}
+
+    if trees.len() == 1 {
+        trees.pop()
+    } else {
+        None
+    }
+}
+
+fn first_puzzle(tree: &Tree) {
+    println!("Solution to first part: {}.", tree.orbit_count());
+}
+
+fn second_puzzle(tree: &Tree, from: &str, to: &str) {
+    let junction = tree.last_common_ancestor(from, to);
+
+    let distance = match junction {
+        Some(j) => 
+            j.find_distance(from).expect("Not reachable.") +
+            j.find_distance(to).expect("Not reachable.") - 2,
+        None    => panic!("No path between {} and {}.", from, to),
+    };
+
+    println!("Solution to second part: {}.", distance);
+}
+
+fn main() {
+    let orbit_map = read_input();
+
+    let tree = build_tree(orbit_map.clone());
+
+    match &tree {
+        Some(t) => {
+            first_puzzle(t);
+            second_puzzle(t, "YOU", "SAN");
+        },
+        None =>    panic!("Could not make sense of orbit map.")
+    }
+
+
+}