year2017/
day21.rs

1use std::array;
2use utils::parser::{ParseError, ParseResult};
3use utils::prelude::*;
4
5/// Iteratively applying pixel transformations.
6///
7/// The key optimization is that every three iterations a 3x3 square splits into nine independent
8/// 3x3 squares. Therefore, we can store counts for each of the 512 unique 3x3 squares and simulate
9/// three iterations at a time for each square to find the counts for the following three iterations
10#[derive(Clone, Debug)]
11pub struct Day21 {
12    part1: u32,
13    part2: u32,
14}
15
16#[derive(Clone, Debug)]
17enum Rule {
18    TwoToThree(usize, usize),
19    ThreeToFour(usize, usize),
20}
21
22const START_3X3: usize = 0b010_001_111;
23
24impl Day21 {
25    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
26        let parse_iterator = parser::one_of((
27            Self::parse_square::<3>
28                .with_suffix(" => ")
29                .then(Self::parse_square::<4>)
30                .map(|(a, b)| Rule::ThreeToFour(a, b)),
31            Self::parse_square::<2>
32                .with_suffix(" => ")
33                .then(Self::parse_square::<3>)
34                .map(|(a, b)| Rule::TwoToThree(a, b)),
35        ))
36        .with_suffix(parser::eol())
37        .parse_iterator(input);
38
39        let mut rules_2x2_to_3x3 = [0usize; 16];
40        let mut rules_3x3_to_4x4 = [0usize; 512];
41        for item in parse_iterator {
42            match item? {
43                Rule::TwoToThree(two, three) => {
44                    for transformed in Self::transformations_2x2(two) {
45                        rules_2x2_to_3x3[transformed] = three;
46                    }
47                }
48                Rule::ThreeToFour(three, four) => {
49                    for transformed in Self::transformations_3x3(three) {
50                        rules_3x3_to_4x4[transformed] = four;
51                    }
52                }
53            }
54        }
55
56        let (mut three_counts, mut three_counts_next) = ([0; 512], [0; 512]);
57        three_counts[START_3X3] = 1;
58
59        let mut on_pixels = [0; 21];
60        for i in (0..=18).step_by(3) {
61            for (three, &count) in three_counts.iter().enumerate().filter(|&(_, &c)| c > 0) {
62                on_pixels[i] += three.count_ones() * count;
63
64                let four = rules_3x3_to_4x4[three];
65                on_pixels[i + 1] += four.count_ones() * count;
66
67                let six = Self::combine_3x3_into_6x6(
68                    Self::split_4x4_into_2x2(four).map(|two| rules_2x2_to_3x3[two]),
69                );
70                on_pixels[i + 2] += six.count_ones() * count;
71
72                for two in Self::split_6x6_into_2x2(six) {
73                    let next = rules_2x2_to_3x3[two];
74                    three_counts_next[next] += count;
75                }
76            }
77
78            three_counts = three_counts_next;
79            three_counts_next.fill(0);
80        }
81
82        Ok(Self {
83            part1: on_pixels[5],
84            part2: on_pixels[18],
85        })
86    }
87
88    #[must_use]
89    pub fn part1(&self) -> u32 {
90        self.part1
91    }
92
93    #[must_use]
94    pub fn part2(&self) -> u32 {
95        self.part2
96    }
97
98    #[inline]
99    fn parse_square<const N: usize>(mut input: &[u8]) -> ParseResult<usize> {
100        let mut result = 0;
101        for row in 0..N {
102            for col in 0..N {
103                match input.first() {
104                    Some(b'.') => {}
105                    Some(b'#') => result |= 1 << (col + N * row),
106                    _ => return Err((ParseError::Custom("expected '.' or '#'"), input)),
107                }
108                input = &input[1..];
109            }
110
111            if row < N - 1 {
112                if input.first().copied() != Some(b'/') {
113                    return Err((ParseError::Custom("expected '/'"), input));
114                }
115                input = &input[1..];
116            }
117        }
118
119        Ok((result, input))
120    }
121
122    #[inline]
123    #[expect(clippy::identity_op)]
124    fn transformations_2x2(square: usize) -> [usize; 4] {
125        let b: [_; 4] = array::from_fn(|i| (square >> i) & 1);
126
127        [
128            // | Original      | 90° rotation  | 180° rotation | 270° rotation |
129            // | 01            | 20            | 32            | 13            |
130            // | 23            | 31            | 10            | 02            |
131            square,
132            (b[2] << 0) | (b[0] << 1) | (b[3] << 2) | (b[1] << 3),
133            (b[3] << 0) | (b[2] << 1) | (b[1] << 2) | (b[0] << 3),
134            (b[1] << 0) | (b[3] << 1) | (b[0] << 2) | (b[2] << 3),
135        ]
136    }
137
138    #[inline]
139    #[rustfmt::skip]
140    #[expect(clippy::identity_op)]
141    fn transformations_3x3(square: usize) -> [usize; 8] {
142        let b: [_; 9] = array::from_fn(|i| (square >> i) & 1);
143
144        [
145            // | Original      | 90° rotation  | 180° rotation | 270° rotation |
146            // | 012           | 630           | 876           | 258           |
147            // | 345           | 741           | 543           | 147           |
148            // | 678           | 852           | 210           | 036           |
149            square,
150            (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),
151            (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),
152            (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),
153            // | Flipped       | 90° rotation  | 180° rotation | 270° rotation |
154            // | 678           | 036           | 210           | 852           |
155            // | 345           | 147           | 543           | 741           |
156            // | 012           | 258           | 876           | 630           |
157            (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),
158            (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),
159            (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),
160            (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),
161        ]
162    }
163
164    #[inline]
165    fn split_4x4_into_2x2(square: usize) -> [usize; 4] {
166        // [ 0]   1  [ 2]   3     0  0  1  1
167        //   4    5    6    7     0  0  1  1
168        // [ 8]   9  [10]  11     2  2  3  3
169        //  12   13   14   15     2  2  3  3
170        [0, 2, 8, 10].map(|i| ((square >> i) & 0b11) | (((square >> (i + 4)) & 0b11) << 2))
171    }
172
173    #[inline]
174    fn combine_3x3_into_6x6(squares: [usize; 4]) -> usize {
175        // [ 0]   1    2  [ 3]   4    5     [0] 0-2  [1] 0-2
176        //   6    7    8    9   10   11     [0] 3-5  [1] 3-5
177        //  12   13   14   15   16   17     [0] 6-8  [1] 6-8
178        // [18]  19   20  [21]  22   23     [2] 0-2  [3] 0-2
179        //  24   25   26   27   28   29     [2] 3-5  [3] 3-5
180        //  30   31   32   33   34   35     [2] 6-8  [3] 6-8
181        let mut result = 0;
182        for (&square, offset) in squares.iter().zip([0, 3, 18, 21]) {
183            result |= ((square & 0b111) << offset)
184                | (((square >> 3) & 0b111) << (offset + 6))
185                | (((square >> 6) & 0b111) << (offset + 12));
186        }
187        result
188    }
189
190    #[inline]
191    fn split_6x6_into_2x2(square: usize) -> [usize; 9] {
192        // [ 0]   1  [ 2]   3  [ 4]   5      0  0  1  1  2  2
193        //   6    7    8    9   10   11      0  0  1  1  2  2
194        // [12]  13  [14]  15  [16]  17      3  3  4  4  5  5
195        //  18   19   20   21   22   23      3  3  4  4  5  5
196        // [24]  25  [26]  27  [28]  29      6  6  7  7  8  8
197        //  30   31   32   33   34   35      6  6  7  7  8  8
198        [0, 2, 4, 12, 14, 16, 24, 26, 28]
199            .map(|i| ((square >> i) & 0b11) | (((square >> (i + 6)) & 0b11) << 2))
200    }
201}
202
203examples!(Day21 -> (u32, u32) []);
year2017/day21.rs

year2017/
day21.rs
