day13

2 files changed, 154 insertions, 0 deletions

diff --git a/inputs/day13 b/inputs/day13
new file mode 100644
index 0000000..83755b0
--- /dev/null
+++ b/inputs/day13
@@ -0,0 +1,56 @@
+Alice would lose 57 happiness units by sitting next to Bob.
+Alice would lose 62 happiness units by sitting next to Carol.
+Alice would lose 75 happiness units by sitting next to David.
+Alice would gain 71 happiness units by sitting next to Eric.
+Alice would lose 22 happiness units by sitting next to Frank.
+Alice would lose 23 happiness units by sitting next to George.
+Alice would lose 76 happiness units by sitting next to Mallory.
+Bob would lose 14 happiness units by sitting next to Alice.
+Bob would gain 48 happiness units by sitting next to Carol.
+Bob would gain 89 happiness units by sitting next to David.
+Bob would gain 86 happiness units by sitting next to Eric.
+Bob would lose 2 happiness units by sitting next to Frank.
+Bob would gain 27 happiness units by sitting next to George.
+Bob would gain 19 happiness units by sitting next to Mallory.
+Carol would gain 37 happiness units by sitting next to Alice.
+Carol would gain 45 happiness units by sitting next to Bob.
+Carol would gain 24 happiness units by sitting next to David.
+Carol would gain 5 happiness units by sitting next to Eric.
+Carol would lose 68 happiness units by sitting next to Frank.
+Carol would lose 25 happiness units by sitting next to George.
+Carol would gain 30 happiness units by sitting next to Mallory.
+David would lose 51 happiness units by sitting next to Alice.
+David would gain 34 happiness units by sitting next to Bob.
+David would gain 99 happiness units by sitting next to Carol.
+David would gain 91 happiness units by sitting next to Eric.
+David would lose 38 happiness units by sitting next to Frank.
+David would gain 60 happiness units by sitting next to George.
+David would lose 63 happiness units by sitting next to Mallory.
+Eric would gain 23 happiness units by sitting next to Alice.
+Eric would lose 69 happiness units by sitting next to Bob.
+Eric would lose 33 happiness units by sitting next to Carol.
+Eric would lose 47 happiness units by sitting next to David.
+Eric would gain 75 happiness units by sitting next to Frank.
+Eric would gain 82 happiness units by sitting next to George.
+Eric would gain 13 happiness units by sitting next to Mallory.
+Frank would gain 77 happiness units by sitting next to Alice.
+Frank would gain 27 happiness units by sitting next to Bob.
+Frank would lose 87 happiness units by sitting next to Carol.
+Frank would gain 74 happiness units by sitting next to David.
+Frank would lose 41 happiness units by sitting next to Eric.
+Frank would lose 99 happiness units by sitting next to George.
+Frank would gain 26 happiness units by sitting next to Mallory.
+George would lose 63 happiness units by sitting next to Alice.
+George would lose 51 happiness units by sitting next to Bob.
+George would lose 60 happiness units by sitting next to Carol.
+George would gain 30 happiness units by sitting next to David.
+George would lose 100 happiness units by sitting next to Eric.
+George would lose 63 happiness units by sitting next to Frank.
+George would gain 57 happiness units by sitting next to Mallory.
+Mallory would lose 71 happiness units by sitting next to Alice.
+Mallory would lose 28 happiness units by sitting next to Bob.
+Mallory would lose 10 happiness units by sitting next to Carol.
+Mallory would gain 44 happiness units by sitting next to David.
+Mallory would gain 22 happiness units by sitting next to Eric.
+Mallory would gain 79 happiness units by sitting next to Frank.
+Mallory would lose 16 happiness units by sitting next to George.
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);
+    }
+}