adventofcode

commit

9b77bc242ba210404b4b4b43bfa86b1b5d241933

parent

6e2cb42f5ff9d20f5a0f60752f6d322a431ad240

Author

Tobias Bengfort <tobias.bengfort@posteo.de>

Date

2022-12-23 10:36

perf: use HashSet for elves everywhere

Diffstat

1 files changed, 16 insertions, 14 deletions

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

@@ -7,12 +7,12 @@ enum Dir { North, East, South, West }
    7     7 
    8     8 const DIRS: [Dir; 4] = [Dir::North, Dir::South, Dir::West, Dir::East];
    9     9 
   10    -1 fn get_input() -> Vec<(i64, i64)> {
   11    -1     let mut elves = vec![];
   -1    10 fn get_input() -> HashSet<(i64, i64)> {
   -1    11     let mut elves = HashSet::new();
   12    12     for (y, line) in lib::iter_input().enumerate() {
   13    13         for (x, c) in line.chars().enumerate() {
   14    14             if c == '#' {
   15    -1                 elves.push((x as i64, y as i64));
   -1    15                 elves.insert((x as i64, y as i64));
   16    16             }
   17    17         }
   18    18     }
@@ -60,21 +60,23 @@ fn propose_move(elves: &HashSet<(i64, i64)>, x: i64, y: i64, offset: usize) -> (
   60    60     return (x, y);
   61    61 }
   62    62 
   63    -1 fn do_round(elves: &mut Vec<(i64, i64)>, offset: usize) -> bool {
   64    -1     let mut proposals: HashMap<(i64, i64), Vec<usize>> = HashMap::new();
   -1    63 fn do_round(elves: &mut HashSet<(i64, i64)>, offset: usize) -> bool {
   -1    64     let mut proposals: HashMap<(i64, i64), Vec<(i64, i64)>> = HashMap::new();
   65    65     let mut changed = false;
   66    66 
   67    -1     let elves_set = elves.iter().map(|a| *a).collect();
   68    -1     for i in 0..elves.len() {
   69    -1         let (x, y) = elves[i];
   70    -1         let proposal = propose_move(&elves_set, x, y, offset);
   71    -1         proposals.entry(proposal).and_modify(|v| v.push(i)).or_insert(vec![i]);
   -1    67     for pos in elves.iter() {
   -1    68         let proposal = propose_move(elves, pos.0, pos.1, offset);
   -1    69         if proposal != *pos {
   -1    70             proposals.entry(proposal)
   -1    71                 .and_modify(|v| v.push(*pos))
   -1    72                 .or_insert(vec![*pos]);
   -1    73         }
   72    74     }
   73    75 
   74    -1     for (pos, is) in proposals.iter() {
   75    -1         let i = is[0];
   76    -1         if is.len() == 1 && elves[i] != *pos {
   77    -1             elves[i] = *pos;
   -1    76     for (new, olds) in proposals.iter() {
   -1    77         if olds.len() == 1 {
   -1    78             elves.remove(&olds[0]);
   -1    79             elves.insert(*new);
   78    80             changed = true;
   79    81         }
   80    82     }