day9

4 files changed, 117 insertions, 0 deletions

diff --git a/Cargo.lock b/Cargo.lock
index 3099f39..465073c 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -6,6 +6,7 @@ version = 3
 name = "advent"
 version = "0.1.0"
 dependencies = [
+ "itertools",
  "md5",
  "regex",
 ]
@@ -20,6 +21,21 @@ dependencies = [
 ]
 
 [[package]]
+name = "either"
+version = "1.8.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "90e5c1c8368803113bf0c9584fc495a58b86dc8a29edbf8fe877d21d9507e797"
+
+[[package]]
+name = "itertools"
+version = "0.10.3"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "a9a9d19fa1e79b6215ff29b9d6880b706147f16e9b1dbb1e4e5947b5b02bc5e3"
+dependencies = [
+ "either",
+]
+
+[[package]]
 name = "md5"
 version = "0.7.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
diff --git a/Cargo.toml b/Cargo.toml
index 7f06b58..8254f34 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -7,3 +7,4 @@ edition = "2021"
 [dependencies]
 md5 = "0.7"
 regex = "1"
+itertools = "0.10"
diff --git a/inputs/day9 b/inputs/day9
new file mode 100644
index 0000000..997758f
--- /dev/null
+++ b/inputs/day9
@@ -0,0 +1,28 @@
+Tristram to AlphaCentauri = 34
+Tristram to Snowdin = 100
+Tristram to Tambi = 63
+Tristram to Faerun = 108
+Tristram to Norrath = 111
+Tristram to Straylight = 89
+Tristram to Arbre = 132
+AlphaCentauri to Snowdin = 4
+AlphaCentauri to Tambi = 79
+AlphaCentauri to Faerun = 44
+AlphaCentauri to Norrath = 147
+AlphaCentauri to Straylight = 133
+AlphaCentauri to Arbre = 74
+Snowdin to Tambi = 105
+Snowdin to Faerun = 95
+Snowdin to Norrath = 48
+Snowdin to Straylight = 88
+Snowdin to Arbre = 7
+Tambi to Faerun = 68
+Tambi to Norrath = 134
+Tambi to Straylight = 107
+Tambi to Arbre = 40
+Faerun to Norrath = 11
+Faerun to Straylight = 66
+Faerun to Arbre = 144
+Norrath to Straylight = 115
+Norrath to Arbre = 135
+Straylight to Arbre = 127
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);
+    }
+}