adventofcode

commit

6e2cb42f5ff9d20f5a0f60752f6d322a431ad240

parent

13b6e228cb0478e633629510657edf65a6a97187

Author

Tobias Bengfort <tobias.bengfort@posteo.de>

Date

2022-12-23 10:32

perf: use HashMap for proposals

Diffstat

1 files changed, 10 insertions, 6 deletions

diff --git a/2022/23/solution.rs b/2022/23/solution.rs

@@ -1,4 +1,5 @@
    1     1 use std::collections::HashSet;
   -1     2 use std::collections::HashMap;
    2     3 
    3     4 #[path = "../lib.rs"] mod lib;
    4     5 
@@ -60,17 +61,20 @@ fn propose_move(elves: &HashSet<(i64, i64)>, x: i64, y: i64, offset: usize) -> (
   60    61 }
   61    62 
   62    63 fn do_round(elves: &mut Vec<(i64, i64)>, offset: usize) -> bool {
   63    -1     let mut proposed = vec![];
   -1    64     let mut proposals: HashMap<(i64, i64), Vec<usize>> = HashMap::new();
   64    65     let mut changed = false;
   65    66 
   66    67     let elves_set = elves.iter().map(|a| *a).collect();
   67    -1     for (x, y) in elves.iter() {
   68    -1         proposed.push(propose_move(&elves_set, *x, *y, offset));
   -1    68     for i in 0..elves.len() {
   -1    69         let (x, y) = elves[i];
   -1    70         let proposal = propose_move(&elves_set, x, y, offset);
   -1    71         proposals.entry(proposal).and_modify(|v| v.push(i)).or_insert(vec![i]);
   69    72     }
   70    73 
   71    -1     for i in 0..elves.len() {
   72    -1         if proposed[i] != elves[i] && proposed.iter().filter(|(x2, y2)| (*x2, *y2) == proposed[i]).count() == 1 {
   73    -1             elves[i] = proposed[i];
   -1    74     for (pos, is) in proposals.iter() {
   -1    75         let i = is[0];
   -1    76         if is.len() == 1 && elves[i] != *pos {
   -1    77             elves[i] = *pos;
   74    78             changed = true;
   75    79         }
   76    80     }