aoc2022_day15.rs

pub fn part1(input: &str) -> isize {
    get_empty_ranges(&parse(input), 2000000).iter()
        .map(|(s, e)| e - s)
        .sum()
}

pub fn part2(input: &str) -> isize {
    std::iter::once(parse(input)).map(|sensors| (
        sensors.iter().fold((
            std::collections::BTreeMap::<isize, isize>::new(),
            std::collections::BTreeMap::<isize, isize>::new(),
        ), |(mut a, mut b), s| {
            for i in 0..4 {
                match i {
                    0 => *a.entry(s.y - s.x + s.r + 1).or_default() += 1,
                    1 => *a.entry(s.y - s.x - s.r - 1).or_default() += 1,
                    2 => *b.entry(s.x + s.y + s.r + 1).or_default() += 1,
                    _ => *b.entry(s.x + s.y - s.r - 1).or_default() += 1,
                }
            }

            (a, b)
        }),
        sensors,
    )).map(|((a, b), sensors)| (
        a.into_iter()
            .filter_map(|(k, v)| (v > 1).then_some(k)),
        b.into_iter()
            .filter_map(|(k, v)| (v > 1).then_some(k))
            .collect::<Vec<_>>(),
        sensors,
    )).fold(0, |_, (a, b, sensors)|
        a.flat_map(|x| std::iter::repeat(x).zip(b.iter()))
            .map(|(a, b)| ((b - a) / 2, (a + b) / 2))
            .find_map(|(x, y)| (
                x.min(y) > 0
                && x.max(y) < 4000000
                && sensors.iter().all(|s| distance((s.x, s.y), (x, y)) > s.r)
            ).then_some(x * 4000000 + y))
            .unwrap_or_default())
}

fn parse(input: &str) -> Vec<Sensor> {
    input.lines()
        .flat_map(|l| TryInto::<[_; 4]>::try_into(
            l.split(|c: char| !c.is_ascii_digit() && c != '-')
                .flat_map(|p| p.parse::<isize>().ok())
                .collect::<Vec<_>>()))
        .map(|[x, y, bx, by]| Sensor {
            x, y, r: distance((x, y), (bx, by)),
        })
        .collect()
}

fn get_empty_ranges(sensors: &[Sensor], row: isize) -> Vec<(isize, isize)> {
    flatten_ranges(&sensors.iter()
        .filter_map(|s| std::iter::once((s.y - row).abs())
            .find_map(|d| (d <= s.r).then_some((
                s.x - (s.r - d),
                s.x + (s.r - d),
            ))))
        .collect::<std::collections::BinaryHeap<_>>()
        .into_sorted_vec())
}

// https://www.geeksforgeeks.org/merging-intervals/
fn flatten_ranges(ranges: &[(isize, isize)]) -> Vec<(isize, isize)> {
    (!ranges.is_empty()).then_some(ranges.iter()
        .skip(1)
        .fold(vec![ranges[0]], |flat, &r|
            std::iter::once(flat.len() - 1).fold(flat, |mut flat, last| {
                match flat[last].0 <= r.0 && r.0 <= flat[last].1 {
                    true => flat[last].1 = flat[last].1.max(r.1),
                    _ => flat.push(r),
                }

                flat
            })))
        .unwrap_or_default()
}

fn distance(a: (isize, isize), b: (isize, isize)) -> isize {
    (a.0 - b.0).abs() + (a.1 - b.1).abs()
}

#[derive(Debug, Clone, Copy)]
struct Sensor {
    x: isize,
    y: isize,
    r: isize,
}