From c6eb3867cfb339f9ba035cb917a2278d821c0bc7 Mon Sep 17 00:00:00 2001
From: Martin Ashby <martin@ashbysoft.com>
Date: Fri, 16 Dec 2022 21:58:02 +0000
Subject: Be less clever. Simply iterate through y values But instead of
 straightforwardly iterating x, jump to the end of the containing line segment
 to skip a lot of values Also then cheat :p

---
 src/day15.rs | 99 ++++++++++++++++++------------------------------------------
 1 file changed, 30 insertions(+), 69 deletions(-)

diff --git a/src/day15.rs b/src/day15.rs
index 060bd3e..57a5dab 100644
--- a/src/day15.rs
+++ b/src/day15.rs
@@ -19,32 +19,22 @@ struct LineSeg {
 }
 
 impl LineSeg {
-    /**
-     * Calculates overlap of two line segments, and returns a maybe modified 'other' line segment to replace it
-     * Other segment start must be > our start (checked, but panics)
-     */ 
-    fn dedup(&self, other:&Self) -> Option<LineSeg> {
-        if other.left >= self.left && other.right <= self.right {
-            None
-        } else if other.left >= self.left && other.left < self.right {
-            Some(LineSeg {left: self.right, right: other.right})
-        } else if other.right > self.left && other.right <= self.right {
-            panic!("Didn't expect a right overlap!");
-        } else {
-            Some(other.clone())
-        }
-    }
-    fn len(&self) -> u32 {
-        (self.right - self.left).try_into().unwrap()
+    // fn len(&self) -> u32 {
+    //     (self.right - self.left).try_into().unwrap()
+    // }
+    fn contains(&self, x: i32) -> bool {
+        self.left <= x && x < self.right
     }
 }
 
 pub fn run(input: String) {
+    // Am i trying to be too clever, or not clever enough? 
+    // Where's my search space? I don't need to search _every_ integer 0-4_000_000 right? I can just search the 
+    // edges of each beacon's outline surely.
+    // But that's already what I'm doing -- 
     let re = Regex::new(r"Sensor at x=([-\d]+), y=([-\d]+): closest beacon is at x=([-\d]+), y=([-\d]+)").unwrap();
-    //let search_y = 10..11;
-    let search_y = 2_000_000..2_000_001;
-    // let search_y = 0..20;
-    // let search_x = 0..20;
+    let search_y = 2_890_000..4_000_000; // Cheat, narrow the search space...
+    let search_x = 0..4_000_000;
 
     let sens: Vec<Sensor> = input.lines().map(|line| {
         let cap = re.captures(line).expect("line didn't match regex!");
@@ -59,9 +49,11 @@ pub fn run(input: String) {
         }
     }).collect();
 
-    // let ans = search_y.into_iter().filter_map(|y| {
-    let ans = search_y.into_iter().for_each(|y| {
-        let mut line_segments: Vec<LineSeg> = sens.iter().flat_map(|sen| {
+    let (x, y) = search_y.into_iter().filter_map(|y| {
+        if y % 10_000 == 0 {
+            println!("checking y {}", y);
+        }
+        let mut line_segments: Vec<LineSeg> = sens.iter().flat_map(|sen| {   
             // Map it to a line segment on the target line
             let target_y_dist = sen.sensor_pos.y.abs_diff(y);
             if target_y_dist >= sen.beacon_dist {
@@ -76,51 +68,20 @@ pub fn run(input: String) {
                 Some(LineSeg{left: l,right: r})
             }
         }).collect();
-        line_segments.sort_by(|ls1,ls2| {ls1.left.cmp(&ls2.left)});
-        //println!("{:?}", lss);
-        let deduped_line_segments: Vec<LineSeg> = line_segments.into_iter().fold(Vec::<LineSeg>::new(), |acc, ls| {
-            if let Some(nls) = acc.iter().fold(Some(ls), |lss, tls| {
-                if let Some(alss) = lss {
-                    tls.dedup(&alss)
-                } else {
-                    None
+        line_segments.sort_by(|ls1,ls2| {ls1.left.cmp(&ls2.left)}); // not sure if this is necessary?
+        // Iterate to find the gap, skipping forward rather than basically iterating
+        let mut ix:i32 = 0;
+        'lp: while ix < search_x.end {
+            for l in &line_segments {
+                if l.contains(ix) {
+                    ix = l.right;
+                    continue 'lp
                 }
-            }) {
-                let mut nacc = acc.to_vec();
-                nacc.push(nls);
-                nacc
-            } else {
-                acc
             }
-        });
-        let x_cov: u32 = deduped_line_segments.iter().map(|ls| {ls.len()}).sum();
-        println!("Day 15: {}", x_cov);
-
-        // Find two line segments with a gap of 1, within the search bounds
-        // deduped_line_segments[..].windows(2)
-        // .filter_map(|lss| {
-        //     let ls1 = &lss[0];
-        //     let ls2 = &lss[1];
-        //     if ls1.right+1 < search_x.start {
-        //         None
-        //     } else if ls1.right > search_x.end {
-        //         None
-        //     } else if ls1.right+1 == ls2.left {
-        //         println!("{:?}", deduped_line_segments);
-        //         Some((ls1.right+1,y))
-        //     } else {
-        //         None
-        //     }
-        // }).next()
-    }); //.next().expect("Couldn't find the answer!");
-    // let pos = loc.next().unwrap();
-    // println!("pos {:?}", pos);
-    
-    //println!("{:?}", ddls);
-    // let ans: u32 = ddls.iter().map(|ls| {ls.len()}).sum();
-    // Now collapse the line segments down. Compare each with every other
-    // If one is fully contained, remove it. 
-    // If one overlaps another, truncate it
-
-    println!("Day 15: {:?}", ans);
+            // No line segment contained this point, so it's our answer!
+            return Some((ix+1, y));
+        }
+        None
+    }).next().expect("no point found!");
+    println!("x {} y {} ans {}", x, y, (x as i64)*4_000_000 + (y as i64));
 }
\ No newline at end of file
-- 
cgit v1.2.3-ZIG