advent_of_code/year2017/
day21.rs

1use crate::input::Input;
2
3/// A 2x2 tile represented as bits. Example: "../.#" is stored as `0b_10_00`.
4#[derive(Clone, Copy, PartialEq, Eq, Hash)]
5struct Tile2 {
6    bits: u8,
7}
8
9impl Tile2 {
10    fn from(input: &str) -> Self {
11        assert_eq!(5, input.len());
12        let bytes = input.as_bytes();
13        let bits = (0..4).fold(0_u8, |acc, bit_offset| {
14            let byte_idx = bit_offset + bit_offset / 2;
15            acc + if bytes[byte_idx] == b'#' {
16                1 << bit_offset
17            } else {
18                0
19            }
20        });
21        Self { bits }
22    }
23
24    const fn rotate(self) -> Self {
25        // AB   =>   CA
26        // CD        DB
27        // First bit  (A): Shift higher 1
28        // Second bit (B): Shift higher 2
29        // Third bit  (C): Shift lower 2
30        // Fourth bit (D): Shift lower 1
31        Self {
32            bits: ((self.bits & 0b_00_01) << 1)
33                + ((self.bits & 0b_00_10) << 2)
34                + ((self.bits & 0b_01_00) >> 2)
35                + ((self.bits & 0b_10_00) >> 1),
36        }
37    }
38
39    const fn flip(self) -> Self {
40        // AB   =>   BA
41        // CD        DC
42        // First bit  (A): Shift higher 1
43        // Second bit (B): Shift lower 1
44        // Third bit  (C): Shift higher 1
45        // Fourth bit (D): Shift lower 1
46        Self {
47            bits: ((self.bits & 0b_00_01) << 1)
48                + ((self.bits & 0b_00_10) >> 1)
49                + ((self.bits & 0b_01_00) << 1)
50                + ((self.bits & 0b_10_00) >> 1),
51        }
52    }
53}
54
55/// A 3x3 tile represented as bits. Example: .#./..#/###" is stored as `0b_111_100_010`
56#[derive(Clone, Copy, PartialEq, Eq, Hash)]
57struct Tile3 {
58    bits: u16,
59}
60
61impl Tile3 {
62    fn from(input: &str) -> Self {
63        assert_eq!(11, input.len());
64        let bytes = input.as_bytes();
65        let bits = (0..9).fold(0_u16, |acc, bit_offset| {
66            let byte_idx = bit_offset + bit_offset / 3;
67            acc + if bytes[byte_idx] == b'#' {
68                1 << bit_offset
69            } else {
70                0
71            }
72        });
73        Self { bits }
74    }
75
76    const fn rotate(self) -> Self {
77        #![allow(clippy::unusual_byte_groupings)]
78        // ABC      GDA
79        // DEF  =>  HEB
80        // GHI      IFC
81        // First bit   (A): Shift higher 2
82        // Second bit  (B): Shift higher 4
83        // Third bit   (C): Shift higher 6
84        // Fourth bit  (D): Shift lower 2
85        // Fifth bit   (E): Unmodified
86        // Sixth bit   (F): Shift higher 2
87        // Seventh bit (G): Shift lower 6
88        // Eight bit   (H): Shift lower 4
89        // Ninth bit   (I): Shift lower 2
90        Self {
91            bits: ((self.bits & 0b_000_000_001) << 2)  // A
92                + ((self.bits & 0b_000_000_010) << 4)  // B
93                + ((self.bits & 0b_000_000_100) << 6)  // C
94                + ((self.bits & 0b_000_001_000) >> 2)  // D
95                + (self.bits & 0b_000_010_000)         // E
96                + ((self.bits & 0b_000_100_000) << 2)  // F
97                + ((self.bits & 0b_001_000_000) >> 6)  // G
98                + ((self.bits & 0b_010_000_000) >> 4)  // H
99                + ((self.bits & 0b_100_000_000) >> 2), // I
100        }
101    }
102
103    const fn flip(self) -> Self {
104        #![allow(clippy::unusual_byte_groupings)]
105        // ABC      CBA
106        // DEF  =>  FED
107        // GHI      IHG
108        Self {
109            bits: ((self.bits & 0b_000_000_001) << 2)
110                + (self.bits & 0b_000_000_010)
111                + ((self.bits & 0b_000_000_100) >> 2)
112                + ((self.bits & 0b_000_001_000) << 2)
113                + (self.bits & 0b_000_010_000)
114                + ((self.bits & 0b_000_100_000) >> 2)
115                + ((self.bits & 0b_001_000_000) << 2)
116                + (self.bits & 0b_010_000_000)
117                + ((self.bits & 0b_100_000_000) >> 2),
118        }
119    }
120}
121
122/// A 4x4 tile represented as bits.
123#[derive(Clone, Copy, PartialEq, Eq, Hash)]
124struct Tile4 {
125    bits: u16,
126}
127
128impl Tile4 {
129    fn from(input: &str) -> Self {
130        assert_eq!(19, input.len());
131        let bytes = input.as_bytes();
132        let bits = (0..16).fold(0_u16, |acc, bit_offset| {
133            let byte_idx = bit_offset + bit_offset / 4;
134            acc + if bytes[byte_idx] == b'#' {
135                1 << bit_offset
136            } else {
137                0
138            }
139        });
140        Self { bits }
141    }
142
143    const fn divided_up(self) -> [Tile2; 4] {
144        [
145            Tile2 {
146                // XX00
147                // XX00
148                // 0000
149                // 0000
150                bits: ((self.bits & 0b_0000_0000_0000_0011)
151                    + ((self.bits & 0b_0000_0000_0011_0000) >> 2)) as u8,
152            },
153            Tile2 {
154                // 00XX
155                // 00XX
156                // 0000
157                // 0000
158                bits: (((self.bits & 0b_0000_0000_0000_1100) >> 2)
159                    + ((self.bits & 0b_0000_0000_1100_0000) >> 4)) as u8,
160            },
161            Tile2 {
162                // 0000
163                // 0000
164                // XX00
165                // XX00
166                bits: (((self.bits & 0b_0000_0011_0000_0000) >> 8)
167                    + ((self.bits & 0b_0011_0000_0000_0000) >> 10)) as u8,
168            },
169            Tile2 {
170                // 0000
171                // 0000
172                // 00XX
173                // 00XX
174                bits: (((self.bits & 0b_0000_1100_0000_0000) >> 10)
175                    + ((self.bits & 0b_1100_0000_0000_0000) >> 12)) as u8,
176            },
177        ]
178    }
179}
180
181pub fn solve(input: &Input) -> Result<u32, String> {
182    #![allow(clippy::unusual_byte_groupings, clippy::unreadable_literal)]
183    let mut from_2_to_3 = [Tile3 { bits: 0 }; 16];
184    let mut from_3_to_4 = [Tile4 { bits: 0 }; 512];
185
186    for (line_idx, line) in input.text.lines().enumerate() {
187        let on_error = || format!("Line {}: Invalid format", line_idx + 1);
188
189        let mut parts = line.splitn(2, " => ");
190        let from = parts.next().ok_or_else(on_error)?;
191        let to = parts.next().ok_or_else(on_error)?;
192
193        match (from.len(), to.len()) {
194            (5, 11) => {
195                // ../.. => #../##./...
196                let from = Tile2::from(from);
197                let to = Tile3::from(to);
198                from_2_to_3[usize::from(from.bits)] = to;
199                from_2_to_3[usize::from(from.rotate().bits)] = to;
200                from_2_to_3[usize::from(from.rotate().rotate().bits)] = to;
201                from_2_to_3[usize::from(from.rotate().rotate().rotate().bits)] = to;
202                from_2_to_3[usize::from(from.flip().bits)] = to;
203                from_2_to_3[usize::from(from.flip().rotate().bits)] = to;
204                from_2_to_3[usize::from(from.flip().rotate().rotate().bits)] = to;
205                from_2_to_3[usize::from(from.flip().rotate().rotate().rotate().bits)] = to;
206            }
207            (11, 19) => {
208                // .../.../... => ##../#.../..../..#.
209                let from = Tile3::from(from);
210                let to = Tile4::from(to);
211                from_3_to_4[usize::from(from.bits)] = to;
212                from_3_to_4[usize::from(from.rotate().bits)] = to;
213                from_3_to_4[usize::from(from.rotate().rotate().bits)] = to;
214                from_3_to_4[usize::from(from.rotate().rotate().rotate().bits)] = to;
215                from_3_to_4[usize::from(from.flip().bits)] = to;
216                from_3_to_4[usize::from(from.flip().rotate().bits)] = to;
217                from_3_to_4[usize::from(from.flip().rotate().rotate().bits)] = to;
218                from_3_to_4[usize::from(from.flip().rotate().rotate().rotate().bits)] = to;
219            }
220            _ => {
221                return Err(on_error());
222            }
223        }
224    }
225
226    let initial_tile = Tile3::from(".#./..#/###");
227    let mut current_2_tiles: Vec<Tile2> = Vec::new();
228    let mut current_3_tiles = vec![initial_tile];
229    let mut current_4_tiles: Vec<Tile4> = Vec::new();
230
231    let num_iterations = input.part_values(5, 18);
232
233    for iteration in 0..num_iterations {
234        match iteration % 3 {
235            0 => {
236                // Map each 3x3 matrix to a 4x4 one:
237                current_4_tiles = current_3_tiles
238                    .iter()
239                    .map(|&tile| from_3_to_4[usize::from(tile.bits)])
240                    .collect();
241            }
242            1 => {
243                current_2_tiles.clear();
244
245                for tile4 in &current_4_tiles {
246                    // Split up a 4x4 matrix into four 2x2 ones:
247                    let tile2_parts = tile4.divided_up();
248                    // Map each 2x2 matrix to the resulting 3x3 matrix:
249                    let tile3_parts: Vec<Tile3> = tile2_parts
250                        .iter()
251                        .map(|&tile| from_2_to_3[usize::from(tile.bits)])
252                        .collect();
253
254                    // From the four 3x3 matrices, build the resulting nine 2x2 ones:
255                    //
256                    // AAABBB
257                    // AAABBB
258                    // AAABBB
259                    // CCCDDD
260                    // CCCDDD
261                    // CCCDDD
262
263                    // Upper row of 2x2:
264                    current_2_tiles.push(Tile2 {
265                        bits: (tile3_parts[0].bits & 0b11 | (tile3_parts[0].bits & 0b11000) >> 1)
266                            as u8,
267                    });
268                    current_2_tiles.push(Tile2 {
269                        bits: (((tile3_parts[0].bits & 0b100) >> 2)
270                            | ((tile3_parts[1].bits & 0b1) << 1)
271                            | ((tile3_parts[0].bits & 0b100000) >> 3)
272                            | (tile3_parts[1].bits & 0b1000)) as u8,
273                    });
274                    current_2_tiles.push(Tile2 {
275                        bits: (((tile3_parts[1].bits & 0b110) >> 1)
276                            | ((tile3_parts[1].bits & 0b110000) >> 2))
277                            as u8,
278                    });
279
280                    // Middle row of 2x2:
281                    current_2_tiles.push(Tile2 {
282                        bits: (((tile3_parts[0].bits & 0b11000000) >> 6)
283                            | ((tile3_parts[2].bits & 0b11) << 2))
284                            as u8,
285                    });
286                    current_2_tiles.push(Tile2 {
287                        bits: (((tile3_parts[0].bits & 0b100000000) >> 8)
288                            | ((tile3_parts[1].bits & 0b1000000) >> 5)
289                            | (tile3_parts[2].bits & 0b100)
290                            | ((tile3_parts[3].bits & 0b1) << 3))
291                            as u8,
292                    });
293                    current_2_tiles.push(Tile2 {
294                        bits: (((tile3_parts[1].bits & 0b110000000) >> 7)
295                            | ((tile3_parts[3].bits & 0b110) << 1))
296                            as u8,
297                    });
298
299                    // Bottom row of 2x2:
300                    current_2_tiles.push(Tile2 {
301                        bits: (((tile3_parts[2].bits & 0b11000) >> 3)
302                            | ((tile3_parts[2].bits & 0b11000000) >> 4))
303                            as u8,
304                    });
305                    current_2_tiles.push(Tile2 {
306                        bits: (((tile3_parts[2].bits & 0b100000) >> 5)
307                            | ((tile3_parts[3].bits & 0b1000) >> 2)
308                            | ((tile3_parts[2].bits & 0b100000000) >> 6)
309                            | ((tile3_parts[3].bits & 0b1000000) >> 3))
310                            as u8,
311                    });
312                    current_2_tiles.push(Tile2 {
313                        bits: (((tile3_parts[3].bits & 0b110000) >> 4)
314                            | ((tile3_parts[3].bits & 0b110000000) >> 5))
315                            as u8,
316                    });
317                }
318            }
319            2 => {
320                // Map each 2x2 matrix to a 3x3 one:
321                current_3_tiles = current_2_tiles
322                    .iter()
323                    .map(|tile| from_2_to_3[usize::from(tile.bits)])
324                    .collect();
325            }
326            _ => {
327                return Err("Internal error".to_string());
328            }
329        }
330    }
331
332    Ok(if input.is_part_one() {
333        current_2_tiles
334            .iter()
335            .map(|tile| tile.bits.count_ones())
336            .sum()
337    } else {
338        current_3_tiles
339            .iter()
340            .map(|tile| tile.bits.count_ones())
341            .sum()
342    })
343}
344
345#[test]
346pub fn tile_tests() {
347    #![allow(clippy::unusual_byte_groupings)]
348    let tile = Tile2::from("##/.#");
349    assert_eq!(0b_10_11, tile.bits);
350    assert_eq!(tile.bits, tile.rotate().rotate().rotate().rotate().bits);
351    assert_eq!(tile.bits, tile.flip().flip().bits);
352    // ##   =>   .#
353    // .#        ##
354    let rotated_tile = tile.rotate();
355    assert_eq!(Tile2::from(".#/##").bits, rotated_tile.bits);
356
357    let flipped_tile = tile.flip();
358    assert_eq!(Tile2::from("##/#.").bits, flipped_tile.bits);
359
360    let tile = Tile2::from("##/##");
361    assert_eq!(0b_11_11, tile.bits);
362    assert_eq!(tile.bits, tile.rotate().rotate().rotate().rotate().bits);
363    assert_eq!(tile.bits, tile.flip().flip().bits);
364
365    let tile = Tile3::from("##./.#./##.");
366    assert_eq!(0b_011_010_011, tile.bits);
367    assert_eq!(tile.bits, tile.rotate().rotate().rotate().rotate().bits);
368    assert_eq!(tile.bits, tile.flip().flip().bits);
369    // ##.        #.#
370    // .#.   =>   ###
371    // ##.        ...
372    let rotated_tile = tile.rotate();
373    assert_eq!(Tile3::from("#.#/###/...").bits, rotated_tile.bits);
374
375    let flipped_tile = tile.flip();
376    assert_eq!(Tile3::from(".##/.#./.##").bits, flipped_tile.bits);
377
378    let tile = Tile4::from("####/.###/..../#.#.");
379    assert_eq!(0b_0101_0000_1110_1111, tile.bits);
380
381    let tile = Tile4::from("#..#/..../..../#..#");
382    assert_eq!(0b_1001_0000_0000_1001, tile.bits);
383}
384
385#[test]
386pub fn tests() {
387    use crate::input::{test_part_one, test_part_two};
388
389    let real_input = include_str!("day21_input.txt");
390    test_part_one!(real_input => 142);
391    test_part_two!(real_input => 1_879_071);
392}
advent_of_code/year2017/day21.rs

advent_of_code/year2017/
day21.rs
