Thanks to my sponsors: Sawyer Knoblich, Romain Kelifa, Victor Song, Matt Jackson, Manuel Hutter, Sarah Berrettini, Ivo Murrell, Luke Yue, James Leitch, Ives van Hoorne, Boris Dolgov, Zoran Zaric, Borys Minaiev, Yufan Lou, Ryan, Richard Pringle, Mathias Brossard, Yann Schwartz, Helge Eichhorn, Marcus Griep and 230 more

Dec 25, 2022

7 min #rust · #advent-of-code

Day 15 (Advent of Code 2022)

From the series Advent of Code 2022

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

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.

$ cargo add nom@7
(cut)

// in `src/main.rs`

mod parse;

// 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:

$ cargo add itertools
(cut)

// 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();
}

$ 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:

$\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:

Are covered by beacons we do know about
Don't already have a beacon we know about.

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:

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:

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

$ 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.

        // 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:

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...

$ 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:

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

$ 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!

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:

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:

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

$ 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.

You're reading the Advent of Code 2022 series.

Here's another article just for you:

Recursive iterators in Rust

May 08, 2019

7 min #rust

I've been looking for this blog post everywhere, but it doesn't exist, so I guess it's my turn to write about Some Fun with Rust.

The task at hand

Let's say you have a recursive, acyclic data structure, like so:

struct Node {
    values: Vec<i32>,
    children: Vec<Node>,
}

This allows you to represent a tree-like structure: