This is part of the series Advent of Code 2022.
Day 15 - Advent of Code 2022
8 minute read  (1530 words)
rust advent-of-code

Welcome to day 15 of Advent Of Code. Today's challenge is to determine the location of the distress in a network of subterranean tunnels. A set of sensors is deployed into the tunnels, the handheld device indicates the locations of all sensors on a two-dimensional grid. Each sensor knows its own position & can determine the position of a beacon. The distance between sensors is calculated by the Manhattan distance.

All sensors report back their positions and closest beacons. The example input looks as follows:

Sensor at x=2, y=18: closest beacon is at x=-2, y=15
Sensor at x=9, y=16: closest beacon is at x=10, y=16
Sensor at x=13, y=2: closest beacon is at x=15, y=3
Sensor at x=12, y=14: closest beacon is at x=10, y=16
Sensor at x=10, y=20: closest beacon is at x=10, y=16
Sensor at x=14, y=17: closest beacon is at x=10, y=16
Sensor at x=8, y=7: closest beacon is at x=2, y=10
Sensor at x=2, y=0: closest beacon is at x=2, y=10
Sensor at x=0, y=11: closest beacon is at x=2, y=10
Sensor at x=20, y=14: closest beacon is at x=25, y=17
Sensor at x=17, y=20: closest beacon is at x=21, y=22
Sensor at x=16, y=7: closest beacon is at x=15, y=3
Sensor at x=14, y=3: closest beacon is at x=15, y=3
Sensor at x=20, y=1: closest beacon is at x=15, y=3

Each sensor spans a scanning field with a distance to its next found beacon. Each sensor can only see one associated beacon. Multiple sensors can see the same beacon. To detect the distress signal, it's necessary to figure out where the distress beacon isn't.

Part 1

Count the positions where a beacon cannot be just for a single row, in particular for row 2000000. How many positions cannot contain a beacon.

Before the input gets parsed let's define a few useful types to handle coordinates & signals.

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

impl Pos {
    pub fn new(x: i64, y: i64) -> Self {
        Self { x, y }
    }

    pub fn manhattan(&self, rhs: &Pos) -> i64 {
        i64::abs(self.x - rhs.x) + i64::abs(self.y - rhs.y)
    }
}

#[derive(Debug, Clone)]
struct Signal {
    pub sensor: Pos,
    pub beacon: Pos,
}

impl Signal {
    pub fn new(sensor: Pos, beacon: Pos) -> Self {
        Self { sensor, beacon }
    }

    pub fn manhattan(&self) -> i64 {
        self.sensor.manhattan(&self.beacon)
    }
}

The Pos struct holds the coordiantes, similar to previous challenges, while Signal keeps its position and the position of the closest beacon. The Pos#manhattan method calculates the distance between two positions. The peg crate is used again to parse the input.

peg::parser! {
    grammar line_parser() for str {
        rule number() -> i64
            = n:$(['-' | '0'..='9']+) { n.parse::<i64>().unwrap() }

        rule pos() -> Pos
            = "x=" x:number() ", y=" y:number() { Pos::new(x, y) }

        pub(crate) rule signal() -> Signal
            = "Sensor at " sensor:pos() ": closest beacon is at " beacon:pos() { Signal::new(sensor, beacon) }
    }
}

fn part1(signals: Vec<Signal>, line_number: i64) -> usize {
    todo!()
}

fn parse(input: &str) -> Vec<Signal> {
    input
        .lines()
        .filter_map(|line| line_parser::signal(line).ok())
        .collect::<Vec<_>>()
}

fn main() {
    let signals = parse(include_str!("input.txt"));
    println!("Part 1: {}", part1(signals.clone(), 2_000_000));
}

#[cfg(test)]
mod tests {
    use super::*;

    const INPUT: &str = include_str!("test.txt");

    #[test]
    fn check_part1() {
        assert_eq!(26, part1(parse(INPUT), 10));
    }
}

The peg parser matches the input string and parses both beacon & sensor positions. The parse function reads in all input and creates a Vec of Signal. A test checks the algorithm works as intended. For now the program will panic.

There are multiple ways to implement this, the algorithm I came up with is most likely not very efficient. First the list of all unique beacon positions is collected. Then for each signal the manhattan distance is used to determine if the line number (or y coordinate) is inside the covered field of the signal. If the sensor field covers the row the covered segment is determined and all the affected x coordinates stored in a list. This list may contain duplicates when multiple sensor fields overlap on the same x coordinates, therefore only the unique x coordinates are taken into consideration. Finally any possible beacon that is located on the same row is ignored.

fn part1(signals: Vec<Signal>, line_number: i64) -> usize {
    // get all unique beacon positions
    let beacons = signals
        .iter()
        .map(|signal| signal.beacon)
        .collect::<HashSet<Pos>>();

    let x_positions = signals
        .iter()
        .map(|sensor| (sensor.manhattan(), sensor.sensor))
        .filter(|(distance, sensor)| {
            // check if the sensor field reaches the row
            let sensor_range = (sensor.y - distance)..(sensor.y + distance);
            sensor_range.contains(&line_number)
        })
        .flat_map(|(max_distance, sensor)| {
            let distance = (sensor.y - line_number).abs();
            let max_distance = max_distance - distance;

            // create range of x coordinates for row
            (sensor.x - max_distance)..=(sensor.x + max_distance)
        })
        // return unique x coordiantes
        .unique()
        // exclude any beacons on the same row
        .filter(|x| !beacons.contains(&Pos::new(*x, line_number)));

    x_positions.count()
}

With this function in place the test should pass and running the program should output the first solution.

Part 2

The distress signal is coming from a nearby beacon which is not detected by any sensor. It's known that both its coordinates are between 0 and 4000000 each. To find the distress beacon's position is to exclude all known sensor ranges. The remaining uncovered position is the distress location.

Adjusting the current algorithm of part 1 for this part will result in a very long running time of the program, easily in the hours if not days, therefore a different approach has to be considered. We will use a new type Range to check first, if sensor ranges will overlap & second to allow us to merge ranges into a new single Range.


#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
struct Range {
    pub start: i64,
    pub end: i64,
}

impl Range {
    pub fn new(start: i64, end: i64) -> Self {
        Self { start, end }
    }

    #[inline]
    pub fn overlap(&self, rhs: &Range) -> bool {
        self.end >= rhs.start && rhs.end >= self.start
    }

    #[inline]
    pub fn merge(&self, rhs: &Range) -> Range {
        let start = i64::min(self.start, rhs.start);
        let end = i64::max(self.end, rhs.end);
        Range::new(start, end)
    }
}

fn find_missing_beacon(signals: Vec<Signal>, limit: i64) -> Option<Pos> {
    todo!()
}

fn part2(signals: Vec<Signal>, limit: i64) -> usize {
    let pos = find_missing_beacon(signals, limit).expect("Failed to find missing beacon");
    (pos.x * 4_000_000 + pos.y) as usize
}

fn main() {
    let signals = parse(include_str!("input.txt"));
    println!("Part 1: {}", part1(signals.clone(), 2_000_000));
    println!("Part 2: {}", part2(signals, 4_000_000));
}

#[cfg(test)]
mod tests {
    #[test]
    fn check_part2() {
        assert_eq!(56_000_011, part2(parse(INPUT), 20));
    }
}

The Range is similar to std::ops::Range that it takes a start & end value, but it derives PartialOrd & Ord in order to sort them, which Rust's standard Range does not.

The algorithm is outlined as follows. First all signals & their manhattan distances are determined. For all rows between 0 and 4_000_000 each signal is checked if it overlaps with the row. For all intersecting rows their signal ranges are determined. Once these are determined they are sorted, therefore we require the PartialOrd implementation. This is to lay the Range items next to each other, so it's easier to learn if they overlap.

The second part is to use the list of Range and determine if they are contiguous. If they are not then we found a gap between two neighbor ranges which is the missing distress beacon.

fn find_missing_beacon(signals: Vec<Signal>, limit: i64) -> Option<Pos> {
    let signals = signals
        .iter()
        .map(|signal| (signal.sensor, signal.manhattan()))
        .collect::<Vec<_>>();

    for y in 0..=limit {
        // Determine all ranges for `y` coordinate
        let mut ranges = signals
            .iter()
            .filter(|(sensor, distance)| (sensor.y - y).abs() <= *distance)
            .map(|(sensor, manhattan)| {
                let dx = (manhattan - (sensor.y - y).abs()).abs();

                let minx = i64::max(0, sensor.x - dx);
                let maxx = i64::min(limit, sensor.x + dx);

                Range::new(minx, maxx)
            })
            .collect::<Vec<_>>();

        ranges.sort();

        // Check the ranges are contiguous
        let (_result, x) = ranges
            .iter()
            .fold((Range::new(0, 0), None), |mut acc, range| {
                if acc.0.overlap(range) {
                    acc.0 = acc.0.merge(range);
                } else {
                    acc.1 = Some(acc.0.end + 1);
                }
                acc
            });

        // A gap was found
        if let Some(x) = x {
            return Some(Pos::new(x, y));
        }
    }

    None
}

The second part in the for loop is handling the logic to check if ranges are contiguous. After sorting the ranges, they should form a set of neighbors. The fold closure is initialized with Range::new(0, 0). This is not necessarily correct to start with this, because it's not impossible that the distress beacon can be found at 0, y. The iteration in fold checks if the next Range overlaps with the current Range and if so merge them into single Range. This way the range to check grows horizontally in iteration.

Only if two ranges cannot be merged, a gap is found. As there is only a single gap expected, we track this position until fold completes. If there was a gap it's returned as Pos.

The tests should pass & after running the program the second solution is available.