day 9

1 files changed, 62 insertions, 0 deletions

diff --git a/src/2020/9/mod.rs b/src/2020/9/mod.rs
new file mode 100644
index 0000000..ac7e14c
--- /dev/null
+++ b/src/2020/9/mod.rs
@@ -0,0 +1,62 @@
+pub fn part1() -> anyhow::Result<i64> {
+    const WINDOW: usize = 25;
+
+    let list = crate::util::read_ints("data/9.txt")?;
+    for i in 0..(list.len() - WINDOW) {
+        let set = &list[i..i + WINDOW];
+        let n = list[i + WINDOW];
+        if !valid(set, n) {
+            return Ok(n);
+        }
+    }
+
+    Err(anyhow::anyhow!("failed to find invalid number"))
+}
+
+pub fn part2() -> anyhow::Result<i64> {
+    const WINDOW: usize = 25;
+
+    let list = crate::util::read_ints("data/9.txt")?;
+    let mut invalid = None;
+    for i in 0..(list.len() - WINDOW) {
+        let set = &list[i..i + WINDOW];
+        let n = list[i + WINDOW];
+        if !valid(set, n) {
+            invalid = Some(n);
+        }
+    }
+    if invalid.is_none() {
+        return Err(anyhow::anyhow!("failed to find invalid number"));
+    }
+    let invalid = invalid.unwrap();
+
+    for i in 0..list.len() {
+        for j in i..list.len() {
+            let seq = &list[i..=j];
+            if invalid == seq.iter().sum() {
+                return Ok(seq.iter().copied().min().unwrap()
+                    + seq.iter().copied().max().unwrap());
+            }
+        }
+    }
+
+    Err(anyhow::anyhow!(
+        "failed to find sequence summing to invalid number"
+    ))
+}
+
+fn valid(set: &[i64], n: i64) -> bool {
+    for i in 0..set.len() {
+        for j in 0..set.len() {
+            if i == j {
+                continue;
+            }
+            let i = set[i];
+            let j = set[j];
+            if i + j == n {
+                return true;
+            }
+        }
+    }
+    false
+}