day16.rs (5320B)
1 use std::collections::HashMap; 2 3 use regex::Regex; 4 5 #[derive(Debug,Clone)] 6 struct Track { 7 my_current_valve: String, 8 elephant_current_valve: String, 9 final_pressure_release: u32, 10 valves_opened: Vec<String>, 11 debug: String, 12 } 13 #[derive(Debug)] 14 struct Valve { 15 flow_rate: u32, 16 next_valves: Vec<String>, 17 } 18 19 #[derive(PartialEq)] 20 enum Move {Open, Move(String)} 21 22 fn poss_moves(valves: &HashMap<String,Valve>, current_valve: &String, open_valves: &Vec<String>) -> Vec<Move> { 23 let mut res = vec![]; 24 let cv = &valves[current_valve]; 25 // try open the valve (if it's got any flow, and if it's not already open) 26 if cv.flow_rate > 0 && !open_valves.contains(current_valve) { 27 res.push(Move::Open); 28 } 29 // Alt, try moving to another valve 30 for nv in &cv.next_valves { 31 res.push(Move::Move(nv.clone())); 32 } 33 res 34 } 35 36 pub fn run(input: String) { 37 let re = Regex::new(r"^Valve ([A-Z]+) has flow rate=(\d+); tunnels? leads? to valves? ([A-Z, ]+)$").unwrap(); 38 let valves: HashMap<String,Valve> = input.lines().map(|line| { 39 let cap = re.captures(line).expect(format!("line didn't match regex! {}", line).as_str()); 40 let name = cap[1].to_string(); 41 let flow_rate: u32 = cap[2].parse().expect("flow rate wasn't a u32!"); 42 let next_valves: Vec<String> = cap[3].split(", ").map(|x| { x.to_string() }).collect(); 43 (name, Valve{flow_rate,next_valves}) 44 }).collect(); 45 // How to do this one? 46 // I think... tracking all options? It's basically a tree right? 47 // max depth of the tree is 30,corresponding to minutes 48 // at each depth, options are -> open valve OR move to another valve 49 // and at each depth we have a score, and a list of already-opened valves 50 51 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()}; 52 let mut tracks: Vec<Track> = vec![root]; 53 let mut next_tracks: Vec<Track> = Vec::new(); 54 //let total_mins: u32 = 30; 55 let total_mins: u32 = 26; 56 for minute in 0..=total_mins { 57 let mins_remaining = total_mins - minute; 58 for track in &tracks { 59 // Cartesian the next moves by me and the elephant 60 // For each in the product, calculate changed final_pressure_release (if we opened a valve(s)) 61 // And extend the debug string! 62 let my_poss_moves = poss_moves(&valves, &track.my_current_valve, &track.valves_opened); 63 for mm in my_poss_moves { 64 let mut vo = track.valves_opened.clone(); 65 if mm == Move::Open { 66 vo.push(track.my_current_valve.clone()); // Care, we don't try to open the same valve at once. 67 } 68 let e_poss_moves = poss_moves(&valves, &track.elephant_current_valve, &vo); 69 for em in e_poss_moves { 70 let mut nt = track.clone(); 71 nt.debug.push_str(format!("minute {}", minute+1).as_str()); 72 if let Move::Move(nv) = &mm { 73 nt.my_current_valve = nv.clone(); 74 nt.debug.push_str(format!(", I Moved To {}", nv).as_str()); 75 } else { 76 nt.valves_opened.push(track.my_current_valve.clone()); 77 let cv = &valves[&track.my_current_valve]; 78 if mins_remaining > 0 { 79 nt.final_pressure_release += cv.flow_rate * (mins_remaining-1); 80 } 81 nt.debug.push_str(format!(", I Opened {}", track.my_current_valve).as_str()); 82 } 83 if let Move::Move(nv) = &em { 84 nt.elephant_current_valve = nv.clone(); 85 nt.debug.push_str(format!(", Elephant Moved To {}", nv).as_str()); 86 } else { 87 nt.valves_opened.push(track.elephant_current_valve.clone()); 88 let cv = &valves[&track.elephant_current_valve]; 89 if mins_remaining > 0 { 90 nt.final_pressure_release += cv.flow_rate * (mins_remaining-1); 91 } 92 nt.debug.push_str(format!(", Elephant Opened {}", track.elephant_current_valve).as_str()); 93 } 94 nt.debug.push('\n'); 95 next_tracks.push(nt); 96 } 97 } 98 } 99 next_tracks.sort_by(|t1, t2| {t1.final_pressure_release.cmp(&t2.final_pressure_release)}.reverse()); 100 // 3.pow(30) is too many options, just prune weak ones. 101 // It means we can only make maybe a couple of non-optimal steps, so we might get stuck in a local maximum. 102 next_tracks.truncate(3_usize.pow(8)); 103 tracks = next_tracks.clone(); 104 next_tracks = Vec::new();// prune? keep the top N scorers? 105 } 106 // Find the track with the biggest final score 107 let max_track = tracks.iter().max_by(|t1,t2| {t1.final_pressure_release.cmp(&t2.final_pressure_release)}).unwrap(); 108 //let max_pressure_release = tracks.iter().map(|t| {t.final_pressure_release}).max().unwrap(); 109 println!("Day 16: {}", max_track.final_pressure_release); 110 }