2 files changed, 75 insertions, 1 deletions
diff --git a/input16 b/input16
new file mode 100644
index 0000000..a255272
--- /dev/null
+++ b/input16
@@ -0,0 +1 @@
+59750530221324194853012320069589312027523989854830232144164799228029162830477472078089790749906142587998642764059439173975199276254972017316624772614925079238407309384923979338502430726930592959991878698412537971672558832588540600963437409230550897544434635267172603132396722812334366528344715912756154006039512272491073906389218927420387151599044435060075148142946789007756800733869891008058075303490106699737554949348715600795187032293436328810969288892220127730287766004467730818489269295982526297430971411865028098708555709525646237713045259603175397623654950719275982134690893685598734136409536436003548128411943963263336042840301380655801969822
diff --git a/src/main.rs b/src/main.rs
index d3a56b5..f99156c 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -1600,8 +1600,52 @@ fn day15() {
     println!("15b: {}", time);
 }
 
+fn fft_pattern(pos: usize) -> Vec<i8> {
+    let base_pattern = vec![0, 1, 0, -1];
+
+    let mut pattern = Vec::new();
+    pattern.reserve(pos * base_pattern.len());
+
+    for d in base_pattern {
+        for _ in 0..pos+1 {
+            pattern.push(d);
+        }
+    }
+    pattern
+}
+
+fn fft(input: &[i8]) -> Vec<i8> {
+    let mut output = Vec::new();
+
+    for i in 0..input.len() {
+        let pattern = fft_pattern(i);
+        let mut sum : i32 = 0;
+        for j in 0..input.len() {
+            sum += input[j] as i32 * pattern[(j+1) % pattern.len()] as i32;
+        }
+        output.push((sum % 10).abs() as i8);
+    }
+
+    output
+}
+
+fn day16() {
+    let input = read_file("input16");
+    let input = input.trim_end();
+    let mut values : Vec<i8> = input.chars().map(|x| x.to_digit(10).unwrap() as i8).collect();
+    for _ in 0..100 {
+        values = fft(&values);
+    }
+
+    print!("16a: ");
+    for d in 0..8 {
+        print!("{}", values[d]);
+    }
+    println!();
+}
+
 fn main() {
-    day15();
+    day16();
 }
 
 #[cfg(test)]
@@ -1879,4 +1923,33 @@ mod tests {
         assert_eq!(reactions.count_material(1, "FUEL"), 2210736);
         //assert_eq!(reactions.possible_fuel(), 460664);
     }
+
+    #[test]
+    fn test_day16() {
+        assert_eq!(fft(&[1,2,3,4,5,6,7,8]), [4,8,2,2,6,1,5,8]);
+        assert_eq!(fft(&[4,8,2,2,6,1,5,8]), [3,4,0,4,0,4,3,8]);
+        assert_eq!(fft(&[3,4,0,4,0,4,3,8]), [0,3,4,1,5,5,1,8]);
+        assert_eq!(fft(&[0,3,4,1,5,5,1,8]), [0,1,0,2,9,4,9,8]);
+
+        let input = "80871224585914546619083218645595";
+        let mut values : Vec<i8> = input.chars().map(|x| x.to_digit(10).unwrap() as i8).collect();
+        for _ in 0..100 {
+            values = fft(&values);
+        }
+        assert_eq!(values[0..8], [2,4,1,7,6,1,7,6]);
+
+        let input = "19617804207202209144916044189917";
+        let mut values : Vec<i8> = input.chars().map(|x| x.to_digit(10).unwrap() as i8).collect();
+        for _ in 0..100 {
+            values = fft(&values);
+        }
+        assert_eq!(values[0..8], [7,3,7,4,5,4,1,8]);
+
+        let input = "69317163492948606335995924319873";
+        let mut values : Vec<i8> = input.chars().map(|x| x.to_digit(10).unwrap() as i8).collect();
+        for _ in 0..100 {
+            values = fft(&values);
+        }
+        assert_eq!(values[0..8], [5,2,4,3,2,1,3,3]);
+    }
 }