aoc/year2021/
day20.rs

1//! # Trench Map
2//!
3//! This is a cellular automata problem, similar to Conway's Game of Life, except that the rules
4//! are encoded in the enhancement algorithm string, instead of being statically specified. Each
5//! round the initial square area of cells expands by at most one in each direction, so we can store
6//! the cell in a fixed size array with enough space on either side to expand into.
7//!
8//! The interesting nuance is handling the edge cells when all 9 cells are empty (index 0) or all
9//! 9 cell are active (index 511). The sample data encodes a blank cell in both scenarios.
10//! My input encoded an active cell for index 0 and a blank cell for index 511, meaning that each
11//! turn the edge cells toggle from set to unset.
12//!
13//! The algorithm keeps track of the bounds of the expanding square and supplies a `default` value,
14//! that in the example case is always zero, but in the real data toggles between zero and one.
15pub struct Input {
16    size: usize,
17    algorithm: [u8; 512],
18    pixels: [u8; 40_000],
19}
20
21pub fn parse(input: &str) -> Input {
22    // `#` is odd and `.` is even so we can convert to one or zero by bitwise AND with 1.
23    let bits: Vec<Vec<_>> =
24        input.lines().map(|line| line.bytes().map(|b| b & 1).collect()).collect();
25    let size = bits.len() - 2;
26    let algorithm = bits[0][..512].try_into().unwrap();
27
28    // Offset the initial square by 50 cells in both dimensions.
29    // The square expands by at most one in each step so this is enough room to stay within bounds.
30    let mut pixels = [0; 40_000];
31    for (i, row) in bits[2..].iter().enumerate() {
32        let start = (i + 50) * 200 + 50;
33        let end = start + size;
34        pixels[start..end].copy_from_slice(&row[..size]);
35    }
36
37    Input { size, algorithm, pixels }
38}
39
40pub fn part1(input: &Input) -> usize {
41    enhance(input, 2)
42}
43
44pub fn part2(input: &Input) -> usize {
45    enhance(input, 50)
46}
47
48fn enhance(input: &Input, steps: usize) -> usize {
49    let algorithm = input.algorithm;
50    let mut pixels = input.pixels;
51    let mut next = [0; 40_000];
52
53    let mut start = 50;
54    let mut end = 50 + input.size as i32;
55    let mut default = 0;
56
57    for _ in 0..steps {
58        for y in (start - 1)..(end + 1) {
59            // If the pixel is within current bounds then return it, or else use the `default`
60            // edge value specified by the enhancement algorithm.
61            let helper = |sx, sy, shift| {
62                let result = if sx < end && sy >= start && sy < end {
63                    pixels[(sy * 200 + sx) as usize] as usize
64                } else {
65                    default as usize
66                };
67                result << shift
68            };
69
70            // If the edge pixels are 1 then the inital edge will look like
71            // [##a]
72            // [##b]
73            // [##c]
74            // or 11a11b11c when encoded as an index.
75            let mut index = if default == 1 { 0b11011011 } else { 0b00000000 };
76
77            for x in (start - 1)..(end + 1) {
78                // Keeps a sliding window of the index, updated as we evaluate the row from
79                // left to right. Shift the index left by one each turn, updating the values from
80                // the three new rightmost pixels entering the window.
81                index = ((index << 1) & 0b110110110)
82                    + helper(x + 1, y - 1, 6)
83                    + helper(x + 1, y, 3)
84                    + helper(x + 1, y + 1, 0);
85
86                next[(y * 200 + x) as usize] = algorithm[index];
87            }
88        }
89
90        // Boundaries expand by one each turn
91        pixels = next;
92        start -= 1;
93        end += 1;
94
95        // Calculate the next value for edge pixels beyond the boundary.
96        if default == 0 {
97            default = algorithm[0];
98        } else {
99            default = algorithm[511];
100        }
101    }
102
103    pixels.iter().filter(|&&p| p == 1).count()
104}
aoc/year2021/day20.rs

aoc/year2021/
day20.rs
