aoc/year2017/day21.rs
1//! # Fractal Art
2//!
3//! The image size starts at 3x3, growing exponentially to 18x18 after 5 generations and 2187x2187
4//! after 18 generations. The first insight to solving efficiently is realizing that we don't need
5//! to compute the entire image, instead only the *count* of each pattern is needed. Multiplying
6//! the count of each pattern by the number of set bits in each pattern gives the result.
7//!
8//! The second insight is that after 3 generations, the 9x9 image can be split into nine 3x3
9//! images that are independent of each other and the enhancement cycle can start over.
10//! Interestingly, most of the 3x3 patterns in the input are not needed, only the starting 3x3
11//! pattern and the six 2x2 to 3x3 patterns.
12//!
13//! Adding a few extra made up rules:
14//!
15//! ```none
16//! ##/#. => ###/#.#/###
17//! .#/.# => .#./###/.#.
18//! ../.. => #.#/.#./#.#
19//! ```
20//!
21//! then using the example:
22//!
23//! ```none
24//! .#. #..# ##.##. ###|.#.|##.
25//! ..# => .... => #..#.. => #.#|###|#..
26//! ### .... ...... ###|.#.|...
27//! #..# ##.##. ---+---+---
28//! #..#.. .#.|##.|##.
29//! ...... ###|#..|#..
30//! .#.|...|...
31//! ---+---+---
32//! ##.|##.|#.#
33//! #..|#..|.#.
34//! ...|...|#.#
35//! ```
36//!
37//! Splitting the 9x9 grid results in:
38//!
39//! ```none
40//! 1 x ### 2 x .#. 5 x ##. 1 x #.#
41//! # # ### #.. .#.
42//! ### .#. ... #.#
43//! ```
44//!
45//! The enhancement cycle can start again with each 3x3 image. This means that we only need to
46//! calculate 2 generations for the starting image and each 2x2 to 3x3 rule.
47struct Pattern {
48 three: u32,
49 four: u32,
50 six: u32,
51 nine: [usize; 9],
52}
53
54pub fn parse(input: &str) -> Vec<u32> {
55 // 2⁴ = 16 possible 2x2 patterns
56 let mut pattern_lookup = [0; 16];
57 let mut two_to_three = [[0; 9]; 16];
58 // 2⁹ = 512 possible 3x3 patterns
59 let mut three_to_four = [[0; 16]; 512];
60
61 // Starting pattern .#./..#/### => 010/001/111 => b010001111 => 143
62 let mut todo = vec![143];
63
64 for line in input.lines().map(str::as_bytes) {
65 // The ASCII code for "#" 35 is odd and the code for "." 46 is even
66 // so we can convert to a 1 or 0 bit using bitwise AND with 1.
67 let bit = |i: usize| line[i] & 1;
68
69 if line.len() == 20 {
70 // 2x2 to 3x3.
71 let from = [0, 1, 3, 4].map(bit);
72 let value = [9, 10, 11, 13, 14, 15, 17, 18, 19].map(bit);
73
74 let pattern = todo.len();
75 todo.push(to_index(&value));
76
77 for key in two_by_two_permutations(from) {
78 two_to_three[key] = value;
79 pattern_lookup[key] = pattern;
80 }
81 } else {
82 // 3x3 to 4x4.
83 let from = [0, 1, 2, 4, 5, 6, 8, 9, 10].map(bit);
84 let value = [15, 16, 17, 18, 20, 21, 22, 23, 25, 26, 27, 28, 30, 31, 32, 33].map(bit);
85
86 for key in three_by_three_permutations(from) {
87 three_to_four[key] = value;
88 }
89 }
90 }
91
92 let patterns: Vec<_> = todo
93 .iter()
94 .map(|&index| {
95 // Lookup 4x4 pattern then map to 6x6.
96 let four = three_to_four[index];
97 let mut six = [0; 36];
98
99 for (src, dst) in [(0, 0), (2, 3), (8, 18), (10, 21)] {
100 let index = to_index(&[four[src], four[src + 1], four[src + 4], four[src + 5]]);
101 let replacement = two_to_three[index];
102 six[dst..dst + 3].copy_from_slice(&replacement[0..3]);
103 six[dst + 6..dst + 9].copy_from_slice(&replacement[3..6]);
104 six[dst + 12..dst + 15].copy_from_slice(&replacement[6..9]);
105 }
106
107 // Map 6x6 pattern to nine 3x3 patterns.
108 let nine = [0, 2, 4, 12, 14, 16, 24, 26, 28].map(|i| {
109 let index = to_index(&[six[i], six[i + 1], six[i + 6], six[i + 7]]);
110 pattern_lookup[index]
111 });
112
113 let three = index.count_ones();
114 let four = four.iter().sum::<u8>() as u32;
115 let six = six.iter().sum::<u8>() as u32;
116
117 Pattern { three, four, six, nine }
118 })
119 .collect();
120
121 let mut current = vec![0; patterns.len()];
122 let mut result = Vec::new();
123
124 // Begin with single starting pattern.
125 current[0] = 1;
126
127 // Calculate generations 0 to 20 inclusive.
128 for _ in 0..7 {
129 let mut three = 0;
130 let mut four = 0;
131 let mut six = 0;
132 let mut next = vec![0; patterns.len()];
133
134 for (count, pattern) in current.iter().zip(patterns.iter()) {
135 three += count * pattern.three;
136 four += count * pattern.four;
137 six += count * pattern.six;
138 // Each 6x6 grid splits into nine 3x3 grids.
139 pattern.nine.iter().for_each(|&i| next[i] += count);
140 }
141
142 result.push(three);
143 result.push(four);
144 result.push(six);
145 current = next;
146 }
147
148 result
149}
150
151pub fn part1(input: &[u32]) -> u32 {
152 input[5]
153}
154
155pub fn part2(input: &[u32]) -> u32 {
156 input[18]
157}
158
159/// Generate an array of the 8 possible transformations from rotating and flipping
160/// the 2x2 input.
161fn two_by_two_permutations(mut a: [u8; 4]) -> [usize; 8] {
162 let mut indices = [0; 8];
163
164 for (i, index) in indices.iter_mut().enumerate() {
165 // Convert pattern to binary to use as lookup index.
166 *index = to_index(&a);
167 // Rotate clockwise
168 // 0 1 => 2 0
169 // 2 3 3 1
170 a = [a[2], a[0], a[3], a[1]];
171 // Flip vertical
172 // 0 1 => 2 3
173 // 2 3 0 1
174 if i == 3 {
175 a = [a[2], a[3], a[0], a[1]];
176 }
177 }
178
179 indices
180}
181
182/// Generate an array of the 8 possible transformations from rotating and flipping
183/// the 3x3 input.
184fn three_by_three_permutations(mut a: [u8; 9]) -> [usize; 8] {
185 let mut indices = [0; 8];
186
187 for (i, index) in indices.iter_mut().enumerate() {
188 // Convert pattern to binary to use as lookup index.
189 *index = to_index(&a);
190 // Rotate clockwise
191 // 0 1 2 => 6 3 0
192 // 3 4 5 7 4 1
193 // 6 7 8 8 5 2
194 a = [a[6], a[3], a[0], a[7], a[4], a[1], a[8], a[5], a[2]];
195 // Flip vertical
196 // 0 1 2 => 6 7 8
197 // 3 4 5 3 4 5
198 // 6 7 8 0 1 2
199 if i == 3 {
200 a = [a[6], a[7], a[8], a[3], a[4], a[5], a[0], a[1], a[2]];
201 }
202 }
203
204 indices
205}
206
207/// Convert a pattern slice of ones and zeroes to a binary number.
208fn to_index(a: &[u8]) -> usize {
209 a.iter().fold(0, |acc, &n| (acc << 1) | n as usize)
210}