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

aoc/year2022/
day15.rs
