From 3b877bf4cc667eb8bcc787d145203600a4dba2d2 Mon Sep 17 00:00:00 2001
From: Prefetch
Date: Sat, 25 Feb 2023 11:41:27 +0100
Subject: Initial commit

---
 d20/src/main.rs | 72 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 72 insertions(+)
 create mode 100644 d20/src/main.rs

(limited to 'd20/src/main.rs')

diff --git a/d20/src/main.rs b/d20/src/main.rs
new file mode 100644
index 0000000..fbfd5dc
--- /dev/null
+++ b/d20/src/main.rs
@@ -0,0 +1,72 @@
+use std::fs;
+
+fn solve_part1(ranges: &Vec<(u32, u32)>) -> u32 {
+    'outer: for i in 0..u32::MAX {
+        for &(lower, upper) in ranges {
+            if i >= lower && i <= upper {
+                // This IP is blacklisted
+                continue 'outer;
+            }
+        }
+
+        return i;
+    }
+
+    u32::MAX // shouldn't be reached
+}
+
+fn solve_part2(mut ranges: Vec<(u32, u32)>) -> u32 {
+    // Sort by upper limit, so we know if a range is still needed
+    ranges.sort_by_key(|x| x.1);
+
+    let mut count = 0;
+    'outer: for i in 0..u32::MAX {
+        // Reduce the size of `ranges' to keep loop time reasonable
+        if i > ranges[0].1 {
+            ranges.remove(0);
+        }
+
+        for &(lower, upper) in &ranges {
+            if i >= lower && i <= upper {
+                // This IP is blacklisted
+                continue 'outer;
+            }
+        }
+
+        count += 1;
+    }
+
+    count
+}
+
+fn main() {
+    // Read blacklist from input text file
+    let input = fs::read_to_string("input.txt").unwrap();
+    let lines: Vec<&str> = input.lines().collect();
+
+    let mut ranges = Vec::new();
+    for line in lines {
+        let split: Vec<&str> = line.split('-').collect();
+        let lower: u32 = split[0].parse().unwrap();
+        let upper: u32 = split[1].parse().unwrap();
+        ranges.push((lower, upper));
+    }
+    ranges.sort_by_key(|x| x.0);
+
+    // Part 1 gives 23923783 for me
+    println!("Part 1 solution: {}", solve_part1(&ranges));
+
+    // Part 2 gives 125 for me
+    println!("Part 2 solution: {}", solve_part2(ranges));
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn part1_example1() {
+        let ranges = vec![(5, 8), (0, 2), (4, 7)];
+        assert_eq!(solve_part1(&ranges), 3);
+    }
+}
-- 
cgit v1.2.3