summaryrefslogtreecommitdiff
path: root/2018/src
diff options
context:
space:
mode:
authorTom Smeding <tom.smeding@gmail.com>2018-12-05 13:15:03 +0100
committerTom Smeding <tom.smeding@gmail.com>2018-12-05 13:15:03 +0100
commitd38746c3b68f139fb2f6df78a219c2577fc0338c (patch)
treebf51edf668f9054ea8b3c28aa6043061ad136d83 /2018/src
parentd139374ef1518c5bd4e5c84e1d88263fdda2e15c (diff)
Day 5 + benchmarking
Diffstat (limited to '2018/src')
-rw-r--r--2018/src/day1.rs10
-rw-r--r--2018/src/day2.rs9
-rw-r--r--2018/src/day3.rs8
-rw-r--r--2018/src/day4.rs8
-rw-r--r--2018/src/day5.rs88
-rw-r--r--2018/src/main.rs86
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),