Module day14

Chocolate Charts

This solution is heavily inspired by Askalski’s excellent post Breaking the 1 billion recipes per second barrier

The key insight is that after 23 recipes the elves converge into using the same subset of recipes. This subset can be stored compactly in about 20% of the space and read sequentially to allow efficient vector processing.

Tricks used to speed things up:

• Separate writer and reader threads to generate recipes and check them in parallel.
• Vector processing of recipes using techniques similar to SIMD.

Constants

• PREFIX 🔒
  Pre-calculate the first 23 recipes.

Functions

• from_be_bytes 🔒
  Convert 8 bytes in big endian order into a usize.
• lsb 🔒
  Convenience function that returns least significant byte.
• parse
• part1
• part2
• prefix_sum 🔒
  Compute the prefix sum of each byte within a usize. Let a..h denote the bytes from most significant to least significant and Σx..y denote the sum from x to y inclusive.
• reader 🔒
  Receives batches of recipes from the writer thread, then scans them byte by byte searching for the part two pattern. For simplicity the pattern is always assumed to by six digits.
• unpack 🔒
  Takes two groups of 8 digits each packed into a usize as input, then returns the output digits and their respective locations. Ones from sums greater than ten are implicit and not included since recipes has already been pre-filled with ones.
• writer 🔒
  Generates recipes then sends them to the reader thread for checking in batches. Processing is broken into alternating “cold” and “hot” loops. An outer enclosing loop checks periodically for the done signal from the reader thread.

Type Aliases

• Input 🔒