advent-of-code

commit 12391979efbcb423aca0f1ea5c4a552e133b5845
parent cbd3c63584bd7d7bb68db69deabd59368afc2700
Author: Shimmy Xu <shimmy.xu@shimmy1996.com>
Date:   Mon, 16 Dec 2019 10:06:03 -0500

Add Rust solution for day 16

Diffstat:
A
day-16/day-16.rs
 | 
56
++++++++++++++++++++++++++++++++++++++++++++++++++++++++

1 file changed, 56 insertions(+), 0 deletions(-)
diff --git a/day-16/day-16.rs b/day-16/day-16.rs
@@ -0,0 +1,56 @@
+fn main() {
+    let input = std::fs::read_to_string("input.txt")
+        .unwrap()
+        .trim()
+        .chars()
+        .map(|ch| ch.to_digit(10).unwrap() as i32)
+        .collect::<Vec<i32>>();
+    println!("Rust:");
+    println!("Part 1: {}", part_1(&input));
+    println!("Part 2: {}", part_2(&input));
+}
+
+fn fft(signal: &mut Vec<i32>) {
+    let pattern = [0, 1, 0, -1];
+    for i in 0..signal.len() {
+        let mut curr_signal = 0;
+        for j in i..signal.len() {
+            curr_signal += pattern[(j + 1) / (i + 1) % pattern.len()] * signal[j];
+        }
+        signal[i] = curr_signal.abs() % 10;
+    }
+}
+
+fn digits_to_num(digits: &[i32]) -> i32 {
+    digits.iter().fold(0, |acc, digit| acc * 10 + digit)
+}
+
+fn part_1(input: &Vec<i32>) -> i32 {
+    let mut signal = input.clone();
+    for _ in 0..100 {
+        fft(&mut signal);
+    }
+    digits_to_num(&signal[..8])
+}
+
+fn part_2(input: &Vec<i32>) -> i32 {
+    let offset = digits_to_num(&input[..7]) as usize;
+    // We only care about signal beyond the offset.
+    let mut signal = (offset..(10000 * input.len()))
+        .map(|i| input[i % input.len()])
+        .collect::<Vec<_>>();
+    // Since this will be in latter half of the signal, the only pattern we see
+    // is i 0s and (n - i) 1s.
+    for _ in 0..100 {
+        signal = signal
+            .iter()
+            .rev()
+            .scan(0, |acc, &x| {
+                *acc += x;
+                Some(*acc % 10)
+            })
+            .collect();
+        signal.reverse();
+    }
+    digits_to_num(&signal[..8])
+}