aoc/year2020/
day17.rs

1//! # Conway Cubes
2//!
3//! Solving this problem reveals an interesting insight that the active cells are very sparse.
4//! Of the total possible volume of the cube formed by the maximum extents in part one, only
5//! roughly 8% is active and of the hypercube from part two only 3% is active for my input.
6//!
7//! To speed things up our high level strategy will flip from a "pull" model where we check the
8//! surrounding neighbors of each cell, to a "push" model where we update the neighbors of each
9//! active cell instead.
10//!
11//! A `HashSet` is generally a good choice for very sparse infinite grids, however for this
12//! problem we'll pack all dimensions into a single `vec` to achieve a five times increase
13//! in lookup speed.
14use crate::util::grid::*;
15use crate::util::point::*;
16
17/// x and y dimensions are in the plane of the input. Each dimension can expand by at most two in each
18/// axis per round (one positive and one negative). Adding padding at the edges to avoid boundary
19/// checks gives a maximum width of 8 + 2 * (6 + 1) = 22 for the x and y dimensions and
20/// 1 + 2 * (6 + 1) = 15 for the z and w dimensions.
21pub mod size {
22    pub const X: i32 = 22;
23    pub const Y: i32 = 22;
24    pub const Z: i32 = 15;
25    pub const W: i32 = 15;
26}
27
28/// Pack a four dimensional array into a one dimensional vec to avoid the speed penalty of
29/// following multiple pointers and increase memory locality for caching.
30pub mod stride {
31    use super::size;
32    pub const X: i32 = 1;
33    pub const Y: i32 = size::X * X;
34    pub const Z: i32 = size::Y * Y;
35    pub const W: i32 = size::Z * Z;
36}
37
38/// Use our utility [`Grid`] method to parse the input.
39///
40/// [`Grid`]: crate::util::grid::Grid
41pub fn parse(input: &str) -> Grid<u8> {
42    Grid::parse(input)
43}
44
45/// Part one cells form a cube.
46pub fn part1(input: &Grid<u8>) -> usize {
47    let size = size::X * size::Y * size::Z;
48    let base = stride::X + stride::Y + stride::Z;
49    boot_process(input, size, base, &[0])
50}
51
52/// Part two forms a hypercube.
53pub fn part2(input: &Grid<u8>) -> usize {
54    let size = size::X * size::Y * size::Z * size::W;
55    let base = stride::X + stride::Y + stride::Z + stride::W;
56    boot_process(input, size, base, &[-1, 0, 1])
57}
58
59/// Re-use logic between both parts.
60fn boot_process(input: &Grid<u8>, size: i32, base: i32, fourth_dimension: &[i32]) -> usize {
61    let dimension = [-1, 0, 1];
62    let mut neighbors = Vec::new();
63
64    // Pre-calculate either the 26 or 80 offsets formed by the combination of dimensions.
65    for x in dimension {
66        for y in dimension {
67            for z in dimension {
68                for w in fourth_dimension {
69                    let offset = x * stride::X + y * stride::Y + z * stride::Z + w * stride::W;
70                    if offset != 0 {
71                        neighbors.push(offset as usize);
72                    }
73                }
74            }
75        }
76    }
77
78    let mut active = Vec::with_capacity(5_000);
79    let mut candidates = Vec::with_capacity(5_000);
80    let mut next_active = Vec::with_capacity(5_000);
81
82    // To prevent negative array indices offset the starting cells by seven units in each
83    // dimension. This allows six for growth, plus one for padding to prevent needing edge checks.
84    for x in 0..input.width {
85        for y in 0..input.height {
86            if input[Point::new(x, y)] == b'#' {
87                let index = 7 * base + x + y * stride::Y;
88                active.push(index as usize);
89            }
90        }
91    }
92
93    for _ in 0..6 {
94        let mut state: Vec<u8> = vec![0; size as usize];
95
96        for &cube in &active {
97            for &offset in &neighbors {
98                // Earlier we converted the offsets from signed `i32` to unsigned `usize`. To
99                // achieve subtraction for negative indices, we use a `wrapping_add` that performs
100                // [two's complement](https://en.wikipedia.org/wiki/Two%27s_complement) arithmetic.
101                let index = cube.wrapping_add(offset);
102                state[index] += 1;
103
104                if state[index] == 3 {
105                    candidates.push(index);
106                }
107            }
108        }
109
110        // Active cubes remain active with both two and three neighbors.
111        for &cube in &active {
112            if state[cube] == 2 {
113                next_active.push(cube);
114            }
115        }
116
117        // Check that the neighbor count for inactive cubes hasn't exceeded three.
118        for &cube in &candidates {
119            if state[cube] == 3 {
120                next_active.push(cube);
121            }
122        }
123
124        // Swap to make next generation the current generation.
125        (active, next_active) = (next_active, active);
126        candidates.clear();
127        next_active.clear();
128    }
129
130    active.len()
131}
aoc/year2020/day17.rs

aoc/year2020/
day17.rs
