year2020/
day17.rs

1use utils::bit::carry_save_adder;
2use utils::grid;
3use utils::prelude::*;
4
5/// Simulating a cellular automaton in three and four dimensions.
6///
7/// The key optimization is that the initial state is at z = w = 0 and the update rule treats all
8/// directions the same, so layers z and -z are always equal, as well as w and -w, and (z, w) and
9/// (w, z). Therefore, only layers with z >= 0 for part 1 and 0 <= w <= z for part 2 are simulated.
10///
11/// Each cycle first counts the neighbours of each cell within its own layer, then adds the counts
12/// from the adjacent w and z layers to get each cell's total.
13#[derive(Clone, Debug)]
14pub struct Day17 {
15    initial: Vec<u32>,
16}
17
18const CYCLES: usize = 6;
19const PADDING: usize = CYCLES + 1;
20const DEPTH: usize = CYCLES + 2;
21const MAX_ROWS: usize = 8;
22const MAX_COLS: usize = u32::BITS as usize - 2 * CYCLES;
23// Rounding up to a multiple of 8/16 rows helps with vectorization in AVX2/AVX512 builds
24const INNER_ROWS: usize = (MAX_ROWS + 2 * CYCLES).next_multiple_of(cfg_select! {
25    target_feature = "avx512f" => 16,
26    target_feature = "avx2" => 8,
27    _ => 1,
28});
29const HEIGHT: usize = INNER_ROWS + 2;
30const LAYERS: usize = DEPTH * (DEPTH + 1) / 2;
31
32impl Day17 {
33    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
34        let mut initial = Vec::with_capacity(MAX_ROWS);
35        grid::for_each_row(
36            input,
37            |b| matches!(b, b'.' | b'#'),
38            || "expected '.' or '#'",
39            |row, cols, row_bytes| {
40                if row == MAX_ROWS {
41                    return Err(InputError::new(
42                        input,
43                        row_bytes,
44                        format!("expected at most {MAX_ROWS} rows"),
45                    ));
46                }
47                if row == 0 && cols > MAX_COLS {
48                    return Err(InputError::new(
49                        input,
50                        row_bytes,
51                        format!("expected at most {MAX_COLS} columns"),
52                    ));
53                }
54
55                let bits = row_bytes
56                    .iter()
57                    .rfold(0u32, |bits, &b| (bits << 1) | u32::from(b == b'#'));
58                initial.push(bits << CYCLES);
59                Ok(())
60            },
61        )?;
62        Ok(Self { initial })
63    }
64
65    #[must_use]
66    pub fn part1(&self) -> u32 {
67        let mut first = [[0u32; HEIGHT]; DEPTH];
68        let mut second = [[0u32; HEIGHT]; DEPTH];
69        let mut layer_counts = [NeighbourCounts::default(); DEPTH];
70        let (mut current, mut next) = (&mut first, &mut second);
71
72        let rows = self.initial.len();
73        current[0][PADDING..PADDING + rows].copy_from_slice(&self.initial);
74
75        for cycle in 1..=CYCLES {
76            // Only layers below cycle can contain active cells
77            for z in 0..cycle {
78                layer_counts[z] = NeighbourCounts::within_layer(&current[z]);
79            }
80
81            // Add the counts from the adjacent z layers to get each cell's total
82            for z in 0..=cycle {
83                let adjacent = Self::adjacent(z).map(|z| &layer_counts[z]);
84                next[z] = Self::next_layer(&current[z], adjacent);
85            }
86
87            (current, next) = (next, current);
88        }
89
90        // Each layer other than z = 0 also counts for the equal -z layer
91        let mut total = 0;
92        for (z, layer) in current.iter().enumerate().take(CYCLES + 1) {
93            let multiplier = 1 + u32::from(z != 0);
94            total += multiplier * layer.iter().map(|row| row.count_ones()).sum::<u32>();
95        }
96        total
97    }
98
99    #[must_use]
100    pub fn part2(&self) -> u32 {
101        let mut first = [[0u32; HEIGHT]; LAYERS];
102        let mut second = [[0u32; HEIGHT]; LAYERS];
103        let mut layer_counts = [NeighbourCounts::default(); LAYERS];
104        let mut z_sums = [[NeighbourCounts::default(); DEPTH]; DEPTH];
105        let (mut current, mut next) = (&mut first, &mut second);
106
107        let rows = self.initial.len();
108        current[0][PADDING..PADDING + rows].copy_from_slice(&self.initial);
109
110        for cycle in 1..=CYCLES {
111            // Only layers with w <= z < cycle can contain active cells
112            for w in 0..cycle {
113                for z in w..cycle {
114                    let layer = Self::layer_index(w, z);
115                    layer_counts[layer] = NeighbourCounts::within_layer(&current[layer]);
116                }
117            }
118
119            // Add the counts from the adjacent z layers
120            for (w, sums) in z_sums.iter_mut().enumerate().take(cycle) {
121                for (z, sum) in sums[..cycle]
122                    .iter_mut()
123                    .enumerate()
124                    .skip(w.saturating_sub(1))
125                {
126                    let adjacent = Self::adjacent(z).map(|z| Self::layer_index(w, z));
127                    *sum = NeighbourCounts::sum(adjacent.map(|layer| &layer_counts[layer]));
128                }
129
130                // Only the layer below the new layer can contain active cells
131                sums[cycle] = layer_counts[Self::layer_index(w, cycle - 1)];
132            }
133
134            // Add the counts from the adjacent w layers to get each cell's total
135            for w in 0..=cycle {
136                let [inner, middle, outer] = Self::adjacent(w).map(|w| &z_sums[w]);
137                for z in w..=cycle {
138                    let layer = Self::layer_index(w, z);
139                    let adjacent = [&inner[z], &middle[z], &outer[z]];
140                    next[layer] = Self::next_layer(&current[layer], adjacent);
141                }
142            }
143            (current, next) = (next, current);
144        }
145
146        // Each (w, z) layer also counts for the equal layers with -w, -z, and w and z swapped
147        let mut total = 0;
148        for w in 0..=CYCLES {
149            for z in w..=CYCLES {
150                let multiplier =
151                    (1 + u32::from(w != 0)) * (1 + u32::from(z != 0)) * (1 + u32::from(w != z));
152                let layer = &current[Self::layer_index(w, z)];
153                total += multiplier * layer.iter().map(|row| row.count_ones()).sum::<u32>();
154            }
155        }
156        total
157    }
158
159    fn next_layer(current: &[u32; HEIGHT], adjacent: [&NeighbourCounts; 3]) -> [u32; HEIGHT] {
160        let mut next = [0; HEIGHT];
161        for row in 0..INNER_ROWS {
162            let [ones, twos, fours] = NeighbourCounts::sum_row(adjacent, row);
163
164            // Counts include the cell itself, so 3 is always active and 4 only if already active
165            let exactly_three = ones & twos & !fours;
166            let exactly_four = fours & !(ones | twos);
167            next[row + 1] = exactly_three | (current[row + 1] & exactly_four);
168        }
169        next
170    }
171
172    #[inline]
173    fn adjacent(z: usize) -> [usize; 3] {
174        if z == 0 { [1, 0, 1] } else { [z - 1, z, z + 1] }
175    }
176
177    #[inline]
178    fn layer_index(w: usize, z: usize) -> usize {
179        let (w, z) = if w < z { (w, z) } else { (z, w) };
180        z * (z + 1) / 2 + w
181    }
182}
183
184// Saturating neighbour counts for the inner rows from one layer, stored as three arrays so the row
185// loops can be vectorized by the compiler. Also aligned to 64 bytes when using 256+ bit AVX vectors
186#[derive(Clone, Copy, Debug, Default)]
187#[cfg_attr(target_feature = "avx2", repr(align(64)))]
188struct NeighbourCounts {
189    ones: [u32; INNER_ROWS],
190    twos: [u32; INNER_ROWS],
191    fours: [u32; INNER_ROWS],
192}
193
194impl NeighbourCounts {
195    // Counts each cell's neighbours within the layer, including itself
196    #[inline]
197    fn within_layer(layer: &[u32; HEIGHT]) -> Self {
198        let mut counts = Self::default();
199        let mut above = Self::within_row(layer[0]);
200        let mut middle = Self::within_row(layer[1]);
201        for r in 0..INNER_ROWS {
202            let below = Self::within_row(layer[r + 2]);
203            [counts.ones[r], counts.twos[r], counts.fours[r]] = Self::add(above, middle, below);
204            (above, middle) = (middle, below);
205        }
206        counts
207    }
208
209    #[inline]
210    fn within_row(row: u32) -> [u32; 3] {
211        let (ones, twos) = carry_save_adder(row << 1, row, row >> 1);
212        [ones, twos, 0]
213    }
214
215    // Adds the counts from three adjacent layers
216    #[inline]
217    fn sum(adjacent: [&Self; 3]) -> Self {
218        let mut counts = Self::default();
219        for r in 0..INNER_ROWS {
220            [counts.ones[r], counts.twos[r], counts.fours[r]] = Self::sum_row(adjacent, r);
221        }
222        counts
223    }
224
225    // Adds one row of the counts from three adjacent layers
226    #[inline]
227    fn sum_row([a, b, c]: [&Self; 3], row: usize) -> [u32; 3] {
228        Self::add(
229            [a.ones[row], a.twos[row], a.fours[row]],
230            [b.ones[row], b.twos[row], b.fours[row]],
231            [c.ones[row], c.twos[row], c.fours[row]],
232        )
233    }
234
235    #[inline]
236    fn add([a1, a2, a4]: [u32; 3], [b1, b2, b4]: [u32; 3], [c1, c2, c4]: [u32; 3]) -> [u32; 3] {
237        let (ones, carry2) = carry_save_adder(a1, b1, c1);
238        let (twos, carry4a) = carry_save_adder(a2, b2, c2);
239        let (twos, carry4b) = carry_save_adder(twos, carry2, 0);
240        let (fours, carry8a) = carry_save_adder(a4, b4, c4);
241        let (fours, carry8b) = carry_save_adder(fours, carry4a, carry4b);
242
243        // carry8 means the value is at least 8, which is stored as 7
244        let eights = carry8a | carry8b;
245
246        [ones | eights, twos | eights, fours | eights]
247    }
248}
249
250examples!(Day17 -> (u32, u32) [
251    {input: ".#.\n..#\n###", part1: 112, part2: 848},
252]);
year2020/day17.rs

year2020/
day17.rs
