/// Represents a point in the 2D plane where our sensors are located
#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
struct Point(isize, isize);

impl Point {
    // Calculate the Manhattan Distance from one Point to another Point
    pub fn distance_to(&self, other: &Self) -> usize {
        let Point(x1, y1) = self;
        let Point(x2, y2) = other;
        x1.abs_diff(*x2) + y1.abs_diff(*y2)
    }
}

/// Easily create a Point from a tuple of i32's. This is mostly here because
/// the `nom` parsers don't provide isize directly.
impl From<(i32, i32)> for Point {
    fn from(value: (i32, i32)) -> Self {
        let (x, y) = value;
        Point(x as isize, y as isize)
    }
}

/// Represents one of our sensors. Encapsulates the location of the beacon it is
/// detecting and the Sensor's detection range.
#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord)]
struct Sensor {
    location: Point,
    beacon: Point,
    range: usize,
}

impl Sensor {
    fn new(location: Point, beacon: Point) -> Self {
        let range = location.distance_to(&beacon);
        Sensor {
            location,
            beacon,
            range,
        }
    }
}

/// Convert a tuple of Points into a Sensor. The first Point is the location of the
/// Sensor, the second is the location of the beacon.
impl From<(Point, Point)> for Sensor {
    fn from(value: (Point, Point)) -> Self {
        let (location, beacon) = value;
        Sensor::new(location, beacon)
    }
}

/// Internal module wrapping the `nom` parser for the input
mod parser {
    use super::*;
    use anyhow::{anyhow, Result};
    use nom::{
        bytes::complete::take_till,
        character::{
            complete::{i32, newline},
            is_alphabetic, is_digit,
        },
        combinator::{map, recognize},
        multi::separated_list0,
        sequence::{pair, preceded},
        Finish, IResult,
    };

    /// Nom parser to skip everything that's not a number or minus sign
    fn till_number(s: &str) -> IResult<&str, &str> {
        take_till(|c: char| c.is_ascii_digit() || c == '-')(s)
    }

    /// Nom parser to parse an i32 with a bunch of cruft in front of it
    fn prefixed_number(s: &str) -> IResult<&str, i32> {
        preceded(till_number, i32)(s)
    }

    /// Nom parser to take the first two found numbers and return a Point from them
    fn point(s: &str) -> IResult<&str, Point> {
        map(pair(prefixed_number, prefixed_number), Point::from)(s)
    }

    /// Get the two Points from an input line
    fn sensor(s: &str) -> IResult<&str, Sensor> {
        map(pair(point, point), Sensor::from)(s)
    }

    /// Parse all lines from the input into a list of Sensors
    fn sensors(s: &str) -> IResult<&str, Vec<Sensor>> {
        separated_list0(newline, sensor)(s)
    }

    /// Parse the input, returns a list of Sensors
    pub fn parse(s: &str) -> Result<Vec<Sensor>> {
        let (_, result) = sensors(s).finish().map_err(|e| anyhow!("{e}"))?;
        Ok(result)
    }
}

const INPUT: &str = include_str!("../../input/15/input.txt");

/// Parse that input!
fn read() -> Vec<Sensor> {
    let mut input = parser::parse(INPUT).unwrap();
    input.sort_unstable();
    input
}

use itertools::Itertools;

/// Solve Day 15, Part 1
fn solve(input: &[Sensor]) -> u32 {
    let row = 2_000_000; // Our hard-coded row of interest

    // Identify a RowRange for each sensor indicated the furthest left and furthest
    // right point detected by each sensor. These RowRanges may overlap, though, so
    // we need to 'condense' the ranges so we don't double-count any points. This
    // part depends on the input being sorted ahead of time, so that the RowRanges
    // come out sorted, so that all the RowRanges that can be condensed will be
    // encountered one after another. If the input isn't sorted here, you'll get a
    // different (wrong) answer.
    let mut ranges: Vec<RowRange> = Vec::new();
    for range in input.iter().flat_map(|s| s.row_range_sensed(row)) {
        // If the current range can be merged with the last range in `ranges`, do so.
        // Otherwise, just push the current range to the list.
        if let Some(last_rng) = ranges.last_mut() {
            if last_rng.overlaps(&range) {
                last_rng.merge(&range);
            }
            continue;
        }
        ranges.push(range);
    }

    // Count the number of observable positions on the target row, defined by
    // the limits of the `ranges`.
    let sensed_on_row = ranges.iter().map(|r| r.count_positions()).sum::<usize>();

    // We'll need to subtract out the number of beacons on the row, since those
    // points definitely _can_ contain a beacon.
    let beacons_on_row = input
        .iter()
        .filter_map(|s| s.beacon_on_row(row))
        .unique()
        .count();

    let definitely_not_beacons = sensed_on_row - beacons_on_row;
    (definitely_not_beacons as u32)
}

/// Represents a range of points on a given row of the scan. Includes the start and
/// end points on that row.
#[derive(Debug)]
struct RowRange(isize, isize);

impl RowRange {
    /// Does this range overlap another?
    fn overlaps(&self, other: &Self) -> bool {
        other.1 >= self.0 && self.1 >= other.0
    }

    /// Merge this range with another
    fn merge(&mut self, other: &Self) {
        *self = RowRange(self.0.min(other.0), self.1.max(other.1));
    }

    /// Count the number of positions in this range
    fn count_positions(&self) -> usize {
        self.0.abs_diff(self.1) + 1
    }
}

impl Sensor {
    /// Indicates if the sensor can detect the given Point
    pub fn can_detect(&self, point: &Point) -> bool {
        self.location.distance_to(point) <= self.range
    }

    /// Workhorse of part one. Identifies and returns the range of positions
    /// that can be detected by this sensor on the indicated row, as a RowRange.
    fn row_range_sensed(&self, row: isize) -> Option<RowRange> {
        let distance_to_row = self.location.1.abs_diff(row);
        if distance_to_row > self.range {
            return None;
        }

        // The spread indicates how much of the Manhattan distance for detection
        // is remaining to 'spread' out to the left and right. Essentially half
        // the width of the detection zone on this row.
        let spread = self.range - distance_to_row;
        let range_start = self.location.0.saturating_sub_unsigned(spread);
        let range_end = self.location.0.saturating_add_unsigned(spread);
        Some(RowRange(range_start, range_end))
    }

    /// If the beacon is on the given row, return the location of the beacon.
    /// Otherwise, return None.
    fn beacon_on_row(&self, row: isize) -> Option<Point> {
        if self.beacon.1 == row {
            return Some(self.beacon);
        }
        None
    }
}

use itertools::Itertools;

/// Solve Day 15, Part 2
///
/// Well, I think this is my first "what the heck is he doing" comment of the year.
/// Yay! So, this solution relies on some assumptions, the biggest of which is that
/// the beacon we're searching for will lie one space outside the range of a Sensor.
/// Why can we assume that? Well, the only possible way that a gap of larger than
/// one could contain the beacon is if the beacon were located in one of the four
/// corner points of the allowed range. That would kind of suck, though, so it's
/// probably not how it is. If it turns out to be the case, then we only have four
/// possible answers to try, so it's a win-win. So, given that the beacon most
/// likely lies in a one-wide gap between sensor ranges, we can treat that gap like
/// a line. The other assumption is that there's more than one one-wide gap.
/// Otherwise, again, we'd have multiple unscanned spaces. That other gap would
/// necessarily have a slope with opposite sign of the first gap, making an X with
/// the center on the beacon. X marks the spot! So, if we can identify all the
/// one-wide gaps in the range of the sensors, we can identify all the places where
/// these gap-lines intersect. If we can find one intersection that can't be
/// detected by any sensor, that's the one we want.
fn solve(input: &[Sensor]) -> u64 {
    // Identify all the diagonal gaps between sensor detection ranges that are only
    // one space wide.
    let mut diagonal_gaps = Vec::new();
    for (sensor1, sensor2) in input.iter().tuple_combinations() {
        let Some(gap) = sensor1.gap_size(sensor2) else { continue; };
        if gap == 1 {
            diagonal_gaps.push(sensor1.diagonal_between(sensor2));
        }
    }

    // Identify all the points where these one-wide gaps intersect.
    let intersects = diagonal_gaps
        .iter()
        .tuple_combinations()
        .flat_map(|(diag1, diag2)| diag1.intersect(diag2))
        .unique()
        .collect_vec();

    // Check the intersections against all the sensors to identify the intersection
    // that cannot be detected by any Sensor. Now, for my input, there was only one
    // intersection that made it this far, but this check should make the solution
    // more robust for other inputs.
    'outer: for intersect in intersects {
        for sensor in input.iter() {
            if sensor.can_detect(&intersect) {
                continue 'outer;
            }
        }
        return intersect.tuning_frequency();
    }

    // Freak out if we can't find an intersection that can't be detected.
    panic!("Could not find the beacon!");
}

/// Represents a diagonal line. The Positive variant indicates a line with a slope
/// of 1 and the Negative variant indicates a line with a slope of -1.
#[derive(Debug)]
enum Diagonal {
    Positive(isize),
    Negative(isize),
}

impl Diagonal {
    /// Identify the point where two Diagonal lines intersect.
    fn intersect(&self, other: &Self) -> Option<Point> {
        // It's simple geometry! Which explains why it was so hard for me
        // to implement. Uses the formula for the two lines to calculate the
        // intersecting point, with some shortcuts because we know the slope
        // will either be positive or negative one for both lines, and if
        // the lines have the same slope, they're parallel and we can bail.
        use Diagonal::*;
        let (neg, pos) = match (self, other) {
            (Positive(pos), Negative(neg)) => (neg, pos),
            (Negative(neg), Positive(pos)) => (neg, pos),
            (Positive(_), Positive(_)) => return None,
            (Negative(_), Negative(_)) => return None,
        };
        let x = (neg - pos) / 2;
        let y = x + pos;
        Some(Point(x, y))
    }
}

impl Sensor {
    /// Find the size of the gap in the sensor range between two Sensors.
    /// If there's no gap (they overlap), return None.
    fn gap_size(&self, other: &Self) -> Option<usize> {
        let distance = self.location.distance_to(&other.location);
        let total_range = self.range + other.range;
        if total_range >= distance {
            return None;
        }
        Some(distance - total_range - 1)
    }

    /// Calculate the formula for the line that lies in the gap between two
    /// Sensor detection ranges. The line will lie diagonally just outside
    /// the range of `self`.
    fn diagonal_between(&self, other: &Self) -> Diagonal {
        let Point(x1, y1) = self.location;
        let Point(x2, y2) = other.location;
        let offset = self.range + 1;

        // Here, we identify two points on the diagonal line. We'll pick points just
        // outside the cardinal direction points of the `self` sensor range.
        let (p1x, p1y) = if x2 > x1 {
            (x1.saturating_add_unsigned(offset), y1)
        } else {
            (x1.saturating_sub_unsigned(offset), y1)
        };
        let (p2x, p2y) = if y2 > y1 {
            (x1, y1.saturating_add_unsigned(offset))
        } else {
            (x1, y1.saturating_sub_unsigned(offset))
        };

        // We know that the slope will either be 1 or -1, since these lines
        // are diagonals.
        let slope = (p2x - p1x) / (p2y - p1y);
        let intercept = p1y - (slope * p1x);
        if slope > 0 {
            Diagonal::Positive(intercept)
        } else {
            Diagonal::Negative(intercept)
        }
    }
}

impl Point {
    /// Calculate the tuning frequency the way the puzzle told us to.
    fn tuning_frequency(&self) -> u64 {
        (4_000_000 * self.0 as u64) + self.1 as u64
    }
}