diff options
author | Tom Smeding <tom.smeding@gmail.com> | 2018-12-05 13:15:03 +0100 |
---|---|---|
committer | Tom Smeding <tom.smeding@gmail.com> | 2018-12-05 13:15:03 +0100 |
commit | d38746c3b68f139fb2f6df78a219c2577fc0338c (patch) | |
tree | bf51edf668f9054ea8b3c28aa6043061ad136d83 /2018/src/day5.rs | |
parent | d139374ef1518c5bd4e5c84e1d88263fdda2e15c (diff) |
Day 5 + benchmarking
Diffstat (limited to '2018/src/day5.rs')
-rw-r--r-- | 2018/src/day5.rs | 88 |
1 files changed, 88 insertions, 0 deletions
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())) +} |