adventofcode

commit

cbe257c3e02a48eb385e627019597f96c05db4e8

parent

466ce8ac1b07f881dcbf43e99744256a4b8e2b03

Author

Tobias Bengfort <tobias.bengfort@posteo.de>

Date

2022-12-23 09:44

perf: use HashSet

Diffstat

1 files changed, 20 insertions, 7 deletions

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

@@ -1,3 +1,5 @@
   -1     1 use std::collections::HashSet;
   -1     2 
    1     3 #[path = "../lib.rs"] mod lib;
    2     4 
    3     5 enum Dir { North, East, South, West }
@@ -16,30 +18,39 @@ fn get_input() -> Vec<(i64, i64)> {
   16    18     return elves;
   17    19 }
   18    20 
   19    -1 fn propose_move(elves: &Vec<(i64, i64)>, x: i64, y: i64, offset: usize) -> (i64, i64) {
   20    -1     if !elves.iter().any(|(x2, y2)| (*x2, *y2) != (x, y) && (*x2 - x).abs() <= 1 && (*y2 - y).abs() <= 1) {
   -1    21 fn propose_move(elves: &HashSet<(i64, i64)>, x: i64, y: i64, offset: usize) -> (i64, i64) {
   -1    22     if !(
   -1    23         elves.contains(&(x, y - 1))
   -1    24         || elves.contains(&(x + 1, y - 1))
   -1    25         || elves.contains(&(x + 1, y))
   -1    26         || elves.contains(&(x + 1, y + 1))
   -1    27         || elves.contains(&(x, y + 1))
   -1    28         || elves.contains(&(x - 1, y + 1))
   -1    29         || elves.contains(&(x - 1, y))
   -1    30         || elves.contains(&(x - 1, y - 1))
   -1    31     ) {
   21    32         return (x, y);
   22    33     }
   23    34 
   24    35     for dir_i in 0..4 {
   25    36         match DIRS[(dir_i + offset) % 4] {
   26    37             Dir::North => {
   27    -1                 if !elves.iter().any(|(x2, y2)| *y2 == y - 1 && (*x2 - x).abs() <= 1) {
   -1    38                 if !(elves.contains(&(x - 1, y - 1)) || elves.contains(&(x, y - 1)) || elves.contains(&(x + 1, y - 1))) {
   28    39                     return (x, y - 1);
   29    40                 }
   30    41             },
   31    42             Dir::East => {
   32    -1                 if !elves.iter().any(|(x2, y2)| *x2 == x + 1 && (*y2 - y).abs() <= 1) {
   -1    43                 if !(elves.contains(&(x + 1, y - 1)) || elves.contains(&(x + 1, y)) || elves.contains(&(x + 1, y + 1))) {
   33    44                     return (x + 1, y);
   34    45                 }
   35    46             },
   36    47             Dir::South => {
   37    -1                 if !elves.iter().any(|(x2, y2)| *y2 == y + 1 && (*x2 - x).abs() <= 1) {
   -1    48                 if !(elves.contains(&(x - 1, y + 1)) || elves.contains(&(x, y + 1)) || elves.contains(&(x + 1, y + 1))) {
   38    49                     return (x, y + 1);
   39    50                 }
   40    51             },
   41    52             Dir::West => {
   42    -1                 if !elves.iter().any(|(x2, y2)| *x2 == x - 1 && (*y2 - y).abs() <= 1) {
   -1    53                 if !(elves.contains(&(x - 1, y - 1)) || elves.contains(&(x - 1, y)) || elves.contains(&(x - 1, y + 1))) {
   43    54                     return (x - 1, y);
   44    55                 }
   45    56             },
@@ -52,8 +63,10 @@ fn do_round(elves: &Vec<(i64, i64)>, offset: usize) -> (Vec<(i64, i64)>, bool) {
   52    63     let mut tmp = vec![];
   53    64     let mut changed = false;
   54    65 
   -1    66     let elves_set = elves.iter().map(|a| *a).collect();
   -1    67 
   55    68     for (x, y) in elves.iter() {
   56    -1         let proposed = propose_move(elves, *x, *y, offset);
   -1    69         let proposed = propose_move(&elves_set, *x, *y, offset);
   57    70         tmp.push(proposed);
   58    71         changed |= proposed != (*x, *y);
   59    72     }