Module aoc::year2019::day16

source ·
Expand description

§Flawed Frequency Transmission

§Part One

For each phase we split the input into two halves. The first half is processed using the pattern “stretched” for the current phase. For the second half we notice that the coefficients before are always zero and after always one, so the result can only depend on later digits. Using the first example:

    5*1  + 6*1  + 7*1  + 8*1
    5*0  + 6*1  + 7*1  + 8*1
    5*0  + 6*0  + 7*1  + 8*1
    5*0  + 6*0  + 7*0  + 8*1

Each digit is the sum of itself and subsequent digits and can be computed using a reverse rolling prefix sum.

§Part Two

If the index from the first 7 digits lies in the second half of the input then we only need to consider coefficients that form an upper triangular matrix, for example:

  1  1  1  1
  0  1  1  1
  0  0  1  1
  0  0  0  1

After the first phase:

  1  2  3  4
  0  1  2  3
  0  0  1  2
  0  0  0  1

After the second phase:

  1  3  6 10
  0  1  3  6
  0  0  1  3
  0  0  0  1

After the third phase:

  1  4 10 20
  0  1  4 10
  0  0  1  6
  0  0  0  1

We can see that the third phase is the triangular number sequence and that the fourth phase is the tetrahedral number sequence. More generally the ith coefficient of the 100th phase is the binomial coefficient (i + 99, i).

We could compute the coefficient using the formula nᵏ/k! however this grows rather large and quickly will overflow even a u128.

However we only need to coefficient modulo 10. Lucas’s theorem allow us to computer binomial coefficients modulo some prime number. If we compute the coefficients modulo 2 and modulo 5 then we can use the Chinese remainder theorem to find the result modulo 10.

Constants§

Functions§