Skip to main content

year2019/
day24.rs

1use utils::bit::{bitwise_count4, bitwise_count8};
2use utils::prelude::*;
3
4/// Simulating a cellular automaton on a recursive grid.
5#[derive(Clone, Debug)]
6pub struct Day24 {
7    initial: u32,
8    recursive_minutes: usize,
9}
10
11const SIDE: usize = 5;
12const TILE_COUNT: usize = SIDE * SIDE;
13const MIDDLE: usize = TILE_COUNT / 2;
14const GRID_MASK: u32 = (1 << TILE_COUNT) - 1;
15const EXAMPLE_MINUTES: usize = 10;
16const REAL_MINUTES: usize = 200;
17const LEVELS: usize = 2 * REAL_MINUTES + 3;
18const ROW_MASK: u32 = 0b1_1111;
19const COLUMN_MASK: u32 = 0b00001_00001_00001_00001_00001;
20
21impl Day24 {
22    pub fn new(input: &str, input_type: InputType) -> Result<Self, InputError> {
23        let (rows, grid_str) = parser::bitmask_n::<SIDE, u32>(b".#")
24            .repeat_n::<SIDE, _>(parser::eol())
25            .with_consumed()
26            .parse_complete(input)?;
27        let initial = rows
28            .iter()
29            .enumerate()
30            .fold(0, |acc, (row, &bits)| acc | bits << (row * SIDE));
31        if Self::bug_at(initial, MIDDLE) != 0 {
32            return Err(InputError::new(
33                input,
34                grid_str,
35                "expected '.' in the middle",
36            ));
37        }
38
39        Ok(Self {
40            initial,
41            recursive_minutes: match input_type {
42                InputType::Example => EXAMPLE_MINUTES,
43                InputType::Real => REAL_MINUTES,
44            },
45        })
46    }
47
48    #[must_use]
49    pub fn part1(&self) -> u32 {
50        // Brent's algorithm for cycle detection, as used in 2017 day 6.
51        // The first repeated layout is the start of the cycle, and its bitmask is its rating.
52        let (mut power, mut lambda) = (1, 1);
53        let mut tortoise = self.initial;
54        let mut hare = Self::flat_step(self.initial);
55
56        while tortoise != hare {
57            if power == lambda {
58                tortoise = hare;
59                power *= 2;
60                lambda = 0;
61            }
62            hare = Self::flat_step(hare);
63            lambda += 1;
64        }
65
66        tortoise = self.initial;
67        hare = self.initial;
68        for _ in 0..lambda {
69            hare = Self::flat_step(hare);
70        }
71        while tortoise != hare {
72            tortoise = Self::flat_step(tortoise);
73            hare = Self::flat_step(hare);
74        }
75
76        tortoise
77    }
78
79    #[inline]
80    fn flat_step(bugs: u32) -> u32 {
81        let [ones, twos, fours] = bitwise_count4(&Self::cardinal_neighbors(bugs));
82        Self::next_layout(bugs, [ones, twos, fours, 0]) & GRID_MASK
83    }
84
85    #[inline]
86    fn cardinal_neighbors(current: u32) -> [u32; 4] {
87        let left = (current & !(COLUMN_MASK << (SIDE - 1))) << 1;
88        let right = (current & !COLUMN_MASK) >> 1;
89        let above = current << SIDE;
90        let below = current >> SIDE;
91        [left, right, above, below]
92    }
93
94    #[inline]
95    fn next_layout(current: u32, [ones, twos, fours, eights]: [u32; 4]) -> u32 {
96        let at_least_three = (ones & twos) | fours | eights;
97        let exactly_one = ones & !at_least_three;
98        let exactly_two = twos & !at_least_three;
99        exactly_one | (!current & exactly_two)
100    }
101
102    #[must_use]
103    pub fn part2(&self) -> u32 {
104        let mut first = [0; LEVELS];
105        let mut second = [0; LEVELS];
106        let (mut levels, mut next) = (&mut first, &mut second);
107
108        let level0 = REAL_MINUTES + 1;
109        let mut start = level0 - 1;
110        let mut end = level0 + 1;
111
112        levels[level0] = self.initial;
113
114        for _ in 0..self.recursive_minutes {
115            for (next_level, adjacent) in next[start..=end]
116                .iter_mut()
117                .zip(levels[start - 1..=end + 1].windows(3))
118            {
119                *next_level = Self::recursive_step(adjacent[0], adjacent[1], adjacent[2]);
120            }
121
122            start -= usize::from(next[start] != 0);
123            end += usize::from(next[end] != 0);
124            (levels, next) = (next, levels);
125        }
126
127        levels[start..=end]
128            .iter()
129            .copied()
130            .map(u32::count_ones)
131            .sum()
132    }
133
134    #[inline]
135    fn recursive_step(outer: u32, current: u32, inner: u32) -> u32 {
136        // Tile numbering:
137        //   0  1  2  3  4
138        //   5  6  7  8  9
139        //  10 11 12 13 14
140        //  15 16 17 18 19
141        //  20 21 22 23 24
142        // Current tile 12 holds the entire inner level
143        // Outer tile 12 holds the entire current level.
144
145        let [mut left, mut right, mut above, mut below] = Self::cardinal_neighbors(current);
146
147        // Every tile in this level's left column, right column, top row or bottom row gains a
148        // neighbour from a bug in tile 11, 13, 7 or 17 of outer.
149        left |= Self::bug_at(outer, MIDDLE - 1) * COLUMN_MASK;
150        right |= Self::bug_at(outer, MIDDLE + 1) * (COLUMN_MASK << (SIDE - 1));
151        above |= Self::bug_at(outer, MIDDLE - SIDE) * ROW_MASK;
152        below |= Self::bug_at(outer, MIDDLE + SIDE) * (ROW_MASK << (TILE_COUNT - SIDE));
153
154        // Tiles 7, 11, 13 and 17 gain up to 5 neighbours each from the outside edge of inner.
155        // The bits for these tiles in the above masks are always zero (as they are shifted from
156        // the middle which is always empty), which allows packing the 5 neighbours into the 4
157        // existing masks + 4 additional masks, so bitwise_count8 can be used.
158        let [l, r, a, b] = Self::inner_edge_neighbors(inner, 0);
159        left |= l;
160        right |= r;
161        above |= a;
162        below |= b;
163
164        let mut additional = [0; 4];
165        for (mask, i) in additional.iter_mut().zip(1..SIDE) {
166            let [l, r, a, b] = Self::inner_edge_neighbors(inner, i);
167            *mask = l | r | a | b;
168        }
169
170        // The middle tile holds the inner level, so it is never a bug
171        Self::next_layout(
172            current,
173            bitwise_count8(&[
174                left,
175                right,
176                above,
177                below,
178                additional[0],
179                additional[1],
180                additional[2],
181                additional[3],
182            ]),
183        ) & (GRID_MASK ^ (1 << MIDDLE))
184    }
185
186    // The [left, right, above, below] neighbours added by tile i of each of the inner level's edges
187    #[inline]
188    fn inner_edge_neighbors(inner: u32, i: usize) -> [u32; 4] {
189        [
190            Self::bug_at(inner, i * SIDE + SIDE - 1) << (MIDDLE + 1),
191            Self::bug_at(inner, i * SIDE) << (MIDDLE - 1),
192            Self::bug_at(inner, TILE_COUNT - SIDE + i) << (MIDDLE + SIDE),
193            Self::bug_at(inner, i) << (MIDDLE - SIDE),
194        ]
195    }
196
197    #[inline]
198    fn bug_at(bugs: u32, tile: usize) -> u32 {
199        (bugs >> tile) & 1
200    }
201}
202
203examples!(Day24 -> (u32, u32) [
204    {input: "....#\n#..#.\n#..##\n..#..\n#....", part1: 2_129_920, part2: 99},
205]);