From bfecedb355b768d19bf7f29c9b13c1d9d9daa895 Mon Sep 17 00:00:00 2001 From: Curtis McEnroe Date: Tue, 20 Dec 2016 21:38:16 -0500 Subject: Day 20 part 2 I'm not quite sure why I need the +1. --- src/bin/day20.rs | 49 ++++++++++++++++++++++++++++++++++++++++++------- 1 file changed, 42 insertions(+), 7 deletions(-) (limited to 'src') diff --git a/src/bin/day20.rs b/src/bin/day20.rs index 3ed55af..396bb7c 100644 --- a/src/bin/day20.rs +++ b/src/bin/day20.rs @@ -1,18 +1,21 @@ use std::io::{self, Read}; +use std::u32; -fn solve(input: &str) -> u32 { +fn parse_ranges(input: &str) -> Vec<(u32, u32)> { let mut ranges = vec![]; - for line in input.lines() { let hyphen = line.find('-').unwrap(); let (start, end) = line.split_at(hyphen); - let start: u32 = start.parse().unwrap(); - let end: u32 = end[1..].parse().unwrap(); + let start = start.parse().unwrap(); + let end = end[1..].parse().unwrap(); ranges.push((start, end)); } - ranges.sort(); + ranges +} +fn solve1(input: &str) -> u32 { + let ranges = parse_ranges(input); let mut lowest = 0; for &(start, end) in &ranges { @@ -24,11 +27,33 @@ fn solve(input: &str) -> u32 { lowest } +fn solve2(input: &str) -> u32 { + let ranges = parse_ranges(input); + let mut merged = vec![]; + + for &(start, end) in &ranges { + if let Some(&mut (ref mut last_start, ref mut last_end)) = merged.last_mut() { + if start >= *last_start && end <= *last_end { + continue; + } else if start >= *last_start && start <= *last_end + 1 && end > *last_end { + *last_end = end; + continue; + } + } + merged.push((start, end)); + } + + let blocked: u32 = merged.iter().map(|&(start, end)| end - start + 1).sum(); + + u32::MAX - blocked + 1 +} + fn main() { let mut input = String::new(); io::stdin().read_to_string(&mut input).unwrap(); - println!("Part 1: {}", solve(&input)); + println!("Part 1: {}", solve1(&input)); + println!("Part 2: {}", solve2(&input)); } #[test] @@ -38,5 +63,15 @@ fn part1() { 0-2 4-7 "; - assert_eq!(3, solve(input.trim())); + assert_eq!(3, solve1(input.trim())); +} + +#[test] +fn part2() { + let input = " +5-8 +0-2 +4-7 +"; + assert_eq!(u32::MAX - 8, solve2(input.trim())); } -- cgit 1.4.1