Advent Of Code 2022 第八天 - 树顶树屋

发表于 更新于 分类于 ，

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

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

问题

找到一个 Grid 里面一个点的能见度。

第一部分

探险队遇到了一片奇特的高大树木，它们都被小心翼翼地种植在一个网格中。精灵们解释说，以前的探险队种植这些树木是为了重新造林。现在，他们很好奇这里是否是建造树屋的好地方。

首先，确定这里是否有足够的树木覆盖，以保持树屋的 隐蔽性 。要做到这一点，你需要计算从网格外直接沿某一行或某一列观察时 可见的树 的数量。

精灵们已经发射了一架四轴飞行器来生成一张有每棵树高度的地图（你的谜题输入）。比如说：

1
2
3
4
5
30373
25512
65332
33549
35390

每棵树都用一个数字表示，其值是它的高度，其中0是最短的，9是最高的。

如果一棵树和网格边缘之间的所有其他树都比它 短 ，那么该树就是 可见的 。只考虑同一行或同一列的树；也就是说，只从任何给定的树上、下、左或右看。

网格边缘的所有树木都是 可见的 ，因为它们已经在边缘了，所以没有树木阻挡视线。在这个例子中，只剩下 内部的九棵树 需要考虑。

  • 左上角的 5 从左边和上面是 可见 的（从右边和下面不可见，因为其他高度为 5 的树挡住了）。
  • 中上层的5从顶部和右侧都是 可见 的。
  • 右上角的 1 从任何方向都不可见；要使其可见，需要在其与边缘之间只有高度为 0 的树。
  • 左中的5是 可见 的，但只能从右边看。
  • 中间的3从任何方向都是不可见的；如果它是可见的，在它和一条边之间最多只有高度为2的树。
  • 右侧中间的3从右边是 可见 的。
  • 在底排，中间的5是 可见 的，但3和4不是。

边缘有16棵树是可见的，内部还有5棵树是可见的，在这种安排下，总共有 21 棵树是可见的。

考虑一下你的地图； 从网格外可以看到多少棵树？

第二部分

精灵们对现有的树木覆盖量感到满意，他们只需要知道建造树屋的最佳地点：他们希望能够看到很多*树。

要测量从某棵树上看到的距离，从那棵树往上、往下、往左、往右看；如果你走到一个边缘或在第一棵与考虑中的树相同高度或更高的树上，就停下来。(如果一棵树正处于边缘，至少有一个观察距离是零。）

精灵们并不关心比上述规则找到的树更高的远处的树；提议的树屋有很大的屋檐以保持干燥，所以无论如何他们都无法看到比树屋更高的地方。

在上面的例子中，考虑第二行中的5：

1
2
3
4
5
30373
25512
65332
33549
35390
  • 向上看，它的视线没有被阻挡；它可以看到 1 树（高度为3）。
  • 向左看，它的视线立即被挡住了；它只能看到 1 棵树（高度为5，就在它旁边）。
  • 向右看，它的视线没有被挡住；它可以看到 2 棵树。
  • 向下看，它的视线最终被挡住了；它可以看到 2 棵树（一棵高度为3，然后是挡住它视线的高度为5的树）。

一棵树的 风景得分 是通过 乘以 它在四个方向上的观察距离而得到的。对于这棵树，这是 4 （通过乘以1*1*2*2找到）。

然而，你可以做得更好：考虑第四行中间高度为5的树：

1
2
3
4
5
30373
25512
65332
33549
35390
  • 向上看，它的视线被 2 棵树挡住（被另一棵5高度的树挡住）。
  • 向左看，它的视线没有被挡住；它可以看到 2 棵树。
  • 向下看，它的视线也没有被阻挡；它可以看到 1 棵树。
  • 向右看，它的视线被 2 棵树挡住了（被一棵高度为9的大树）。

这棵树的风景得分是 8 （2*2*1*2）；这是建造树屋的理想地点。

考虑一下你地图上的每棵树。 任何一棵树的最高景观得分是多少？

代码

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

08.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
use advent_of_code::{Direction, Point, SimpleGrid};
use itertools::Itertools;

type Input<'a> = SimpleGrid<u32>;

static FOUR_DIRECTIONS: [Direction; 4] = [
    Direction::North,
    Direction::East,
    Direction::South,
    Direction::West,
];

fn parse(input: &str) -> Input {
    SimpleGrid::from_str(input, &mut |c, _, _| c.to_digit(10).unwrap())
}

pub fn part_one(input: Input) -> Option<usize> {
    Some(
        input
            .points()
            .iter()
            .filter(|&point| {
                if input.is_boundary(point) {
                    true
                } else {
                    let height = input.get(point);
                    FOUR_DIRECTIONS
                        .iter()
                        .any(|dir| {
                            input
                                .walk(point, dir)
                                .all(|point_b| {
                                    input.get(&point_b) < height
                                })
                        })
                }
            })
            .count()
    )
}

pub fn part_two(input: Input) -> Option<u32> {
    input
        .points()
        .iter()
        .map(|point| {
            let height = input.get(point);

            FOUR_DIRECTIONS
                .iter()
                .map(|dir| {
                    let points = input.walk(point, &dir).collect::<Vec<Point>>();
                    let length = points.len() as u32;

                    points
                        .iter()
                        .find_position(|point_b| input.get(&point_b) >= height)
                        .map(|(pos, _item)| (pos + 1) as u32)
                        .unwrap_or(length)
                })
                .product()
        })
        .max()
}

解析器

每一个点变成 Grid 上面的每一个点。

第一部分

对于每个点，首先看是否在边缘，然后以该点为中心对于四个方向走，一个方向如果碰到了比自己高的树就代表不可见，如果任意一个方向可见就是可见的。

第二部分

对于每个点，在四个方向上找到比自己高的那棵树，找到加一就是能见度，找不到能见度就是那一个 Iterator 的长度。

运行时间

所有时间由我这垃圾笔记本电脑进行(不科学的)测试，均以 --release 启动。

1
2
3
4
5
Day 8
------
Parser: ✓ (72.6µs)
Part 1: 1662 (403.4µs)
Part 2: 537600 (15.9ms)