- commit
- 7e72b100899e4c9766c2cb5d509a5e2d2d784f35
- parent
- 49a3c4fc04ae371ef287b40c059b6b96d769e8ae
- Author
- Tobias Bengfort <tobias.bengfort@posteo.de>
- Date
- 2022-12-17 10:57
2022-12-16 wip
Diffstat
| M | 2022/16/solution.rs | 70 | ++++++++++++++++++++++++++++++++++++++++++------------------- |
1 files changed, 48 insertions, 22 deletions
diff --git a/2022/16/solution.rs b/2022/16/solution.rs
@@ -45,6 +45,7 @@ fn get_input() -> HashMap<String, Valve> {
45 45
46 46 fn make_entry(
47 47 valves: &HashMap<String, Valve>,
-1 48 min_distance: u64,
48 49 pos1: String,
49 50 pos2: String,
50 51 time1: u64,
@@ -52,10 +53,12 @@ fn make_entry(
52 53 open: HashSet<String>,
53 54 pressure: u64,
54 55 ) -> QueueEntry {
55 -1 let min_distance = valves.values().map(|valve|
56 -1 valve.tunnels.values().min().unwrap()
57 -1 ).min().unwrap();
-1 56 // swap so that the pos1 always refers to the one behind on time
-1 57 let swap = time1 < time2;
-1 58 let (time1, time2) = if swap { (time2, time1) } else { (time1, time2) };
-1 59 let (pos1, pos2) = if swap { (pos2, pos1) } else { (pos1, pos2) };
58 60
-1 61 // calculute upper bound for pressure
59 62 let mut rates = valves.iter()
60 63 .filter(|(key, _valve)| !open.contains(*key))
61 64 .map(|(_key, valve)| valve.rate)
@@ -65,39 +68,44 @@ fn make_entry(
65 68
66 69 let mut potential = pressure;
67 70 let mut t = (time1, time2);
-1 71 let is_open = open.contains(&pos1);
68 72 for i in 0..rates.len() {
69 -1 let t1 = t.0.max(t.1);
70 -1 let t2 = t.0.min(t.1);
71 -1 potential += rates[i] * (t1 - 1);
72 -1 if t1 > min_distance + 1 {
73 -1 t = (t1 - min_distance - 1, t2);
-1 73 if !is_open {
-1 74 potential += rates[i] * (t.0 - 1);
-1 75 }
-1 76 if t.0 > min_distance + 1 {
-1 77 t = (t.0 - min_distance - 1, t.1);
-1 78 if t.0 < t.1 {
-1 79 t = (t.1, t.0);
-1 80 }
74 81 } else {
75 82 break;
76 83 }
-1 84 if is_open {
-1 85 potential += rates[i] * (t.0 - 1);
-1 86 }
77 87 }
78 88
79 -1 // swap so that the pos1 always refers to the one behind on time
80 -1 let swap = time1 < time2;
81 -1 let (time1, time2) = if swap { (time2, time1) } else { (time1, time2) };
82 -1 let (pos1, pos2) = if swap { (pos2, pos1) } else { (pos1, pos2) };
83 -1
84 89 return QueueEntry { pos1, pos2, time1, time2, open, pressure, potential };
85 90 }
86 91
87 92 fn get_next(queue: &mut Vec<QueueEntry>) -> Option<QueueEntry> {
88 93 // from experiments this seems to be a good way to pick the next entry
89 -1 // let (i, _) = queue.iter()
90 -1 // .enumerate()
91 -1 // .max_by_key(|(_, entry)| entry.potential + entry.pressure)?;
92 -1 // return Some(queue.remove(i));
93 -1
94 -1 return queue.pop();
-1 94 let (i, _) = queue.iter()
-1 95 .enumerate()
-1 96 .max_by_key(|(_, entry)| entry.pressure)?;
-1 97 return Some(queue.remove(i));
95 98 }
96 99
97 100 fn part1(valves: &HashMap<String, Valve>, time: u64) -> u64 {
-1 101 let min_distance = *valves.values().map(|valve|
-1 102 valve.tunnels.values().min().unwrap()
-1 103 ).min().unwrap();
-1 104
98 105 let mut max_pressure = 0;
99 106 let mut queue = vec![make_entry(
100 107 valves,
-1 108 min_distance,
101 109 "AA".to_string(),
102 110 "AA".to_string(),
103 111 time,
@@ -123,6 +131,7 @@ fn part1(valves: &HashMap<String, Valve>, time: u64) -> u64 {
123 131 if entry.time1 > 1 {
124 132 queue.push(make_entry(
125 133 valves,
-1 134 min_distance,
126 135 entry.pos1.clone(),
127 136 entry.pos2.clone(),
128 137 entry.time1 - 1,
@@ -137,6 +146,7 @@ fn part1(valves: &HashMap<String, Valve>, time: u64) -> u64 {
137 146 if entry.time1 > *len {
138 147 queue.push(make_entry(
139 148 valves,
-1 149 min_distance,
140 150 name.clone(),
141 151 entry.pos2.clone(),
142 152 entry.time1 - len,
@@ -152,9 +162,14 @@ fn part1(valves: &HashMap<String, Valve>, time: u64) -> u64 {
152 162 }
153 163
154 164 fn part2(valves: &HashMap<String, Valve>, time: u64) -> u64 {
-1 165 let min_distance = *valves.values().map(|valve|
-1 166 valve.tunnels.values().min().unwrap()
-1 167 ).min().unwrap();
-1 168
155 169 let mut max_pressure = 0;
156 170 let mut queue = vec![make_entry(
157 171 valves,
-1 172 min_distance,
158 173 "AA".to_string(),
159 174 "AA".to_string(),
160 175 time,
@@ -169,11 +184,13 @@ fn part2(valves: &HashMap<String, Valve>, time: u64) -> u64 {
169 184 continue;
170 185 }
171 186
-1 187 println!("{} {} {} {} {}", entry.time1, entry.potential, max_pressure, queue.len(), valves.len());
-1 188
172 189 if !entry.open.contains(&entry.pos1) {
173 190 let pressure = entry.pressure + valves[&entry.pos1].rate * (entry.time1 - 1);
174 191 if pressure > max_pressure {
175 192 max_pressure = pressure;
176 -1 println!("{} {} {}", entry.time1, max_pressure, queue.len());
-1 193 // println!("{} {} {}", entry.time1, max_pressure, queue.len());
177 194 }
178 195
179 196 let mut open = entry.open.clone();
@@ -181,6 +198,7 @@ fn part2(valves: &HashMap<String, Valve>, time: u64) -> u64 {
181 198 if entry.time1 > 1 {
182 199 queue.push(make_entry(
183 200 valves,
-1 201 min_distance,
184 202 entry.pos1.clone(),
185 203 entry.pos2.clone(),
186 204 entry.time1 - 1,
@@ -195,6 +213,7 @@ fn part2(valves: &HashMap<String, Valve>, time: u64) -> u64 {
195 213 if entry.time1 > *len {
196 214 queue.push(make_entry(
197 215 valves,
-1 216 min_distance,
198 217 name.clone(),
199 218 entry.pos2.clone(),
200 219 entry.time1 - len,
@@ -249,6 +268,13 @@ fn optimize_graph(valves: &HashMap<String, Valve>) -> HashMap<String, Valve> {
249 268 fn main() {
250 269 let valves = get_input();
251 270 let optimized = optimize_graph(&valves);
252 -1 println!("part1: {}", part1(&optimized, 30));
253 -1 println!("part2: {}", part2(&optimized, 26));
-1 271 println!("graph {{");
-1 272 for (key, valve) in valves.iter() {
-1 273 for other in valve.tunnels.keys() {
-1 274 println!(" \"{} {}\" -- \"{} {}\";", key, valve.rate, other, valves[other].rate);
-1 275 }
-1 276 }
-1 277 println!("}}");
-1 278 // println!("part1: {}", part1(&optimized, 30));
-1 279 // println!("part2: {}", part2(&optimized, 26));
254 280 }