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 reuse 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
83//! (for brevity only showing the 2nd pattern 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 (prefix.as_bytes(), suffix.iter_unsigned().collect())
132 })
133 .collect()
134}
135
136pub fn part1(input: &[Spring<'_>]) -> u64 {
137 solve(input.iter(), 1)
138}
139
140pub fn part2(input: &[Spring<'_>]) -> u64 {
141 // Use as many cores as possible to parallelize the calculation.
142 let result = spawn_parallel_iterator(input, |iter| solve(iter, 5));
143 result.into_iter().sum()
144}
145
146fn solve<'a>(iter: impl Iterator<Item = &'a Spring<'a>>, repeat: usize) -> u64 {
147 let mut result = 0;
148 let mut pattern = Vec::new();
149 let mut springs = Vec::new();
150 // Exact size is not too important as long as there's enough space.
151 let mut broken = vec![0; 200];
152 let mut table = vec![0; 200 * 50];
153
154 for (first, second) in iter {
155 // Create input sequence reusing the buffers to minimize memory allocations.
156 pattern.clear();
157 springs.clear();
158
159 for _ in 1..repeat {
160 pattern.extend_from_slice(first);
161 pattern.push(b'?');
162 springs.extend_from_slice(second);
163 }
164
165 // Add a trailing '.' so that we don't have to check bounds when testing the last pattern.
166 // This has no effect on the number of possible combinations.
167 pattern.extend_from_slice(first);
168 pattern.push(b'.');
169 springs.extend_from_slice(second);
170
171 // Calculate prefix sum of the number of broken springs and unknowns before each index
172 // to quickly check if a range can contain a broken spring without checking every element.
173 // For example `.??..??...?##` becomes `[0, 0, 1, 2, 2, 2, 3, 4, 4, 4, 4, 5, 6, 7, 7]`.
174 let mut sum = 0;
175
176 for (i, &b) in pattern.iter().enumerate() {
177 if b != b'.' {
178 sum += 1;
179 }
180 broken[i + 1] = sum;
181 }
182
183 // Determine how many spaces each pattern can slide around to speed things up.
184 // We only need to check at most that many spaces for each pattern.
185 let wiggle = pattern.len() - springs.iter().sum::<usize>() - springs.len() + 1;
186
187 // Count combinations, handling the first row as a special case.
188 let size = springs[0];
189 let mut sum = 0;
190 let mut valid = true;
191
192 for i in 0..wiggle {
193 // In order to be a broken spring, an interval must only contain `#` or `?`
194 // characters and not have a '#' character immediately before or after.
195 if pattern[i + size] == b'#' {
196 sum = 0;
197 } else if valid && broken[i + size] - broken[i] == size {
198 sum += 1;
199 }
200
201 table[i + size] = sum;
202
203 // The first pattern can't have any '#' characters anywhere to its left
204 // otherwise it wouldn't be the first pattern.
205 valid &= pattern[i] != b'#';
206 }
207
208 // Count each subsequent spring. The previous patterns take at least the sum of their size
209 // and 1 space afterward so no need to check indices before that.
210 let mut start = size + 1;
211
212 for (row, &size) in springs.iter().enumerate().skip(1) {
213 // We're using a one-dimensional vec to implement a two-dimensional table.
214 // Calculate the starting index of current and previous row for convenience.
215 let previous = (row - 1) * pattern.len();
216 let current = row * pattern.len();
217
218 // Reset the running sum.
219 sum = 0;
220
221 for i in start..start + wiggle {
222 // As a minor optimization only check the pattern if the previous row
223 // will contribute a non-zero value.
224 if pattern[i + size] == b'#' {
225 sum = 0;
226 } else if table[previous + i - 1] > 0
227 && pattern[i - 1] != b'#'
228 && broken[i + size] - broken[i] == size
229 {
230 sum += table[previous + i - 1];
231 }
232
233 table[current + i + size] = sum;
234 }
235
236 start += size + 1;
237 }
238
239 // The final value of sum (the bottom right of the table) is the number of possible
240 // arrangements of the pattern.
241 result += sum;
242 }
243
244 result
245}