use nom::{
    bytes::complete::tag,
    character::complete::{i64, line_ending},
    combinator::map,
    multi::separated_list1,
    sequence::tuple,
    IResult,
};
use std::{collections::BTreeSet, fs, ops::Range};

fn main() -> Result<(), Box<dyn std::error::Error>> {
    let input = fs::read_to_string("inputs/day_15.txt")?;
    let sensors = Sensors::parser(&input).unwrap().1;

    dbg!(sensors.count_covered_non_beacons_in_row(2000000));

    dbg!(sensors
        .find_hole_in_range(
            Point { x: 0, y: 0 }..Point {
                x: 4000001,
                y: 4000001
            }
        )
        .tuning_frequency());

    Ok(())
}

#[derive(Debug, Clone)]
struct Sensors(Vec<Sensor>);

#[derive(Debug, Clone)]
struct Sensor {
    center: Point,
    closest_beacon: Point,
}

#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
struct Point {
    x: i64,
    y: i64,
}

impl Sensors {
    fn parser(input: &str) -> IResult<&str, Self> {
        map(separated_list1(line_ending, Sensor::parser), Sensors)(input)
    }

    fn ranges_in_row(&self, y: i64) -> Vec<Range<i64>> {
        let mut ranges: Vec<Range<i64>> = self
            .0
            .iter()
            .filter_map(|s| s.get_range_in_row(y))
            .collect();

        let mut any_changes = true;
        while any_changes {
            any_changes = false;
            ranges.sort_unstable_by_key(|r| r.start);
            if ranges.len() > 0 {
                for i in 0..ranges.len() - 1 {
                    if ranges[i].end > ranges[i + 1].start {
                        ranges[i + 1].start = ranges[i].end;
                        any_changes = true;
                    }
                }
                ranges.retain(|r| !r.is_empty());
            }
        }
        ranges
    }

    fn count_covered_non_beacons_in_row(&self, y: i64) -> u64 {
        let ranges = self.ranges_in_row(y);

        // these beacons are all distinct, and are all definitely on
        // the line because the beacons are how the line is found!
        let beacons: BTreeSet<i64> = self
            .0
            .iter()
            .filter(|s| s.closest_beacon.y == y)
            .map(|s| s.closest_beacon.x)
            .collect();

        ranges.into_iter().map(|r| r.count() as u64).sum::<u64>() - beacons.len() as u64
    }

    fn find_hole_in_range(&self, field_range: Range<Point>) -> Point {
        let full_row_len = field_range.end.x - field_range.start.x;
        for y in field_range.start.y..field_range.end.y {
            let ranges = self.ranges_in_row(y);
            let count = ranges
                .into_iter()
                .map(|mut r| {
                    if r.start < field_range.start.x {
                        r.start = field_range.start.x
                    };
                    if r.end > field_range.end.x {
                        r.end = field_range.end.x
                    };
                    r
                })
                .map(|r| r.count() as i64)
                .sum::<i64>();
            if full_row_len != count {
                for x in field_range.start.x..field_range.end.x {
                    let p = Point { x, y };
                    if !self.0.iter().any(|s| s.contains(&p)) {
                        return p;
                    }
                }
            }
        }
        panic!("Didn't find the hole as specified!")
    }
}

impl Sensor {
    fn parser(input: &str) -> IResult<&str, Self> {
        map(
            tuple((
                tag("Sensor at "),
                Point::parser,
                tag(": closest beacon is at "),
                Point::parser,
            )),
            |(_, center, _, closest_beacon)| Sensor {
                center,
                closest_beacon,
            },
        )(input)
    }

    fn get_range_in_row(&self, y: i64) -> Option<Range<i64>> {
        let dy = (self.center.y - y).abs();
        let dx = self.radius() - dy;
        if dx < 0 {
            None
        } else {
            let min_x = self.center.x - dx;
            let max_x = self.center.x + dx;
            Some(min_x..(max_x + 1))
        }
    }

    fn radius(&self) -> i64 {
        (self.center.x - self.closest_beacon.x).abs()
            + (self.center.y - self.closest_beacon.y).abs()
    }

    fn contains(&self, other: &Point) -> bool {
        let d = (self.center.x - other.x).abs() + (self.center.y - other.y).abs();
        d <= self.radius()
    }
}

impl Point {
    fn parser(input: &str) -> IResult<&str, Self> {
        map(tuple((tag("x="), i64, tag(", y="), i64)), |(_, x, _, y)| {
            Point { x, y }
        })(input)
    }

    fn tuning_frequency(&self) -> i64 {
        self.x * 4000000 + self.y
    }
}