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