adventofcode

commit

216f857e28a885401fd3a7f72b4995efcc4a4e03

parent

afb9f7d85386897979a9d5b4ef5144ae967a13bb

Author

Tobias Bengfort <tobias.bengfort@posteo.de>

Date

2022-12-25 17:06

2022-12-24: much faster version

inspired by https://github.com/Kiraffi/aoc2022/blob/main/day24/src/main.rs

Diffstat

1 files changed, 54 insertions, 101 deletions

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

@@ -1,15 +1,10 @@
    1    -1 use std::collections::HashSet;
    2    -1 use std::collections::binary_heap::BinaryHeap;
    3    -1 use std::cmp::Reverse;
    4    -1 
    5     1 #[path = "../lib.rs"] mod lib;
    6     2 
    7    -1 enum Dir { Up, Right, Down, Left }
    8    -1 
    9     3 struct Blizzard {
   10    -1     x0: usize,
   11    -1     y0: usize,
   12    -1     dir: Dir,
   -1     4     up: u128,
   -1     5     right: u128,
   -1     6     down: u128,
   -1     7     left: u128,
   13     8 }
   14     9 
   15    10 struct Map {
@@ -18,119 +13,77 @@ struct Map {
   18    13     blizzards: Vec<Blizzard>,
   19    14 }
   20    15 
   21    -1 fn abs_diff(a: usize, b: usize) -> usize {
   22    -1     return a.max(b) - a.min(b);
   23    -1 }
   24    -1 
   25    16 fn get_input() -> Map {
   26    17     let mut blizzards = vec![];
   27    -1     let mut max_x = 0;
   28    -1     let mut max_y = 0;
   -1    18     let mut line_len = 0;
   -1    19 
   -1    20     for (y, line) in lib::iter_input().skip(1).enumerate() {
   -1    21         line_len = line.len();
   -1    22         blizzards.push(Blizzard {
   -1    23             up: 0,
   -1    24             right: 0,
   -1    25             down: 0,
   -1    26             left: 0,
   -1    27         });
   29    28 
   30    -1     for (y, line) in lib::iter_input().enumerate() {
   31    -1         max_y = y;
   32    29         for (x, c) in line.chars().enumerate() {
   33    -1             max_x = x;
   34    30             match c {
   35    -1                 '.' => {},
   -1    31                 '^' => blizzards[y].up |= 1 << (x - 1),
   -1    32                 '>' => blizzards[y].right |= 1 << (x - 1),
   -1    33                 'v' => blizzards[y].down |= 1 << (x - 1),
   -1    34                 '<' => blizzards[y].left |= 1 << (x - 1),
   36    35                 '#' => {},
   37    -1                 '^' => {
   38    -1                     blizzards.push(Blizzard { x0: x - 1, y0: y - 1, dir: Dir::Up });
   39    -1                 },
   40    -1                 '>' => {
   41    -1                     blizzards.push(Blizzard { x0: x - 1, y0: y - 1, dir: Dir::Right });
   42    -1                 },
   43    -1                 'v' => {
   44    -1                     blizzards.push(Blizzard { x0: x - 1, y0: y - 1, dir: Dir::Down });
   45    -1                 },
   46    -1                 '<' => {
   47    -1                     blizzards.push(Blizzard { x0: x - 1, y0: y - 1, dir: Dir::Left });
   48    -1                 },
   -1    36                 '.' => {},
   49    37                 _ => unreachable!(),
   50    38             }
   51    39         }
   52    40     }
   53    41 
   -1    42     blizzards.pop();
   -1    43 
   54    44     return Map {
   55    -1         width: max_x - 1,
   56    -1         height: max_y - 1,
   -1    45         width: line_len - 2,
   -1    46         height: blizzards.len(),
   57    47         blizzards: blizzards,
   58    48     };
   59    49 }
   60    50 
   61    -1 fn is_blocked(map: &Map, x: usize, y: usize, i: usize) -> bool {
   62    -1     return map.blizzards.iter().any(|blizzard| match blizzard.dir {
   63    -1         Dir::Up => x == blizzard.x0 && y == (blizzard.y0 + (map.height - 1) * i) % map.height,
   64    -1         Dir::Right => y == blizzard.y0 && x == (blizzard.x0 + i) % map.width,
   65    -1         Dir::Down => x == blizzard.x0 && y == (blizzard.y0 + i) % map.height,
   66    -1         Dir::Left => y == blizzard.y0 && x == (blizzard.x0 + (map.width - 1) * i) % map.width,
   67    -1     });
   -1    51 fn shift(i: u128, n: usize, width: usize) -> u128 {
   -1    52     let _n = n % width;
   -1    53     return (i >> _n) | (i << (width - _n));
   68    54 }
   69    55 
   70    56 fn find_path(map: &Map, start: (usize, usize), end: (usize, usize), offset: usize) -> usize {
   71    -1     let mut best_i = usize::MAX - 1;
   72    -1     let mut seen = HashSet::new();
   73    -1     let mut queue = BinaryHeap::new();
   74    -1     queue.push((
   75    -1         Reverse(usize::MAX - 2),
   76    -1         usize::MAX,
   77    -1         usize::MAX,
   78    -1         offset,
   79    -1     ));
   80    -1     let mut k = 0;
   81    -1 
   82    -1     while let Some((Reverse(min_i), x, y, i)) = queue.pop() {
   83    -1         if min_i >= best_i {
   84    -1             // for some reason, continue is faster than break/return
   85    -1             continue;
   86    -1         }
   87    -1 
   88    -1         if seen.contains(&(x, y, i)) {
   89    -1             continue;
   90    -1         } else {
   91    -1             seen.insert((x, y, i));
   92    -1         }
   93    -1 
   94    -1         if is_blocked(map, x, y, i) {
   95    -1             continue;
   96    -1         }
   97    -1 
   98    -1         if x == end.0 && y == end.1 {
   99    -1             best_i = i;
  100    -1             continue;
  101    -1         }
  102    -1         k += 1;
  103    -1 
  104    -1         let mut moves = vec![(x, y)];
  105    -1         if x == usize::MAX && y == usize::MAX {
  106    -1             moves.push(start);
  107    -1         } else {
  108    -1             if x + 1 < map.width {
  109    -1                 moves.push((x + 1, y));
  110    -1             }
  111    -1             if y + 1 < map.height {
  112    -1                 moves.push((x, y + 1));
  113    -1             }
  114    -1             if x > 0 {
  115    -1                 moves.push((x - 1, y));
  116    -1             }
  117    -1             if y > 0 {
  118    -1                 moves.push((x, y - 1));
  119    -1             }
  120    -1         }
  121    -1 
  122    -1         for (xx, yy) in moves {
  123    -1             queue.push((
  124    -1                 Reverse((i + 1) + abs_diff(xx, end.0) + abs_diff(yy, end.1)),
  125    -1                 xx,
  126    -1                 yy,
  127    -1                 i + 1,
  128    -1             ));
   -1    57     let mut positions = vec![0; map.height];
   -1    58     let mut i = offset;
   -1    59 
   -1    60     let mask = (1 << map.width) - 1;
   -1    61 
   -1    62     while positions[end.1] & (1 << end.0) == 0 {
   -1    63         i += 1;
   -1    64         let mut prev = 0;
   -1    65         for y in 0..map.height {
   -1    66             let curr = positions[y];
   -1    67             let next = if y + 1 < map.height { positions[y + 1] } else { 0 };
   -1    68 
   -1    69             positions[y] = (
   -1    70                 curr
   -1    71                 | prev
   -1    72                 | next
   -1    73                 | (curr >> 1)
   -1    74                 | ((curr << 1) & mask)
   -1    75                 | if y == start.1 { 1 << start.0 } else { 0 }
   -1    76             ) & !(
   -1    77                 map.blizzards[(y + i) % map.height].up
   -1    78                 | (shift(map.blizzards[y].right, (map.width - 1) * i, map.width) & mask)
   -1    79                 | map.blizzards[(y + (map.height - 1) * i) % map.height].down
   -1    80                 | (shift(map.blizzards[y].left, i, map.width) & mask)
   -1    81             );
   -1    82 
   -1    83             prev = curr;
  129    84         }
  130    85     }
  131    -1 
  132    -1     println!("{}", k);
  133    -1     return best_i + 1;
   -1    86     return i + 1;
  134    87 }
  135    88 
  136    89 fn main() {