part1 (4831B)
1--- Day 16: Flawed Frequency Transmission --- 2 3You're 3/4ths of the way through the gas giants. Not only do roundtrip signals to Earth take five 4hours, but the signal quality is quite bad as well. You can clean up the signal with the Flawed 5Frequency Transmission algorithm, or [1m[97mFFT[0m. 6 7As input, FFT takes a list of numbers. In the signal you received (your puzzle input), each number 8is a single digit: data like 15243 represents the sequence 1, 5, 2, 4, 3. 9 10FFT operates in repeated [1m[97mphases[0m. In each phase, a new list is constructed with the same length as 11the input list. This new list is also used as the input for the next phase. 12 13Each element in the new list is built by multiplying every value in the input list by a value in a 14repeating [1m[97mpattern[0m and then adding up the results. So, if the input list were 9, 8, 7, 6, 5 and the 15pattern for a given element were 1, 2, 3, the result would be 9*1 + 8*2 + 7*3 + 6*1 + 5*2 (with each 16input element on the left and each value in the repeating pattern on the right of each 17multiplication). Then, only the ones digit is kept: 38 becomes 8, -17 becomes 7, and so on. 18 19While each element in the output array uses all of the same input array elements, the actual 20repeating pattern to use depends on [1m[97mwhich output element[0m is being calculated. The base pattern is 0, 211, 0, -1. Then, repeat each value in the pattern a number of times equal to the [1m[97mposition in the 22output list[0m being considered. Repeat once for the first element, twice for the second element, three 23times for the third element, and so on. So, if the third element of the output list is being 24calculated, repeating the values would produce: 0, 0, 0, 1, 1, 1, 0, 0, 0, -1, -1, -1. 25 26When applying the pattern, skip the very first value exactly once. (In other words, offset the whole 27pattern left by one.) So, for the second element of the output list, the actual pattern used would 28be: 0, 1, 1, 0, 0, -1, -1, 0, 0, 1, 1, 0, 0, -1, -1, .... 29 30After using this process to calculate each element of the output list, the phase is complete, and 31the output list of this phase is used as the new input list for the next phase, if any. 32 33Given the input signal 12345678, below are four phases of FFT. Within each phase, each output digit 34is calculated on a single line with the result at the far right; each multiplication operation shows 35the input digit on the left and the pattern value on the right: 36 37Input signal: 12345678 38 391*1 + 2*0 + 3*-1 + 4*0 + 5*1 + 6*0 + 7*-1 + 8*0 = 4 401*0 + 2*1 + 3*1 + 4*0 + 5*0 + 6*-1 + 7*-1 + 8*0 = 8 411*0 + 2*0 + 3*1 + 4*1 + 5*1 + 6*0 + 7*0 + 8*0 = 2 421*0 + 2*0 + 3*0 + 4*1 + 5*1 + 6*1 + 7*1 + 8*0 = 2 431*0 + 2*0 + 3*0 + 4*0 + 5*1 + 6*1 + 7*1 + 8*1 = 6 441*0 + 2*0 + 3*0 + 4*0 + 5*0 + 6*1 + 7*1 + 8*1 = 1 451*0 + 2*0 + 3*0 + 4*0 + 5*0 + 6*0 + 7*1 + 8*1 = 5 461*0 + 2*0 + 3*0 + 4*0 + 5*0 + 6*0 + 7*0 + 8*1 = 8 47 48After 1 phase: 48226158 49 504*1 + 8*0 + 2*-1 + 2*0 + 6*1 + 1*0 + 5*-1 + 8*0 = 3 514*0 + 8*1 + 2*1 + 2*0 + 6*0 + 1*-1 + 5*-1 + 8*0 = 4 524*0 + 8*0 + 2*1 + 2*1 + 6*1 + 1*0 + 5*0 + 8*0 = 0 534*0 + 8*0 + 2*0 + 2*1 + 6*1 + 1*1 + 5*1 + 8*0 = 4 544*0 + 8*0 + 2*0 + 2*0 + 6*1 + 1*1 + 5*1 + 8*1 = 0 554*0 + 8*0 + 2*0 + 2*0 + 6*0 + 1*1 + 5*1 + 8*1 = 4 564*0 + 8*0 + 2*0 + 2*0 + 6*0 + 1*0 + 5*1 + 8*1 = 3 574*0 + 8*0 + 2*0 + 2*0 + 6*0 + 1*0 + 5*0 + 8*1 = 8 58 59After 2 phases: 34040438 60 613*1 + 4*0 + 0*-1 + 4*0 + 0*1 + 4*0 + 3*-1 + 8*0 = 0 623*0 + 4*1 + 0*1 + 4*0 + 0*0 + 4*-1 + 3*-1 + 8*0 = 3 633*0 + 4*0 + 0*1 + 4*1 + 0*1 + 4*0 + 3*0 + 8*0 = 4 643*0 + 4*0 + 0*0 + 4*1 + 0*1 + 4*1 + 3*1 + 8*0 = 1 653*0 + 4*0 + 0*0 + 4*0 + 0*1 + 4*1 + 3*1 + 8*1 = 5 663*0 + 4*0 + 0*0 + 4*0 + 0*0 + 4*1 + 3*1 + 8*1 = 5 673*0 + 4*0 + 0*0 + 4*0 + 0*0 + 4*0 + 3*1 + 8*1 = 1 683*0 + 4*0 + 0*0 + 4*0 + 0*0 + 4*0 + 3*0 + 8*1 = 8 69 70After 3 phases: 03415518 71 720*1 + 3*0 + 4*-1 + 1*0 + 5*1 + 5*0 + 1*-1 + 8*0 = 0 730*0 + 3*1 + 4*1 + 1*0 + 5*0 + 5*-1 + 1*-1 + 8*0 = 1 740*0 + 3*0 + 4*1 + 1*1 + 5*1 + 5*0 + 1*0 + 8*0 = 0 750*0 + 3*0 + 4*0 + 1*1 + 5*1 + 5*1 + 1*1 + 8*0 = 2 760*0 + 3*0 + 4*0 + 1*0 + 5*1 + 5*1 + 1*1 + 8*1 = 9 770*0 + 3*0 + 4*0 + 1*0 + 5*0 + 5*1 + 1*1 + 8*1 = 4 780*0 + 3*0 + 4*0 + 1*0 + 5*0 + 5*0 + 1*1 + 8*1 = 9 790*0 + 3*0 + 4*0 + 1*0 + 5*0 + 5*0 + 1*0 + 8*1 = 8 80 81After 4 phases: 01029498 82 83Here are the first eight digits of the final output list after 100 phases for some larger inputs: 84 85 86 - 80871224585914546619083218645595 becomes 24176176. 87 88 - 19617804207202209144916044189917 becomes 73745418. 89 90 - 69317163492948606335995924319873 becomes 52432133. 91 92 93After [1m[97m100[0m phases of FFT, [1m[97mwhat are the first eight digits in the final output list?[0m 94 95