From 02e2e9efee30055cab27a5a709e1e2d087e68fed Mon Sep 17 00:00:00 2001
From: omagdy7 <omar.professional8777@gmail.com>
Date: Tue, 5 Dec 2023 18:57:11 +0200
Subject: Almost part2 I think?

---
 2023/Rust/src/day5.rs | 92 ++++++++++++++++++++++++++++++++++++++++-----------
 1 file changed, 72 insertions(+), 20 deletions(-)

(limited to '2023')

diff --git a/2023/Rust/src/day5.rs b/2023/Rust/src/day5.rs
index bd57e90..36011f4 100644
--- a/2023/Rust/src/day5.rs
+++ b/2023/Rust/src/day5.rs
@@ -1,16 +1,42 @@
-use std::collections::HashSet;
+use std::{collections::HashSet, ops::Add, ops::AddAssign};
 
-fn solve_part_one(data: &str) -> u32 {
-    let mut almanac = Almanac::from(data);
-    let mut seeds = almanac.seeds.clone();
-    let mut nseeds = vec![];
-    for i in (0..seeds.len()).step_by(2) {
-        for j in seeds[i]..seeds[i] + seeds[i + 1] {
-            nseeds.push(j);
+#[derive(Debug, Clone, PartialEq, PartialOrd, Eq, Hash)]
+struct Range {
+    start: i64,
+    end: i64,
+}
+
+impl Range {
+    fn new(s: i64, e: i64) -> Self {
+        Self { start: s, end: e }
+    }
+
+    fn add(&mut self, inc: i64) {
+        self.start += inc;
+        self.end += inc;
+    }
+
+    fn contains(&self, val: i64) -> bool {
+        (self.start..self.end).contains(&val)
+    }
+
+    fn is_in(&self, other: &Range) -> bool {
+        self.start >= other.start && self.end <= other.end
+    }
+
+    fn overlap(&self, other: &Range) -> Option<(Range, Range)> {
+        use std::cmp::{max, min};
+        if self.start > other.start && self.start > other.end {
+            return None;
         }
+        let overlap_rng = Range::new(max(self.start, other.start), min(self.end, other.end - 1));
+        let rest = Range::new(overlap_rng.end + 1, max(self.start, other.start));
+        Some((overlap_rng, rest))
     }
-    almanac.seeds = nseeds;
+}
 
+fn solve_part_one(data: &str) -> u32 {
+    let almanac = Almanac::from(data);
     let mut seeds = almanac.seeds.clone();
     for (_, maps) in almanac.maps.iter() {
         for seed in seeds.iter_mut() {
@@ -26,18 +52,34 @@ fn solve_part_one(data: &str) -> u32 {
 }
 
 fn solve_part_two(data: &str) -> u64 {
-    let mut almanac = Almanac::from(data);
-    let seeds = almanac.seeds.clone();
-    let mut set: HashSet<i64> = HashSet::new();
-    let mut sum = 0;
-    for i in (0..seeds.len()).step_by(2) {
-        for j in seeds[i]..seeds[i] + seeds[i + 1] {
-            set.insert(j);
+    let almanac = Almanac::from(data);
+    let mut seeds: Vec<Range> = vec![];
+    for i in (0..almanac.seeds.len()).step_by(2) {
+        seeds.push(Range::new(
+            almanac.seeds[i],
+            almanac.seeds[i] + almanac.seeds[i + 1],
+        ))
+    }
+    for (_, maps) in almanac.maps.iter() {
+        dbg!(&seeds);
+        let mut new_seeds: HashSet<Range> = HashSet::from_iter(seeds.clone().into_iter());
+        for seed in seeds.iter_mut() {
+            let tmp = seed.clone();
+            for seed_map in maps.iter() {
+                if seed_map.is_in(&tmp) {
+                    (*seed).add(seed_map.dest as i64 - seed_map.src as i64);
+                } else if let Some((mut overlap_rng, rest)) = seed_map.overlap(&tmp) {
+                    overlap_rng.add(seed_map.dest as i64 - seed_map.src as i64);
+                    new_seeds.remove(seed);
+                    new_seeds.insert(overlap_rng);
+                    new_seeds.insert(rest);
+                }
+            }
         }
-        sum += seeds[i] + seeds[i + 1];
+        seeds = Vec::from_iter(new_seeds.into_iter());
     }
-    dbg!(set.len());
-    sum as u64
+    // dbg!(&seeds);
+    (*seeds).iter().map(|rng| rng.start).min().unwrap() as u64
 }
 
 type Seeds = Vec<i64>;
@@ -78,6 +120,16 @@ struct SeedMap {
 }
 
 impl SeedMap {
+    fn is_in(&self, seed: &Range) -> bool {
+        let rng = Range::new(self.src as i64, self.src as i64 + self.range_len as i64);
+        seed.is_in(&rng)
+    }
+
+    fn overlap(&self, seed: &Range) -> Option<(Range, Range)> {
+        let rng = Range::new(self.src as i64, self.src as i64 + self.range_len as i64);
+        seed.overlap(&rng)
+    }
+
     fn contains(&self, seed: i64) -> bool {
         (self.src..self.src + self.range_len).contains(&(seed as usize))
     }
@@ -102,6 +154,6 @@ fn main() {
     let prod = include_str!("../input/day5.prod");
     println!("part_1 test: {:?}", solve_part_one(test));
     println!("part_1 prod {:?}", solve_part_one(prod));
-    // println!("part_2 test: {:?}", solve_part_two(test));
+    println!("part_2 test: {:?}", solve_part_two(test));
     // println!("part_2 prod {:?}", solve_part_two(prod));
 }
-- 
cgit v1.2.3