1use utils::bit::{bitwise_count4, bitwise_count8};
2use utils::prelude::*;
3
4#[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 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 let [mut left, mut right, mut above, mut below] = Self::cardinal_neighbors(current);
146
147 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 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 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 #[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]);