summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorMartin Ashby <martin@ashbysoft.com>2022-12-17 22:06:56 +0000
committerMartin Ashby <martin@ashbysoft.com>2022-12-17 22:06:56 +0000
commit425c3a241fb9b3a13ef52ccf300dc6f214cb4520 (patch)
tree2db1ed0284f0524c94e8d92cad48c4902ec8e4ca /src
parent627266fdf043443de2d45783b800563299d6a899 (diff)
downloadaoc2022-425c3a241fb9b3a13ef52ccf300dc6f214cb4520.tar.gz
aoc2022-425c3a241fb9b3a13ef52ccf300dc6f214cb4520.tar.bz2
aoc2022-425c3a241fb9b3a13ef52ccf300dc6f214cb4520.tar.xz
aoc2022-425c3a241fb9b3a13ef52ccf300dc6f214cb4520.zip
day16 part 1
Diffstat (limited to 'src')
-rw-r--r--src/day16.rs67
-rw-r--r--src/main.rs2
2 files changed, 69 insertions, 0 deletions
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!"));
}