day15 pt1

5 files changed, 192 insertions, 17 deletions

diff --git a/input/day15.txt b/input/day15.txt
new file mode 100644
index 0000000..68b61fa
--- /dev/null
+++ b/input/day15.txt
@@ -0,0 +1,33 @@
+Sensor at x=2899860, y=3122031: closest beacon is at x=2701269, y=3542780
+Sensor at x=1836719, y=1116779: closest beacon is at x=2037055, y=2000000
+Sensor at x=3995802, y=2706630: closest beacon is at x=3944538, y=3053285
+Sensor at x=2591204, y=2008272: closest beacon is at x=2597837, y=2509170
+Sensor at x=2546593, y=1538222: closest beacon is at x=2037055, y=2000000
+Sensor at x=252214, y=61954: closest beacon is at x=1087565, y=-690123
+Sensor at x=950, y=1106672: closest beacon is at x=-893678, y=1276864
+Sensor at x=1349445, y=1752783: closest beacon is at x=2037055, y=2000000
+Sensor at x=3195828, y=3483667: closest beacon is at x=3334657, y=3531523
+Sensor at x=2057761, y=2154359: closest beacon is at x=2037055, y=2000000
+Sensor at x=2315350, y=3364640: closest beacon is at x=2701269, y=3542780
+Sensor at x=327139, y=2426600: closest beacon is at x=-88420, y=3646947
+Sensor at x=3943522, y=2854345: closest beacon is at x=3944538, y=3053285
+Sensor at x=3358620, y=516881: closest beacon is at x=3260516, y=2246079
+Sensor at x=1788376, y=8679: closest beacon is at x=1087565, y=-690123
+Sensor at x=3344883, y=3537985: closest beacon is at x=3334657, y=3531523
+Sensor at x=2961064, y=2697125: closest beacon is at x=2597837, y=2509170
+Sensor at x=3780090, y=2093546: closest beacon is at x=3260516, y=2246079
+Sensor at x=3291917, y=3398703: closest beacon is at x=3334657, y=3531523
+Sensor at x=3999864, y=2998005: closest beacon is at x=3944538, y=3053285
+Sensor at x=2919272, y=3732950: closest beacon is at x=2701269, y=3542780
+Sensor at x=2057404, y=2947435: closest beacon is at x=2037055, y=2000000
+Sensor at x=1072126, y=645784: closest beacon is at x=1087565, y=-690123
+Sensor at x=3549465, y=2554712: closest beacon is at x=3260516, y=2246079
+Sensor at x=3550313, y=3121694: closest beacon is at x=3944538, y=3053285
+Sensor at x=3405149, y=3483630: closest beacon is at x=3334657, y=3531523
+Sensor at x=2600212, y=3961193: closest beacon is at x=2701269, y=3542780
+Sensor at x=1102632, y=3932527: closest beacon is at x=-88420, y=3646947
+Sensor at x=67001, y=3506079: closest beacon is at x=-88420, y=3646947
+Sensor at x=3994250, y=3975025: closest beacon is at x=3944538, y=3053285
+Sensor at x=3019750, y=2125144: closest beacon is at x=3260516, y=2246079
+Sensor at x=3282319, y=3656404: closest beacon is at x=3334657, y=3531523
+Sensor at x=2797371, y=3645126: closest beacon is at x=2701269, y=3542780
\ No newline at end of file
diff --git a/input/day15_ex.txt b/input/day15_ex.txt
new file mode 100644
index 0000000..652e631
--- /dev/null
+++ b/input/day15_ex.txt
@@ -0,0 +1,14 @@
+Sensor at x=2, y=18: closest beacon is at x=-2, y=15
+Sensor at x=9, y=16: closest beacon is at x=10, y=16
+Sensor at x=13, y=2: closest beacon is at x=15, y=3
+Sensor at x=12, y=14: closest beacon is at x=10, y=16
+Sensor at x=10, y=20: closest beacon is at x=10, y=16
+Sensor at x=14, y=17: closest beacon is at x=10, y=16
+Sensor at x=8, y=7: closest beacon is at x=2, y=10
+Sensor at x=2, y=0: closest beacon is at x=2, y=10
+Sensor at x=0, y=11: closest beacon is at x=2, y=10
+Sensor at x=20, y=14: closest beacon is at x=25, y=17
+Sensor at x=17, y=20: closest beacon is at x=21, y=22
+Sensor at x=16, y=7: closest beacon is at x=15, y=3
+Sensor at x=14, y=3: closest beacon is at x=15, y=3
+Sensor at x=20, y=1: closest beacon is at x=15, y=3
\ No newline at end of file
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!"));
 }