diff options
| -rw-r--r-- | src/day16.rs | 83 | ||||
| -rw-r--r-- | src/main.rs | 60 |
2 files changed, 93 insertions, 50 deletions
diff --git a/src/day16.rs b/src/day16.rs index da1709c..03e7945 100644 --- a/src/day16.rs +++ b/src/day16.rs @@ -4,7 +4,8 @@ use regex::Regex; #[derive(Debug,Clone)] struct Track { - current_valve: String, + my_current_valve: String, + elephant_current_valve: String, final_pressure_release: u32, valves_opened: Vec<String>, debug: String, @@ -14,6 +15,24 @@ struct Valve { flow_rate: u32, next_valves: Vec<String>, } + +#[derive(PartialEq)] +enum Move {Open, Move(String)} + +fn poss_moves(valves: &HashMap<String,Valve>, current_valve: &String, open_valves: &Vec<String>) -> Vec<Move> { + let mut res = vec![]; + let cv = &valves[current_valve]; + // try open the valve (if it's got any flow, and if it's not already open) + if cv.flow_rate > 0 && !open_valves.contains(current_valve) { + res.push(Move::Open); + } + // Alt, try moving to another valve + for nv in &cv.next_valves { + res.push(Move::Move(nv.clone())); + } + res +} + 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| { @@ -29,34 +48,58 @@ pub fn run(input: String) { // 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 root = Track {my_current_valve: "AA".to_string(), elephant_current_valve: "AA".to_string(), final_pressure_release:0, valves_opened: vec![], debug: "Start at AA\n".to_string()}; let mut tracks: Vec<Track> = vec![root]; let mut next_tracks: Vec<Track> = Vec::new(); - let total_mins: u32 = 30; + //let total_mins: u32 = 30; + let total_mins: u32 = 26; 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); + // Cartesian the next moves by me and the elephant + // For each in the product, calculate changed final_pressure_release (if we opened a valve(s)) + // And extend the debug string! + let my_poss_moves = poss_moves(&valves, &track.my_current_valve, &track.valves_opened); + for mm in my_poss_moves { + let mut vo = track.valves_opened.clone(); + if mm == Move::Open { + vo.push(track.my_current_valve.clone()); // Care, we don't try to open the same valve at once. + } + let e_poss_moves = poss_moves(&valves, &track.elephant_current_valve, &vo); + for em in e_poss_moves { + let mut nt = track.clone(); + nt.debug.push_str(format!("minute {}", minute+1).as_str()); + if let Move::Move(nv) = &mm { + nt.my_current_valve = nv.clone(); + nt.debug.push_str(format!(", I Moved To {}", nv).as_str()); + } else { + nt.valves_opened.push(track.my_current_valve.clone()); + let cv = &valves[&track.my_current_valve]; + if mins_remaining > 0 { + nt.final_pressure_release += cv.flow_rate * (mins_remaining-1); + } + nt.debug.push_str(format!(", I Opened {}", track.my_current_valve).as_str()); + } + if let Move::Move(nv) = &em { + nt.elephant_current_valve = nv.clone(); + nt.debug.push_str(format!(", Elephant Moved To {}", nv).as_str()); + } else { + nt.valves_opened.push(track.elephant_current_valve.clone()); + let cv = &valves[&track.elephant_current_valve]; + if mins_remaining > 0 { + nt.final_pressure_release += cv.flow_rate * (mins_remaining-1); + } + nt.debug.push_str(format!(", Elephant Opened {}", track.elephant_current_valve).as_str()); + } + nt.debug.push('\n'); + next_tracks.push(nt); } - 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)); + // 3.pow(30) is too many options, just prune weak ones. + // It means we can only make maybe a couple of non-optimal steps, so we might get stuck in a local maximum. + next_tracks.truncate(3_usize.pow(8)); tracks = next_tracks.clone(); next_tracks = Vec::new();// prune? keep the top N scorers? } diff --git a/src/main.rs b/src/main.rs index afee780..bdbb41e 100644 --- a/src/main.rs +++ b/src/main.rs @@ -2,38 +2,38 @@ #![feature(iterator_try_collect)] use std::fs; -mod day1; -mod day2; -mod day3; -mod day4; -mod day5; -mod day6; -mod day7; -mod day8; -mod day9; -mod day10; -mod day11; -mod day12; -mod day13; -mod day14; -mod day15; +// mod day1; +// mod day2; +// mod day3; +// mod day4; +// mod day5; +// mod day6; +// mod day7; +// mod day8; +// mod day9; +// mod day10; +// mod day11; +// 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!")); - day2::run(fs::read_to_string("input/day2.txt").expect("Failed to read input file!")); - day3::run(fs::read_to_string("input/day3.txt").expect("Failed to read input file!")); - day4::run(fs::read_to_string("input/day4.txt").expect("Failed to read input file!")); - day5::run(fs::read_to_string("input/day5.txt").expect("Failed to read input file!")); - day6::run(fs::read_to_string("input/day6.txt").expect("Failed to read input file!")); - day7::run(fs::read_to_string("input/day7.txt").expect("Failed to read input file!")); - day8::run(fs::read_to_string("input/day8.txt").expect("Failed to read input file!")); - day9::run(fs::read_to_string("input/day9.txt").expect("Failed to read input file!")); - day10::run(fs::read_to_string("input/day10.txt").expect("Failed to read input file!")); - day11::run(fs::read_to_string("input/day11.txt").expect("Failed to read input file!")); - day12::run(fs::read_to_string("input/day12.txt").expect("Failed to read input file!")); - 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!")); + // day1::run(fs::read_to_string("input/day1.txt").expect("Failed to read input file!")); + // day2::run(fs::read_to_string("input/day2.txt").expect("Failed to read input file!")); + // day3::run(fs::read_to_string("input/day3.txt").expect("Failed to read input file!")); + // day4::run(fs::read_to_string("input/day4.txt").expect("Failed to read input file!")); + // day5::run(fs::read_to_string("input/day5.txt").expect("Failed to read input file!")); + // day6::run(fs::read_to_string("input/day6.txt").expect("Failed to read input file!")); + // day7::run(fs::read_to_string("input/day7.txt").expect("Failed to read input file!")); + // day8::run(fs::read_to_string("input/day8.txt").expect("Failed to read input file!")); + // day9::run(fs::read_to_string("input/day9.txt").expect("Failed to read input file!")); + // day10::run(fs::read_to_string("input/day10.txt").expect("Failed to read input file!")); + // day11::run(fs::read_to_string("input/day11.txt").expect("Failed to read input file!")); + // day12::run(fs::read_to_string("input/day12.txt").expect("Failed to read input file!")); + // 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!")); } |