Fast solution to advent of code 2022 day 15

advent_of_code_2022_day_15.rs

// https://adventofcode.com/2022/day/15
// https://www.youtube.com/@robertking

use std::collections::{BTreeMap, HashSet};
use regex::Regex;

const INPUT: &str = "Sensor at x=3391837, y=2528277: closest beacon is at x=3448416, y=2478759
Sensor at x=399473, y=1167503: closest beacon is at x=1188862, y=2000000
Sensor at x=3769110, y=2896086: closest beacon is at x=4076658, y=2478123
Sensor at x=900438, y=3835648: closest beacon is at x=-435606, y=3506717
Sensor at x=2913762, y=3937542: closest beacon is at x=2964244, y=3612685
Sensor at x=3646459, y=3446878: closest beacon is at x=3264675, y=3635510
Sensor at x=1182092, y=2135147: closest beacon is at x=1188862, y=2000000
Sensor at x=3213897, y=2710772: closest beacon is at x=3448416, y=2478759
Sensor at x=3242113, y=3984214: closest beacon is at x=3264675, y=3635510
Sensor at x=2809237, y=3782833: closest beacon is at x=2872059, y=3592616
Sensor at x=2962421, y=37354: closest beacon is at x=3358601, y=-1111474
Sensor at x=3456740, y=2458922: closest beacon is at x=3448416, y=2478759
Sensor at x=1799203, y=3569221: closest beacon is at x=2872059, y=3592616
Sensor at x=3907873, y=3898376: closest beacon is at x=3264675, y=3635510
Sensor at x=3481951, y=2453964: closest beacon is at x=3448416, y=2478759
Sensor at x=1120077, y=2963237: closest beacon is at x=1188862, y=2000000
Sensor at x=2901181, y=3029961: closest beacon is at x=2872059, y=3592616
Sensor at x=3111105, y=3361570: closest beacon is at x=2964244, y=3612685
Sensor at x=2533601, y=3956413: closest beacon is at x=2872059, y=3592616
Sensor at x=108898, y=2275290: closest beacon is at x=1188862, y=2000000
Sensor at x=3501591, y=2414995: closest beacon is at x=3448416, y=2478759
Sensor at x=3035657, y=3700769: closest beacon is at x=2964244, y=3612685
Sensor at x=1286795, y=298997: closest beacon is at x=308571, y=-434280
Sensor at x=200812, y=3470019: closest beacon is at x=-435606, y=3506717
Sensor at x=2550124, y=1556776: closest beacon is at x=1188862, y=2000000
Sensor at x=3955070, y=601908: closest beacon is at x=4076658, y=2478123
Sensor at x=3565419, y=2355172: closest beacon is at x=3448416, y=2478759";

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

impl Point {

    fn manhattan(&self, other: &Point) -> i64 {
        return (self.x - other.x).abs() + (self.y - other.y).abs()
    }
}

impl From<&[i64]> for Point {
    fn from(v: &[i64]) -> Self {
        Point { x: v[0], y: v[1] }
    }
}

fn overlap(ivs: &[(i64, i64)]) -> i64 {
    let mut tree: BTreeMap<i64, i64> = BTreeMap::new();
    for &(left, right) in ivs {
        *tree.entry(left).or_default() += 1;
        *tree.entry(right+1).or_default() -= 1;
    }
    let mut count = 0;
    let mut prev_x = None;
    for (x, delta) in tree {
        if count == 0 {
            assert!(delta > 0);
            prev_x = Some(x);
        }
        count += delta;
        if count == 0 {
            count += x - prev_x.unwrap();
            println!("{} {}", x, prev_x.unwrap());
        }
    }
    count
}

fn main() {
    let row = 2000000;
    let re = Regex::new(r"\d+").unwrap();
    let mut intervals = vec![];
    let mut beacons_on_row = HashSet::new();
    for line in INPUT.lines() {
        let nums = re.find_iter(line)
            .map(
                |m| m.as_str().parse::<i64>().unwrap()
            )
            .collect::<Vec<i64>>();
        let sensor = Point::from(&nums[..2]); // if I had many different ways of creating a point, rather than calling Point::new() each time.
        let beacon = Point::from(&nums[2..]);
        let d = sensor.manhattan(&beacon);
        let dy = (row - sensor.y).abs();
        let left = sensor.x - d + dy;
        let right = sensor.x + d - dy;
        if left <= right {
            intervals.push((left, right));
        }
        if beacon.y == row {
            beacons_on_row.insert(beacon);
        }
    }
    println!("{intervals:?}");
    println!("{beacons_on_row:?}");
    let ans = overlap(&intervals) - beacons_on_row.len() as i64;
    println!("Ans: {ans}");
}