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
68    for time in start + 1.. {
69        // Left and right offsets stay within the doubled arrays.
70        let left = &left[time % width..];
71        let right = &right[width - time % width..];
72        let vertical = &vertical[width * (time % height)..];
73
74        // We modify the state in-place as we process each column, so preserve the previous state
75        // for subsequent calculations.
76        let mut prev;
77        let mut cur = 0;
78        let mut next = state[0];
79
80        for i in 0..*width {
81            prev = cur;
82            cur = next;
83            next = state[i + 1];
84            // The Elves frontier can spread out 1 in each orthogonal direction unless there
85            // is a blizzard present.
86            state[i] =
87                (cur | (cur >> 1) | (cur << 1) | prev | next) & left[i] & right[i] & vertical[i];
88        }
89
90        // Depending on the direction elves can wait indefinitely in the start or end positions.
91        if forward {
92            // Start position.
93            state[0] |= 1 << (height - 1);
94            // If we reached the end then stop.
95            if state[width - 1] & 1 != 0 {
96                return time + 1;
97            }
98        } else {
99            // End position.
100            state[width - 1] |= 1;
101            // If we've reached the start then stop.
102            if state[0] & (1 << (height - 1)) != 0 {
103                return time + 1;
104            }
105        }
106    }
107
108    unreachable!()
109}
aoc/year2022/day24.rs

aoc/year2022/
day24.rs
