From 2047776ff9e33be8261cbe26961316f87862422f Mon Sep 17 00:00:00 2001
From: Greg Burri <greg.burri@gmail.com>
Date: Fri, 16 Dec 2022 16:04:32 +0100
Subject: [PATCH] Day 16 part 1

---
 src/day16.rs | 143 +++++++++++++++++++++++++++++++++++++++++++++++++++
 src/days.rs  |   9 ++++
 src/main.rs  |   2 +
 3 files changed, 154 insertions(+)
 create mode 100644 src/day16.rs

diff --git a/src/day16.rs b/src/day16.rs
new file mode 100644
index 0000000..ae2920f
--- /dev/null
+++ b/src/day16.rs
@@ -0,0 +1,143 @@
+use std::collections::HashMap;
+
+use itertools::Itertools;
+use regex::{self, Regex};
+
+#[derive(Debug)]
+pub struct Valve {
+    neighbours: Vec<i32>,
+    flow: i32,
+}
+
+pub fn parse(input: &str) -> (i32, Vec<Valve>) {
+    let regex =
+        Regex::new(r"Valve (\w{2}) has flow rate=(\d+); tunnels? leads? to valves? (.+)").unwrap();
+
+    let mut valve_aa = 0;
+
+    let mut names = HashMap::<String, i32>::new();
+    let lines = input
+        .lines()
+        .enumerate()
+        .map(|(i, l)| {
+            let captures = regex.captures(l).unwrap();
+            let i = i as i32;
+
+            if &captures[1] == "AA" {
+                valve_aa = i;
+            }
+
+            names.insert(captures[1].to_string(), i);
+
+            (
+                captures[2].parse::<i32>().unwrap(),
+                captures[3]
+                    .split(", ")
+                    .map(str::to_string)
+                    .collect::<Vec<String>>(),
+            )
+        })
+        .collect_vec();
+
+    let mut valves = Vec::new();
+
+    for (flow, neigbours) in lines {
+        valves.push(Valve {
+            neighbours: neigbours.iter().map(|n| names[n]).collect(),
+            flow,
+        });
+    }
+
+    (valve_aa, valves)
+}
+
+pub fn most_pressure(start: i32, time: i32, valves: &[Valve]) -> i32 {
+    let n = valves.len();
+    let mut times_tables = vec![vec![0; n]; n];
+    for i in 0..valves.len() {
+        let mut visited = vec![false; n];
+        let mut to_visit = Vec::new();
+        let mut next_to_visit = vec![i as i32];
+        let mut l = 0;
+        while !next_to_visit.is_empty() {
+            std::mem::swap(&mut to_visit, &mut next_to_visit);
+            while let Some(n) = to_visit.pop() {
+                if !visited[n as usize] {
+                    visited[n as usize] = true;
+                    times_tables[i as usize][n as usize] = l;
+                    next_to_visit.extend_from_slice(&valves[n as usize].neighbours)
+                }
+            }
+            l += 1;
+        }
+    }
+
+    let non_broken_valves: Vec<i32> = valves
+        .iter()
+        .enumerate()
+        .filter_map(|(i, v)| if v.flow > 0 { Some(i as i32) } else { None })
+        .collect();
+
+    fn best_score(
+        time_left: i32,
+        current_path: Vec<i32>,
+        non_broken_valves: &[i32],
+        times_tables: &[Vec<i32>],
+        valves: &[Valve],
+    ) -> i32 {
+        non_broken_valves
+            .iter()
+            .map(|v| {
+                if !current_path.contains(v) {
+                    let time = times_tables[*current_path.last().unwrap() as usize][*v as usize];
+                    // -1 is the time to open the valve.
+                    let time_left_after_v = time_left - time - 1;
+                    if time_left_after_v > 0 {
+                        let mut path_cloned = current_path.clone();
+                        path_cloned.push(*v);
+                        time_left_after_v * valves[*v as usize].flow
+                            + best_score(
+                                time_left_after_v,
+                                path_cloned,
+                                non_broken_valves,
+                                times_tables,
+                                valves,
+                            )
+                    } else {
+                        0
+                    }
+                } else {
+                    0
+                }
+            })
+            .max()
+            .unwrap()
+    }
+
+    best_score(time, vec![start], &non_broken_valves, &times_tables, valves)
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    static VALVES: &str = "Valve AA has flow rate=0; tunnels lead to valves DD, II, BB
+    Valve BB has flow rate=13; tunnels lead to valves CC, AA
+    Valve CC has flow rate=2; tunnels lead to valves DD, BB
+    Valve DD has flow rate=20; tunnels lead to valves CC, AA, EE
+    Valve EE has flow rate=3; tunnels lead to valves FF, DD
+    Valve FF has flow rate=0; tunnels lead to valves EE, GG
+    Valve GG has flow rate=0; tunnels lead to valves FF, HH
+    Valve HH has flow rate=22; tunnel leads to valve GG
+    Valve II has flow rate=0; tunnels lead to valves AA, JJ
+    Valve JJ has flow rate=21; tunnel leads to valve II";
+
+    #[test]
+    fn part1() {
+        let (start, valves) = parse(VALVES);
+        assert_eq!(most_pressure(start, 30, &valves), 1651);
+    }
+
+    #[test]
+    fn part2() {}
+}
diff --git a/src/days.rs b/src/days.rs
index 45a6b9b..3168dea 100644
--- a/src/days.rs
+++ b/src/days.rs
@@ -160,3 +160,12 @@ pub fn day15() -> String {
         day15::tuning_frequency(&sensors, 4_000_000)
     )
 }
+
+pub fn day16() -> String {
+    let (start, valves) = day16::parse(&fs::read_to_string("data/day16.input").unwrap());
+    format!(
+        "part1: {}, part2: {}",
+        day16::most_pressure(start, 30, &valves),
+        0
+    )
+}
diff --git a/src/main.rs b/src/main.rs
index c56644b..1086131 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -18,6 +18,7 @@ mod day12;
 mod day13;
 mod day14;
 mod day15;
+mod day16;
 mod days;
 
 #[derive(Parser, Debug)]
@@ -49,6 +50,7 @@ fn main() {
         days::day13,
         days::day14,
         days::day15,
+        days::day16,
     ];
 
     let args = Args::parse();
-- 
2.45.2