From bfecedb355b768d19bf7f29c9b13c1d9d9daa895 Mon Sep 17 00:00:00 2001
From: Curtis McEnroe <programble@gmail.com>
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/bin')

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