adventofcode

commit

360f969eb0b3ca9dab459d3c4733cf0362a1ea00

parent

183954410f86a50b9f23affc7f3e3d79f8337802

Author

Tobias Bengfort <tobias.bengfort@posteo.de>

Date

2021-12-23 16:14

store estimates in queue

Diffstat

2 files changed, 12 insertions, 18 deletions

diff --git a/2021/23/part1.rs b/2021/23/part1.rs

@@ -211,26 +211,23 @@ fn main() {
  211   211     let (initial, target) = get_input();
  212   212     let mut queue = vec![];
  213   213     let mut energies = HashMap::new();
  214    -1     let mut estimates = HashMap::new();
  215   214 
  216    -1     queue.push(initial);
   -1   215     queue.push((initial, 0));
  217   216     energies.insert(initial, 0);
  218    -1     estimates.insert(initial, 0);
  219   217 
  220   218     while queue.len() > 0 {
  221    -1         let map = queue.pop().unwrap();
   -1   219         let (map, _) = queue.pop().unwrap();
  222   220         for (m, e_new) in legal_steps(&map) {
  223   221             let e = e_new + energies.get(&map).unwrap();
  224   222             let ee = e + estimate(&m);
  225   223             if better(e, energies.get(&m)) && better(ee, energies.get(&target)) {
  226   224                 energies.insert(m, e);
  227    -1                 estimates.insert(m, ee);
  228   225                 if m == target {
  229    -1                     queue = queue.into_iter().filter(|map| *estimates.get(map).unwrap() < e).collect();
   -1   226                     queue = queue.into_iter().filter(|(_map, ee_old)| *ee_old < e).collect();
  230   227                 } else {
  231    -1                     match queue.binary_search_by_key(&ee, |map| -estimates.get(map).unwrap()) {
  232    -1                         Ok(i) => queue.insert(i, m),
  233    -1                         Err(i) => queue.insert(i, m),
   -1   228                     match queue.binary_search_by_key(&ee, |(_map, ee_old)| -ee_old) {
   -1   229                         Ok(i) => queue.insert(i, (m, ee)),
   -1   230                         Err(i) => queue.insert(i, (m, ee)),
  234   231                     }
  235   232                 }
  236   233             }

diff --git a/2021/23/part2.rs b/2021/23/part2.rs

@@ -229,26 +229,23 @@ fn main() {
  229   229     let (initial, target) = get_input();
  230   230     let mut queue = vec![];
  231   231     let mut energies = HashMap::new();
  232    -1     let mut estimates = HashMap::new();
  233   232 
  234    -1     queue.push(initial);
   -1   233     queue.push((initial, 0));
  235   234     energies.insert(initial, 0);
  236    -1     estimates.insert(initial, 0);
  237   235 
  238   236     while queue.len() > 0 {
  239    -1         let map = queue.pop().unwrap();
   -1   237         let (map, _) = queue.pop().unwrap();
  240   238         for (m, e_new) in legal_steps(&map) {
  241   239             let e = e_new + energies.get(&map).unwrap();
  242   240             let ee = e + estimate(&m);
  243   241             if better(e, energies.get(&m)) && better(ee, energies.get(&target)) {
  244   242                 energies.insert(m, e);
  245    -1                 estimates.insert(m, ee);
  246   243                 if m == target {
  247    -1                     queue = queue.into_iter().filter(|map| *estimates.get(map).unwrap() < e).collect();
   -1   244                     queue = queue.into_iter().filter(|(_map, ee_old)| *ee_old < e).collect();
  248   245                 } else {
  249    -1                     match queue.binary_search_by_key(&ee, |map| -estimates.get(map).unwrap()) {
  250    -1                         Ok(i) => queue.insert(i, m),
  251    -1                         Err(i) => queue.insert(i, m),
   -1   246                     match queue.binary_search_by_key(&ee, |(_map, ee_old)| -ee_old) {
   -1   247                         Ok(i) => queue.insert(i, (m, ee)),
   -1   248                         Err(i) => queue.insert(i, (m, ee)),
  252   249                     }
  253   250                 }
  254   251             }