year2018/
day14.rs

1use utils::prelude::*;
2
3/// Searching for a pattern in an infinite recipe list.
4///
5/// This implementation is based on
6/// [/u/askalski's post "Breaking the 1 billion recipes per second barrier"](https://www.reddit.com/r/adventofcode/comments/a6wpwa/2018_day_14_breaking_the_1_billion_recipes_per/)
7/// and accompanying [gist](https://gist.github.com/Voltara/5069980afbf6cf0762fcbb09948e5649),
8/// adapted to safe Rust without intrinsics or explicit SIMD while achieving similar performance.
9///
10/// The key optimization is that all the elves converge on the same subset of recipes after the
11/// first 23 recipes, allowing them to be processed in bulk using SIMD.
12#[derive(Clone, Debug)]
13pub struct Day14 {
14    part1: [u8; 10],
15    part2: usize,
16}
17
18impl Day14 {
19    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
20        let pattern = parser::digit()
21            .repeat_n(parser::noop())
22            .parse_complete(input)?;
23        let index = input.parse().unwrap();
24
25        let mut searcher = Searcher::new(pattern);
26        let part2 = searcher.run();
27
28        // Use a string for part 1 to preserve leading zeros
29        let mut part1 = [0u8; 10];
30        part1.copy_from_slice(&searcher.recipes[index..index + 10]);
31        for x in &mut part1 {
32            *x += b'0';
33        }
34
35        Ok(Self { part1, part2 })
36    }
37
38    #[must_use]
39    pub fn part1(&self) -> &str {
40        str::from_utf8(&self.part1).unwrap()
41    }
42
43    #[must_use]
44    pub fn part2(&self) -> usize {
45        self.part2
46    }
47}
48
49struct Searcher {
50    pattern: [u8; 6],
51    recipes: Vec<u8>,
52    recipes_len: usize,
53    packed: Vec<u8>,
54    packed_len: usize,
55    packed_next_idx: usize,
56    packed_last_idx: usize,
57    elves: [usize; 2],
58    initial: [i32; 2],
59    searched: usize,
60}
61
62// Pre-calculated sequences of recipes processed before index 23 where they all converge
63const INITIAL_SEQUENCES: [u32; 9] = [
64    0xfff9_4113,
65    0xffff_0657,
66    0xfff9_4111,
67    0xfff9_4110,
68    0xffff_9411,
69    0xffff_9410,
70    0xffff_f941,
71    0xffff_1812,
72    0xffff_ff94,
73];
74
75// The first 23 recipes
76const RECIPES: [u8; 23] = [
77    3, 7, 1, 0, 1, 0, 1, 2, 4, 5, 1, 5, 8, 9, 1, 6, 7, 7, 9, 2, 5, 1, 0,
78];
79
80const RECIPES_LEN: usize = 22_000_000;
81const PACKED_LEN: usize = RECIPES_LEN / 4;
82const SEARCH_INTERVAL: usize = 16384;
83
84impl Searcher {
85    fn new(pattern: [u8; 6]) -> Self {
86        // Prefill the recipes array with ones so 2-digit recipes can be written with a single
87        // write by skipping over the leading 1.
88        let mut recipes = vec![1u8; RECIPES_LEN];
89        recipes[..RECIPES.len()].copy_from_slice(&RECIPES);
90
91        Self {
92            pattern,
93            recipes,
94            recipes_len: RECIPES.len(),
95            packed: vec![0u8; PACKED_LEN],
96            packed_len: 0,
97            packed_next_idx: RECIPES.len(),
98            packed_last_idx: RECIPES.len(),
99            elves: [0, 0],
100            initial: [INITIAL_SEQUENCES[0] as i32, INITIAL_SEQUENCES[8] as i32],
101            searched: 0,
102        }
103    }
104
105    #[inline]
106    fn append_recipe(&mut self, mut recipe: u8) {
107        // Tens digit
108        if recipe >= 10 {
109            recipe -= 10;
110            if self.recipes_len == self.packed_next_idx {
111                self.packed[self.packed_len] = 1;
112                self.packed_len += 1;
113                self.packed_last_idx = self.packed_next_idx;
114                self.packed_next_idx += 2;
115            }
116            // No write to self.recipes as the array is prefilled with 1
117            self.recipes_len += 1;
118        }
119
120        // Ones digit
121        if self.recipes_len == self.packed_next_idx {
122            self.packed[self.packed_len] = recipe;
123            self.packed_len += 1;
124            self.packed_last_idx = self.packed_next_idx;
125            self.packed_next_idx += recipe as usize + 1;
126        }
127        self.recipes[self.recipes_len] = recipe;
128        self.recipes_len += 1;
129
130        // Handle wrapping around to the start
131        for i in 0..2 {
132            if self.elves[i] == self.packed_len {
133                let initial_index = self.packed_last_idx
134                    + (self.packed[self.packed_len - 1] as usize + 1)
135                    - self.recipes_len;
136                self.initial[i] = INITIAL_SEQUENCES[initial_index] as i32;
137                self.elves[i] = 0;
138            }
139        }
140    }
141
142    #[inline]
143    fn run(&mut self) -> usize {
144        loop {
145            // At least one elf is in the first 23 recipes, before the pattern coverages
146            while self.initial[0] != -1 || self.initial[1] != -1 {
147                let mut recipe = 0;
148                for i in 0..2 {
149                    if self.initial[i] == -1 {
150                        recipe += self.packed[self.elves[i]];
151                        self.elves[i] += 1;
152                    } else {
153                        recipe += (self.initial[i] & 0xF) as u8;
154                        self.initial[i] >>= 4;
155                    }
156                }
157                self.append_recipe(recipe);
158            }
159
160            // Both elves are after recipe 23, so recipes can be processed in bulk
161            loop {
162                let mut iterations = (self.packed_len - self.elves[0].max(self.elves[1])) / 32;
163                if iterations == 0 {
164                    break;
165                }
166
167                while iterations > 0 {
168                    if iterations > 16 {
169                        self.bulk_mix::<512>();
170                        iterations -= 16;
171                    } else {
172                        self.bulk_mix::<32>();
173                        iterations -= 1;
174                    }
175
176                    // Periodically search for the pattern
177                    if self.searched + SEARCH_INTERVAL < self.recipes_len
178                        && let Some(index) = self.search()
179                    {
180                        return index;
181                    }
182                }
183
184                // Pack the new recipes
185                while self.packed_next_idx < self.recipes_len {
186                    self.packed_last_idx = self.packed_next_idx;
187                    self.packed[self.packed_len] = self.recipes[self.packed_next_idx];
188                    self.packed_len += 1;
189                    self.packed_next_idx += self.recipes[self.packed_next_idx] as usize + 1;
190                }
191            }
192
193            // Handle the remaining recipes before wrapping around to the start
194            while self.initial[0] == -1 && self.initial[1] == -1 {
195                let sum = self.packed[self.elves[0]] + self.packed[self.elves[1]];
196                self.elves[0] += 1;
197                self.elves[1] += 1;
198                self.append_recipe(sum);
199            }
200        }
201    }
202
203    #[inline]
204    fn bulk_mix<const N: usize>(&mut self) {
205        const { assert!(N.is_multiple_of(32)) }
206
207        let v0 = &self.packed[self.elves[0]..self.elves[0] + N];
208        let v1 = &self.packed[self.elves[1]..self.elves[1] + N];
209        self.elves[0] += N;
210        self.elves[1] += N;
211
212        // Calculate the ones digit and carry for each recipe sum.
213        // This loop should be vectorized by the compiler.
214        let mut digits = [0u8; N];
215        let mut carry = [0u8; N];
216        for i in 0..N {
217            let s = v0[i] + v1[i];
218            let c = u8::from(s >= 10);
219            carry[i] = c;
220            digits[i] = s - (c * 10);
221        }
222
223        // Process the carry and digits sequentially in chunks of 8. This allows calculating the
224        // indexes for all 8 items in a few u64 operations, avoiding dependencies between each
225        // recipe.
226        let (digits, []) = digits.as_chunks::<8>() else {
227            unreachable!("N is a multiple of 8");
228        };
229        let (carry, []) = carry.as_chunks::<8>() else {
230            unreachable!("N is a multiple of 8");
231        };
232        for (digits, carry) in digits.iter().zip(carry) {
233            let slice = &mut self.recipes[self.recipes_len..self.recipes_len + 256];
234
235            let mut indexes = u64::from_le_bytes(*carry);
236            // Each recipe after the first is offset by 1
237            indexes += 0x0101_0101_0101_0100;
238            // Bytewise prefix sum
239            indexes += indexes << 8;
240            indexes += indexes << 16;
241            indexes += indexes << 32;
242
243            for (i, &d) in digits.iter().enumerate() {
244                // Use a u8 index into a 256 long slice to remove bounds checks here, reducing
245                // the number of bounds checks to 1 per 8 recipes.
246                let idx = (indexes >> (i * 8)) as u8;
247                slice[idx as usize] = d;
248            }
249
250            self.recipes_len += (indexes >> 56) as usize + 1;
251        }
252    }
253
254    #[inline]
255    fn search(&mut self) -> Option<usize> {
256        // Search for the pattern in sliding 64-byte windows
257        while self.searched + 64 + 5 < self.recipes_len {
258            // Find matches of the first two bytes across the window.
259            // This loop should be vectorized by the compiler.
260            let mut candidates = [0u8; 64];
261            let mut any_matches = false;
262            for (i, (&a, &b)) in self.recipes[self.searched..self.searched + 64]
263                .iter()
264                .zip(&self.recipes[self.searched + 1..self.searched + 65])
265                .enumerate()
266            {
267                let matches = (a == self.pattern[0]) & (b == self.pattern[1]);
268                // wrapping_neg produces 0xFF for matches and 0x00 for non-matches, which matches
269                // x86 SIMD comparison function semantics, slightly improving codegen.
270                candidates[i] = u8::from(matches).wrapping_neg();
271                any_matches |= matches;
272            }
273
274            // If no matches were found, skip to the next window.
275            // Do this before calculating the mask which can be expensive.
276            if !any_matches {
277                self.searched += 64;
278                continue;
279            }
280
281            let mut mask = candidates
282                .iter()
283                .enumerate()
284                .fold(0u64, |acc, (i, &x)| acc | u64::from(x != 0) << i);
285
286            // For each bit in the mask, check if the full pattern matches.
287            while mask != 0 {
288                let m = mask.trailing_zeros() as usize;
289                mask &= !(1 << m);
290
291                let index = self.searched + m;
292                if self.recipes[index..index + 6] == self.pattern {
293                    return Some(index);
294                }
295            }
296
297            self.searched += 64;
298        }
299
300        None
301    }
302}
303
304examples!(Day14 -> (&'static str, usize) [
305    // Custom examples
306    {input: "100100", part1: "8239938101", part2: 377203},
307    {input: "123456", part1: "1371276618", part2: 450697},
308    {input: "924933", part1: "0012267210", part2: 16462928},
309    {input: "054274", part1: "6112136872", part2: 21000203},
310]);
year2018/day14.rs

year2018/
day14.rs
