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.
5//!
6//! We further optimize by memoizing the position of blizzards as they repeat
7//! every `width` minutes for horizontal and every `height` minutes for vertical.
8pub struct Input {
9    width: usize,
10    height: usize,
11    horizontal: Vec<u128>,
12    vertical: Vec<u128>,
13}
14
15pub fn parse(input: &str) -> Input {
16    // Don't include the left and right walls.
17    let raw: Vec<_> = input.lines().map(|line| &line.as_bytes()[1..line.len() - 1]).collect();
18
19    let width = raw[0].len();
20    let height = raw.len() - 2;
21    // For each blizzard type set a `0` bit in the corresponding integer. Later on we can AND this
22    // with elves to eliminate possible positions.
23    let build = |kind| -> Vec<_> {
24        let fold = |row: &&[u8]| row.iter().fold(0, |acc, &b| (acc << 1) | (b != kind) as u128);
25        raw[1..=height].iter().map(fold).collect()
26    };
27    // Process each row.
28    let left = build(b'<');
29    let right = build(b'>');
30    let up = build(b'^');
31    let down = build(b'v');
32
33    // Blizzard patterns repeat every `width` minutes, so we can precompute all possible
34    // horizontal patterns.
35    let mut horizontal = Vec::with_capacity(width * height);
36    for time in 0..width {
37        for i in 0..height {
38            let left = (left[i] << time) | (left[i] >> (width - time));
39            let right = (right[i] >> time) | (right[i] << (width - time));
40            horizontal.push(left & right);
41        }
42    }
43
44    // Similarly, vertical blizzards repeat every `height` minutes so precompute to save time later.
45    let mut vertical = Vec::with_capacity(height * height);
46    for time in 0..height {
47        for i in 0..height {
48            let up = up[(i + time) % height];
49            let down = down[(height + i - time % height) % height];
50            vertical.push(up & down);
51        }
52    }
53
54    Input { width, height, horizontal, vertical }
55}
56
57pub fn part1(input: &Input) -> usize {
58    expedition(input, 0, true)
59}
60
61pub fn part2(input: &Input) -> usize {
62    let first = expedition(input, 0, true);
63    let second = expedition(input, first, false);
64    expedition(input, second, true)
65}
66
67fn expedition(input: &Input, start: usize, forward: bool) -> usize {
68    let Input { width, height, horizontal, vertical } = input;
69    let mut time = start;
70    let mut state = vec![0; height + 1];
71
72    loop {
73        time += 1;
74        // We modify the state in-place as we process each row, 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..*height {
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] = (cur | (cur >> 1) | (cur << 1) | prev | next)
87                & horizontal[height * (time % width) + i]
88                & vertical[height * (time % height) + i];
89        }
90
91        // Depending on the direction elves can wait indefinitely in the start or end positions.
92        if forward {
93            // Start position.
94            state[0] |= 1 << (width - 1);
95            // If we reached the end then stop.
96            if state[height - 1] & 1 != 0 {
97                break time + 1;
98            }
99        } else {
100            // End position.
101            state[height - 1] |= 1;
102            // If we've reached the start then stop.
103            if state[0] & (1 << (width - 1)) != 0 {
104                break time + 1;
105            }
106        }
107    }
108}
aoc/year2022/day24.rs

aoc/year2022/
day24.rs
