adventofcode

commit

30a31e74f232471c33812cbc4bd989fff377aadd

parent

a59a12207c481260b0a184f37ec8fd4077114217

Author

Tobias Bengfort <tobias.bengfort@posteo.de>

Date

2023-12-18 14:38

refactor: do not include steps in key space

Diffstat

1 files changed, 31 insertions, 36 deletions

diff --git a/2023/17/solution.rs b/2023/17/solution.rs

@@ -13,26 +13,20 @@ enum Dir {
   13    13 }
   14    14 
   15    15 impl Dir {
   16    -1     fn inverse(&self) -> Self {
   -1    16     fn apply(&self, x: usize, y: usize, k: usize, n: usize) -> Option<(usize, usize)> {
   17    17         return match self {
   18    -1             Dir::Left => Dir::Right,
   19    -1             Dir::Right => Dir::Left,
   20    -1             Dir::Up => Dir::Down,
   21    -1             Dir::Down => Dir::Up,
   -1    18             Dir::Left => if x >= k { Some((x - k, y)) } else { None }
   -1    19             Dir::Right => if x + k < n { Some((x + k, y)) } else { None }
   -1    20             Dir::Up => if y >= k { Some((x, y - k)) } else { None }
   -1    21             Dir::Down => if y + k < n { Some((x, y + k)) } else { None }
   22    22         };
   23    23     }
   24    24 
   25    -1     fn apply(&self, x: usize, y: usize, n: usize) -> Option<(usize, usize)> {
   -1    25     fn sides(&self) -> [Self; 2] {
   26    26         return match self {
   27    -1             Dir::Left => if x > 0 { Some((x - 1, y)) } else { None }
   28    -1             Dir::Right => if x + 1 < n { Some((x + 1, y)) } else { None }
   29    -1             Dir::Up => if y > 0 { Some((x, y - 1)) } else { None }
   30    -1             Dir::Down => if y + 1 < n { Some((x, y + 1)) } else { None }
   31    -1         };
   32    -1     }
   33    -1 
   34    -1     fn iter() -> [Self; 4] {
   35    -1         return [Dir::Left, Dir::Right, Dir::Up, Dir::Down];
   -1    27             Dir::Left | Dir::Right => [Dir::Up, Dir::Down],
   -1    28             Dir::Up | Dir::Down => [Dir::Left, Dir::Right],
   -1    29         }
   36    30     }
   37    31 }
   38    32 
@@ -52,30 +46,31 @@ fn find_path(map: &Vec<Vec<u32>>, min_steps: usize, max_steps: usize) -> u32 {
   52    46     let mut min = HashMap::new();
   53    47     let mut result = u32::MAX;
   54    48 
   55    -1     min.insert((0, 0, Dir::Right, 1), 0);
   56    -1     queue.push_back((0, 0, Dir::Right, 1));
   -1    49     min.insert((0, 0, Dir::Right), 0);
   -1    50     queue.push_back((0, 0, Dir::Right));
   57    51 
   58    -1     min.insert((0, 0, Dir::Down, 1), 0);
   59    -1     queue.push_back((0, 0, Dir::Down, 1));
   -1    52     min.insert((0, 0, Dir::Down), 0);
   -1    53     queue.push_back((0, 0, Dir::Down));
   60    54 
   61    -1     while let Some((y, x, dir, steps)) = queue.pop_front() {
   62    -1         let v = *min.get(&(y, x, dir, steps)).unwrap_or(&u32::MAX);
   63    -1         if (x, y) == (n - 1, n - 1) && steps >= min_steps {
   64    -1             result = result.min(v);
   -1    55     while let Some((y, x, dir)) = queue.pop_front() {
   -1    56         let value = *min.get(&(y, x, dir)).unwrap_or(&u32::MAX);
   -1    57         if (x, y) == (n - 1, n - 1) {
   -1    58             result = result.min(value);
   65    59         }
   66    -1         for ndir in Dir::iter() {
   67    -1             if (ndir == dir && steps >= max_steps)
   68    -1                 || ndir == dir.inverse()
   69    -1                 || (ndir != dir && steps < min_steps)
   70    -1             {
   71    -1                 continue;
   72    -1             }
   73    -1             if let Some((nx, ny)) = ndir.apply(x, y, n) {
   74    -1                 let s = if ndir == dir { steps + 1 } else { 1 };
   75    -1                 let key = (ny, nx, ndir, s);
   76    -1                 if v + map[ny][nx] < *min.get(&key).unwrap_or(&u32::MAX) {
   77    -1                     min.insert(key, v + map[ny][nx]);
   78    -1                     queue.push_back(key);
   -1    60         for ndir in dir.sides() {
   -1    61             let mut new_value = value;
   -1    62             for k in 1..=max_steps {
   -1    63                 if let Some((nx, ny)) = ndir.apply(x, y, k, n) {
   -1    64                     new_value += map[ny][nx];
   -1    65                     if k >= min_steps {
   -1    66                         let key = (ny, nx, ndir);
   -1    67                         if new_value < *min.get(&key).unwrap_or(&u32::MAX) {
   -1    68                             min.insert(key, new_value);
   -1    69                             queue.push_back(key);
   -1    70                         }
   -1    71                     }
   -1    72                 } else {
   -1    73                     break;
   79    74                 }
   80    75             }
   81    76         }