aoc/year2020/
day20.rs

1//! # Jurassic Jigsaw
2//!
3//! At first this seems like a daunting problem. However a little analysis shows that the input
4//! has some nice properties that makes solving this more tractable.
5//!
6//! * Tile edges match with at most one other tile
7//! * The forward and reverse tile edges form two distinct sets of 312 values with no overlap.
8//!
9//! Tiles can be flipped and rotated for a total of 8 possible permutations each. When parsing
10//! the tiles we store all 8 edge possibilities to enable assembling the jigsaw in part two. For
11//! performance we avoid transforming the inner 8x8 pixels until we have determined the
12//! layout of the grid.
13
14//!
15//! ## Part One
16//!
17//! First we calculate the frequency of each edge, both forward and backward as tiles can be in
18//! any orientation. As there are only 2¹⁰ or 1024 possible edge values we can use an array instead of a
19//! hash table for speed, converting the edges into a binary number to index the array.
20//!
21//! This results in 96 values that occur once and 528 values that occur twice. Then for every tile
22//! we sum the frequency of each edge. Corner tiles will have two edges that only occur once, not
23//! matching with any other tile, for a total of 1 + 1 + 2 + 2 = 6.
24//!
25//! Other edge tiles have a total of 1 + 2 + 2 + 2 = 7 and inner tiles a total of 2 + 2 + 2 + 2 = 8.
26//!
27//! ## Part Two
28//!
29//! First we arbitrarily pick any corner tile that is oriented so that its unique edges are facing
30//! top and left. Then we proceed row by row, looking up the next tile to the right. Each time
31//! we find a tile we remove it from the remaining tiles, so that looking up a tile is always a
32//! very fast constant time `O(1)` operation.
33//!
34//! The complete picture is stored as an array of `u128` values as the tiles form a square 12 wide,
35//! for a total of 12 * 8 = 96 pixels. As we add each tile, we convert its pixels into a `u8` binary
36//! number and left shift to add to the existing pixels.
37//!
38//! When finding the monsters we make some further assumptions about the input:
39//!
40//! * The monsters will all be oriented the same way
41//! * Monsters will not overlap with each other
42//!
43//! For speed the monster bit patterns are rotated and flipped instead of the image, then stored
44//! in hardcoded arrays. The search ends as soon as we find monsters in any orientation.
45use crate::util::parse::*;
46use std::array::from_fn;
47
48pub struct Tile {
49    id: u64,
50    top: [usize; 8],
51    left: [usize; 8],
52    bottom: [usize; 8],
53    right: [usize; 8],
54    pixels: [[u8; 10]; 10],
55}
56
57impl Tile {
58    // O = Original
59    // H = Flip horizontal
60    // V = Flip vertical
61    // R = Rotate clockwise 90 degrees
62    // Sequence: [O, H, V, HV, R, RH, RV, RHV]
63    const COEFFICIENTS: [[i32; 6]; 8] = [
64        [1, 0, 1, 0, 1, 1],
65        [-1, 0, 8, 0, 1, 1],
66        [1, 0, 1, 0, -1, 8],
67        [-1, 0, 8, 0, -1, 8],
68        [0, 1, 1, -1, 0, 8],
69        [0, 1, 1, 1, 0, 1],
70        [0, -1, 8, -1, 0, 8],
71        [0, -1, 8, 1, 0, 1],
72    ];
73
74    fn from(chunk: &[&str]) -> Tile {
75        let id = (&chunk[0][5..9]).unsigned();
76
77        let pixels: [[u8; 10]; 10] = from_fn(|i| chunk[i + 1].as_bytes().try_into().unwrap());
78
79        // The ASCII code for "#" 35 is odd and the code for "." 46 is even
80        // so we can convert to a 1 or 0 bit using bitwise AND with 1.
81        let binary = |row: usize, col: usize| (pixels[row][col] & 1) as usize;
82        let mut t = 0;
83        let mut l = 0;
84        let mut b = 0;
85        let mut r = 0;
86
87        for i in 0..10 {
88            t = (t << 1) | binary(0, i);
89            l = (l << 1) | binary(i, 0);
90            b = (b << 1) | binary(9, i);
91            r = (r << 1) | binary(i, 9);
92        }
93
94        let reverse = |edge: usize| edge.reverse_bits() >> 54;
95        let rt = reverse(t);
96        let rl = reverse(l);
97        let rb = reverse(b);
98        let rr = reverse(r);
99
100        // Same transform sequence as coefficients:
101        // [O, H, V, HV, R, RH, RV, RHV]
102        let top = [t, rt, b, rb, rl, l, rr, r];
103        let left = [l, r, rl, rr, b, t, rb, rt];
104        let bottom = [b, rb, t, rt, rr, r, rl, l];
105        let right = [r, l, rr, rl, t, b, rt, rb];
106
107        Tile { id, top, left, bottom, right, pixels }
108    }
109
110    // Coefficients allow us to reuse the loop logic for each of the 8 possible permutations.
111    fn transform(&self, image: &mut [u128], permutation: usize) {
112        let [a, b, c, d, e, f] = Self::COEFFICIENTS[permutation];
113
114        for row in 0..8 {
115            let mut acc = 0;
116
117            for col in 0..8 {
118                let x = a * col + b * row + c;
119                let y = d * col + e * row + f;
120                let b = self.pixels[y as usize][x as usize];
121                acc = (acc << 1) | (b & 1);
122            }
123
124            image[row as usize] = (image[row as usize] << 8) | (acc as u128);
125        }
126    }
127}
128
129pub fn parse(input: &str) -> Vec<Tile> {
130    let lines: Vec<_> = input.lines().collect();
131    lines.chunks(12).map(Tile::from).collect()
132}
133
134pub fn part1(input: &[Tile]) -> u64 {
135    let mut freq = [0; 1024];
136    let mut result = 1;
137
138    for tile in input {
139        for edge in tile.top {
140            freq[edge] += 1;
141        }
142    }
143
144    for tile in input {
145        // Any orientation will do, pick the first.
146        let total =
147            freq[tile.top[0]] + freq[tile.left[0]] + freq[tile.bottom[0]] + freq[tile.right[0]];
148        if total == 6 {
149            result *= tile.id;
150        }
151    }
152
153    result
154}
155
156pub fn part2(input: &[Tile]) -> u32 {
157    // Store mapping of tile edges to tile index in order to allow
158    // constant time lookup by edge when assembling the jigsaw.
159    let mut edge_to_tile = [[0; 2]; 1024];
160    let mut freq = [0; 1024];
161    let mut placed = [false; 1024];
162
163    for (i, tile) in input.iter().enumerate() {
164        for edge in tile.top {
165            edge_to_tile[edge][freq[edge]] = i;
166            freq[edge] += 1;
167        }
168    }
169
170    let mut find_arbitrary_corner = || {
171        for tile in input {
172            for j in 0..8 {
173                if freq[tile.top[j]] == 1 && freq[tile.left[j]] == 1 {
174                    freq[tile.top[j]] += 1;
175                    return tile.top[j];
176                }
177            }
178        }
179        unreachable!()
180    };
181    let mut find_matching_tile = |edge: usize| {
182        let [first, second] = edge_to_tile[edge];
183        let next = if placed[first] { second } else { first };
184        placed[next] = true;
185        &input[next]
186    };
187
188    // Assemble the image
189    let mut next_top = find_arbitrary_corner();
190    let mut image = [0; 96];
191    let mut index = 0;
192
193    while freq[next_top] == 2 {
194        let tile = find_matching_tile(next_top);
195        let permutation = (0..8).position(|i| tile.top[i] == next_top).unwrap();
196        tile.transform(&mut image[index..], permutation);
197        next_top = tile.bottom[permutation];
198
199        let mut next_left = tile.right[permutation];
200
201        while freq[next_left] == 2 {
202            let tile = find_matching_tile(next_left);
203            let permutation = (0..8).position(|i| tile.left[i] == next_left).unwrap();
204            tile.transform(&mut image[index..], permutation);
205            next_left = tile.right[permutation];
206        }
207
208        index += 8;
209    }
210
211    // Common search logic
212    let sea: u32 = image.iter().map(|n| n.count_ones()).sum();
213    let find = |monster: &mut [u128], width: usize, height: usize| {
214        let mut rough = sea;
215
216        for _ in 0..(96 - width + 1) {
217            for window in image.windows(height) {
218                if monster.iter().enumerate().all(|(i, &n)| n & window[i] == n) {
219                    rough -= 15;
220                }
221            }
222            monster.iter_mut().for_each(|n| *n <<= 1);
223        }
224
225        (rough < sea).then_some(rough)
226    };
227
228    // Transform the monsters instead of the image.
229    // Hardcoded bit patterns for [O, H, V, HV].
230    let mut monsters = [
231        [0b00000000000000000010, 0b10000110000110000111, 0b01001001001001001000],
232        [0b01001001001001001000, 0b10000110000110000111, 0b00000000000000000010],
233        [0b01000000000000000000, 0b11100001100001100001, 0b00010010010010010010],
234        [0b00010010010010010010, 0b11100001100001100001, 0b01000000000000000000],
235    ];
236
237    for monster in &mut monsters {
238        if let Some(rough) = find(monster, 20, 3) {
239            return rough;
240        }
241    }
242
243    // Hardcoded bit patterns [R, RH, RV, RHV].
244    let mut monsters = [
245        [2, 4, 0, 0, 4, 2, 2, 4, 0, 0, 4, 2, 2, 4, 0, 0, 4, 2, 3, 2],
246        [2, 3, 2, 4, 0, 0, 4, 2, 2, 4, 0, 0, 4, 2, 2, 4, 0, 0, 4, 2],
247        [2, 1, 0, 0, 1, 2, 2, 1, 0, 0, 1, 2, 2, 1, 0, 0, 1, 2, 6, 2],
248        [2, 6, 2, 1, 0, 0, 1, 2, 2, 1, 0, 0, 1, 2, 2, 1, 0, 0, 1, 2],
249    ];
250
251    for monster in &mut monsters {
252        if let Some(rough) = find(monster, 3, 20) {
253            return rough;
254        }
255    }
256
257    unreachable!()
258}
aoc/year2020/day20.rs

aoc/year2020/
day20.rs
