DEV Community

Cover image for Advent of Code 2022 - Day 15
Eric Burden
Eric Burden

Posted on • Originally published at ericburden.work on

Advent of Code 2022 - Day 15

It’s that time of year again! Just like last year, I’ll be posting my solutions to the Advent of Code puzzles. This year, I’ll be solving the puzzles in Rust. I’ll post my solutions and code to GitHub as well. After finishing last year (and 2015-2019) in Julia, I needed to spend some time with Rust again! If you haven’t given AoC a try, I encourage you to do so along with me!

Day 15 - Beacon Exclusion Zone

Find the problem description HERE.

The Input - Who Senses the Sensors?

Today’s puzzle has us extracting the x/y coordinates of a sensor and a beacon from each line. There’s a lot of extra stuff on each line to ignore, so that’s what we’ll do! We’ll also need to know about the range of each sensor, which we can get from the distance of the beacon from the sensor.

/// Represents a point in the 2D plane where our sensors are located
#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
struct Point(isize, isize);

impl Point {
    // Calculate the Manhattan Distance from one Point to another Point
    pub fn distance_to(&self, other: &Self) -> usize {
        let Point(x1, y1) = self;
        let Point(x2, y2) = other;
        x1.abs_diff(*x2) + y1.abs_diff(*y2)
    }
}

/// Easily create a Point from a tuple of i32's. This is mostly here because
/// the `nom` parsers don't provide isize directly.
impl From<(i32, i32)> for Point {
    fn from(value: (i32, i32)) -> Self {
        let (x, y) = value;
        Point(x as isize, y as isize)
    }
}

/// Represents one of our sensors. Encapsulates the location of the beacon it is
/// detecting and the Sensor's detection range.
#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord)]
struct Sensor {
    location: Point,
    beacon: Point,
    range: usize,
}

impl Sensor {
    fn new(location: Point, beacon: Point) -> Self {
        let range = location.distance_to(&beacon);
        Sensor {
            location,
            beacon,
            range,
        }
    }
}

/// Convert a tuple of Points into a Sensor. The first Point is the location of the
/// Sensor, the second is the location of the beacon.
impl From<(Point, Point)> for Sensor {
    fn from(value: (Point, Point)) -> Self {
        let (location, beacon) = value;
        Sensor::new(location, beacon)
    }
}

/// Internal module wrapping the `nom` parser for the input
mod parser {
    use super::*;
    use anyhow::{anyhow, Result};
    use nom::{
        bytes::complete::take_till,
        character::{
            complete::{i32, newline},
            is_alphabetic, is_digit,
        },
        combinator::{map, recognize},
        multi::separated_list0,
        sequence::{pair, preceded},
        Finish, IResult,
    };

    /// Nom parser to skip everything that's not a number or minus sign
    fn till_number(s: &str) -> IResult<&str, &str> {
        take_till(|c: char| c.is_ascii_digit() || c == '-')(s)
    }

    /// Nom parser to parse an i32 with a bunch of cruft in front of it
    fn prefixed_number(s: &str) -> IResult<&str, i32> {
        preceded(till_number, i32)(s)
    }

    /// Nom parser to take the first two found numbers and return a Point from them
    fn point(s: &str) -> IResult<&str, Point> {
        map(pair(prefixed_number, prefixed_number), Point::from)(s)
    }

    /// Get the two Points from an input line
    fn sensor(s: &str) -> IResult<&str, Sensor> {
        map(pair(point, point), Sensor::from)(s)
    }

    /// Parse all lines from the input into a list of Sensors
    fn sensors(s: &str) -> IResult<&str, Vec<Sensor>> {
        separated_list0(newline, sensor)(s)
    }

    /// Parse the input, returns a list of Sensors
    pub fn parse(s: &str) -> Result<Vec<Sensor>> {
        let (_, result) = sensors(s).finish().map_err(|e| anyhow!("{e}"))?;
        Ok(result)
    }
}

const INPUT: &str = include_str!("../../input/15/input.txt");

/// Parse that input!
fn read() -> Vec<Sensor> {
    let mut input = parser::parse(INPUT).unwrap();
    input.sort_unstable();
    input
}

Enter fullscreen mode Exit fullscreen mode

The trickiest bit for parsing today was forgetting to account for the minus sign in front of negative x/y position values. Got the wrong answers a few times before realizing I had some numbers that were supposed to be negative as positive. Need to remember that.

Part One - A New Hand Touches the Beacon

Ah, yes, back to tracking down the distress beacon with lots of computation! I’m guessing the sensors can only be deployed once, huh? Couldn’t just tell each sensor to move around a bit to try finding the distress beacon? Nah, that wouldn’t work. Let’s write some code!

use itertools::Itertools;

/// Solve Day 15, Part 1
fn solve(input: &[Sensor]) -> u32 {
    let row = 2_000_000; // Our hard-coded row of interest

    // Identify a RowRange for each sensor indicated the furthest left and furthest
    // right point detected by each sensor. These RowRanges may overlap, though, so
    // we need to 'condense' the ranges so we don't double-count any points. This
    // part depends on the input being sorted ahead of time, so that the RowRanges
    // come out sorted, so that all the RowRanges that can be condensed will be
    // encountered one after another. If the input isn't sorted here, you'll get a
    // different (wrong) answer.
    let mut ranges: Vec<RowRange> = Vec::new();
    for range in input.iter().flat_map(|s| s.row_range_sensed(row)) {
        // If the current range can be merged with the last range in `ranges`, do so.
        // Otherwise, just push the current range to the list.
        if let Some(last_rng) = ranges.last_mut() {
            if last_rng.overlaps(&range) {
                last_rng.merge(&range);
            }
            continue;
        }
        ranges.push(range);
    }

    // Count the number of observable positions on the target row, defined by
    // the limits of the `ranges`.
    let sensed_on_row = ranges.iter().map(|r| r.count_positions()).sum::<usize>();

    // We'll need to subtract out the number of beacons on the row, since those
    // points definitely _can_ contain a beacon.
    let beacons_on_row = input
        .iter()
        .filter_map(|s| s.beacon_on_row(row))
        .unique()
        .count();

    let definitely_not_beacons = sensed_on_row - beacons_on_row;
    (definitely_not_beacons as u32)
}

/// Represents a range of points on a given row of the scan. Includes the start and
/// end points on that row.
#[derive(Debug)]
struct RowRange(isize, isize);

impl RowRange {
    /// Does this range overlap another?
    fn overlaps(&self, other: &Self) -> bool {
        other.1 >= self.0 && self.1 >= other.0
    }

    /// Merge this range with another
    fn merge(&mut self, other: &Self) {
        *self = RowRange(self.0.min(other.0), self.1.max(other.1));
    }

    /// Count the number of positions in this range
    fn count_positions(&self) -> usize {
        self.0.abs_diff(self.1) + 1
    }
}

impl Sensor {
    /// Indicates if the sensor can detect the given Point
    pub fn can_detect(&self, point: &Point) -> bool {
        self.location.distance_to(point) <= self.range
    }

    /// Workhorse of part one. Identifies and returns the range of positions
    /// that can be detected by this sensor on the indicated row, as a RowRange.
    fn row_range_sensed(&self, row: isize) -> Option<RowRange> {
        let distance_to_row = self.location.1.abs_diff(row);
        if distance_to_row > self.range {
            return None;
        }

        // The spread indicates how much of the Manhattan distance for detection
        // is remaining to 'spread' out to the left and right. Essentially half
        // the width of the detection zone on this row.
        let spread = self.range - distance_to_row;
        let range_start = self.location.0.saturating_sub_unsigned(spread);
        let range_end = self.location.0.saturating_add_unsigned(spread);
        Some(RowRange(range_start, range_end))
    }

    /// If the beacon is on the given row, return the location of the beacon.
    /// Otherwise, return None.
    fn beacon_on_row(&self, row: isize) -> Option<Point> {
        if self.beacon.1 == row {
            return Some(self.beacon);
        }
        None
    }
}

Enter fullscreen mode Exit fullscreen mode

The real trick here is not to try identifying each position on the row individually that can be sensed, but to identify the ranges of positions that can be sensed by the starting and ending positions on the row. I’m sure you_could_ identify each position on the row uniquely, but those ranges are large.

Part Two - That One Spot You Can’t Reach

Wait, hold on, these sensor ranges are absolutely huge, and yet there is one and only one position in the midst of all those sensors that isn’t in range. Really? How unlucky can we be!? That’s fine, at least we get a pretty good logic puzzle out of the deal. The puzzle description gives us some constraints that we can use to make solving this part a lot less computationally expensive. Check out the comment in the code below for an explanation.

use itertools::Itertools;

/// Solve Day 15, Part 2
///
/// Well, I think this is my first "what the heck is he doing" comment of the year.
/// Yay! So, this solution relies on some assumptions, the biggest of which is that
/// the beacon we're searching for will lie one space outside the range of a Sensor.
/// Why can we assume that? Well, the only possible way that a gap of larger than
/// one could contain the beacon is if the beacon were located in one of the four
/// corner points of the allowed range. That would kind of suck, though, so it's
/// probably not how it is. If it turns out to be the case, then we only have four
/// possible answers to try, so it's a win-win. So, given that the beacon most
/// likely lies in a one-wide gap between sensor ranges, we can treat that gap like
/// a line. The other assumption is that there's more than one one-wide gap.
/// Otherwise, again, we'd have multiple unscanned spaces. That other gap would
/// necessarily have a slope with opposite sign of the first gap, making an X with
/// the center on the beacon. X marks the spot! So, if we can identify all the
/// one-wide gaps in the range of the sensors, we can identify all the places where
/// these gap-lines intersect. If we can find one intersection that can't be
/// detected by any sensor, that's the one we want.
fn solve(input: &[Sensor]) -> u64 {
    // Identify all the diagonal gaps between sensor detection ranges that are only
    // one space wide.
    let mut diagonal_gaps = Vec::new();
    for (sensor1, sensor2) in input.iter().tuple_combinations() {
        let Some(gap) = sensor1.gap_size(sensor2) else { continue; };
        if gap == 1 {
            diagonal_gaps.push(sensor1.diagonal_between(sensor2));
        }
    }

    // Identify all the points where these one-wide gaps intersect.
    let intersects = diagonal_gaps
        .iter()
        .tuple_combinations()
        .flat_map(|(diag1, diag2)| diag1.intersect(diag2))
        .unique()
        .collect_vec();

    // Check the intersections against all the sensors to identify the intersection
    // that cannot be detected by any Sensor. Now, for my input, there was only one
    // intersection that made it this far, but this check should make the solution
    // more robust for other inputs.
    'outer: for intersect in intersects {
        for sensor in input.iter() {
            if sensor.can_detect(&intersect) {
                continue 'outer;
            }
        }
        return intersect.tuning_frequency();
    }

    // Freak out if we can't find an intersection that can't be detected.
    panic!("Could not find the beacon!");
}

/// Represents a diagonal line. The Positive variant indicates a line with a slope
/// of 1 and the Negative variant indicates a line with a slope of -1.
#[derive(Debug)]
enum Diagonal {
    Positive(isize),
    Negative(isize),
}

impl Diagonal {
    /// Identify the point where two Diagonal lines intersect.
    fn intersect(&self, other: &Self) -> Option<Point> {
        // It's simple geometry! Which explains why it was so hard for me
        // to implement. Uses the formula for the two lines to calculate the
        // intersecting point, with some shortcuts because we know the slope
        // will either be positive or negative one for both lines, and if
        // the lines have the same slope, they're parallel and we can bail.
        use Diagonal::*;
        let (neg, pos) = match (self, other) {
            (Positive(pos), Negative(neg)) => (neg, pos),
            (Negative(neg), Positive(pos)) => (neg, pos),
            (Positive(_), Positive(_)) => return None,
            (Negative(_), Negative(_)) => return None,
        };
        let x = (neg - pos) / 2;
        let y = x + pos;
        Some(Point(x, y))
    }
}

impl Sensor {
    /// Find the size of the gap in the sensor range between two Sensors.
    /// If there's no gap (they overlap), return None.
    fn gap_size(&self, other: &Self) -> Option<usize> {
        let distance = self.location.distance_to(&other.location);
        let total_range = self.range + other.range;
        if total_range >= distance {
            return None;
        }
        Some(distance - total_range - 1)
    }

    /// Calculate the formula for the line that lies in the gap between two
    /// Sensor detection ranges. The line will lie diagonally just outside
    /// the range of `self`.
    fn diagonal_between(&self, other: &Self) -> Diagonal {
        let Point(x1, y1) = self.location;
        let Point(x2, y2) = other.location;
        let offset = self.range + 1;

        // Here, we identify two points on the diagonal line. We'll pick points just
        // outside the cardinal direction points of the `self` sensor range.
        let (p1x, p1y) = if x2 > x1 {
            (x1.saturating_add_unsigned(offset), y1)
        } else {
            (x1.saturating_sub_unsigned(offset), y1)
        };
        let (p2x, p2y) = if y2 > y1 {
            (x1, y1.saturating_add_unsigned(offset))
        } else {
            (x1, y1.saturating_sub_unsigned(offset))
        };

        // We know that the slope will either be 1 or -1, since these lines
        // are diagonals.
        let slope = (p2x - p1x) / (p2y - p1y);
        let intercept = p1y - (slope * p1x);
        if slope > 0 {
            Diagonal::Positive(intercept)
        } else {
            Diagonal::Negative(intercept)
        }
    }
}

impl Point {
    /// Calculate the tuning frequency the way the puzzle told us to.
    fn tuning_frequency(&self) -> u64 {
        (4_000_000 * self.0 as u64) + self.1 as u64
    }
}

Enter fullscreen mode Exit fullscreen mode

You know, I didn’t come into this day’s puzzle expecting to need to think about the formulas for lines and calculating intersections.

Wrap Up

Today was a doozy! The biggest things that tripped me up were (a) thinking through the logic for solving part two and (b) translating line formula and equations into code. I honestly kept distracting myself by realizing that the special cases for lines meant I could simplify the code, but taking a while to get it written down. We’ve officially hit the part of Advent of Code where the difficulty has ramped up a bit. Given that this puzzle hit on a Thursday, I’m honestly a bit concerned about what Saturday will bring, given that puzzles tend to be tougher on the weekends. I learned a lot from today’s puzzle, though. Not so much about code, but about about how to think through these puzzles. It’s a good warm-up for the tougher puzzles that are coming. That said, I’m kind of hoping for a bit of a step-down tomorrow. Let’s find out!

Top comments (0)