aoc/year2019/
day24.rs

1//! # Planet of Discord
2//!
3//! ## Part One
4//!
5//! The "biodiversity rating" is a very strong hint to store the 5x5 grid as bits in a integer.
6//! To make calculating the rating a no-op, we store the grid:
7//!
8//! ```none
9//!     abcde
10//!     fghij
11//!     klmno
12//!     pqrst
13//!     uvwxy
14//! ```
15//!
16//! packed into a `u32` as `yxwvutsrqponmlkjihgfedcba`.
17//!
18//! Then for each position we create a bitmask for up to 4 potential neighbors.
19//! For example the bitmask for position `a` is `100010` and for position `h` is `1000101000100`.
20//!
21//! For each generation we bitwise `AND` each position with its mask, then use the [`count_ones`]
22//! intrinsic to to efficiently find the number of neighbors.
23//!
24//! ## Part Two
25//!
26//! The multiple levels can be represented as an array, the outer layer as the previous element
27//! and the inner layer as the next. We add two more bitmasks for the outer and inner layers
28//! respectively, then calculate the total sum for the 16 tiles on the outer edges with the
29//! previous layer and the 9 inner tiles with the next layer. The center tile is a no-op and
30//! always zero.
31//!
32//! [`count_ones`]: u32::count_ones
33use crate::util::hash::*;
34
35const LEVEL: [u32; 25] = [
36    0b0000000000000000000100010,
37    0b0000000000000000001000101,
38    0b0000000000000000010001010,
39    0b0000000000000000100010100,
40    0b0000000000000001000001000,
41    0b0000000000000010001000001,
42    0b0000000000000100010100010,
43    0b0000000000001000101000100,
44    0b0000000000010001010001000,
45    0b0000000000100000100010000,
46    0b0000000001000100000100000,
47    0b0000000010001010001000000,
48    0b0000000100010100010000000,
49    0b0000001000101000100000000,
50    0b0000010000010001000000000,
51    0b0000100010000010000000000,
52    0b0001000101000100000000000,
53    0b0010001010001000000000000,
54    0b0100010100010000000000000,
55    0b1000001000100000000000000,
56    0b0001000001000000000000000,
57    0b0010100010000000000000000,
58    0b0101000100000000000000000,
59    0b1010001000000000000000000,
60    0b0100010000000000000000000,
61];
62
63const OUTER: [u32; 25] = [
64    0b0000000000000100010000000,
65    0b0000000000000000010000000,
66    0b0000000000000000010000000,
67    0b0000000000000000010000000,
68    0b0000000000010000010000000,
69    0b0000000000000100000000000,
70    0b0000000000000000000000000,
71    0b0000000000000000000000000,
72    0b0000000000000000000000000,
73    0b0000000000010000000000000,
74    0b0000000000000100000000000,
75    0b0000000000000000000000000,
76    0b0000000000000000000000000,
77    0b0000000000000000000000000,
78    0b0000000000010000000000000,
79    0b0000000000000100000000000,
80    0b0000000000000000000000000,
81    0b0000000000000000000000000,
82    0b0000000000000000000000000,
83    0b0000000000010000000000000,
84    0b0000000100000100000000000,
85    0b0000000100000000000000000,
86    0b0000000100000000000000000,
87    0b0000000100000000000000000,
88    0b0000000100010000000000000,
89];
90
91const INNER: [u32; 25] = [
92    0b0000000000000000000000000,
93    0b0000000000000000000000000,
94    0b0000000000000000000000000,
95    0b0000000000000000000000000,
96    0b0000000000000000000000000,
97    0b0000000000000000000000000,
98    0b0000000000000000000000000,
99    0b0000000000000000000011111,
100    0b0000000000000000000000000,
101    0b0000000000000000000000000,
102    0b0000000000000000000000000,
103    0b0000100001000010000100001,
104    0b0000000000000000000000000,
105    0b1000010000100001000010000,
106    0b0000000000000000000000000,
107    0b0000000000000000000000000,
108    0b0000000000000000000000000,
109    0b1111100000000000000000000,
110    0b0000000000000000000000000,
111    0b0000000000000000000000000,
112    0b0000000000000000000000000,
113    0b0000000000000000000000000,
114    0b0000000000000000000000000,
115    0b0000000000000000000000000,
116    0b0000000000000000000000000,
117];
118
119/// Parse the initial grid, placing the top left bug into the least significant bit of the result.
120pub fn parse(input: &str) -> u32 {
121    input
122        .bytes()
123        .rev()
124        .filter(|b| !b.is_ascii_whitespace())
125        .fold(0, |acc, b| (acc << 1) | (b & 1) as u32)
126}
127
128pub fn part1(input: &u32) -> u32 {
129    let mut grid = *input;
130    let mut seen = FastSet::new();
131
132    // `insert` returns false if the element is already present
133    while seen.insert(grid) {
134        let mut next = 0;
135
136        for (i, level) in LEVEL.iter().enumerate() {
137            let mask = 1 << i;
138            let bug = grid & mask;
139            let adjacent = (grid & level).count_ones();
140
141            if adjacent == 1 || (bug == 0 && adjacent == 2) {
142                next |= mask;
143            }
144        }
145
146        grid = next;
147    }
148
149    grid
150}
151
152pub fn part2(input: &u32) -> u32 {
153    part2_testable(input, 200)
154}
155
156pub fn part2_testable(input: &u32, minutes: usize) -> u32 {
157    // The bugs can expand by at most 1 level during each minute, so we need
158    // 1 + 2 * (200 + 1 buffer for convenience) = 403 total.
159    let mut start = 200;
160    let mut end = 203;
161    let mut grid = &mut [0; 403];
162    let mut next = &mut [0; 403];
163
164    // Place the initial level exactly in the middle.
165    grid[201] = *input;
166
167    for _ in 0..minutes {
168        for i in start..end {
169            let outer = grid[i - 1];
170            let level = grid[i];
171            let inner = grid[i + 1];
172
173            let mut acc = 0;
174
175            macro_rules! repeat {
176                ($other:ident, $mask:ident, $($i:literal)*) => ($(
177                    let mask = 1 << $i;
178                    let bug = level & mask;
179                    let adjacent = (level & LEVEL[$i]).count_ones()
180                        + ($other & $mask[$i]).count_ones();
181
182                    if adjacent == 1 || (bug == 0 && adjacent == 2) {
183                        acc |= mask;
184                    }
185                )*)
186            }
187
188            repeat!(outer, OUTER, 0 1 2 3 4 5 9 10 14 15 19 20 21 22 23 24);
189            repeat!(inner, INNER, 6 7 8 11 13 16 17 18);
190            next[i] = acc;
191        }
192
193        // As an optimization only expand if there are bugs in the level.
194        if next[start] != 0 {
195            start -= 1;
196        }
197        if next[end - 1] != 0 {
198            end += 1;
199        }
200
201        (grid, next) = (next, grid);
202    }
203
204    grid[start..end].iter().copied().map(u32::count_ones).sum()
205}
aoc/year2019/day24.rs

aoc/year2019/
day24.rs
