Day 15 (Advent of Code 2022)

This article is part of the Advent of Code 2022 series.

The day 15 puzzle falls into the "math puzzle" territory more than "let's learn something new about Rust", but since several folks asked if I was going to continue... let's continue.

The sample input is 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

As is custom, let's use nom to parse it. We'll do so in a separate module.

Shell session
$ cargo add nom@7
(cut)
Rust code
// in `src/main.rs`

mod parse;
Rust code
// in `src/parse.rs`

use std::fmt;

use nom::{
    bytes::streaming::tag,
    combinator::{all_consuming, map},
    sequence::{preceded, separated_pair},
    Finish, IResult,
};

#[derive(Debug)]
pub struct Record {
    // a sensor
    pub sensor: Point,
    // the closest beacon to that sensor
    pub beacon: Point,
}

impl Record {
    pub fn must_parse(i: &str) -> Self {
        all_consuming(Self::parse)(i)
            .finish()
            .expect("failed to parse input")
            .1
    }

    fn parse(i: &str) -> IResult<&str, Self> {
        // example line:
        // Sensor at x=2, y=18: closest beacon is at x=-2, y=15
        map(
            separated_pair(
                preceded(tag("Sensor at "), Point::parse),
                tag(": closest beacon is at "),
                Point::parse,
            ),
            |(sensor, beacon)| Record { sensor, beacon },
        )(i)
    }
}

#[derive(Clone, Copy, PartialEq, Eq, Hash)]
pub struct Point {
    pub x: i64,
    pub y: i64,
}

impl fmt::Debug for Point {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "({}, {})", self.x, self.y)
    }
}

impl Point {
    fn parse(i: &str) -> IResult<&str, Point> {
        map(
            separated_pair(
                preceded(tag("x="), nom::character::complete::i64),
                tag(", "),
                preceded(tag("y="), nom::character::complete::i64),
            ),
            |(x, y)| Point { x, y },
        )(i)
    }

    // cf. https://en.wikipedia.org/wiki/Taxicab_geometry
    pub fn manhattan_dist(self, other: Self) -> i64 {
        (self.x.abs_diff(other.x) + self.y.abs_diff(other.y)) as i64
    }
}

This'll get us pretty far.

First let's make sure we've parsed everything correctly: we'll put the sample input in src/input-sample.txt, grab itertools for the road, and see what we get:

Shell session
$ cargo add itertools
(cut)
Rust code
// in `src/main.rs`

use parse::Record;

mod parse;

struct Map {
    records: Vec<Record>,
}

impl Map {
    fn parse(input: &str) -> Self {
        let records = input.lines().map(Record::must_parse).collect();
        Self { records }
    }

    fn dump(&self) {
        for record in &self.records {
            println!("{record:?}");
        }
    }
}

fn main() {
    let input = include_str!("input-sample.txt");

    let map = Map::parse(input);
    map.dump();
}
Shell session
$ cargo run
(cut)
Record { sensor: (2, 18), beacon: (-2, 15) }
Record { sensor: (9, 16), beacon: (10, 16) }
Record { sensor: (13, 2), beacon: (15, 3) }
Record { sensor: (12, 14), beacon: (10, 16) }
Record { sensor: (10, 20), beacon: (10, 16) }
Record { sensor: (14, 17), beacon: (10, 16) }
Record { sensor: (8, 7), beacon: (2, 10) }
Record { sensor: (2, 0), beacon: (2, 10) }
Record { sensor: (0, 11), beacon: (2, 10) }
Record { sensor: (20, 14), beacon: (25, 17) }
Record { sensor: (17, 20), beacon: (21, 22) }
Record { sensor: (16, 7), beacon: (15, 3) }
Record { sensor: (14, 3), beacon: (15, 3) }
Record { sensor: (20, 1), beacon: (15, 3) }

Looks okay!

Now, the problem statement is a bit thorny. We have a list of sensors, and the beacon closest to them (beacons emit signals that are.. sensed by sensors).

They provide this sample map:

               1    1    2    2
     0    5    0    5    0    5
-2 ..........#.................
-1 .........###................
 0 ....S...#####...............
 1 .......#######........S.....
 2 ......#########S............
 3 .....###########SB..........
 4 ....#############...........
 5 ...###############..........
 6 ..#################.........
 7 .#########S#######S#........
 8 ..#################.........
 9 ...###############..........
10 ....B############...........
11 ..S..###########............
12 ......#########.............
13 .......#######..............
14 ........#####.S.......S.....
15 B........###................
16 ..........#SB...............
17 ................S..........B
18 ....S.......................
19 ............................
20 ............S......S........
21 ............................
22 .......................B....

The Manhattan distance between two points is (dx + dy), where dx and dy are the absolute difference between the x and y coordinates of those points. Between the sensor (8, 7) and the beacon (2, 10), that gives us:

d=82+710=6+3=6+3=9 \begin{aligned} d &= |8 - 2| + |7 - 10| \ &= |6| + |{-3}| \ &= 6 + 3 \ &= 9 \end{aligned}

Hence, if we look at the line the sensor is at:

 7 .#########S#######S#........

The middle is at x = sensor.x, and it expands 9 to the left and 9 to the right. If we consider the line below:

 7 .#########S#######S#........
 8 ..#################.........

The middle is at the same x coordinate, but we have one less unit of distance covered to the left and to the right of it: only 8.

This goes on until we reach a line where only the middle is within the covered area:

 7 .#########S#######S#........
 8 ..#################.........
 9 ...###############..........
10 ....B############...........
11 ..S..###########............
12 ......#########.............
13 .......#######..............
14 ........#####.S.......S.....
15 B........###................
16 ..........#SB...............
             ^
            here !

In part 1, we have to find how many positions of a given row "cannot contain a beacon". In other words, we need to find positions that:

The idea being that, there's a beacon that's not in our puzzle input, and because we know about all beacons closest to our list of sensors, it must be outside of the "zone of coverage" of each of these sensors.

The sample input has us consider line y=10:

                 1    1    2    2
       0    5    0    5    0    5
 9 ...#########################...
10 ..####B######################..
11 .###S#############.###########.

And, graphically: we must count the number of # on the line. The . signifies that this position isn't covered by our network of sensors, and the B signifies that there's already a beacon we know about in this position.

(And we're looking for a beacon that isn't in the list, by first finding out where it isn't).

All good? This took me a few reads, to be completely honest.

Part 1 solution

So, a naive strategy could work something like this:

Rust code
use parse::Point;

impl Map {
    fn num_impossible_positions(&self, y: i64) -> usize {
        let mut total = 0;
        let min_x = -4;
        let max_x = 26;

        for x in min_x..=max_x {
            let point = Point { x, y };
            if self.records.iter().any(|rec| rec.beacon == point) {
                // already have a beacon there, not an impossible position
            } else if self.records.iter().any(|rec| {
                let radius = rec.sensor.manhattan_dist(rec.beacon);
                rec.sensor.manhattan_dist(point) <= radius
            }) {
                // covered!
                total += 1
            }
        }

        total
    }
}

And this does work for the sample input:

Rust code
fn main() {
    let input = include_str!("input-sample.txt");
    let y = 10;

    let map = Map::parse(input);
    map.dump();

    dbg!(map.num_impossible_positions(y));
}
Shell session
$ cargo run
(cut)
[src/main.rs:52] map.num_impossible_positions(y) = 26

We can also make it work for the real input, although now we can't cheat to get min_x / max_x anymore. And finding the minimum/maximum X coordinates of "beacons or sensors" is not enough: we could have a situation like this:

..........#............
.........###...........
........#####..........
.......#######.........
......####S###B........
.......#######.........
........#####..........
.........###...........
..........#............

...where the coverage area extends far beyond the sensor's and the beacon's coordinates.

Rust code
        // in `num_impossible_positions`
        let mut min_x = i64::MAX;
        let mut max_x = i64::MIN;
        for rec in &self.records {
            let radius = rec.sensor.manhattan_dist(rec.beacon);
            let y_dist = (y - rec.beacon.y).abs();
            if y_dist > radius {
                // coverage area doesn't touch line at `y`
                continue;
            }
            let middle = rec.sensor.x;
            let start = middle - radius;
            let end = middle + radius;
            min_x = min_x.min(start);
            max_x = max_x.max(end);
        }
        dbg!(min_x, max_x);

Now if we just substitute the real input:

Rust code
fn main() {
    // let input = include_str!("input-sample.txt");
    // let y = 10;

    let input = include_str!("input.txt");
    let y = 2_000_000;

    let map = Map::parse(input);
    map.dump();

    dbg!(map.num_impossible_positions(y));
}

And run a release build...

Rust code
$ cargo build --release
$ time ./target/release/day15
(cut)
[src/main.rs:70] map.num_impossible_positions(y) = 5083287
./target/release/day15  0.39s user 0.00s system 99% cpu 0.389 total

It works! And it's not even that slow!

Range-based strategy

...but of course, in part 2, they have us searching between y=0 and y=4_000_000. And "not that slow" times 4 million is "really slow".

So let's see what else we can do.

We're already building "coverage ranges" for every sensor/beacon pair in num_imposible_positions. We wouldn't need to go through each x coordinate one by one if we simply thought in terms of ranges!

Let's see how that would work:

Rust code
impl Map {
    fn ranges(&self, y: i64) -> impl Iterator<Item = RangeInclusive<i64>> {
        let mut ranges = vec![];
        for rec in &self.records {
            let radius = rec.sensor.manhattan_dist(rec.beacon);
            let y_dist = (y - rec.sensor.y).abs();
            if y_dist > radius {
                // coverage area doesn't touch line at `y`
                continue;
            }
            let d = radius - y_dist;
            let middle = rec.sensor.x;
            let start = middle - d;
            let end = middle + d;
            let range = start..=end;
            ranges.push(range);
        }
        ranges.sort_by_key(|r| *r.start());

        ranges.into_iter().coalesce(|a, b| {
            if b.start() - 1 <= *a.end() {
                if b.end() > a.end() {
                    Ok(*a.start()..=*b.end())
                } else {
                    Ok(a)
                }
            } else {
                Err((a, b))
            }
        })
    }

    fn num_impossible_positions(&self, y: i64) -> usize {
        let beacon_x_coords = self
            .records
            .iter()
            .filter(|rec| rec.beacon.y == y)
            .map(|rec| rec.beacon.x)
            .collect::<HashSet<_>>();

        self.ranges(y)
            .map(|r| {
                let range_size = (r.end() - r.start() + 1) as usize;
                let num_beacons_in_range = beacon_x_coords.iter().filter(|x| r.contains(x)).count();
                range_size - num_beacons_in_range
            })
            .sum::<usize>()
    }
}
Shell session
$ cargo build --release
$ time ./target/release/day15
(cut)
[src/main.rs:78] map.num_impossible_positions(y) = 5083287
./target/release/day15  0.00s user 0.00s system 79% cpu 0.002 total

Pretty well, as it turns out! And pretty fast.

Let's adapt this to the part 2 problem.

Part 2 solution

For part 2, we must search where the hidden beacon is: somewhere between y=0 and y=20 for the sample input, and somewhere between y=0 and y=4_000_000, for the real input.

Thanks to our Map::ranges method, our solution is short and sweet.

Most lines will have a single range, because it's full covered:

#################################################################
|------------------------- single range ------------------------|

But the line we're looking for will have two ranges, with a one-wide gap between them:

                           there it is!
                               v
###############################.#################################
|-------- first range --------| |-------- second range ---------|

So, if we have a second range, the x coordinate of the hidden beacon we're looking for is its start, minus one.

Well.. that would be true if our ranges went from x=0 to x=4_000_000, which they don't, currently, but we can fix that!

Rust code
impl Map {
    fn ranges_clamped(
        &self,
        y: i64,
        x_range: RangeInclusive<i64>,
    ) -> impl Iterator<Item = RangeInclusive<i64>> {
        self.ranges(y).filter_map(move |r| {
            // make sure `r` fits into `x_range`
            let r = *r.start().max(x_range.start())..=*r.end().min(x_range.end());
            if r.start() > r.end() {
                // it didn't fit at all!
                None
            } else {
                // we successfully clamped it / it was contained within `x_range` already
                Some(r)
            }
        })
    }
}

And now, we can use the scheme we just came up with:

Rust code
impl Map {
    fn beacon_position(
        &self,
        y_range: &RangeInclusive<i64>,
        x_range: &RangeInclusive<i64>,
    ) -> Option<Point> {
        y_range.clone().find_map(|y| {
            self.ranges_clamped(y, x_range.clone())
                .nth(1)
                .map(|r| Point {
                    x: r.start() - 1,
                    y,
                })
        })
    }
}

Let's take it for a spin:

Rust code
fn main() {
    for (input, y, range) in [
        (include_str!("input-sample.txt"), 10, 0..=20),
        (include_str!("input.txt"), 2_000_000, 0..=4_000_000),
    ] {
        let map = Map::parse(input);
        dbg!(map.num_impossible_positions(y));
        let bp = map.beacon_position(&range, &range).unwrap();
        dbg!(bp);
        println!("tuning frequency: {}", bp.x * 4_000_000 + bp.y);
    }
}
Shell session
$ cargo run --release
   Compiling day15 v0.1.0 (/home/amos/bearcove/aoc2022/day15-art)
(cut)
    Finished release [optimized] target(s) in 0.67s
     Running `target/release/day15`
[src/main.rs:111] map.num_impossible_positions(y) = 26
[src/main.rs:113] bp = (14, 11)
tuning frequency: 56000011
[src/main.rs:111] map.num_impossible_positions(y) = 5083287
[src/main.rs:113] bp = (3283509, 3205729)
tuning frequency: 13134039205729

Those numbers check out!

I have to say, these solutions were very annoying to debug: visualizations don't really work for the real input, since it's so large, so I had to just pepper dbg! in strategic places.

But now it's done, and we never have to think about it again.

This article is part 15 of the Advent of Code 2022 series.

Read the next part

If you liked what you saw, please support my work!

Github logo Donate on GitHub Patreon logo Donate on Patreon

Latest video View all

video cover image
C++ vs Rust: which is faster?

I ported some Advent of Code solutions from C/C++ to Rust, and used the opportunity to compare performance. When I couldn't explain why they performed differently, I had no choice but to disassemble both and look at what the codegen was like!

Watch now
Looking for the homepage?