https://adventofcode.com/2019/day/16
당신은 거대 가스 행성을 거의 4분의 3 정도 지나갔습니다. 지구와 주고받는 신호는 여전히 5시간이나 걸릴 뿐만 아니라 신호 품질도 상당히 나쁩니다. 결함이 있는 전파 전송 알고리즘(FFT)을 통해 신호를 깔끔하게 정리할 수 있습니다.
FFT는 입력으로 숫자 목록을 받습니다. 수신한 신호(퍼즐 입력)에서 각 숫자는 한자리 숫자입니다. 즉, 15243 같은 데이터는 1, 5, 2, 4, 3의 순서를 가지는 숫자 목록을 나타냅니다.
FFT는 여러 단계를 반복하여 동작합니다. 각 단계에서 입력 목록과 같은 길이의 새로운 목록이 만들어집니다. 이 새 목록은 다음 단계의 입력으로 사용됩니다.
새 목록의 각 요소는 입력 목록의 모든 값에 반복되는 패턴의 값을 곱한 다음, 그 결과를 합산하여 구성됩니다. 예를들어 입력 목록이 9, 8, 7, 6, 5이고 주어진 패턴이 1, 2, 3이라면 결과는 9*1 + 8*2 + 7*3 + 6*1 + 5*2가 됩니다.(입력 목록의 각 원소는 곱셈 기호 왼쪽에 있고, 패턴 목록의 각 원소는 곱셈 기호 오른쪽에 있습니다.) 계산이 완료되면, 한자리의 숫자를 만들기 위해 결과 값의 절대값에서 1의 자리수만을 취합니다. 즉, 38은 8이 되며, -17은 7이 됩니다.
출력 목록의 각 원소는 모두 동일한 입력 목록을 사용하지만, 반복되는 패턴 목록은 출력 목록의 각 원소마다 달라집니다. 기본 패턴은 0, 1, 0, -1입니다. 이 기본 패턴의 각 값을 현재 계산하고자 하는 출력 목록의 위치와 동일한 횟수만큼 반복합니다. 출력 목록의 첫번째 원소에 대해서는 한번, 두번째 원소에 대해서는 두번, 세번째 원소에 대해서는 세번과 같이 반복합니다. 따라서 출력 목록의 세번째 원소를 계산할 때 사용되는 패턴 목록은 0, 0, 0, 1, 1, 1, 0, 0, 0, -1, -1, -1입니다.
패턴을 적용할 때는 첫번째 패턴 값을 건너뜁니다. (달리말해, 전체 패턴에서 시작 오프셋을 1로 설정합니다.) 따라서 출력 목록의 두번째 원소에 사용되는 실제 패턴은 0, 1, 1, 0, 0, -1, -1, 0, 0, 1, 1, -1, -1, ... 입니다.
이 과정을 출력 목록의 각 원소에 대해 모두 진행하면, 한 단계가 완료 됩니다. 그리고 해당 단계에서 만들어진 출력 목록은 다음 단계의 입력 목록으로 사용됩니다.
입력 신호 12345678가 주어졌을 때, 아래는 FFT의 처음 4단계가 진행되는 과정입니다. 각 단계에서, 출력 목록의 각 원소는 한 줄에서 계산되어 등호(=) 연사 오른쪽에 결과로 나타납니다. 또한, 각 곱셈 연산에서 왼쪽 숫자는 입력 목록의 원소, 오른쪽 숫자는 패턴의 값을 나타냅니다.
입력 신호: 12345678
1*1 + 2*0 + 3*-1 + 4*0 + 5*1 + 6*0 + 7*-1 + 8*0 = 4
1*0 + 2*1 + 3*1 + 4*0 + 5*0 + 6*-1 + 7*-1 + 8*0 = 8
1*0 + 2*0 + 3*1 + 4*1 + 5*1 + 6*0 + 7*0 + 8*0 = 2
1*0 + 2*0 + 3*0 + 4*1 + 5*1 + 6*1 + 7*1 + 8*0 = 2
1*0 + 2*0 + 3*0 + 4*0 + 5*1 + 6*1 + 7*1 + 8*1 = 6
1*0 + 2*0 + 3*0 + 4*0 + 5*0 + 6*1 + 7*1 + 8*1 = 1
1*0 + 2*0 + 3*0 + 4*0 + 5*0 + 6*0 + 7*1 + 8*1 = 5
1*0 + 2*0 + 3*0 + 4*0 + 5*0 + 6*0 + 7*0 + 8*1 = 8
1단계 이후: 48226158
4*1 + 8*0 + 2*-1 + 2*0 + 6*1 + 1*0 + 5*-1 + 8*0 = 3
4*0 + 8*1 + 2*1 + 2*0 + 6*0 + 1*-1 + 5*-1 + 8*0 = 4
4*0 + 8*0 + 2*1 + 2*1 + 6*1 + 1*0 + 5*0 + 8*0 = 0
4*0 + 8*0 + 2*0 + 2*1 + 6*1 + 1*1 + 5*1 + 8*0 = 4
4*0 + 8*0 + 2*0 + 2*0 + 6*1 + 1*1 + 5*1 + 8*1 = 0
4*0 + 8*0 + 2*0 + 2*0 + 6*0 + 1*1 + 5*1 + 8*1 = 4
4*0 + 8*0 + 2*0 + 2*0 + 6*0 + 1*0 + 5*1 + 8*1 = 3
4*0 + 8*0 + 2*0 + 2*0 + 6*0 + 1*0 + 5*0 + 8*1 = 8
2단계 이후: 34040438
3*1 + 4*0 + 0*-1 + 4*0 + 0*1 + 4*0 + 3*-1 + 8*0 = 0
3*0 + 4*1 + 0*1 + 4*0 + 0*0 + 4*-1 + 3*-1 + 8*0 = 3
3*0 + 4*0 + 0*1 + 4*1 + 0*1 + 4*0 + 3*0 + 8*0 = 4
3*0 + 4*0 + 0*0 + 4*1 + 0*1 + 4*1 + 3*1 + 8*0 = 1
3*0 + 4*0 + 0*0 + 4*0 + 0*1 + 4*1 + 3*1 + 8*1 = 5
3*0 + 4*0 + 0*0 + 4*0 + 0*0 + 4*1 + 3*1 + 8*1 = 5
3*0 + 4*0 + 0*0 + 4*0 + 0*0 + 4*0 + 3*1 + 8*1 = 1
3*0 + 4*0 + 0*0 + 4*0 + 0*0 + 4*0 + 3*0 + 8*1 = 8
3단계 이후: 03415518
0*1 + 3*0 + 4*-1 + 1*0 + 5*1 + 5*0 + 1*-1 + 8*0 = 0
0*0 + 3*1 + 4*1 + 1*0 + 5*0 + 5*-1 + 1*-1 + 8*0 = 1
0*0 + 3*0 + 4*1 + 1*1 + 5*1 + 5*0 + 1*0 + 8*0 = 0
0*0 + 3*0 + 4*0 + 1*1 + 5*1 + 5*1 + 1*1 + 8*0 = 2
0*0 + 3*0 + 4*0 + 1*0 + 5*1 + 5*1 + 1*1 + 8*1 = 9
0*0 + 3*0 + 4*0 + 1*0 + 5*0 + 5*1 + 1*1 + 8*1 = 4
0*0 + 3*0 + 4*0 + 1*0 + 5*0 + 5*0 + 1*1 + 8*1 = 9
0*0 + 3*0 + 4*0 + 1*0 + 5*0 + 5*0 + 1*0 + 8*1 = 8
4단계 이후: 01029498
아래는 더 큰 입력 값에 대해 100 단계를 진행한 후, 최종 출력 목록의 앞에서부터 8자리 숫자입니다.
80871224585914546619083218645595은24176176이 됩니다.19617804207202209144916044189917은73745418이 됩니다.69317163492948606335995924319873은52432133이 됩니다.
주어진 퍼즐 입력으로 FFT 100 단계를 진행했을 때, 최종 출력 목록의 앞에서부터 8자리 숫자는 무엇입니까?
FFT가 잘 작동하므로, 이제 실제 신호를 복호화할 수 있습니다.
실제 신호는 퍼즐 입력을 10,000번 반복한 것입니다. 이 실제 신호를 입력 목록으로 사용하면 됩니다. 또한 패턴은 이전에 사용했던 것과 같으며, FFT를 100단계 만큼 진행하는 것도 동일합니다.
초기 입력 신호의 처음 7자리는 메시지 오프셋을 나타냅니다. 메시지 오프셋은 최종 출력 목록에서 추출할 8자리 메시지의 위치입니다. 구체적으로 말하면, 메시지 오프셋은 8자리 메시지를 읽기 위해 건너뛰어야할 숫자의 개수를 나타냅니다. 예를들어 초기 입력 신호의 처음 7자리가 1234567이면, 8자리 메시지는 최종 출력 목록에서 1234567을 건너뛴 다음의 8자리 숫자가 됩니다. 다른 예시를 들자면, 만약 메시지 오프셋이 7이고 최종 출력 목록이 98765432109876543210이라면, 8자리 메시지는 21098765가 됩니다. (물론 실제 메시지 오프셋은 7과 같은 한자리 숫자가 아니라 7자리 숫자입니다.)
다음은 100 단계 이후의 최종 출력 리스트에 있는 8자리 메시지입니다. 각 입력에 지정된 메시지 오프셋을 강조표시하였습니다. (아래에 제시된 입력은 실제 입력 리스트를 만들기 위해 10000번 반복됩니다.)
-03036732577212944063491565474664은 84462026이 됩니다.
-02935109699940807407585447034323은 78725270이 됩니다.
-03081770884921959731165446850517은 53553731이 됩니다.
주어진 퍼즐 입력을 10_000번 반복하고 FFT 100단계를 수행하여 얻은 최종 출력 리스트에 포함된 8자리 메시지는 무엇입니까?