Day 15 (Advent of Code 2022)
fasterthanlime
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.
$ 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:
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.
This article is part 15 of the Advent of Code 2022 series.
If you liked what you saw, please support my work!
