diff options
| -rw-r--r-- | input/day16.txt | 55 | ||||
| -rw-r--r-- | input/day16_ex.txt | 10 | ||||
| -rw-r--r-- | src/day16.rs | 67 | ||||
| -rw-r--r-- | src/main.rs | 2 |
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!")); } |