day15 pt1

3 files changed, 145 insertions, 17 deletions

diff --git a/src/day14.rs b/src/day14.rs
index 97c06fe..a89ed06 100644
--- a/src/day14.rs
+++ b/src/day14.rs
@@ -1,7 +1,7 @@
 const AIR: char = '.';
 const ROCK: char = '#';
-const SANDSPAWN: char = '+';
-const MOVING_SAND: char = '*';
+//const SANDSPAWN: char = '+';
+//const MOVING_SAND: char = '*';
 const STUCK_SAND: char  = 'o';
 
 pub fn run(input: String) {
@@ -108,18 +108,18 @@ fn mov(grid: &Vec<Vec<char>>, sand: &(usize,usize)) -> Option<(usize,usize)> {
     }
 }
 
-fn print(grid: &Vec<Vec<char>>, sandspawn: &(usize,usize), sand: &(usize,usize)) {
-    for (y, line) in grid.into_iter().enumerate() {
-        for (x, ch) in line.into_iter().enumerate().skip(480) {
-            let pt = (x,y);
-            if sand == &pt {
-                print!("{}", MOVING_SAND);
-            } else if sandspawn == &pt {
-                print!("{}", SANDSPAWN);
-            } else {
-                print!("{}", ch);
-            }
-        }
-        print!("\n");
-    }
-}
\ No newline at end of file
+// fn print(grid: &Vec<Vec<char>>, sandspawn: &(usize,usize), sand: &(usize,usize)) {
+//     for (y, line) in grid.into_iter().enumerate() {
+//         for (x, ch) in line.into_iter().enumerate().skip(480) {
+//             let pt = (x,y);
+//             if sand == &pt {
+//                 print!("{}", MOVING_SAND);
+//             } else if sandspawn == &pt {
+//                 print!("{}", SANDSPAWN);
+//             } else {
+//                 print!("{}", ch);
+//             }
+//         }
+//         print!("\n");
+//     }
+// }
\ No newline at end of file
diff --git a/src/day15.rs b/src/day15.rs
new file mode 100644
index 0000000..060bd3e
--- /dev/null
+++ b/src/day15.rs
@@ -0,0 +1,126 @@
+use regex::Regex;
+
+#[derive(Debug,Clone)]
+struct Pos {
+    x: i32,
+    y: i32
+}
+
+#[derive(Debug)]
+struct Sensor {
+    sensor_pos: Pos,
+    beacon_dist: u32
+}
+
+#[derive(Debug,Clone)]
+struct LineSeg {
+    left: i32,
+    right: i32, // Exclusive!
+}
+
+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()
+    }
+}
+
+pub fn run(input: String) {
+    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 sens: Vec<Sensor> = input.lines().map(|line| {
+        let cap = re.captures(line).expect("line didn't match regex!");
+        let sensor_x: i32 = cap[1].parse().expect("sx wasn't an i32!");
+        let sensor_y: i32 = cap[2].parse().expect("sy wasn't an i32!");
+        let beacon_x: i32 = cap[3].parse().expect("bx wasn't an i32!");
+        let beacon_y: i32 = cap[4].parse().expect("by wasn't an i32!");
+        let beacon_dist = sensor_x.abs_diff(beacon_x)+sensor_y.abs_diff(beacon_y);
+        Sensor {
+            sensor_pos: Pos { x: sensor_x, y: sensor_y },
+            beacon_dist,
+        }
+    }).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| {
+            // 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 {
+                // It's too far from the target line entirely
+                None
+            } else {
+                // Reach along the line is the remaining beacon dist after reachig target y
+                let reach = sen.beacon_dist  - target_y_dist;
+                let l = sen.sensor_pos.x-(reach as i32);
+                let r = sen.sensor_pos.x+(reach as i32);
+                //println!("{:?} yd {} reach {} l {} r {}", sen, yd, reach, l,r);
+                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
+                }
+            }) {
+                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 newline at end of file
diff --git a/src/main.rs b/src/main.rs
index 38ed88d..9b0ea44 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -16,6 +16,7 @@ mod day11;
 mod day12;
 mod day13;
 mod day14;
+mod day15;
 
 fn main() {
     day1::run(fs::read_to_string("input/day1.txt").expect("Failed to read input file!"));
@@ -32,4 +33,5 @@ fn main() {
     day12::run(fs::read_to_string("input/day12.txt").expect("Failed to read input file!"));
     day13::run(fs::read_to_string("input/day13.txt").expect("Failed to read input file!"));
     day14::run(fs::read_to_string("input/day14.txt").expect("Failed to read input file!"));
+    day15::run(fs::read_to_string("input/day15.txt").expect("Failed to read input file!"));
 }