aoc2022

day15.rs (3191B)

---

 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 {
     // 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 = 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!");
         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 (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 {
                 // 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)}); // 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
                 }
             }
             // No line segment contained this point, so it's our answer!
             return Some((ix+1, y));
         }
         None
     }).next().expect("no point found!");
     println!("Day 15: {}", (x as i64)*4_000_000 + (y as i64));
 }