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));
}