1 files changed, 72 insertions, 0 deletions
diff --git a/src/bin/day9.rs b/src/bin/day9.rs
new file mode 100644
index 0000000..685a178
--- /dev/null
+++ b/src/bin/day9.rs
@@ -0,0 +1,72 @@
+use std::collections::{HashMap, HashSet};
+use regex::Regex;
+use itertools::Itertools;
+
+fn main() {
+    let input = advent::read_lines(9);
+    println!("9a: {}", shortest_route(&input));
+    println!("9b: {}", longest_route(&input));
+}
+
+fn parse_routes<T: AsRef<str>>(input: &[T]) -> HashMap<String, HashMap<String, u32>> {
+    let re = Regex::new(r"^([A-Za-z]+) to ([A-Za-z]+) = ([0-9]+)$").unwrap();
+
+    let mut routes = HashMap::new();
+
+    for line in input {
+        let cap = re.captures(line.as_ref()).unwrap();
+        let from = cap[1].to_string();
+        let to = cap[2].to_string();
+        let distance = cap[3].parse::<u32>().unwrap();
+
+        let entry = routes.entry(from.clone()).or_insert_with(HashMap::new);
+        entry.insert(to.clone(), distance);
+
+        let entry = routes.entry(to).or_insert_with(HashMap::new);
+        entry.insert(from, distance);
+    }
+
+    routes
+}
+
+fn distances<T: AsRef<str>>(input: &[T]) -> HashSet<u32> {
+    let routes = parse_routes(input);
+
+    let mut distances = HashSet::new();
+    for route in routes.keys().permutations(routes.keys().len()) {
+        let mut distance = 0;
+        let mut prev_city = (*route.first().unwrap()).clone();
+        for city in route.iter().skip(1).cloned().cloned() {
+            let reachable_from_prev = routes.get(&prev_city).unwrap();
+            distance += reachable_from_prev.get(&city).unwrap();
+            prev_city = city;
+        }
+        distances.insert(distance);
+    }
+
+    distances
+}
+
+fn shortest_route<T: AsRef<str>>(input: &[T]) -> u32 {
+    *distances(input).iter().min().unwrap()
+}
+
+fn longest_route<T: AsRef<str>>(input: &[T]) -> u32 {
+    *distances(input).iter().max().unwrap()
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn test() {
+        let input = [
+            "London to Dublin = 464",
+            "London to Belfast = 518",
+            "Dublin to Belfast = 141",
+        ];
+        assert_eq!(shortest_route(&input), 605);
+        assert_eq!(longest_route(&input), 982);
+    }
+}