1use utils::prelude::*;
2
3#[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 #[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 *x = 19 - *x;
167 }
168 if ORIENTATION & 2 != 0 {
169 *y = 2 - *y;
171 }
172 if ORIENTATION & 4 != 0 {
173 (*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 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 (t, r, b, l) = (reverse(t), l, reverse(b), r);
205 }
206 if orientation & 2 != 0 {
207 (t, r, b, l) = (b, reverse(r), t, reverse(l));
209 }
210 if orientation & 4 != 0 {
211 (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 let pixels = delta_swap(pixels, 0x00AA_00AA_00AA_00AA, 7);
253
254 let pixels = delta_swap(pixels, 0x0000_CCCC_0000_CCCC, 14);
264
265 delta_swap(pixels, 0x0000_0000_F0F0_F0F0, 28)
275}
276
277fn delta_swap(x: u64, mask: u64, shift: u32) -> u64 {
278 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 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]);