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
18        .lines()
19        .map(|line| {
20            let bytes = line.as_bytes();
21            &bytes[1..(bytes.len() - 1)]
22        })
23        .collect();
24
25    let width = raw[0].len();
26    let height = raw.len() - 2;
27    // For each blizzard type set a `0` bit in the corresponding integer. Later on we can AND this
28    // with elves to eliminate possible positions.
29    let build = |kind| -> Vec<_> {
30        let fold = |row: &&[u8]| row.iter().fold(0, |acc, &b| (acc << 1) | (b != kind) as u128);
31        raw[1..=height].iter().map(fold).collect()
32    };
33    // Process each row.
34    let left = build(b'<');
35    let right = build(b'>');
36    let up = build(b'^');
37    let down = build(b'v');
38
39    // Blizzard patterns repeat every `width` minutes, so we can precompute all possible
40    // horizontal patterns.
41    let mut horizontal = Vec::with_capacity(width * height);
42    for time in 0..width {
43        for i in 0..height {
44            let left = (left[i] << time) | (left[i] >> (width - time));
45            let right = (right[i] >> time) | (right[i] << (width - time));
46            horizontal.push(left & right);
47        }
48    }
49
50    // Similarly vertical blizzards repeat every `height` minutes so precompute to save time later.
51    let mut vertical = Vec::with_capacity(height * height);
52    for time in 0..height {
53        for i in 0..height {
54            let up = up[(i + time) % height];
55            let down = down[(height + i - time % height) % height];
56            vertical.push(up & down);
57        }
58    }
59
60    Input { width, height, horizontal, vertical }
61}
62
63pub fn part1(input: &Input) -> usize {
64    expedition(input, 0, true)
65}
66
67pub fn part2(input: &Input) -> usize {
68    let first = expedition(input, 0, true);
69    let second = expedition(input, first, false);
70    expedition(input, second, true)
71}
72
73fn expedition(input: &Input, start: usize, forward: bool) -> usize {
74    let Input { width, height, horizontal, vertical } = input;
75    let mut time = start;
76    let mut state = vec![0; height + 1];
77
78    loop {
79        time += 1;
80        // We modify the state in-place as we process each row, so preserve the previous state
81        // for subsequent calculations.
82        let mut prev;
83        let mut cur = 0;
84        let mut next = state[0];
85
86        for i in 0..*height {
87            prev = cur;
88            cur = next;
89            next = state[i + 1];
90            // The Elves frontier can spread out 1 in each orthogonal direction unless there
91            // is a blizzard present.
92            state[i] = (cur | (cur >> 1) | (cur << 1) | prev | next)
93                & horizontal[height * (time % width) + i]
94                & vertical[height * (time % height) + i];
95        }
96
97        // Depending on the direction elves can wait indefinitely in the start or end positions.
98        if forward {
99            // Start position.
100            state[0] |= 1 << (width - 1);
101            // If we reached the end then stop.
102            if state[height - 1] & 1 != 0 {
103                break time + 1;
104            }
105        } else {
106            // End position.
107            state[height - 1] |= 1;
108            // If we've reached the start then stop.
109            if state[0] & (1 << (width - 1)) != 0 {
110                break time + 1;
111            }
112        }
113    }
114}
aoc/year2022/day24.rs

aoc/year2022/
day24.rs
