1use std::array;
2use utils::prelude::*;
3
4#[derive(Clone, Debug)]
10pub struct Day21 {
11 part1: u32,
12 part2: u32,
13}
14
15#[derive(Clone, Debug)]
16enum Rule {
17 TwoToThree(usize, usize),
18 ThreeToFour(usize, usize),
19}
20
21const START_3X3: usize = 0b010_001_111;
22
23impl Day21 {
24 pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
25 let square_2x2 = parser::bitmask_n::<2, u16>(b".#")
26 .repeat_n::<2, _>(b'/')
27 .map(Self::pack_square);
28 let square_3x3 = parser::bitmask_n::<3, u16>(b".#")
29 .repeat_n::<3, _>(b'/')
30 .map(Self::pack_square);
31 let square_4x4 = parser::bitmask_n::<4, u16>(b".#")
32 .repeat_n::<4, _>(b'/')
33 .map(Self::pack_square);
34
35 let parse_iterator = parser::one_of((
36 square_3x3
37 .with_suffix(" => ")
38 .then(square_4x4)
39 .map(|(a, b)| Rule::ThreeToFour(a, b)),
40 square_2x2
41 .with_suffix(" => ")
42 .then(square_3x3)
43 .map(|(a, b)| Rule::TwoToThree(a, b)),
44 ))
45 .with_eol()
46 .parse_iterator(input);
47
48 let mut rules_2x2_to_3x3 = [0usize; 16];
49 let mut rules_3x3_to_4x4 = [0usize; 512];
50 for item in parse_iterator {
51 match item? {
52 Rule::TwoToThree(two, three) => {
53 for transformed in Self::transformations_2x2(two) {
54 rules_2x2_to_3x3[transformed] = three;
55 }
56 }
57 Rule::ThreeToFour(three, four) => {
58 for transformed in Self::transformations_3x3(three) {
59 rules_3x3_to_4x4[transformed] = four;
60 }
61 }
62 }
63 }
64
65 let (mut three_counts, mut three_counts_next) = ([0; 512], [0; 512]);
66 three_counts[START_3X3] = 1;
67
68 let mut on_pixels = [0; 21];
69 for i in (0..=18).step_by(3) {
70 for (three, &count) in three_counts.iter().enumerate().filter(|&(_, &c)| c > 0) {
71 on_pixels[i] += three.count_ones() * count;
72
73 let four = rules_3x3_to_4x4[three];
74 on_pixels[i + 1] += four.count_ones() * count;
75
76 let six = Self::combine_3x3_into_6x6(
77 Self::split_4x4_into_2x2(four).map(|two| rules_2x2_to_3x3[two]),
78 );
79 on_pixels[i + 2] += six.count_ones() * count;
80
81 for two in Self::split_6x6_into_2x2(six) {
82 let next = rules_2x2_to_3x3[two];
83 three_counts_next[next] += count;
84 }
85 }
86
87 three_counts = three_counts_next;
88 three_counts_next.fill(0);
89 }
90
91 Ok(Self {
92 part1: on_pixels[5],
93 part2: on_pixels[18],
94 })
95 }
96
97 fn pack_square<const N: usize>(rows: [u16; N]) -> usize {
98 rows.iter()
99 .enumerate()
100 .fold(0, |acc, (row, &bits)| acc | usize::from(bits) << (N * row))
101 }
102
103 #[must_use]
104 pub fn part1(&self) -> u32 {
105 self.part1
106 }
107
108 #[must_use]
109 pub fn part2(&self) -> u32 {
110 self.part2
111 }
112
113 #[inline]
114 #[expect(clippy::identity_op)]
115 fn transformations_2x2(square: usize) -> [usize; 4] {
116 let b: [_; 4] = array::from_fn(|i| (square >> i) & 1);
117
118 [
119 square,
123 (b[2] << 0) | (b[0] << 1) | (b[3] << 2) | (b[1] << 3),
124 (b[3] << 0) | (b[2] << 1) | (b[1] << 2) | (b[0] << 3),
125 (b[1] << 0) | (b[3] << 1) | (b[0] << 2) | (b[2] << 3),
126 ]
127 }
128
129 #[inline]
130 #[rustfmt::skip]
131 #[expect(clippy::identity_op)]
132 fn transformations_3x3(square: usize) -> [usize; 8] {
133 let b: [_; 9] = array::from_fn(|i| (square >> i) & 1);
134
135 [
136 square,
141 (b[6] << 0) | (b[3] << 1) | (b[0] << 2) | (b[7] << 3) | (b[4] << 4) | (b[1] << 5) | (b[8] << 6) | (b[5] << 7) | (b[2] << 8),
142 (b[8] << 0) | (b[7] << 1) | (b[6] << 2) | (b[5] << 3) | (b[4] << 4) | (b[3] << 5) | (b[2] << 6) | (b[1] << 7) | (b[0] << 8),
143 (b[2] << 0) | (b[5] << 1) | (b[8] << 2) | (b[1] << 3) | (b[4] << 4) | (b[7] << 5) | (b[0] << 6) | (b[3] << 7) | (b[6] << 8),
144 (b[6] << 0) | (b[7] << 1) | (b[8] << 2) | (b[3] << 3) | (b[4] << 4) | (b[5] << 5) | (b[0] << 6) | (b[1] << 7) | (b[2] << 8),
149 (b[0] << 0) | (b[3] << 1) | (b[6] << 2) | (b[1] << 3) | (b[4] << 4) | (b[7] << 5) | (b[2] << 6) | (b[5] << 7) | (b[8] << 8),
150 (b[2] << 0) | (b[1] << 1) | (b[0] << 2) | (b[5] << 3) | (b[4] << 4) | (b[3] << 5) | (b[8] << 6) | (b[7] << 7) | (b[6] << 8),
151 (b[8] << 0) | (b[5] << 1) | (b[2] << 2) | (b[7] << 3) | (b[4] << 4) | (b[1] << 5) | (b[6] << 6) | (b[3] << 7) | (b[0] << 8),
152 ]
153 }
154
155 #[inline]
156 fn split_4x4_into_2x2(square: usize) -> [usize; 4] {
157 [0, 2, 8, 10].map(|i| ((square >> i) & 0b11) | (((square >> (i + 4)) & 0b11) << 2))
162 }
163
164 #[inline]
165 fn combine_3x3_into_6x6(squares: [usize; 4]) -> usize {
166 let mut result = 0;
173 for (&square, offset) in squares.iter().zip([0, 3, 18, 21]) {
174 result |= ((square & 0b111) << offset)
175 | (((square >> 3) & 0b111) << (offset + 6))
176 | (((square >> 6) & 0b111) << (offset + 12));
177 }
178 result
179 }
180
181 #[inline]
182 fn split_6x6_into_2x2(square: usize) -> [usize; 9] {
183 [0, 2, 4, 12, 14, 16, 24, 26, 28]
190 .map(|i| ((square >> i) & 0b11) | (((square >> (i + 6)) & 0b11) << 2))
191 }
192}
193
194examples!(Day21 -> (u32, u32) []);