NickyMeulemanNime

• ### By

• Nicky Meuleman

• ### Older post

Advent of Code 2022 Day 14

Advent of Code 2022 Day 16

1. Day 15: Beacon Exclusion Zone
2. Parsing
3. Part 1
4. Part 2
1. Final code
5. Final code

# Advent of Code 2022 Day 15

## Day 15: Beacon Exclusion Zone

The distress signal leads you to a large network of tunnels.

You can’t search them all manually.
Your backpack has a series of sensors that by the power of wintery magic or something, fly off into the tunnels and come to rest.

Each sensor records the coordinate of the nearest beacon it receives a signal from.

Today’s input is a list of sensor positions paired with the position of its closest beacon.

An example input looks like this:

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

That closest distance is determined by the Manhattan distance.

Yup! We’re dealing with sets of coordinates that fit on a perfectly rectangular plane again.

Because each sensor only identifies its closest beacon, if a sensor detects a beacon, you know there are no other beacons that close or closer to that sensor

## Parsing

#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]struct Coord {    row: i32,    col: i32,}

Every line turns in to 2 Coords.

1. The first is the sensor
2. The second is the closest beacon
day_15.rs
fn parse() -> Option<Vec<[Coord; 2]>> {    let input = std::fs::read_to_string("src/day15.txt").ok()?;.css-13aqjzy{display:inline-block;}
let mut pairs = Vec::new();    for line in input.lines() {        let (sensor, beacon) = line.split_once(": ")?;        let sensor = sensor.strip_prefix("Sensor at ")?;        let beacon = beacon.strip_prefix("closest beacon is at ")?;        let (sx, sy) = sensor.split_once(", ")?;        let (bx, by) = beacon.split_once(", ")?;        let sx = sx.strip_prefix("x=")?;        let sy = sy.strip_prefix("y=")?;        let bx = bx.strip_prefix("x=")?;        let by = by.strip_prefix("y=")?;
let pair = [            Coord {                col: sx.parse().ok()?,                row: sy.parse().ok()?,            },            Coord {                col: bx.parse().ok()?,                row: by.parse().ok()?,            },        ];
pairs.push(pair);    }
Some(pairs)}

## Part 1

The distress signal isn’t coming from any of the detected beacons.
It must be coming from a beacon that’s not the closest beacon for any sensor.

The question asks how many positions cannot contain a beacon on the row y=2000000.

Staring off with a decently filled out bit of skeleton code:

pseudocode.rs
let input = parse().unwrap();let row = 2_000_000;
// total amount of coordinates covered by any beacon on rowlet covered = row_ranges(row, &input)    .iter()    // the amount of coordinates covered by a range    .map(|range| range.size())    .sum();
// total amount of beacons on rowlet beacons = input    .iter()    .map(|pair| pair)    .filter(|beacon| beacon.row == row)    .map(|beacon| beacon.col)    // remove duplicates    .dedup()    .count();
covered - beacons

### Helpers

A function to help determine how many coordinates are covered on a certain row given a combo of sensor and beacon:

fn beacon_row_range(sensor: &Coord, beacon: &Coord, row: i32) -> Option<RangeInclusive<i32>> {    let radius = sensor.manhattan(beacon);    let offset = radius - (sensor.row - row).abs();    if offset < 0 {        None    } else {        Some(sensor.col - offset..=sensor.col + offset)    }}

A method on Coord to determine the manhattan distance to an other Coord:

impl Coord {    fn manhattan(self, other: Self) -> i32 {        (self.row - other.row).abs() + (self.col - other.col).abs()    }}

The remaining question is how to combine the ranges on a single row for all beacons in the input.

fn row_ranges(row: i32, pairs: &[[Coord; 2]]) -> Vec<RangeInclusive<i32>> {    let mut ranges: Vec<_> = pairs        .iter()        .flat_map(|pair| beacon_row_range(&pair, &pair, row))        .collect();    ranges.sort_unstable_by_key(|range| *range.start());
let mut merged_ranges = vec![ranges.clone()];    for next in &ranges[1..] {        let last_idx = merged_ranges.len() - 1;        let last = &merged_ranges[last_idx];        // check if the two sorted ranges overlap        if next.start() <= last.end() || last.end() + 1 == *next.start() {            // replace last with a single bigger range if possible            if next.end() > last.end() {                let old = &merged_ranges[last_idx];                let new = *old.start()..=*next.end();                merged_ranges[last_idx] = new;            }        } else {            // add to the ranges for this row            merged_ranges.push(next.clone());        }    }
merged_ranges}

Pluggin everything into our skeletoncode, and that’s part1!

### Final code

day_15.rs
pub fn part_1() -> usize {    let input = parse().unwrap();    let row = 2_000_000;
let covered = row_ranges(row, &input)        .iter()        .map(|range| range.end() - range.start() + 1)        .sum::<i32>() as usize;
let beacons = input        .into_iter()        .map(|pair| pair)        .filter(|beacon| beacon.row == row)        .map(|beacon| beacon.col)        .dedup()        .count();
covered - beacons}

## Part 2

The distress beacon is not detected by any sensor, but the distress beacon must have x and y coordinates each no lower than 0 and no larger than 4000000.

The question asks what the tuning frequency of the distress beacon is.

A tuning frequency can be found by multiplying a beacon’s x coordinate by 4000000 and then adding its y coordinate.

The question is set up so there’s a single gap in the coverage of sensors, that’s where the distress beacon is.

So the question is asking to find that single coordinate in the given range that isn’t covered.

### Final code

day_15.rs
pub fn part_2() -> i64 {    let input = parse().unwrap();    let size = 4_000_000;
let (row, col_ranges) = (0..=size)        // not needed but faster        .rev()        .map(|row| (row, row_ranges(row, &input)))        // if there is more than one range covering the row, there is a gap!        .find(|(_, ranges)| ranges.len() > 1)        .unwrap();
let col = col_ranges.first().unwrap().end() + 1;
i64::from(col) * 4_000_000 + i64::from(row)}

## Final code

day_15.rs
.css-1mjim83{display:inline-block;width:2ch;text-align:right;-webkit-user-select:none;-moz-user-select:none;-ms-user-select:none;user-select:none;opacity:0.3;margin-right:0.5rem;}1use std::ops::RangeInclusive;2
3use itertools::Itertools;4
5#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]6struct Coord {7    row: i32,8    col: i32,9}10
11impl Coord {12    fn manhattan(&self, other: &Self) -> i32 {13        (self.row - other.row).abs() + (self.col - other.col).abs()14    }15}16
17fn parse() -> Option<Vec<[Coord; 2]>> {18    let input = std::fs::read_to_string("src/day15.txt").ok()?;19
20    let mut pairs = Vec::new();21    for line in input.lines() {22        let (sensor, beacon) = line.split_once(": ")?;23        let sensor = sensor.strip_prefix("Sensor at ")?;24        let beacon = beacon.strip_prefix("closest beacon is at ")?;25        let (sx, sy) = sensor.split_once(", ")?;26        let (bx, by) = beacon.split_once(", ")?;27        let sx = sx.strip_prefix("x=")?;28        let sy = sy.strip_prefix("y=")?;29        let bx = bx.strip_prefix("x=")?;30        let by = by.strip_prefix("y=")?;31
32        let pair = [33            Coord {34                col: sx.parse().ok()?,35                row: sy.parse().ok()?,36            },37            Coord {38                col: bx.parse().ok()?,39                row: by.parse().ok()?,40            },41        ];42
43        pairs.push(pair);44    }45
46    Some(pairs)47}48
49fn beacon_row_range(sensor: &Coord, beacon: &Coord, row: i32) -> Option<RangeInclusive<i32>> {50    let radius = sensor.manhattan(beacon);51    let offset = radius - (sensor.row - row).abs();52    if offset < 0 {53        None54    } else {55        Some(sensor.col - offset..=sensor.col + offset)56    }57}58
59fn row_ranges(row: i32, pairs: &[[Coord; 2]]) -> Vec<RangeInclusive<i32>> {60    let mut ranges: Vec<_> = pairs61        .iter()62        .flat_map(|pair| beacon_row_range(&pair, &pair, row))63        .collect();64    ranges.sort_unstable_by_key(|range| *range.start());65
66    let mut merged_ranges = vec![ranges.clone()];67    for next in &ranges[1..] {68        let last_idx = merged_ranges.len() - 1;69        let last = &merged_ranges[last_idx];70        // check if the two sorted ranges overlap71        // create a single bigger range if possible72        if next.start() <= last.end() || last.end() + 1 == *next.start() {73            if next.end() > last.end() {74                let old = &merged_ranges[last_idx];75                let new = *old.start()..=*next.end();76                merged_ranges[last_idx] = new;77            }78        } else {79            merged_ranges.push(next.clone());80        }81    }82
83    merged_ranges84}85
86pub fn part_1() -> usize {87    let input = parse().unwrap();88    let row = 2_000_000;89
90    let covered = row_ranges(row, &input)91        .iter()92        .map(|range| range.end() - range.start() + 1)93        .sum::<i32>() as usize;94
95    let beacons = input96        .into_iter()97        .map(|pair| pair)98        .filter(|beacon| beacon.row == row)99        .map(|beacon| beacon.col)100        .dedup()101        .count();102
103    covered - beacons104}105
106pub fn part_2() -> i64 {107    let input = parse().unwrap();108    let size = 4_000_000;109
110    let (row, col_ranges) = (0..=size)111        // not needed but faster112        .rev()113        .map(|row| (row, row_ranges(row, &input)))114        .find(|(_, ranges)| ranges.len() > 1)115        .unwrap();116
117    let col = col_ranges.first().unwrap().end() + 1;118
119    i64::from(col) * 4_000_000 + i64::from(row)120}