1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
|
use std::collections::HashMap;
use regex::Regex;
#[derive(Debug,Clone)]
struct Track {
my_current_valve: String,
elephant_current_valve: String,
final_pressure_release: u32,
valves_opened: Vec<String>,
debug: String,
}
#[derive(Debug)]
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| {
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 {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 = 26;
for minute in 0..=total_mins {
let mins_remaining = total_mins - minute;
for track in &tracks {
// 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);
}
}
}
next_tracks.sort_by(|t1, t2| {t1.final_pressure_release.cmp(&t2.final_pressure_release)}.reverse());
// 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?
}
// 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);
}
|
