Module aoc::year2016::day16

Dragon Checksum

We solve efficiently with a key insight that the checksum is simply the odd parity bit for each block. If the total number of ones is even then the result is one, if the total is odd then the result is zero.

This means that only the total number of ones is important not the pattern itself. Each checksum bit is computed over the largest power of two divisible into the output size. For part one this is 2⁴ or 16 and for part this is 2²¹ or 2097152. If we can calculate the number of ones for any arbitrary length then we can find the number at the start and end of each block, subtract from each other to get the total in the range then find the checksum bit.

We find the number of ones for a pattern of length n in log(n) complexity as follows:

• Start with a known pattern abcde and let the reversed bit inverse of this pattern be EDCBA.
• Caculate the prefix sum of the known sequence.
• If the requested length is within the known sequence (in this example from 0 to 5 inclusive) then we’re done, return the number of ones directly.
• Else after one repetition this becomes abcde0EDCBA.
• If the length is at or to the right of the middle 0, for example length is 8 then the number of ones is:
  • Let half = 5 the length of the left hand known sequence.
  • Let full = 11 the length of the entire sequence.
  • Ones in abcde => x
  • Ones in EDCBA => the number of zeroes in abcde => 5 - x => half - x
  • Ones in abc => y
  • Ones in CBA => the number of zeroes in abc => 3 - y => 11 - 8 - y => full - length - y => next - y
  • The total number of ones in abcde0ED is x + (half - x) - (next - y) => half - next + y

Now for the really neat part. We can recursively find the number of ones in y by repeating the same process by setting the new length to next. We keep recursing until the length is less the size of the inital input and we can lookup the final count from the prefix sum.

Functions

• checksum 🔒
  Collect the ones count at each step_size then subtract in pairs to calculate the number of ones in each interval to give the checksum.
• count 🔒
  Counts the number of ones from the start to the index (inclusive).
• parse
  Build a prefix sum of the number of ones at each length in the pattern including zero at the start.
• part1
  272 is 17 * 2⁴
• part2
  35651584 is 17 * 2²¹