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.
47use std::array::from_fn;
48
49struct Pattern {
50 three: u32,
51 four: u32,
52 six: u32,
53 nine: [usize; 9],
54}
55
56pub fn parse(input: &str) -> Vec<u32> {
57 // 2⁴ = 16 possible 2x2 patterns
58 let mut pattern_lookup = [0; 16];
59 let mut two_to_three = [[0; 9]; 16];
60 // 2⁹ = 512 possible 3x3 patterns
61 let mut three_to_four = [[0; 16]; 512];
62
63 // Starting pattern .#./..#/### => 010/001/111 => b010001111 => 143
64 let mut todo = vec![143];
65
66 for line in input.lines().map(str::as_bytes) {
67 // The ASCII code for "#" 35 is odd and the code for "." 46 is even
68 // so we can convert to a 1 or 0 bit using bitwise AND with 1.
69 let bit = |i| line[i] & 1;
70
71 if line.len() == 20 {
72 // 2x2 to 3x3.
73 let from = [0, 1, 3, 4].map(bit);
74 let value = [9, 10, 11, 13, 14, 15, 17, 18, 19].map(bit);
75
76 let pattern = todo.len();
77 todo.push(to_index(&value));
78
79 for key in two_by_two_permutations(from) {
80 two_to_three[key] = value;
81 pattern_lookup[key] = pattern;
82 }
83 } else {
84 // 3x3 to 4x4.
85 let from = [0, 1, 2, 4, 5, 6, 8, 9, 10].map(bit);
86 let value = [15, 16, 17, 18, 20, 21, 22, 23, 25, 26, 27, 28, 30, 31, 32, 33].map(bit);
87
88 for key in three_by_three_permutations(from) {
89 three_to_four[key] = value;
90 }
91 }
92 }
93
94 let patterns: Vec<_> = todo
95 .iter()
96 .map(|&index| {
97 // Lookup 4x4 pattern then map to 6x6.
98 let four = three_to_four[index];
99 let mut six = [0; 36];
100
101 for (src, dst) in [(0, 0), (2, 3), (8, 18), (10, 21)] {
102 let index = to_index(&[four[src], four[src + 1], four[src + 4], four[src + 5]]);
103 let replacement = two_to_three[index];
104 six[dst..dst + 3].copy_from_slice(&replacement[0..3]);
105 six[dst + 6..dst + 9].copy_from_slice(&replacement[3..6]);
106 six[dst + 12..dst + 15].copy_from_slice(&replacement[6..9]);
107 }
108
109 // Map 6x6 pattern to nine 3x3 patterns.
110 let nine = [0, 2, 4, 12, 14, 16, 24, 26, 28].map(|i| {
111 let index = to_index(&[six[i], six[i + 1], six[i + 6], six[i + 7]]);
112 pattern_lookup[index]
113 });
114
115 let three = index.count_ones();
116 let four = u32::from(four.iter().sum::<u8>());
117 let six = u32::from(six.iter().sum::<u8>());
118
119 Pattern { three, four, six, nine }
120 })
121 .collect();
122
123 let mut current = vec![0; patterns.len()];
124 let mut result = Vec::new();
125
126 // Begin with single starting pattern.
127 current[0] = 1;
128
129 // Calculate generations 0 to 20 inclusive.
130 for _ in 0..7 {
131 let mut three = 0;
132 let mut four = 0;
133 let mut six = 0;
134 let mut next = vec![0; patterns.len()];
135
136 for (count, pattern) in current.iter().zip(&patterns) {
137 three += count * pattern.three;
138 four += count * pattern.four;
139 six += count * pattern.six;
140 // Each 6x6 grid splits into nine 3x3 grids.
141 pattern.nine.iter().for_each(|&i| next[i] += count);
142 }
143
144 result.extend([three, four, 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 from_fn(|i| {
163 // Convert pattern to binary to use as lookup index.
164 let index = to_index(&a);
165 // Rotate clockwise
166 // 0 1 => 2 0
167 // 2 3 3 1
168 a = [a[2], a[0], a[3], a[1]];
169 // Flip vertical
170 // 0 1 => 2 3
171 // 2 3 0 1
172 if i == 3 {
173 a = [a[2], a[3], a[0], a[1]];
174 }
175 index
176 })
177}
178
179/// Generate an array of the 8 possible transformations from rotating and flipping
180/// the 3x3 input.
181fn three_by_three_permutations(mut a: [u8; 9]) -> [usize; 8] {
182 from_fn(|i| {
183 // Convert pattern to binary to use as lookup index.
184 let index = to_index(&a);
185 // Rotate clockwise
186 // 0 1 2 => 6 3 0
187 // 3 4 5 7 4 1
188 // 6 7 8 8 5 2
189 a = [a[6], a[3], a[0], a[7], a[4], a[1], a[8], a[5], a[2]];
190 // Flip vertical
191 // 0 1 2 => 6 7 8
192 // 3 4 5 3 4 5
193 // 6 7 8 0 1 2
194 if i == 3 {
195 a = [a[6], a[7], a[8], a[3], a[4], a[5], a[0], a[1], a[2]];
196 }
197 index
198 })
199}
200
201/// Convert a pattern slice of ones and zeroes to a binary number.
202fn to_index(a: &[u8]) -> usize {
203 a.iter().fold(0, |acc, &n| (acc << 1) | usize::from(n))
204}