Skip to main content

year2017/
day21.rs

1use std::array;
2use utils::prelude::*;
3
4/// Iteratively applying pixel transformations.
5///
6/// The key optimization is that every three iterations a 3x3 square splits into nine independent
7/// 3x3 squares. Therefore, we can store counts for each of the 512 unique 3x3 squares and simulate
8/// three iterations at a time for each square to find the counts for the following three iterations
9#[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            // | Original      | 90° rotation  | 180° rotation | 270° rotation |
120            // | 01            | 20            | 32            | 13            |
121            // | 23            | 31            | 10            | 02            |
122            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            // | Original      | 90° rotation  | 180° rotation | 270° rotation |
137            // | 012           | 630           | 876           | 258           |
138            // | 345           | 741           | 543           | 147           |
139            // | 678           | 852           | 210           | 036           |
140            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            // | Flipped       | 90° rotation  | 180° rotation | 270° rotation |
145            // | 678           | 036           | 210           | 852           |
146            // | 345           | 147           | 543           | 741           |
147            // | 012           | 258           | 876           | 630           |
148            (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]   1  [ 2]   3     0  0  1  1
158        //   4    5    6    7     0  0  1  1
159        // [ 8]   9  [10]  11     2  2  3  3
160        //  12   13   14   15     2  2  3  3
161        [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        // [ 0]   1    2  [ 3]   4    5     [0] 0-2  [1] 0-2
167        //   6    7    8    9   10   11     [0] 3-5  [1] 3-5
168        //  12   13   14   15   16   17     [0] 6-8  [1] 6-8
169        // [18]  19   20  [21]  22   23     [2] 0-2  [3] 0-2
170        //  24   25   26   27   28   29     [2] 3-5  [3] 3-5
171        //  30   31   32   33   34   35     [2] 6-8  [3] 6-8
172        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]   1  [ 2]   3  [ 4]   5      0  0  1  1  2  2
184        //   6    7    8    9   10   11      0  0  1  1  2  2
185        // [12]  13  [14]  15  [16]  17      3  3  4  4  5  5
186        //  18   19   20   21   22   23      3  3  4  4  5  5
187        // [24]  25  [26]  27  [28]  29      6  6  7  7  8  8
188        //  30   31   32   33   34   35      6  6  7  7  8  8
189        [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) []);