aoc/year2022/
day15.rs

1//! # Beacon Exclusion Zone
2use crate::util::hash::*;
3use crate::util::iter::*;
4use crate::util::parse::*;
5use crate::util::point::*;
6use std::ops::Range;
7
8pub struct Input {
9    sensor: Point,
10    beacon: Point,
11    manhattan: i32,
12}
13
14pub fn parse(input: &str) -> Vec<Input> {
15    input
16        .iter_signed()
17        .chunk::<4>()
18        .map(|[x1, y1, x2, y2]| {
19            let sensor = Point::new(x1, y1);
20            let beacon = Point::new(x2, y2);
21            Input { sensor, beacon, manhattan: sensor.manhattan(beacon) }
22        })
23        .collect()
24}
25
26/// The example uses y=10 but the real data uses y=2000000, so break out the logic
27/// into a separate function to enable integration testing.
28pub fn part1(input: &[Input]) -> i32 {
29    part1_testable(input, 2_000_000)
30}
31
32/// A beacon cannot be located within the radius of a sensor unless it is the closest beacon.
33///
34/// We first convert each scanner's diamond shaped area into a one-dimensional range at the
35/// specified row. By sorting the ranges, we can quickly calculate the total number of distinct
36/// ranges where another beacon cannot exist, only counting overlapping areas once.
37///
38/// Beacons can also not be located at the same position as another beacon so we then also discount
39/// any beacon located exactly on the specified row.
40pub fn part1_testable(input: &[Input], row: i32) -> i32 {
41    // Converts the "diamond" shaped area of each scanner into a one-dimensional row.
42    // If the scanner's range does not reach the specified row then return `None`.
43    fn build_range(input: &Input, row: i32) -> Option<Range<i32>> {
44        let Input { sensor, manhattan, .. } = input;
45        let extra = manhattan - (sensor.y - row).abs();
46        (extra >= 0).then(|| (sensor.x - extra)..(sensor.x + extra))
47    }
48
49    // Sort the ranges first.
50    let mut ranges: Vec<_> = input.iter().filter_map(|i| build_range(i, row)).collect();
51    ranges.sort_unstable_by_key(|r| r.start);
52
53    let mut total = 0;
54    let mut max = i32::MIN;
55
56    // Compare each range to the next.
57    for Range { start, end } in ranges {
58        if start > max {
59            // If there is no overlap with the previous range, then add the entire length.
60            total += end - start + 1;
61            max = end;
62        } else {
63            // If some part of the range overlaps, then only add any extra length.
64            // (it's possible that there is no extra length)
65            total += (end - max).max(0);
66            max = max.max(end);
67        }
68    }
69
70    // Returns the x position of all beacons that are located on the specified row.
71    let beacons: FastSet<_> =
72        input.iter().filter_map(|i| (i.beacon.y == row).then_some(i.beacon.x)).collect();
73    total - (beacons.len() as i32)
74}
75
76/// Similar to part one, the logic is broken out into a separate function to enable testing.
77pub fn part2(input: &[Input]) -> u64 {
78    part2_testable(input, 4_000_000)
79}
80
81/// The trick to solving this efficiently is to first *rotate* the corners of the diamond
82/// scanner shape by 45 degrees. This transforms them into squares that make it much easier
83/// to find the missing distress beacon.
84///
85/// Of the entire 4000000 by 4000000 area the missing beacon must be located in the only
86/// square area not covered by a scanner.
87pub fn part2_testable(input: &[Input], size: i32) -> u64 {
88    let mut top = FastSet::new();
89    let mut left = FastSet::new();
90    let mut bottom = FastSet::new();
91    let mut right = FastSet::new();
92
93    // Rotate points clockwise by 45 degrees, scale by √2 and extend edge by 1.
94    // This transforms each sensor into an axis aligned bounding box.
95    // The distress beacon is located where the top, left, bottom and right
96    // edges of 4 separate bounding boxes intersect.
97    for Input { sensor, manhattan, .. } in input {
98        top.insert(sensor.x + sensor.y - manhattan - 1);
99        left.insert(sensor.x - sensor.y - manhattan - 1);
100        bottom.insert(sensor.x + sensor.y + manhattan + 1);
101        right.insert(sensor.x - sensor.y + manhattan + 1);
102    }
103
104    let horizontal: Vec<_> = top.intersection(&bottom).copied().collect();
105    let vertical: Vec<_> = left.intersection(&right).copied().collect();
106    let range = 0..=size;
107
108    for &x in &vertical {
109        for &y in &horizontal {
110            // Rotate intersection point counter-clockwise and scale by 1 / √2
111            // to return to original coordinates.
112            #[expect(clippy::manual_midpoint)]
113            let point = Point::new((x + y) / 2, (y - x) / 2);
114            // As we're mixing overlaps from different boxes there may be some spurious false
115            // positives, so double check all points are within the specified area
116            // and outside the range of all scanners.
117            if range.contains(&point.x)
118                && range.contains(&point.y)
119                && input.iter().all(|i| i.sensor.manhattan(point) > i.manhattan)
120            {
121                return 4_000_000 * (point.x as u64) + (point.y as u64);
122            }
123        }
124    }
125
126    unreachable!()
127}
aoc/year2022/day15.rs

aoc/year2022/
day15.rs
