- commit
- 49a3c4fc04ae371ef287b40c059b6b96d769e8ae
- parent
- 04348834a32d318307642ed814c794f007ecd8b5
- Author
- Tobias Bengfort <tobias.bengfort@posteo.de>
- Date
- 2022-12-16 12:05
part2
Diffstat
| M | 2022/16/solution.rs | 162 | +++++++++++++++++++++++++++++++++++++++++++++++++++---------- |
1 files changed, 136 insertions, 26 deletions
diff --git a/2022/16/solution.rs b/2022/16/solution.rs
@@ -10,9 +10,11 @@ struct Valve {
10 10 }
11 11
12 12 struct QueueEntry {
13 -1 pos: String,
-1 13 pos1: String,
-1 14 pos2: String,
-1 15 time1: u64,
-1 16 time2: u64,
14 17 open: HashSet<String>,
15 -1 time: u64,
16 18 pressure: u64,
17 19 potential: u64,
18 20 }
@@ -41,7 +43,19 @@ fn get_input() -> HashMap<String, Valve> {
41 43 return map;
42 44 }
43 45
44 -1 fn make_entry(valves: &HashMap<String, Valve>, pos: String, open: HashSet<String>, time: u64, pressure: u64) -> QueueEntry {
-1 46 fn make_entry(
-1 47 valves: &HashMap<String, Valve>,
-1 48 pos1: String,
-1 49 pos2: String,
-1 50 time1: u64,
-1 51 time2: u64,
-1 52 open: HashSet<String>,
-1 53 pressure: u64,
-1 54 ) -> QueueEntry {
-1 55 let min_distance = valves.values().map(|valve|
-1 56 valve.tunnels.values().min().unwrap()
-1 57 ).min().unwrap();
-1 58
45 59 let mut rates = valves.iter()
46 60 .filter(|(key, _valve)| !open.contains(*key))
47 61 .map(|(_key, valve)| valve.rate)
@@ -50,28 +64,47 @@ fn make_entry(valves: &HashMap<String, Valve>, pos: String, open: HashSet<String
50 64 rates.reverse();
51 65
52 66 let mut potential = pressure;
53 -1 let mut i = 0;
54 -1 let mut t = time;
55 -1 while i < rates.len() && t > 1 {
56 -1 potential += rates[i] * (t - 1);
57 -1 i += 1;
58 -1 t -= 2;
-1 67 let mut t = (time1, time2);
-1 68 for i in 0..rates.len() {
-1 69 let t1 = t.0.max(t.1);
-1 70 let t2 = t.0.min(t.1);
-1 71 potential += rates[i] * (t1 - 1);
-1 72 if t1 > min_distance + 1 {
-1 73 t = (t1 - min_distance - 1, t2);
-1 74 } else {
-1 75 break;
-1 76 }
59 77 }
60 78
61 -1 return QueueEntry { pos, open, time, pressure, potential };
-1 79 // swap so that the pos1 always refers to the one behind on time
-1 80 let swap = time1 < time2;
-1 81 let (time1, time2) = if swap { (time2, time1) } else { (time1, time2) };
-1 82 let (pos1, pos2) = if swap { (pos2, pos1) } else { (pos1, pos2) };
-1 83
-1 84 return QueueEntry { pos1, pos2, time1, time2, open, pressure, potential };
62 85 }
63 86
64 87 fn get_next(queue: &mut Vec<QueueEntry>) -> Option<QueueEntry> {
-1 88 // from experiments this seems to be a good way to pick the next entry
65 89 // let (i, _) = queue.iter()
66 90 // .enumerate()
67 -1 // .max_by_key(|(_, entry)| entry.pressure)?;
-1 91 // .max_by_key(|(_, entry)| entry.potential + entry.pressure)?;
68 92 // return Some(queue.remove(i));
-1 93
69 94 return queue.pop();
70 95 }
71 96
72 -1 fn part1(valves: &HashMap<String, Valve>) -> u64 {
-1 97 fn part1(valves: &HashMap<String, Valve>, time: u64) -> u64 {
73 98 let mut max_pressure = 0;
74 -1 let mut queue = vec![make_entry(valves, "AA".to_string(), HashSet::new(), 30, 0)];
-1 99 let mut queue = vec![make_entry(
-1 100 valves,
-1 101 "AA".to_string(),
-1 102 "AA".to_string(),
-1 103 time,
-1 104 0,
-1 105 HashSet::new(),
-1 106 0,
-1 107 )];
75 108
76 109 while let Some(entry) = get_next(&mut queue) {
77 110 // PERF: stop early if there is no way to reach max_pressure
@@ -79,22 +112,96 @@ fn part1(valves: &HashMap<String, Valve>) -> u64 {
79 112 continue;
80 113 }
81 114
82 -1 println!("{} {} {} {} {} {}", entry.pos, entry.time, entry.pressure, entry.potential, max_pressure, queue.len());
-1 115 if !entry.open.contains(&entry.pos1) {
-1 116 let pressure = entry.pressure + valves[&entry.pos1].rate * (entry.time1 - 1);
-1 117 if pressure > max_pressure {
-1 118 max_pressure = pressure;
-1 119 }
-1 120
-1 121 let mut open = entry.open.clone();
-1 122 open.insert(entry.pos1.clone());
-1 123 if entry.time1 > 1 {
-1 124 queue.push(make_entry(
-1 125 valves,
-1 126 entry.pos1.clone(),
-1 127 entry.pos2.clone(),
-1 128 entry.time1 - 1,
-1 129 entry.time2,
-1 130 open,
-1 131 pressure,
-1 132 ));
-1 133 }
-1 134 }
-1 135
-1 136 for (name, len) in valves[&entry.pos1].tunnels.iter() {
-1 137 if entry.time1 > *len {
-1 138 queue.push(make_entry(
-1 139 valves,
-1 140 name.clone(),
-1 141 entry.pos2.clone(),
-1 142 entry.time1 - len,
-1 143 entry.time2,
-1 144 entry.open.clone(),
-1 145 entry.pressure,
-1 146 ));
-1 147 }
-1 148 }
-1 149 }
83 150
84 -1 if !entry.open.contains(&entry.pos) && valves[&entry.pos].rate > 0 {
85 -1 let pressure = entry.pressure + valves[&entry.pos].rate * (entry.time - 1);
-1 151 return max_pressure;
-1 152 }
-1 153
-1 154 fn part2(valves: &HashMap<String, Valve>, time: u64) -> u64 {
-1 155 let mut max_pressure = 0;
-1 156 let mut queue = vec![make_entry(
-1 157 valves,
-1 158 "AA".to_string(),
-1 159 "AA".to_string(),
-1 160 time,
-1 161 time,
-1 162 HashSet::new(),
-1 163 0,
-1 164 )];
-1 165
-1 166 while let Some(entry) = get_next(&mut queue) {
-1 167 // PERF: stop early if there is no way to reach max_pressure
-1 168 if entry.potential <= max_pressure {
-1 169 continue;
-1 170 }
-1 171
-1 172 if !entry.open.contains(&entry.pos1) {
-1 173 let pressure = entry.pressure + valves[&entry.pos1].rate * (entry.time1 - 1);
86 174 if pressure > max_pressure {
87 175 max_pressure = pressure;
-1 176 println!("{} {} {}", entry.time1, max_pressure, queue.len());
88 177 }
89 178
90 179 let mut open = entry.open.clone();
91 -1 open.insert(entry.pos.clone());
92 -1 queue.push(make_entry(valves, entry.pos.clone(), open, entry.time - 1, pressure));
-1 180 open.insert(entry.pos1.clone());
-1 181 if entry.time1 > 1 {
-1 182 queue.push(make_entry(
-1 183 valves,
-1 184 entry.pos1.clone(),
-1 185 entry.pos2.clone(),
-1 186 entry.time1 - 1,
-1 187 entry.time2,
-1 188 open,
-1 189 pressure,
-1 190 ));
-1 191 }
93 192 }
94 193
95 -1 for (name, len) in valves[&entry.pos].tunnels.iter() {
96 -1 if entry.time >= *len {
97 -1 queue.push(make_entry(valves, name.clone(), entry.open.clone(), entry.time - len, entry.pressure));
-1 194 for (name, len) in valves[&entry.pos1].tunnels.iter() {
-1 195 if entry.time1 > *len {
-1 196 queue.push(make_entry(
-1 197 valves,
-1 198 name.clone(),
-1 199 entry.pos2.clone(),
-1 200 entry.time1 - len,
-1 201 entry.time2,
-1 202 entry.open.clone(),
-1 203 entry.pressure,
-1 204 ));
98 205 }
99 206 }
100 207 }
@@ -126,9 +233,7 @@ fn optimize_tunnels(valves: &HashMap<String, Valve>, name: &String, path: &Vec<S
126 233 return tunnels;
127 234 }
128 235
129 -1 fn main() {
130 -1 let valves = get_input();
131 -1
-1 236 fn optimize_graph(valves: &HashMap<String, Valve>) -> HashMap<String, Valve> {
132 237 let mut optimized = HashMap::new();
133 238 for (name, valve) in valves.iter() {
134 239 if valve.rate > 0 || name == "AA" {
@@ -138,7 +243,12 @@ fn main() {
138 243 });
139 244 }
140 245 }
-1 246 return optimized;
-1 247 }
141 248
142 -1 println!("part1: {}", part1(&optimized));
143 -1 println!("part2: {}", 0);
-1 249 fn main() {
-1 250 let valves = get_input();
-1 251 let optimized = optimize_graph(&valves);
-1 252 println!("part1: {}", part1(&optimized, 30));
-1 253 println!("part2: {}", part2(&optimized, 26));
144 254 }