day13

1 files changed, 98 insertions, 0 deletions

diff --git a/src/bin/day13.rs b/src/bin/day13.rs
new file mode 100644
index 0000000..37590e1
--- /dev/null
+++ b/src/bin/day13.rs
@@ -0,0 +1,98 @@
+use std::collections::HashMap;
+use regex::Regex;
+use itertools::Itertools;
+
+type HappinessMap = HashMap<String, HashMap<String, i32>>;
+
+fn main() {
+    let input = advent::read_lines(13);
+    println!("13a: {}", max_happiness(&input));
+    println!("13b: {}", max_happiness_you(&input));
+}
+
+fn parse_happiness<T: AsRef<str>>(input: &[T]) -> HappinessMap {
+    let mut happiness_map = HashMap::new();
+    let re = Regex::new(r"^([A-Za-z]+) would (gain|lose) ([0-9]+) happiness units by sitting next to ([A-Za-z]+).$").unwrap();
+
+    for line in input {
+        let cap = re.captures(line.as_ref()).unwrap();
+        let person = cap[1].to_string();
+        let action = cap[2].to_string();
+        let amount = cap[3].parse::<i32>().unwrap();
+        let nextto = cap[4].to_string();
+
+        let entry = happiness_map.entry(person).or_insert_with(HashMap::new);
+        match action.as_ref() {
+            "gain" => { entry.insert(nextto, amount); },
+            "lose" => { entry.insert(nextto, -amount); },
+            _ => panic!("invalid action"),
+        }
+    }
+
+    happiness_map
+}
+
+fn calculate_happiness(happiness_map: &HappinessMap, seating: &[&String]) -> i32 {
+    let mut happiness = 0;
+    let first = *seating.first().unwrap();
+    let mut prev = first;
+    for person in seating.iter().skip(1).cloned() {
+        happiness += happiness_map.get(prev).unwrap().get(person).unwrap();
+        happiness += happiness_map.get(person).unwrap().get(prev).unwrap();
+        prev = person;
+    }
+    happiness += happiness_map.get(prev).unwrap().get(first).unwrap();
+    happiness += happiness_map.get(first).unwrap().get(prev).unwrap();
+
+    happiness
+}
+
+fn max_happiness<T: AsRef<str>>(input: &[T]) -> i32 {
+    let happiness_map = parse_happiness(input);
+
+    happiness_map.keys()
+                 .permutations(happiness_map.keys().len())
+                 .map(|seating| calculate_happiness(&happiness_map, &seating))
+                 .max()
+                 .unwrap()
+}
+
+fn max_happiness_you<T: AsRef<str>>(input: &[T]) -> i32 {
+    let mut happiness_map = parse_happiness(input);
+    let mut your_map = HashMap::new();
+    for (person, map) in happiness_map.iter_mut() {
+        your_map.insert(person.clone(), 0);
+        map.insert("You".to_string(), 0);
+    }
+    happiness_map.insert("You".to_string(), your_map);
+
+    happiness_map.keys()
+                 .permutations(happiness_map.keys().len())
+                 .map(|seating| calculate_happiness(&happiness_map, &seating))
+                 .max()
+                 .unwrap()
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn test() {
+        let input = [
+            "Alice would gain 54 happiness units by sitting next to Bob.",
+            "Alice would lose 79 happiness units by sitting next to Carol.",
+            "Alice would lose 2 happiness units by sitting next to David.",
+            "Bob would gain 83 happiness units by sitting next to Alice.",
+            "Bob would lose 7 happiness units by sitting next to Carol.",
+            "Bob would lose 63 happiness units by sitting next to David.",
+            "Carol would lose 62 happiness units by sitting next to Alice.",
+            "Carol would gain 60 happiness units by sitting next to Bob.",
+            "Carol would gain 55 happiness units by sitting next to David.",
+            "David would gain 46 happiness units by sitting next to Alice.",
+            "David would lose 7 happiness units by sitting next to Bob.",
+            "David would gain 41 happiness units by sitting next to Carol.",
+        ];
+        assert_eq!(max_happiness(&input), 330);
+    }
+}