aoc/year2022/
day24.rs

1//! # Blizzard Basin
2//!
3//! Similar to the previous day we represent the position of elves and blizzards as bits in an
4//! integer in order to efficiently compute the next minute. The grid is much wider than it is tall,
5//! so we transpose it and store each column as bits in a `u64`, one bit per row. We further
6//! optimize by memoizing the position of vertical blizzards as they repeat every `height` minutes.
7type Input = (usize, usize);
8
9struct Basin {
10    width: usize,
11    height: usize,
12    left: Vec<u64>,
13    right: Vec<u64>,
14    vertical: Vec<u64>,
15}
16
17pub fn parse(input: &str) -> Input {
18    // Exclude the boundary walls.
19    let raw: Vec<_> = input.lines().map(str::as_bytes).collect();
20    let width = raw[0].len() - 2;
21    let height = raw.len() - 2;
22
23    // For each blizzard type set a `0` bit in the corresponding integer. Later on we can AND this
24    // with elves to eliminate possible positions.
25    let build = |kind| -> Vec<_> {
26        let fold = |x| (1..=height).fold(0, |acc, y| (acc << 1) | u64::from(raw[y][x] != kind));
27        (1..=width).map(fold).collect()
28    };
29
30    // Horizontal blizzards repeat every `width` minutes. Storing two copies of the pattern turns
31    // the rotation into a simple offset.
32    let left = build(b'<').repeat(2);
33    let right = build(b'>').repeat(2);
34
35    // Vertical blizzards repeat every `height` minutes so precompute to save time later.
36    let up = build(b'^');
37    let down = build(b'v');
38    let mut vertical = Vec::with_capacity(height * width);
39
40    for time in 0..height {
41        for i in 0..width {
42            let up = (up[i] << time) | (up[i] >> (height - time));
43            let down = (down[i] >> time) | (down[i] << (height - time));
44            vertical.push(up & down);
45        }
46    }
47
48    let basin = Basin { width, height, left, right, vertical };
49    let first = expedition(&basin, 0, true);
50    let second = expedition(&basin, first, false);
51    let third = expedition(&basin, second, true);
52
53    (first, third)
54}
55
56pub fn part1(input: &Input) -> usize {
57    input.0
58}
59
60pub fn part2(input: &Input) -> usize {
61    input.1
62}
63
64fn expedition(basin: &Basin, start: usize, forward: bool) -> usize {
65    let Basin { width, height, left, right, vertical } = basin;
66    let mut state = vec![0; width + 1];
67    let top = (0, 1 << (height - 1));
68    let bottom = (width - 1, 1);
69    let ((entrance, entrance_bit), (exit, exit_bit)) =
70        if forward { (top, bottom) } else { (bottom, top) };
71
72    for time in start + 1.. {
73        // Left and right offsets stay within the doubled arrays.
74        let left = &left[time % width..];
75        let right = &right[width - time % width..];
76        let vertical = &vertical[width * (time % height)..];
77
78        // We modify the state in-place as we process each column, so preserve the previous state
79        // for subsequent calculations.
80        let mut cur = 0;
81        let mut next = state[0];
82
83        for i in 0..*width {
84            let prev = cur;
85            cur = next;
86            next = state[i + 1];
87            // The Elves frontier can spread out 1 in each orthogonal direction unless there
88            // is a blizzard present.
89            state[i] =
90                (cur | (cur >> 1) | (cur << 1) | prev | next) & left[i] & right[i] & vertical[i];
91        }
92
93        // Elves can wait indefinitely at the entrance in either direction.
94        state[entrance] |= entrance_bit;
95        // Once we reach the exit, leaving the basin takes one more minute.
96        if state[exit] & exit_bit != 0 {
97            return time + 1;
98        }
99    }
100
101    unreachable!()
102}
aoc/year2022/day24.rs

aoc/year2022/
day24.rs
