Add day16, 2019

4 files changed, 96 insertions, 0 deletions

diff --git a/2019/rust/Cargo.toml b/2019/rust/Cargo.toml
index e49e67b..b29d375 100644
--- a/2019/rust/Cargo.toml
+++ b/2019/rust/Cargo.toml
@@ -13,4 +13,5 @@ members = [
     "day11",
     "day12",
     "day13",
+    "day16",
 ]
diff --git a/2019/rust/day16/Cargo.toml b/2019/rust/day16/Cargo.toml
new file mode 100644
index 0000000..c9108a6
--- /dev/null
+++ b/2019/rust/day16/Cargo.toml
@@ -0,0 +1,7 @@
+[package]
+name = "day16"
+version = "0.1.0"
+authors = ["cos <cos>"]
+edition = "2018"
+
+[dependencies]
diff --git a/2019/rust/day16/both_parts.sh b/2019/rust/day16/both_parts.sh
new file mode 100755
index 0000000..4c8dfd9
--- /dev/null
+++ b/2019/rust/day16/both_parts.sh
@@ -0,0 +1 @@
+$VG ../target/release/day16 < input
diff --git a/2019/rust/day16/src/main.rs b/2019/rust/day16/src/main.rs
new file mode 100644
index 0000000..543be53
--- /dev/null
+++ b/2019/rust/day16/src/main.rs
@@ -0,0 +1,87 @@
+use std::io::Read;
+
+struct FlawedPattern {
+    base: Vec<i8>,
+    repeat: usize,
+    pos: usize,
+}
+
+impl FlawedPattern {
+    fn new(base: Vec<i8>, repeat: usize) -> FlawedPattern {
+        FlawedPattern {
+            base,
+            repeat,
+            pos: 0,
+        }
+    }
+}
+
+impl Iterator for FlawedPattern {
+    type Item = i8;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        let ret = self.base[(self.pos / (self.repeat + 1)) % self.base.len()];
+        self.pos += 1;
+
+        Some(ret)
+    }
+}
+
+fn read_input() -> Vec<i8> {
+    let stdin = std::io::stdin();
+
+    stdin.lock().bytes().map(|byte| {
+        match byte {
+            Ok(b) => if b >= b'0' && b <= b'9' {
+                (b-b'0') as i8
+            } else if b == b'\n' || b == b'\r' {
+                -1
+            } else {
+                panic!("Invalid digit: {:?}", b);
+            },
+            _ => panic!("Invalid indata. {:?}", byte),
+        }
+    }).filter(|n| *n >= 0).map(|n| n as i8).collect()
+}
+
+fn calculate_digits(input: &Vec<i8>) -> Vec<i8> {
+    input.iter().rev()
+        .scan(0, |s, n| { *s += *n; *s %= 10; Some(*s)})
+        .collect::<Vec<i8>>().into_iter()
+        .rev().map(|n| n.abs() % 10)
+        .collect()
+}
+
+fn calculate_digit(input: &Vec<i8>, n: usize) -> i8 {
+    let base_pattern = vec![0, 1, 0, -1];
+
+    let fft = FlawedPattern::new(base_pattern, n);
+    let factors: Vec<i8> = input.iter()
+        .zip(fft.skip(1).take(input.len()).collect::<Vec<i8>>())
+        .map(|(n, m)| (*n)*m).collect();
+
+    (factors.iter().map(|n| i64::from(*n)).sum::<i64>().abs() % 10) as i8
+}
+
+fn main() {
+    let input = read_input();
+    let mut num = input.clone();
+
+    for _ in 0..100 {
+        num = (0..num.len())
+            .map(|n| calculate_digit(&num, n))
+            .collect();
+    }
+    let part1: usize = num.iter().take(8).fold(0, |r, n| r*10 + (*n as usize));
+    println!("part1: {}", part1);
+
+    num = input;
+    let offset = num.iter().take(7).fold(0, |r, n| r*10 + (*n as usize));
+    let repeat = 10000;
+    let len = num.len();
+    num = num.into_iter().cycle().take(len*repeat).skip(offset).collect();
+
+    for _ in 0..100 { num = calculate_digits(&num); }
+    let part2: usize = num.iter().take(8).fold(0, |r, n| r*10 + (*n as usize));
+    println!("part2: {}", part2);
+}