1 files changed, 123 insertions, 0 deletions
diff --git a/day05/src/main.rs b/day05/src/main.rs
new file mode 100644
index 0000000..ce90869
--- /dev/null
+++ b/day05/src/main.rs
@@ -0,0 +1,123 @@
+use std::io;
+
+#[derive(Clone)]
+struct Range {
+    first: i64,
+    last: i64,
+}
+
+impl Range {
+    fn new(first: i64, last: i64) -> Self {
+        assert!(first <= last);
+        Self { first, last }
+    }
+
+    fn contains(&self, value: i64) -> bool {
+        value >= self.first && value <= self.last
+    }
+
+    fn len(&self) -> i64 {
+        1 + self.last - self.first
+    }
+}
+
+fn in_ranges(ranges: &Vec<Range>, value: i64) -> bool {
+    for range in ranges {
+        if range.contains(value) {
+            return true;
+        }
+    }
+    false
+}
+
+fn merge_or_add(ranges: &mut Vec<Range>, range: &Range) {
+    if range.len() == 0 {
+        return;
+    }
+    let i = ranges.partition_point(|x| x.last < range.first);
+    if i == ranges.len() {
+        ranges.push(range.clone());
+        return;
+    }
+    if ranges[i].first > range.last {
+        ranges.insert(i, range.clone());
+        return;
+    }
+    if ranges[i].contains(range.first) {
+        if ranges[i].contains(range.last) {
+            // Whole range is swallowed
+            return;
+        }
+        merge_or_add(ranges, &Range::new(ranges[i].last + 1, range.last));
+        return;
+    }
+    if ranges[i].contains(range.last) {
+        ranges.insert(i, Range::new(range.first, ranges[i].first - 1));
+        return;
+    }
+
+    let before = Range::new(range.first, ranges[i].first - 1);
+    let after = Range::new(ranges[i].last + 1, range.last);
+
+    ranges.insert(i, before);
+    merge_or_add(ranges, &after);
+}
+
+fn remove_overlap(ranges: &Vec<Range>) -> Vec<Range> {
+    let mut ret = Vec::new();
+
+    for range in ranges {
+        merge_or_add(&mut ret, range);
+    }
+
+    ret
+}
+
+fn main() {
+    let mut ranges = Vec::new();
+
+    loop {
+        let mut buffer = String::new();
+        let bytes = io::stdin().read_line(&mut buffer).unwrap();
+        if bytes == 0 || buffer == "\n" {
+            break;
+        }
+        let mut iter = buffer.trim_end().split('-');
+        let first = iter.next().unwrap().parse::<i64>().unwrap();
+        let last = iter.next().unwrap().parse::<i64>().unwrap();
+        ranges.push(Range::new(first, last));
+    }
+
+    ranges.sort_by(|a, b| a.first.cmp(&b.first));
+
+    let mut available = Vec::new();
+
+    loop {
+        let mut buffer = String::new();
+        let bytes = io::stdin().read_line(&mut buffer).unwrap();
+        if bytes == 0 {
+            break;
+        }
+        available.push(buffer.trim_end().parse::<i64>().unwrap());
+    }
+
+    let mut fresh = 0;
+
+    for ingredient in available {
+        if in_ranges(&ranges, ingredient) {
+            fresh += 1;
+        }
+    }
+
+    println!("Fresh ingrediences {}", fresh);
+
+    let ranges2 = remove_overlap(&ranges);
+
+    let mut fresh2 = 0;
+
+    for range in ranges2 {
+        fresh2 += range.len();
+    }
+
+    println!("Fresh ids {}", fresh2);
+}