Day 5 + benchmarking

6 files changed, 176 insertions, 33 deletions

diff --git a/2018/src/day1.rs b/2018/src/day1.rs
index 741f5b3..b86387b 100644
--- a/2018/src/day1.rs
+++ b/2018/src/day1.rs
@@ -2,11 +2,11 @@ use std::io;
 use std::io::BufRead;
 use std::collections::HashSet;
 
-pub fn main<T: BufRead>(reader: T) -> io::Result<()> {
+pub fn main<T: BufRead>(reader: T) -> io::Result<(String, String)> {
     let values: Vec<i64> =
         reader.lines().map(|l| l.unwrap().parse::<i64>().unwrap()).collect();
 
-    println!("{}", values.iter().sum::<i64>());
+    let part1 = values.iter().sum::<i64>();
 
     let mut seen = HashSet::new();
     seen.insert(0);
@@ -15,11 +15,11 @@ pub fn main<T: BufRead>(reader: T) -> io::Result<()> {
     for val in values.iter().cycle() {
         res += val;
         if seen.contains(&res) {
-            println!("{}", res);
-            return Ok(());
+            return Ok((part1.to_string(), res.to_string()));
         } else {
             seen.insert(res);
         }
     }
-    unreachable!()
+
+    Err(io::Error::new(io::ErrorKind::Other, "Invalid input"))
 }
diff --git a/2018/src/day2.rs b/2018/src/day2.rs
index 6564938..38fd4ba 100644
--- a/2018/src/day2.rs
+++ b/2018/src/day2.rs
@@ -15,7 +15,7 @@ fn close_enough(a: &str, b: &str) -> bool {
     return num == 1;
 }
 
-pub fn main<T: BufRead>(reader: T) -> io::Result<()> {
+pub fn main<T: BufRead>(reader: T) -> io::Result<(String, String)> {
     let lines: Vec<String> = reader.lines().map(|l| l.unwrap()).collect();
 
     let mut num2: i64 = 0;
@@ -40,7 +40,7 @@ pub fn main<T: BufRead>(reader: T) -> io::Result<()> {
         num3 += have3 as i64;
     }
 
-    println!("{}", num2 * num3);
+    let part1 = num2 * num3;
 
     // TODO: Can this be faster than n^2?
     for line1 in &lines {
@@ -55,10 +55,9 @@ pub fn main<T: BufRead>(reader: T) -> io::Result<()> {
                 }
             }
 
-            println!("{}", ans);
-            return Ok(())
+            return Ok((part1.to_string(), ans));
         }
     }
 
-    Ok(())
+    Err(io::Error::new(io::ErrorKind::Other, "Invalid input"))
 }
diff --git a/2018/src/day3.rs b/2018/src/day3.rs
index 15a4dc2..baba8fe 100644
--- a/2018/src/day3.rs
+++ b/2018/src/day3.rs
@@ -49,7 +49,7 @@ impl FromStr for Claim {
     }
 }
 
-pub fn main<T: BufRead>(reader: T) -> io::Result<()> {
+pub fn main<T: BufRead>(reader: T) -> io::Result<(String, String)> {
     let w = 1000;
     let maxnum = 1500;
 
@@ -80,13 +80,13 @@ pub fn main<T: BufRead>(reader: T) -> io::Result<()> {
         }
     }
 
-    println!("{}", double);
+    let part1 = double;
 
     for i in 1 .. maxnum as usize {
         if free[i] {
-            println!("{}", i);
+            return Ok((part1.to_string(), i.to_string()));
         }
     }
 
-    Ok(())
+    Err(io::Error::new(io::ErrorKind::Other, "Invalid input"))
 }
diff --git a/2018/src/day4.rs b/2018/src/day4.rs
index 90cab72..f5e219f 100644
--- a/2018/src/day4.rs
+++ b/2018/src/day4.rs
@@ -68,7 +68,7 @@ fn argmax<T: Ord>(v: &[T]) -> Option<usize> {
     }
 }
 
-pub fn main<T: BufRead>(reader: T) -> io::Result<()> {
+pub fn main<T: BufRead>(reader: T) -> io::Result<(String, String)> {
     let mut records: Vec<Record> = reader.lines().map(|l| parse_line(&l.unwrap())).collect();
 
     records.sort_unstable();
@@ -124,11 +124,11 @@ pub fn main<T: BufRead>(reader: T) -> io::Result<()> {
 
     let sleepy_guard = guards.get(&max_sleep_at).unwrap();
     let max_minute = argmax(&sleepy_guard.asleep).unwrap() as i32;
-    println!("{}", max_minute * sleepy_guard.id);
+    let part1 = max_minute * sleepy_guard.id;
 
     let consistent_guard = guards.get(&max_times_at).unwrap();
     let max_minute = argmax(&consistent_guard.asleep).unwrap() as i32;
-    println!("{}", max_minute * consistent_guard.id);
+    let part2 = max_minute * consistent_guard.id;
 
-    Ok(())
+    Ok((part1.to_string(), part2.to_string()))
 }
diff --git a/2018/src/day5.rs b/2018/src/day5.rs
new file mode 100644
index 0000000..4638858
--- /dev/null
+++ b/2018/src/day5.rs
@@ -0,0 +1,88 @@
+use std::io;
+use std::io::BufRead;
+
+fn reactive(a: u8, b: u8) -> bool {
+    a == b + 32 || b == a + 32
+}
+
+fn react(line: &mut [u8]) -> usize {
+    let len = line.len() as i64;
+    let mut gone = vec![false; len as usize];
+
+    let mut top: i64 = 0;
+    for ptr in 1..len {
+        if top >= ptr {
+            continue;
+        } else if reactive(line[top as usize], line[ptr as usize]) {
+            gone[top as usize] = true;
+            gone[ptr as usize] = true;
+            top -= 1;
+            while top > 0 && gone[top as usize] {
+                top -= 1;
+            }
+            if top < 0 {
+                top = ptr + 1;
+            }
+        } else {
+            top = ptr;
+        }
+    }
+
+    let mut j = 0;
+    for i in 0..len as usize {
+        if !gone[i] {
+            if j < i { line[j] = line[i]; }
+            j += 1;
+        }
+    }
+
+    j
+}
+
+fn full_react(bytes: &mut Vec<u8>, mut len: usize) -> usize {
+    loop {
+        let newlen = react(&mut bytes[..len]);
+        if newlen == len { break; }
+        len = newlen;
+    }
+
+    len
+}
+
+// Pass 'typ' as uppercase.
+fn remove_type(dest: &mut [u8], src: &[u8], typ: u8) -> usize {
+    let mut j = 0;
+    for i in 0..src.len() {
+        if src[i] != typ && src[i] != typ + 32 {
+            dest[j] = src[i];
+            j += 1;
+        }
+    }
+
+    j
+}
+
+pub fn main<T: BufRead>(reader: T) -> io::Result<(String, String)> {
+    let line = reader.lines().next().unwrap().unwrap();
+    let mut bytes: Vec<u8> = line.bytes().collect();
+    let mut len = bytes.len();
+
+    len = full_react(&mut bytes, len);
+
+    let part1 = len;
+
+    let mut minlen = len;
+
+    let mut bytes2 = bytes[..len].to_vec();
+    for typ in 65..65+26 {
+        let newlen = remove_type(&mut bytes2, &bytes[..len], typ);
+        let len2 = full_react(&mut bytes2, newlen);
+        if len2 < minlen {
+            minlen = len2;
+        }
+    }
+
+    let part2 = minlen;
+
+    Ok((part1.to_string(), part2.to_string()))
+}
diff --git a/2018/src/main.rs b/2018/src/main.rs
index 98c0f7b..f9098eb 100644
--- a/2018/src/main.rs
+++ b/2018/src/main.rs
@@ -3,39 +3,96 @@ extern crate regex;
 extern crate argparse;
 
 use std::io;
-use std::io::{BufRead, BufReader, Error, ErrorKind};
+use std::io::{BufRead, BufReader, Error, ErrorKind, Read};
 use std::fs::File;
 use std::process::exit;
+use std::time::Instant;
 use argparse::{ArgumentParser, StoreTrue, Store};
 
 mod day1;
 mod day2;
 mod day3;
 mod day4;
+mod day5;
 
-fn day_switch<T: BufRead>(day: i32, reader: T) -> io::Result<()> {
+static NUM_DAYS: i32 = 5;
+
+fn day_switch<T: BufRead>(day: i32, reader: T) -> io::Result<(String, String)> {
     match day {
         1 => day1::main(reader),
         2 => day2::main(reader),
         3 => day3::main(reader),
         4 => day4::main(reader),
+        5 => day5::main(reader),
         _ => Err(Error::new(ErrorKind::Other, "Invalid day"))
     }
 }
 
+fn file_for_day(day: i32) -> io::Result<BufReader<File>> {
+    match File::open(format!("../input/{}.txt", day)) {
+        Ok(f) => Ok(BufReader::new(f)),
+        Err(_) => Err(Error::new(ErrorKind::Other, format!("No input file for day {}", day)))
+    }
+}
+
+fn benchmark_day(day: i32) -> io::Result<f64> {
+    let num_iters = 100;
+
+    let mut input = Vec::new();
+    file_for_day(day)?.read_to_end(&mut input)?;
+
+    let start = Instant::now();
+    for _i in 0..num_iters {
+        day_switch(day, BufReader::new(&input[..]))?;
+    }
+    let end = Instant::now();
+
+    let dur = (end - start) / num_iters;
+    let secs = dur.as_secs() as f64 + dur.subsec_micros() as f64 / 1000000.0;
+
+    println!("Day {}: {} secs", day, secs);
+
+    Ok(secs)
+}
+
+fn benchmark_all_days() -> io::Result<()> {
+    let mut total = 0.0;
+    for day in 1..NUM_DAYS + 1 {
+        total += benchmark_day(day)?;
+    }
+    println!("Total: {} secs", total);
+    Ok(())
+}
+
 struct Options {
     use_stdin: bool,
+    bench: bool,
 }
 
 fn run_day(day: i32, opts: &Options) -> io::Result<()> {
-    if opts.use_stdin {
-        let stdin = io::stdin();
-        day_switch(day, BufReader::new(stdin))
+    let (part1, part2) = if opts.bench {
+        benchmark_day(day)?;
+        return Ok(())
+    } else if opts.use_stdin {
+        day_switch(day, BufReader::new(io::stdin()))?
+    } else {
+        day_switch(day, file_for_day(day)?)?
+    };
+
+    println!("{}", part1);
+    println!("{}", part2);
+    Ok(())
+}
+
+fn run_all_days(opts: &Options) -> io::Result<()> {
+    if opts.bench {
+        assert!(!opts.use_stdin);
+        benchmark_all_days()
     } else {
-        match File::open(format!("../input/{}.txt", day)) {
-            Ok(f) => day_switch(day, BufReader::new(f)),
-            Err(_) => Err(Error::new(ErrorKind::Other, format!("No input file for day {}", day)))
+        for day in 1..6 {
+            run_day(day, &opts)?;
         }
+        Ok(())
     }
 }
 
@@ -58,15 +115,17 @@ fn error_handler<F>(func: F) -> io::Result<()>
 fn main() -> io::Result<()> {
     let mut day_string = String::new();
     let mut options = Options {
-        use_stdin: false
+        use_stdin: false,
+        bench: false,
     };
 
     {
         let mut parser = ArgumentParser::new();
         parser.set_description("AOC 2018 solutions by Tom Smeding");
         parser.refer(&mut options.use_stdin)
-            .add_option(&["-s", "--stdin"], StoreTrue,
-                        "Read from stdin");
+            .add_option(&["-s", "--stdin"], StoreTrue, "Read from stdin");
+        parser.refer(&mut options.bench)
+            .add_option(&["-b", "--bench"], StoreTrue, "Benchmark the given days");
         parser.refer(&mut day_string)
             .add_argument("day", Store, "Day to execute");
         parser.parse_args_or_exit();
@@ -74,10 +133,7 @@ fn main() -> io::Result<()> {
 
     error_handler(||
         if day_string.len() == 0 {
-            for day in 1..5 {
-                run_day(day, &options)?;
-            }
-            Ok(())
+            run_all_days(&options)
         } else {
             match day_string.parse::<i32>() {
                 Ok(day) => run_day(day, &options),