DEV Community

Nicky Meuleman
Nicky Meuleman

Posted on • Originally published at nickymeuleman.netlify.app

Advent of Code 2022 Day 15

#adventofcode #rust

Day 15: Beacon Exclusion Zone

https://adventofcode.com/2022/day/15

TL;DR: my solution in Rust

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:

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
Enter fullscreen mode Exit fullscreen mode

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

Guess who's back?.

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

Every line turns in to 2 Coords.

  1. The first is the sensor
  2. The second is the closest beacon 
fn parse() -> Option<Vec<[Coord; 2]>> {
    let input = std::fs::read_to_string("src/day15.txt").ok()?;

    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)
}
Enter fullscreen mode Exit fullscreen mode

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:

let input = parse().unwrap();
let row = 2_000_000;

// total amount of coordinates covered by any beacon on `row`
let covered = row_ranges(row, &input)
    .iter()
    // the amount of coordinates covered by a range
    .map(|range| range.size())
    .sum();

// total amount of beacons on `row`
let beacons = input
    .iter()
    .map(|pair| pair[1])
    .filter(|beacon| beacon.row == row)
    .map(|beacon| beacon.col)
    // remove duplicates
    .dedup()
    .count();

covered - beacons
Enter fullscreen mode Exit fullscreen mode

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)
    }
}
Enter fullscreen mode Exit fullscreen mode

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()
    }
}
Enter fullscreen mode Exit fullscreen mode

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[0], &pair[1], row))
        .collect();
    ranges.sort_unstable_by_key(|range| *range.start());

    let mut merged_ranges = vec![ranges[0].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
}
Enter fullscreen mode Exit fullscreen mode

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

Final code 

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[1])
        .filter(|beacon| beacon.row == row)
        .map(|beacon| beacon.col)
        .dedup()
        .count();

    covered - beacons
}
Enter fullscreen mode Exit fullscreen mode

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 

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)
}
Enter fullscreen mode Exit fullscreen mode

Final code 

use std::ops::RangeInclusive;

use itertools::Itertools;

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

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

fn parse() -> Option<Vec<[Coord; 2]>> {
    let input = std::fs::read_to_string("src/day15.txt").ok()?;

    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)
}

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)
    }
}

fn row_ranges(row: i32, pairs: &[[Coord; 2]]) -> Vec<RangeInclusive<i32>> {
    let mut ranges: Vec<_> = pairs
        .iter()
        .flat_map(|pair| beacon_row_range(&pair[0], &pair[1], row))
        .collect();
    ranges.sort_unstable_by_key(|range| *range.start());

    let mut merged_ranges = vec![ranges[0].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
        // create a single bigger range if possible
        if next.start() <= last.end() || last.end() + 1 == *next.start() {
            if next.end() > last.end() {
                let old = &merged_ranges[last_idx];
                let new = *old.start()..=*next.end();
                merged_ranges[last_idx] = new;
            }
        } else {
            merged_ranges.push(next.clone());
        }
    }

    merged_ranges
}

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[1])
        .filter(|beacon| beacon.row == row)
        .map(|beacon| beacon.col)
        .dedup()
        .count();

    covered - beacons
}

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)))
        .find(|(_, ranges)| ranges.len() > 1)
        .unwrap();

    let col = col_ranges.first().unwrap().end() + 1;

    i64::from(col) * 4_000_000 + i64::from(row)
}
Enter fullscreen mode Exit fullscreen mode

Top comments (2)

Collapse
 
aryuuu profile image
M Algah Fattah Illahi •

nice solution!, but I'm wondering if the solution for part 2 will work if the undetected beacon is located on the edge of the 4mx4m box

Collapse
 
nickymeuleman profile image
Nicky Meuleman • • Edited

Good catch!
To cover that case you can add a check to the part where we find a row with more than one range to also consider single ranges that don't cover 4 million tiles.
ranges.len() == 1 && (ranges[0].start().abs_diff(*ranges[0].end())) < 4_000_000
edit: on second though, that wouldn't do it. better check if x >= 0 and <= 4_000_000 to confirm the range is covered.

Read next

francescoxx profile image

Why might Rust be a smart choice for developers today?

Francesco Ciulla -

francescoxx profile image

3 ways to use environment Variables in Rust

Francesco Ciulla -

francescoxx profile image

Rust fullstack web app! WASM + YEW + ROCKET

Francesco Ciulla -

hamzakhan profile image

⚡ **Rust vs Node.js vs Go: Performance Comparison for Backend Development** 🏎️

Hamza Khan -