day16 part 1

4 files changed, 134 insertions, 0 deletions

diff --git a/input/day16.txt b/input/day16.txt
new file mode 100644
index 0000000..de9d13e
--- /dev/null
+++ b/input/day16.txt
@@ -0,0 +1,55 @@
+Valve NA has flow rate=0; tunnels lead to valves MU, PH
+Valve NW has flow rate=0; tunnels lead to valves KB, MH
+Valve MR has flow rate=0; tunnels lead to valves GC, FI
+Valve XD has flow rate=0; tunnels lead to valves UN, CN
+Valve HK has flow rate=0; tunnels lead to valves AA, IF
+Valve JL has flow rate=0; tunnels lead to valves IF, WB
+Valve RQ has flow rate=13; tunnels lead to valves BL, DJ
+Valve AB has flow rate=0; tunnels lead to valves BO, RU
+Valve PE has flow rate=0; tunnels lead to valves AZ, IF
+Valve QF has flow rate=0; tunnels lead to valves TD, AZ
+Valve BA has flow rate=0; tunnels lead to valves RF, GU
+Valve SY has flow rate=0; tunnels lead to valves MH, MU
+Valve NT has flow rate=0; tunnels lead to valves DJ, UN
+Valve GU has flow rate=21; tunnels lead to valves VJ, BA, YP
+Valve AZ has flow rate=12; tunnels lead to valves QF, PI, AS, PE
+Valve WQ has flow rate=23; tunnels lead to valves VJ, UM, CN
+Valve DR has flow rate=0; tunnels lead to valves GA, CQ
+Valve UM has flow rate=0; tunnels lead to valves IE, WQ
+Valve XI has flow rate=0; tunnels lead to valves IE, IF
+Valve SS has flow rate=0; tunnels lead to valves CQ, MH
+Valve IE has flow rate=22; tunnels lead to valves YP, UM, XI, XA
+Valve BT has flow rate=24; tunnels lead to valves KB, BL, GA
+Valve GA has flow rate=0; tunnels lead to valves DR, BT
+Valve AR has flow rate=0; tunnels lead to valves IF, FI
+Valve DJ has flow rate=0; tunnels lead to valves RQ, NT
+Valve PI has flow rate=0; tunnels lead to valves FI, AZ
+Valve WB has flow rate=0; tunnels lead to valves TD, JL
+Valve OQ has flow rate=0; tunnels lead to valves ME, TD
+Valve RU has flow rate=19; tunnel leads to valve AB
+Valve IF has flow rate=7; tunnels lead to valves AR, JL, HK, PE, XI
+Valve BO has flow rate=0; tunnels lead to valves ME, AB
+Valve CN has flow rate=0; tunnels lead to valves WQ, XD
+Valve HH has flow rate=0; tunnels lead to valves AA, FS
+Valve AS has flow rate=0; tunnels lead to valves AA, AZ
+Valve FS has flow rate=0; tunnels lead to valves HH, MH
+Valve PQ has flow rate=0; tunnels lead to valves TD, AA
+Valve AA has flow rate=0; tunnels lead to valves HH, CO, AS, HK, PQ
+Valve ME has flow rate=18; tunnels lead to valves OQ, BO, PH
+Valve RF has flow rate=0; tunnels lead to valves UN, BA
+Valve MH has flow rate=8; tunnels lead to valves FS, NW, SS, SY
+Valve YP has flow rate=0; tunnels lead to valves IE, GU
+Valve FI has flow rate=11; tunnels lead to valves PI, MR, AR, CO, DI
+Valve UU has flow rate=0; tunnels lead to valves CQ, MU
+Valve CO has flow rate=0; tunnels lead to valves AA, FI
+Valve TD has flow rate=16; tunnels lead to valves QF, GC, OQ, WB, PQ
+Valve MU has flow rate=15; tunnels lead to valves SY, UU, NA
+Valve BL has flow rate=0; tunnels lead to valves BT, RQ
+Valve PH has flow rate=0; tunnels lead to valves ME, NA
+Valve XA has flow rate=0; tunnels lead to valves IE, DI
+Valve GC has flow rate=0; tunnels lead to valves TD, MR
+Valve KB has flow rate=0; tunnels lead to valves BT, NW
+Valve DI has flow rate=0; tunnels lead to valves XA, FI
+Valve CQ has flow rate=9; tunnels lead to valves UU, DR, SS
+Valve VJ has flow rate=0; tunnels lead to valves WQ, GU
+Valve UN has flow rate=20; tunnels lead to valves NT, XD, RF
\ No newline at end of file
diff --git a/input/day16_ex.txt b/input/day16_ex.txt
new file mode 100644
index 0000000..85fa5b0
--- /dev/null
+++ b/input/day16_ex.txt
@@ -0,0 +1,10 @@
+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
\ No newline at end of file
diff --git a/src/day16.rs b/src/day16.rs
new file mode 100644
index 0000000..da1709c
--- /dev/null
+++ b/src/day16.rs
@@ -0,0 +1,67 @@
+use std::collections::HashMap;
+
+use regex::Regex;
+
+#[derive(Debug,Clone)]
+struct Track {
+    current_valve: String,
+    final_pressure_release: u32,
+    valves_opened: Vec<String>,
+    debug: String,
+}
+#[derive(Debug)]
+struct Valve {
+    flow_rate: u32,
+    next_valves: Vec<String>,
+}
+pub fn run(input: String) {
+    let re = Regex::new(r"^Valve ([A-Z]+) has flow rate=(\d+); tunnels? leads? to valves? ([A-Z, ]+)$").unwrap();
+    let valves: HashMap<String,Valve> = input.lines().map(|line| {
+        let cap = re.captures(line).expect(format!("line didn't match regex! {}", line).as_str());
+        let name = cap[1].to_string();
+        let flow_rate: u32 = cap[2].parse().expect("flow rate wasn't a u32!");
+        let next_valves: Vec<String> = cap[3].split(", ").map(|x| { x.to_string() }).collect();
+        (name, Valve{flow_rate,next_valves})
+    }).collect();
+    // How to do this one?
+    // I think... tracking all options? It's basically a tree right?
+    // max depth of the tree is 30,corresponding to minutes
+    // at each depth, options are -> open valve OR move to another valve
+    // and at each depth we have a score, and a list of already-opened valves 
+
+    let root = Track {current_valve: "AA".to_string(), final_pressure_release:0, valves_opened: vec![], debug: "Start at AA".to_string()};
+    let mut tracks: Vec<Track> = vec![root];
+    let mut next_tracks: Vec<Track> = Vec::new();
+    let total_mins: u32 = 30;
+    for minute in 0..=total_mins {
+        let mins_remaining = total_mins - minute;
+        for track in &tracks {
+            let cv = &valves[&track.current_valve];
+            // try open the valve (if it's got any flow, and if it's not already open)
+            if cv.flow_rate > 0 && !track.valves_opened.contains(&track.current_valve) {
+                let mut nt = track.clone();
+                nt.valves_opened.push(track.current_valve.clone());
+                if mins_remaining > 0 {
+                    nt.final_pressure_release += cv.flow_rate * (mins_remaining-1);
+                }
+                nt.debug.push_str(format!(", Opened {}", track.current_valve).as_str());
+                next_tracks.push(nt);
+            }
+            // Alt, try moving to another valve
+            for nv in &cv.next_valves {
+                let mut nt = track.clone();
+                nt.current_valve = nv.clone();
+                nt.debug.push_str(format!(", Moved to {}", nv).as_str());
+                next_tracks.push(nt);
+            }
+        }
+        next_tracks.sort_by(|t1, t2| {t1.final_pressure_release.cmp(&t2.final_pressure_release)}.reverse());
+        next_tracks.truncate(3_usize.pow(5));
+        tracks = next_tracks.clone();
+        next_tracks = Vec::new();// prune? keep the top N scorers?
+    }
+    // Find the track with the biggest final score
+    let max_track = tracks.iter().max_by(|t1,t2| {t1.final_pressure_release.cmp(&t2.final_pressure_release)}).unwrap();
+    //let max_pressure_release = tracks.iter().map(|t| {t.final_pressure_release}).max().unwrap();
+    println!("Day 16: {}", max_track.final_pressure_release);
+}
\ No newline at end of file
diff --git a/src/main.rs b/src/main.rs
index 9b0ea44..afee780 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -17,6 +17,7 @@ mod day12;
 mod day13;
 mod day14;
 mod day15;
+mod day16;
 
 fn main() {
     day1::run(fs::read_to_string("input/day1.txt").expect("Failed to read input file!"));
@@ -34,4 +35,5 @@ fn main() {
     day13::run(fs::read_to_string("input/day13.txt").expect("Failed to read input file!"));
     day14::run(fs::read_to_string("input/day14.txt").expect("Failed to read input file!"));
     day15::run(fs::read_to_string("input/day15.txt").expect("Failed to read input file!"));
+    day16::run(fs::read_to_string("input/day16.txt").expect("Failed to read input file!"));
 }