Skip to main content

year2020/
day20.rs

1use utils::prelude::*;
2
3/// Matching image tiles and finding a pattern.
4///
5/// The key optimization is that each edge is on at most two tiles, so XOR can be used to find the
6/// next tile.
7#[derive(Clone, Debug)]
8pub struct Day20 {
9    image: Vec<u128>,
10    part1: u64,
11}
12
13#[derive(Clone, Copy, Debug)]
14struct Tile {
15    id: u16,
16    pixels: u64,
17    edges: [u16; 4],
18}
19
20const MAX_SIZE: usize = u128::BITS as usize / 8;
21
22impl Day20 {
23    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
24        let tiles = parser::digits_range!(1000..=9999)
25            .with_prefix("Tile ")
26            .with_suffix(b':')
27            .with_eol()
28            .then(parser::bitmask_n::<10, u16>(b".#").repeat_n::<10, _>(parser::eol()))
29            .map(|(id, rows)| Tile {
30                id,
31                pixels: rows[1..9].iter().rfold(0, |pixels, &row| {
32                    (pixels << 8) | u64::from((row >> 1) & 0xFF)
33                }),
34                edges: [
35                    rows[0],
36                    rows.iter().rfold(0, |edge, &row| (edge << 1) | (row >> 9)),
37                    rows[9],
38                    rows.iter().rfold(0, |edge, &row| (edge << 1) | (row & 1)),
39                ],
40            })
41            .with_consumed()
42            .with_eol()
43            .parse_lines(input)?;
44
45        let size = tiles.len().isqrt();
46        if !(3..=MAX_SIZE).contains(&size) || size * size != tiles.len() {
47            return Err(InputError::new(
48                input,
49                0,
50                "expected a 3x3 to 16x16 square of tiles",
51            ));
52        }
53
54        let mut ids = [0u64; 10000usize.div_ceil(64)];
55        let mut counts = [0u8; 1024];
56        let mut edge_tiles = [0usize; 1024];
57        for (tile_idx, &(tile, tile_str)) in tiles.iter().enumerate() {
58            let id = usize::from(tile.id);
59            let bit = 1 << (id % 64);
60            if ids[id / 64] & bit != 0 {
61                return Err(InputError::new(input, tile_str, "duplicate tile id"));
62            }
63            ids[id / 64] |= bit;
64
65            for edge_idx in tile.edges.map(edge_index) {
66                if counts[edge_idx] == 2 {
67                    return Err(InputError::new(
68                        input,
69                        tile_str,
70                        "expected each edge on at most two tiles",
71                    ));
72                }
73                counts[edge_idx] += 1;
74                edge_tiles[edge_idx] ^= tile_idx;
75            }
76        }
77
78        let Some(corner) = tiles.iter().position(|(tile, _)| {
79            tile.edges
80                .iter()
81                .filter(|&&e| counts[edge_index(e)] == 1)
82                .count()
83                == 2
84        }) else {
85            return Err(InputError::new(input, 0, "expected a corner tile"));
86        };
87
88        let mut above_edges = [None; MAX_SIZE];
89        let mut row_start = corner;
90        let mut part1 = 1;
91        let mut image = vec![[0u8; MAX_SIZE]; size * 8];
92        for y in 0..size {
93            let mut tile_idx = row_start;
94            let mut left_edge = None;
95            for x in 0..size {
96                let (tile, tile_str) = tiles[tile_idx];
97
98                let id = usize::from(tile.id);
99                let bit = 1 << (id % 64);
100                if ids[id / 64] & bit == 0 {
101                    return Err(InputError::new(input, tile_str, "duplicate tile in image"));
102                }
103                ids[id / 64] ^= bit;
104
105                let Some(tile) = tile.fit(above_edges[x], left_edge, &counts) else {
106                    return Err(InputError::new(input, tile_str, "tile does not fit"));
107                };
108
109                left_edge = Some(tile.edges[1]);
110                above_edges[x] = Some(tile.edges[2]);
111                if x == 0 {
112                    row_start = edge_tiles[edge_index(tile.edges[2])] ^ tile_idx;
113                }
114                tile_idx ^= edge_tiles[edge_index(tile.edges[1])];
115
116                if (x == 0 || x == size - 1) && (y == 0 || y == size - 1) {
117                    part1 *= u64::from(tile.id);
118                }
119
120                for (i, row) in image[y * 8..y * 8 + 8].iter_mut().enumerate() {
121                    row[x] = (tile.pixels >> (i * 8)) as u8;
122                }
123            }
124        }
125
126        Ok(Self {
127            image: image.into_iter().map(u128::from_le_bytes).collect(),
128            part1,
129        })
130    }
131
132    #[must_use]
133    pub fn part1(&self) -> u64 {
134        self.part1
135    }
136
137    #[must_use]
138    pub fn part2(&self) -> u32 {
139        let mut monsters = vec![0u128; self.image.len()];
140        self.find_monsters::<0>(&mut monsters);
141        self.find_monsters::<1>(&mut monsters);
142        self.find_monsters::<2>(&mut monsters);
143        self.find_monsters::<3>(&mut monsters);
144        self.find_monsters::<4>(&mut monsters);
145        self.find_monsters::<5>(&mut monsters);
146        self.find_monsters::<6>(&mut monsters);
147        self.find_monsters::<7>(&mut monsters);
148
149        self.image.iter().map(|r| r.count_ones()).sum::<u32>()
150            - monsters.iter().map(|r| r.count_ones()).sum::<u32>()
151    }
152
153    fn find_monsters<const ORIENTATION: usize>(&self, monsters: &mut [u128]) {
154        //                   #
155        // #    ##    ##    ###
156        //  #  #  #  #  #  #
157        #[rustfmt::skip]
158        let mut pattern = [
159            (18, 0),
160            (0, 1), (5, 1), (6, 1), (11, 1), (12, 1), (17, 1), (18, 1), (19, 1),
161            (1, 2), (4, 2), (7, 2), (10, 2), (13, 2), (16, 2),
162        ];
163        for (x, y) in &mut pattern {
164            if ORIENTATION & 1 != 0 {
165                // Flip horizontally
166                *x = 19 - *x;
167            }
168            if ORIENTATION & 2 != 0 {
169                // Flip vertically
170                *y = 2 - *y;
171            }
172            if ORIENTATION & 4 != 0 {
173                // Transpose
174                (*x, *y) = (*y, *x);
175            }
176        }
177        let rows = if ORIENTATION & 4 == 0 { 3 } else { 20 };
178
179        for y in 0..=self.image.len() - rows {
180            let mut positions = u128::MAX;
181            for &(dx, dy) in &pattern {
182                // Keep x bits only where (x + dx, y + dy) is set
183                positions &= self.image[y + dy] >> dx;
184                if positions == 0 {
185                    break;
186                }
187            }
188
189            if positions != 0 {
190                for &(dx, dy) in &pattern {
191                    monsters[y + dy] |= positions << dx;
192                }
193            }
194        }
195    }
196}
197
198impl Tile {
199    fn fit(self, top: Option<u16>, left: Option<u16>, counts: &[u8; 1024]) -> Option<Self> {
200        'orientations: for orientation in 0..8 {
201            let [mut t, mut r, mut b, mut l] = self.edges;
202            if orientation & 1 != 0 {
203                // Flip horizontally
204                (t, r, b, l) = (reverse(t), l, reverse(b), r);
205            }
206            if orientation & 2 != 0 {
207                // Flip vertically
208                (t, r, b, l) = (b, reverse(r), t, reverse(l));
209            }
210            if orientation & 4 != 0 {
211                // Transpose
212                (t, r, b, l) = (l, b, r, t);
213            }
214
215            for (edge, other) in [(l, left), (t, top)] {
216                if other != Some(edge) && !(other.is_none() && counts[edge_index(edge)] == 1) {
217                    continue 'orientations;
218                }
219            }
220
221            let mut pixels = self.pixels;
222            if orientation & 1 != 0 {
223                pixels = pixels.reverse_bits().swap_bytes();
224            }
225            if orientation & 2 != 0 {
226                pixels = pixels.swap_bytes();
227            }
228            if orientation & 4 != 0 {
229                pixels = transpose(pixels);
230            }
231
232            return Some(Self {
233                id: self.id,
234                pixels,
235                edges: [t, r, b, l],
236            });
237        }
238        None
239    }
240}
241
242fn transpose(pixels: u64) -> u64 {
243    // Swap the top right and bottom left in each 2x2 block
244    // .a.a.a.a
245    // b.b.b.b.
246    // .a.a.a.a
247    // b.b.b.b.
248    // .a.a.a.a
249    // b.b.b.b.
250    // .a.a.a.a
251    // b.b.b.b.
252    let pixels = delta_swap(pixels, 0x00AA_00AA_00AA_00AA, 7);
253
254    // Swap the top right and bottom left in each 4x4 block
255    // ..aa..aa
256    // ..aa..aa
257    // bb..bb..
258    // bb..bb..
259    // ..aa..aa
260    // ..aa..aa
261    // bb..bb..
262    // bb..bb..
263    let pixels = delta_swap(pixels, 0x0000_CCCC_0000_CCCC, 14);
264
265    // Swap the top right and bottom left
266    // ....aaaa
267    // ....aaaa
268    // ....aaaa
269    // ....aaaa
270    // bbbb....
271    // bbbb....
272    // bbbb....
273    // bbbb....
274    delta_swap(pixels, 0x0000_0000_F0F0_F0F0, 28)
275}
276
277fn delta_swap(x: u64, mask: u64, shift: u32) -> u64 {
278    // Swap each bit in mask with the bit shift places after it
279    let swap = (x ^ (x >> shift)) & mask;
280    x ^ swap ^ (swap << shift)
281}
282
283fn edge_index(edge: u16) -> usize {
284    usize::from(edge.min(reverse(edge)))
285}
286
287fn reverse(edge: u16) -> u16 {
288    // Using a precomputed table is ~20% faster
289    const REVERSED: [u16; 1024] = {
290        let mut table = [0; 1024];
291        let mut i = 0;
292        while i < 1024 {
293            table[i] = (i as u16).reverse_bits() >> 6;
294            i += 1;
295        }
296        table
297    };
298    REVERSED[usize::from(edge & 1023)]
299}
300
301examples!(Day20 -> (u64, u32) [
302    {file: "day20_example0.txt", part1: 20899048083289, part2: 273},
303]);