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.