summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorMartin Ashby <martin@ashbysoft.com>2022-12-17 22:49:03 +0000
committerMartin Ashby <martin@ashbysoft.com>2022-12-17 22:49:03 +0000
commit2335c9d7580ac5cf7c0169910684cb974bd4d4bd (patch)
treee44747e35a0ad19191b158c5852d67843c3c4146
parent425c3a241fb9b3a13ef52ccf300dc6f214cb4520 (diff)
downloadaoc2022-2335c9d7580ac5cf7c0169910684cb974bd4d4bd.tar.gz
aoc2022-2335c9d7580ac5cf7c0169910684cb974bd4d4bd.tar.bz2
aoc2022-2335c9d7580ac5cf7c0169910684cb974bd4d4bd.tar.xz
aoc2022-2335c9d7580ac5cf7c0169910684cb974bd4d4bd.zip
day16 pt2
-rw-r--r--src/day16.rs83
-rw-r--r--src/main.rs60
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!"));
}