Add day09, 2020

3 files changed, 154 insertions, 1 deletions

diff --git a/2020/rust/Cargo.toml b/2020/rust/Cargo.toml
index 6ace855..a51672a 100644
--- a/2020/rust/Cargo.toml
+++ b/2020/rust/Cargo.toml
@@ -9,7 +9,7 @@ members = [
     "day06",
     "day07",
     "day08",
-#    "day09",
+    "day09",
 #    "day10",
 #    "day11",
 #    "day12",
diff --git a/2020/rust/day09/Cargo.toml b/2020/rust/day09/Cargo.toml
new file mode 100644
index 0000000..0bff774
--- /dev/null
+++ b/2020/rust/day09/Cargo.toml
@@ -0,0 +1,10 @@
+[package]
+name = "day09"
+version = "0.1.0"
+authors = ["cos <cos>"]
+edition = "2018"
+
+[dependencies]
+aoc = { path = "../aoc" }
+anyhow = "1.0"
+getopts = "0.2"
diff --git a/2020/rust/day09/src/main.rs b/2020/rust/day09/src/main.rs
new file mode 100644
index 0000000..d62f0d4
--- /dev/null
+++ b/2020/rust/day09/src/main.rs
@@ -0,0 +1,143 @@
+use anyhow::Result;
+use getopts::Options;
+use std::env;
+use std::fs::File;
+use std::io::{BufRead, BufReader};
+use std::path::Path;
+
+const DEFAULT_PREAMBLE: usize = 25;
+
+fn usage(program: &str, opts: Options) {
+    let brief = format!("Usage: {} [options] INPUT", program);
+    print!("{}", opts.usage(&brief));
+}
+
+fn parse_args() -> (usize, Vec<String>) {
+    let args: Vec<String> = env::args().collect();
+    let program = args[0].clone();
+
+    let mut opts = Options::new();
+    opts.optopt("p", "preamble", "set preamble length", "25");
+    opts.optflag("h", "help", "print this help menu");
+    let matches = match opts.parse(&args[1..]) {
+        Ok(m) => { m }
+        Err(f) => { panic!(f.to_string()) }
+    };
+    if matches.opt_present("h") {
+        usage(&program, opts);
+        std::process::exit(0);
+    }
+    let preamble = match matches.opt_str("p") {
+        Some(p) => p.parse().expect("Could not parse preamble"),
+        None => DEFAULT_PREAMBLE,
+    };
+    let free = if !matches.free.is_empty() {
+        matches.free
+    } else {
+        usage(&program, opts);
+        std::process::exit(1);
+    };
+
+    (preamble, free)
+}
+
+fn read_input<T: AsRef<Path>>(filename: T) -> Result<Vec<usize>> {
+    let f = File::open(filename)?;
+    let reader = BufReader::new(f);
+
+    let values = reader.lines()
+        .map(|v| v?.parse::<usize>().map_err(anyhow::Error::new)).collect();
+
+    values
+}
+
+fn is_valid_xmas(data: &[usize]) -> bool {
+    let last = data[data.len()-1];
+    for first in 0..data.len()-2 {
+        for second in first+1..data.len()-1 {
+            let sum = data[first] + data[second];
+            if sum == last && data[first] != data[second] {
+                return true;
+            }
+        }
+    }
+
+    false
+}
+
+fn find_sum(needle: usize, data: &[usize]) -> Option<&[usize]> {
+    for first in 0..data.len()-1 {
+        for len in 2..data.len()-first {
+            let slice = data.get(first..first+len).unwrap();
+            let sum: usize = slice.iter().sum();
+            if sum == needle {
+                return Some(slice);
+            }
+        }
+    }
+
+    None
+}
+
+fn part1(input: &[usize], preamble: usize) -> Option<usize> {
+    for index in 0..(input.len()-preamble) {
+        if ! is_valid_xmas(&input[index..(index+preamble+1)]) {
+            return Some(input[index+preamble]);
+        }
+    }
+
+    None
+}
+
+fn part2(input: &[usize], preamble: usize) -> Option<usize> {
+    for index in 0..(input.len()-preamble) {
+        if ! is_valid_xmas(&input[index..(index+preamble+1)]) {
+            if let Some(found) = find_sum(input[index+preamble], input) {
+                return Some(found.iter().min().unwrap() + found.iter().max().unwrap());
+            }
+        }
+    }
+
+    None
+}
+
+fn main() {
+    let ( do_part_1, do_part_2 ) = aoc::do_parts();
+
+    let (preamble, args) = parse_args();
+    let filename = match args.get(0) {
+        Some(f) => f,
+        None => {
+            eprintln!("Missing input filename");
+            std::process::exit(1);
+        },
+    };
+    match read_input(filename) {
+        Ok(input) => {
+            if preamble > input.len() {
+                eprintln!("A preamble of {} is not possible with an input of {} elements",
+                    preamble, input.len());
+                std::process::exit(1);
+            }
+            if do_part_1 {
+                match part1(&input, preamble) {
+                    Some(solution) => println!("Part1: {}", solution),
+                    None => {
+                        eprintln!("Part1, no solution found");
+                        std::process::exit(1);
+                    }
+                };
+            }
+            if do_part_2 {
+                match part2(&input, preamble) {
+                    Some(solution) => println!("Part2: {}", solution),
+                    None => {
+                        eprintln!("Part2, no solution found");
+                        std::process::exit(1);
+                    }
+                };
+            }
+        },
+        Err(err) => eprintln!("Could not read input: {}", err),
+    }
+}