aoc/year2023/day12.rs
1//! # Hot Springs
2//!
3//! A [dynamic programming](https://en.wikipedia.org/wiki/Dynamic_programming) approach calculates
4//! the possible arrangements for each entry in `O(n * w)` complexity where:
5//!
6//! * `n` Number of springs
7//! * `w` "Wiggle" is the amount of extra free space the springs can slide around in the pattern.
8//!
9//! We build a table for each entry with a row for each spring and a column for every character
10//! in the pattern. Adding a trailing `.` character makes bounds checking easier without changing
11//! the number of arrangements. The result will be the bottom right value.
12//!
13//! Using the sample `?###???????? 3,2,1`:
14//!
15//! ```none
16//! n = 3
17//! w = 13 - (3 + 2 + 1) - 3 + 1 = 5
18//!
19//! ? # # # ? ? ? ? ? ? ? ? .
20//! ┌----------------------------------------
21//! 3 | 0 0 0 [0 1 1 1 1] 0 0 0 0 0
22//! 2 | 0 0 0 0 0 0 [0 1 2 3 4] 0 0
23//! 1 | 0 0 0 0 0 0 0 0 [0 1 3 6 10]
24//! ```
25//!
26//! Each pattern updates the total at the index one *after* its end, if it can fit at that location
27//! For example the first spring can only match at indices `[1, 2, 3]` so it updates the total
28//! at index 4 to 1.
29//!
30//! The key insight is that the number of arrangements is then propagated as a prefix sum
31//! from left to right for each row as long as the character at the index is not a `#` or until
32//! `wiggle` characters are reached, whichever comes sooner.
33//!
34//! To calculate the next row, each matching pattern adds the value from the row above at the
35//! index one before its start. The first row is a special case where this value is always 1.
36//!
37//! As a nice side effect this approach always overwrites values so we can re-use the memory buffer
38//! for different entries without having to zero out values.
39//!
40//! ## Alternate approach
41//!
42//! Another way to look at the problem is to search to the left from each matching position
43//! until a `#` character is found. The previous pattern can't leave any trailing `#` characters
44//! otherwise it wouldn't be the previous pattern.
45//!
46//! Using the same example `?###???????? 3,2,1` and adding a trailing `.`:
47//!
48//! * `###` can only match at one location giving:
49//! ```none
50//! . # # # . . . . . . . . .
51//! [0 0 0 0 1 0 0 0 0 0 0 0 0]
52//! ````
53//!
54//!* The next `##` can match at 4 possible locations:
55//! ```none
56//! . # # # . # # . . . . . .
57//! [0 0 0 0 1 0 0 0 0 0 0 0 0]
58//! <<
59//! [0 0 0 0 0 0 0 1 0 0 0 0 0]
60//! ```
61//! * 2nd location:
62//! ```none
63//! . # # # . . # # . . . . .
64//! [0 0 0 0 1 0 0 0 0 0 0 0 0]
65//! <<<<
66//! [0 0 0 0 0 0 0 1 1 0 0 0 0]
67//! ```
68//! * 3rd location:
69//! ```none
70//! . # # # . . . # # . . . .
71//! [0 0 0 0 1 0 0 0 0 0 0 0 0]
72//! <<<<<<
73//! [0 0 0 0 0 0 0 1 1 1 0 0 0]
74//! ```
75//! * 4th location:
76//! ```none
77//! . # # # . . . . # # . . .
78//! [0 0 0 0 1 0 0 0 0 0 0 0 0]
79//! <<<<<<<<
80//! [0 0 0 0 0 0 0 1 1 1 1 0 0]
81//! ```
82//!* The final `#` can also match at 4 possible locations (for brevity only showing the 2nd pattern
83//! in a single position):
84//! ```none
85//! . # # # . # # . # . . . .
86//! [0 0 0 0 1 0 0 0 0 0 0 0 0]
87//! [0 0 0 0 0 0 0 1 1 1 1 0 0]
88//! <<
89//! [0 0 0 0 0 0 0 0 1 0 0 0 0]
90//! ```
91//! * 2nd location:
92//! ```none
93//! . # # # . # # . . # . . .
94//! [0 0 0 0 1 0 0 0 0 0 0 0 0]
95//! [0 0 0 0 0 0 0 1 1 1 1 0 0]
96//! <<<<
97//! [0 0 0 0 0 0 0 0 1 2 0 0 0]
98//! ```
99//! * 3rd location:
100//! ```none
101//! . # # # . # # . . . # . .
102//! [0 0 0 0 1 0 0 0 0 0 0 0 0]
103//! [0 0 0 0 0 0 0 1 1 1 1 0 0]
104//! <<<<<<
105//! [0 0 0 0 0 0 0 0 1 2 3 0 0]
106//! ```
107//! * 4th location:
108//! ```none
109//! . # # # . # # . . . . # .
110//! [0 0 0 0 1 0 0 0 0 0 0 0 0]
111//! [0 0 0 0 0 0 0 1 1 1 1 0 0]
112//! <<<<<<<<
113//! [0 0 0 0 0 0 0 0 1 2 3 4 0]
114//! ```
115//!
116//! The final result is then the sum of the bottom row with the nuance that any numbers before the
117//! last `#` don't count as they represent an invalid pattern.
118//!
119//! This is equivalent to the prefix sum approach described above but a little clearer to
120//! understand however slower to calculate.
121use crate::util::parse::*;
122use crate::util::thread::*;
123
124type Spring<'a> = (&'a [u8], Vec<usize>);
125
126pub fn parse(input: &str) -> Vec<Spring<'_>> {
127 input
128 .lines()
129 .map(|line| {
130 let (prefix, suffix) = line.split_once(' ').unwrap();
131 let first = prefix.as_bytes();
132 let second = suffix.iter_unsigned().collect();
133 (first, second)
134 })
135 .collect()
136}
137
138pub fn part1(input: &[Spring<'_>]) -> u64 {
139 solve(input.iter(), 1)
140}
141
142pub fn part2(input: &[Spring<'_>]) -> u64 {
143 // Use as many cores as possible to parallelize the calculation.
144 let result = spawn_parallel_iterator(input, |iter| solve(iter, 5));
145 result.into_iter().sum()
146}
147
148pub fn solve<'a, I>(iter: I, repeat: usize) -> u64
149where
150 I: Iterator<Item = &'a Spring<'a>>,
151{
152 let mut result = 0;
153 let mut pattern = Vec::new();
154 let mut springs = Vec::new();
155 // Exact size is not too important as long as there's enough space.
156 let mut broken = vec![0; 200];
157 let mut table = vec![0; 200 * 50];
158
159 for (first, second) in iter {
160 // Create input sequence reusing the buffers to minimize memory allocations.
161 pattern.clear();
162 springs.clear();
163
164 for _ in 1..repeat {
165 pattern.extend_from_slice(first);
166 pattern.push(b'?');
167 springs.extend_from_slice(second);
168 }
169
170 // Add a trailing '.' so that we don't have to check bounds when testing the last pattern.
171 // This has no effect on the number of possible combinations.
172 pattern.extend_from_slice(first);
173 pattern.push(b'.');
174 springs.extend_from_slice(second);
175
176 // Calculate prefix sum of the number of broken springs and unknowns before each index
177 // to quickly check if a range can contain a broken spring without checking every element.
178 // For example `.??..??...?##` becomes `[0, 0, 1, 2, 2, 2, 3, 4, 4, 4, 4, 5, 6, 7, 7]`.
179 let mut sum = 0;
180 broken.push(0);
181
182 for (i, &b) in pattern.iter().enumerate() {
183 if b != b'.' {
184 sum += 1;
185 }
186 broken[i + 1] = sum;
187 }
188
189 // Determine how many spaces each pattern can slide around to speed things up.
190 // We only need to check at most that many spaces for each pattern.
191 let wiggle = pattern.len() - springs.iter().sum::<usize>() - springs.len() + 1;
192
193 // Count combinations, handling the first row as a special case.
194 let size = springs[0];
195 let mut sum = 0;
196 let mut valid = true;
197
198 for i in 0..wiggle {
199 // In order to be a broken spring, an interval must only contains `#` or `?`
200 // characters and not have a '#' character immediately before or after.
201 if pattern[i + size] == b'#' {
202 sum = 0;
203 } else if valid && broken[i + size] - broken[i] == size {
204 sum += 1;
205 }
206
207 table[i + size] = sum;
208
209 // The first pattern can't have any '#' characters anywhere to its left
210 // otherwise it wouldn't be the first pattern.
211 valid &= pattern[i] != b'#';
212 }
213
214 // Count each subsequent spring. The previous patterns take at least the sum of their size
215 // and 1 space afterwards so no need to check indices before that.
216 let mut start = size + 1;
217
218 for (row, &size) in springs.iter().enumerate().skip(1) {
219 // We're using a 1 dimensional vec to implement a two dimensional table.
220 // Calculate the starting index of current and previous row for convenience.
221 let previous = (row - 1) * pattern.len();
222 let current = row * pattern.len();
223
224 // Reset the running sum.
225 sum = 0;
226
227 for i in start..start + wiggle {
228 // As a minor optimization only check the pattern if the previous row
229 // will contribute a non-zero value.
230 if pattern[i + size] == b'#' {
231 sum = 0;
232 } else if table[previous + i - 1] > 0
233 && pattern[i - 1] != b'#'
234 && broken[i + size] - broken[i] == size
235 {
236 sum += table[previous + i - 1];
237 }
238
239 table[current + i + size] = sum;
240 }
241
242 start += size + 1;
243 }
244
245 // The final value of sum (the bottom right of the table) is the number of possible
246 // arrangements of the pattern.
247 result += sum;
248 }
249
250 result
251}