1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119

//! # Day 16: Flawed Frequency Transmission
//!
//! You're 3/4ths of the way through the [gas giants]. Not only do roundtrip signals to Earth take
//! five hours, but the signal quality is quite bad as well. You can clean up the signal with the
//! Flawed Frequency Transmission algorithm, or **FFT**.
//!
//! As input, FFT takes a list of numbers. In the signal you received (your puzzle input), each
//! number is a single digit: data like `15243` represents the sequence `1`, `5`, `2`, `4`, `3`.
//!
//! FFT operates in repeated **phases**. In each phase, a new list is constructed with the same
//! length as the input list. This new list is also used as the input for the next phase.
//!
//! Each element in the new list is built by multiplying every value in the input list by a value in
//! a repeating **pattern** and then adding up the results. So, if the input list were
//! `9, 8, 7, 6, 5` and the pattern for a given element were `1, 2, 3`, the result would be
//! `9*1 + 8*2 + 7*3 + 6*1 + 5*2` (with each input element on the left and each value in the
//! repeating pattern on the right of each multiplication). Then, only the ones digit is kept: `38`
//! becomes `8`, `-17` becomes `7`, and so on.
//!
//! While each element in the output array uses all of the same input array elements, the actual
//! repeating pattern to use depends on **which output element** is being calculated. The base
//! pattern is `0, 1, 0, -1`. Then, repeat each value in the pattern a number of times equal to the
//! **position in the output list** being considered. Repeat once for the first element, twice for
//! the second element, three times for the third element, and so on. So, if the third element of
//! the output list is being calculated, repeating the values would produce:
//! `0, 0, 0, 1, 1, 1, 0, 0, 0, -1, -1, -1`.
//!
//! When applying the pattern, skip the very first value exactly once. (In other words, offset the
//! whole pattern left by one.) So, for the second element of the output list, the actual pattern
//! used would be: `0, 1, 1, 0, 0, -1, -1, 0, 0, 1, 1, 0, 0, -1, -1, ...`.
//!
//! After using this process to calculate each element of the output list, the phase is complete,
//! and the output list of this phase is used as the new input list for the next phase, if any.
//!
//! Given the input signal `12345678`, below are four phases of FFT. Within each phase, each output
//! digit is calculated on a single line with the result at the far right; each multiplication
//! operation shows the input digit on the left and the pattern value on the right:
//!
//! ```txt
//! Input signal: 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
//!
//! After 1 phase: 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
//!
//! After 2 phases: 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
//!
//! After 3 phases: 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
//!
//! After 4 phases: 01029498
//! ```
//!
//! Here are the first eight digits of the final output list after 100 phases for some larger
//! inputs:
//!
//! - `80871224585914546619083218645595` becomes `24176176`.
//! - `19617804207202209144916044189917` becomes `73745418`.
//! - `69317163492948606335995924319873` becomes `52432133`.
//!
//! After **100** phases of FFT, **what are the first eight digits in the final output list?**
//!
//! [gas giants]: https://en.wikipedia.org/wiki/Gas_giant

use anyhow::Result;

pub const INPUT: &str = include_str!("d16.txt");

pub fn solve_part_one(input: &str) -> Result<i64> {
    Ok(0)
}

pub fn solve_part_two(input: &str) -> Result<i64> {
    Ok(0)
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn part_one() {}

    #[test]
    fn part_two() {}
}