Advent Of Code 2022 第十五天 - 信标禁区

发表于 更新于 分类于 ，

本文是关于 Advent Of Code 2022 的。
编程圣诞日历，圣诞节前每天一个编程问题。

有兴趣的朋友可以在官网答题，用自己喜欢的编程方式去收集星星⭐️。在官网答题需要登陆并下载为你单独生成的谜题输入，每个人的都不一样。

问题

对于信标覆盖范围进行处理。

第一部分

当求救信号将你引向一个巨大的地下隧道网络时，你又感到了地面的隆隆声。你没有时间去搜索它们，但你不需要：你的背包里有一套可部署的 传感器 ，你想象这些传感器最初是为了定位迷失的精灵而建造的。

这些传感器不是很强大，但没关系；你的手持设备表明你离求救信号的来源足够近，可以使用它们。你从背包里拿出紧急感应系统，按下上面的大按钮，感应器就会在隧道里放大。

一旦传感器找到一个它认为会给它带来良好读数的地方，它就会把自己附在一个坚硬的表面上，开始监测最近的信号源 信标 。传感器和信标总是以整数坐标存在。每个传感器都知道自己的位置，并能 精确地确定信标的位置 ；然而，传感器只能锁定一个信标， 传感器距离 由曼哈顿距离测量。(永远不会出现两个信标与传感器的距离相同的情况)。

传感器很快就会报告他们的位置和最近的信标（你的谜题输入）。比如说：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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

因此，考虑在2,18的传感器；离它最近的信标是在2,15。对于位于9,16的传感器，离它最近的信标是在10,16。

将传感器画成S，信标画成B，上述传感器和信标的安排看起来像这样。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
               1    1    2    2
     0    5    0    5    0    5
 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....

不过，这并不一定是该地区所有信标的全面地图。因为每个传感器只识别其最近的信标，如果一个传感器检测到一个信标，你就知道没有其他信标离这个传感器那么近或更近。仍然有可能存在信标，只是恰好不是离任何传感器最近的信标。考虑一下位于8,7的传感器：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
               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....

这个传感器最近的信标在2,10，所以你知道没有那么近或更近的信标（在任何标有#的位置）。

求救信号并不是由任何一个目前被传感器捕捉到的信标发出，所以你需要通过计算求救信标在哪里 不可能出现 。现在，让事情变得简单些，计算一下信标不可能只出现在某一行的位置上。

所以，假设你有一个信标和传感器的排列，就像上面的例子一样，在y=10的那一行，你想计算信标不可能存在的位置的数量。该行附近的所有传感器的覆盖范围看起来像这样。

1
2
3
4
5
6
                 1    1    2    2
       0    5    0    5    0    5
 9 ...#########################...
10 ..####B######################..
11 .###S#############.###########.

在这个例子中，在y=10的那一行，有 26 个位置不能有信标。

请参考你刚刚部署的传感器的报告。 在y=2000000的一行中，有多少位置不能包含信标？

第二部分

你的手持设备显示求救信号来自附近的一个信标。求救信标没有被任何传感器探测到，但求救信标的x和y坐标必须各不低于0且不大于4000000。

为了隔离遇险信标的信号，你需要确定它的 调谐频率 ，这可以通过将它的x坐标乘以4000000，然后加上它的y坐标来找到。

在上面的例子中，x和y坐标每个最多可以是20。在这个缩小的搜索区域中，只有一个位置可以有一个信标：x=14，y=11。这个遇难信标的调谐频率是 56000011 。

找出该遇难信标的唯一可能位置。 它的调谐频率是多少？

代码

完整的代码可以在 这里 找到。

15.rs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
use itertools::Itertools;
use advent_of_code::{Point};
use advent_of_code::quadrant::Quadrant;
use advent_of_code::range::{Range, RangeStack};

#[derive(Clone, Debug)]
pub struct Pair {
    sensor: Point,
    beacon: Point,
    distance: isize,
}

impl Pair {
    pub fn can_contain_unseen_points(&self, quadrant: &Quadrant) -> bool {
        quadrant.corners().iter().any(|corner| {
            let distance = self.sensor.manhattan_distance(corner);
            distance > self.distance
        })
    }
}

type Input = Vec<Pair>;

fn find_unseen_points(pairs: &[Pair], quadrant: &Quadrant) -> Option<Point> {
    if quadrant.min == quadrant.max {
        return Some(quadrant.min.clone());
    }

    quadrant
        .subdivide()
        .iter()
        .filter(|&sub| sub.min.x <= sub.max.x && sub.min.y <= sub.max.y)
        .filter(|&sub| pairs.iter().all(|pair| pair.can_contain_unseen_points(sub)))
        .filter_map(|sub| find_unseen_points(pairs, sub))
        .next()
}

fn parse_point(s: &str) -> Option<Point> {
    let (_, point_str) = s.split_once("at ")?;
    let (x_str, y_str) = point_str.split_once(", ")?;
    let (_, x) = x_str.split_once('=')?;
    let (_, y) = y_str.split_once('=')?;
    Some(Point {
        x: x.parse().ok()?,
        y: y.parse().ok()?,
    })
}

fn parse(input: &str) -> Input {
    input
        .lines()
        .filter_map(|l| {
            let (sensor_str, beacon_str) = l.split_once(':')?;
            let sensor = parse_point(sensor_str)?;
            let beacon = parse_point(beacon_str)?;
            let distance = sensor.manhattan_distance(&beacon);
            Some(
                Pair{sensor, beacon, distance}
            )
        })
        .collect()
}

pub fn part_one(input: Input) -> Option<usize> {
    let test_value = if cfg!(test) { 10 } else { 2000000 };
    let ranges = input
        .iter()
        .filter_map(|pair| {
            let radius = pair.sensor.manhattan_distance(&pair.beacon);
            let radius_at_test = radius - (test_value - pair.sensor.y).abs();

            let min = pair.sensor.x - radius_at_test;
            let max = pair.sensor.x + radius_at_test;
            if min > max {
                None
            } else {
                Some(Range::new(min, max))
            }
        })
        .collect::<RangeStack>();

    Some(
        ranges.count() - input.iter().filter_map(|pair| {
            if pair.beacon.y == test_value {
                Some(pair.beacon.x)
            } else {
                None
            }
        }).unique().count()
    )
}

pub fn part_two(input: Input) -> Option<isize> {
    let unseen_point = find_unseen_points(&input, &Quadrant {
        min: Point { x: 0, y: 0 },
        max: Point { x: 4000000, y: 4000000 },
    })?;
    Some(unseen_point.x*4000000+unseen_point.y)
}

解析器

从每一行中提取信标和传感器的坐标而已。

第一部分

我使用的方法是计算每一个信标传感器对在检测 y 轴上的长度，并且通过 Range 把它们组合在一起，最后计算那段范围覆盖了多少格。

第二部分

这里使用的方法是通过把区域拆分为四个子区域，并且检测每一个对，对于子区域的四个角落，是否存在任意一个角落到传感器的距离比传感器到信标的距离大，这意味着那个对在那个子区域内必定有点是无法看到的。

经过这样递归下去缩小范围，当找到只有一格的区域的时候，我们就找到答案了。

当然这个题目还有很多解法，我这个解法也大概不是最优解，就我想到的方法还有检测每一个对范围外一格，因为那个信标的唯一性，外两格是不可能的，这样也能够在短时间内找到信标。

运行时间

1
2
3
4
5
Day 15
------
Parser: ✓ (14.3µs)
Part 1: 5256611 (245.3µs)
Part 2: 13337919186981 (44.1ms)