Advent Of Code 2022 第十二天 - 爬山算法

发表于 更新于 分类于 ，

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

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

问题

经典的寻路问题，需要找出最短路径。

第一部分

你试着用你的手持设备与精灵们联系，但是你所沿着的河流一定是太低了，无法得到一个像样的信号。

你要求设备提供周围地区的高度图（你的谜题输入）。高度图显示的是当地的网格，网格中每个方格的高度都由一个小写字母表示，其中a是最低的高度，b是次低的高度，以此类推，直到最高的高度z。

高度图上还包括你的当前位置（S）和应该获得最佳信号的位置（E）的标记。你当前的位置（S）有海拔a，而应该获得最佳信号的位置（E）有海拔z。

你想到达E，但为了节省能量，你应该以 最少的步骤 完成。在每一步中，你可以准确地向上、向下、向左或向右移动一格。为了避免需要拿出你的攀登工具，目标方格的高度最多可以比你当前方格的高度 高一级 ；也就是说，如果你当前的高度是m，你可以走到n的高度，但不能走到o的高度。(这也意味着目标方块的标高可以比你当前方块的标高低很多）。

例如：

1
2
3
4
5
Sabqponm
abcryxxl
accszExk
acctuvwj
abdefghi

在这里，你从左上角开始，你的目标在中间附近。你可以先向下或向右移动，但最终你需要走向底部的 e。从那里，你可以螺旋式地绕到目标。

1
2
3
4
5
v..v<<<<
>v.vv<<^
.>vv>E^^
..v>>>^^
..>>>>>^

在上图中，符号表示路径离开每个方格是向上（^）、向下（v）、向左（<）、还是向右（>）移动。应该得到最佳信号的位置仍然是E，.标志着未访问的方格。

这条路径在 31 步内到达目标，是尽可能少的。

从你现在的位置到应该获得最佳信号的位置，所需的最少步骤是什么？

第二部分

当你走到山上时，你怀疑精灵们会想把这里变成一条徒步小道。不过，开始的地方风景不是很好；也许你可以找到一个更好的起点。

为了在徒步旅行时最大限度地锻炼身体，小路的起点应该尽可能低：海拔a。目标仍然是标有E的广场。然而，小路仍然应该是直接的，用最少的步骤来达到目标。因此，你需要找到从 任何海拔 a到标记E的广场的最短路径。

再次考虑上面的例子。

现在，有六个选择的起始位置（五个标有 a的方格，加上标有 S的方格，算作在海拔 a的位置）。如果你从左下角的方格开始，你可以最快速地到达目标。

1
2
3
4
5
...v<<<<
...vv<<^
...v>E^^
.>v>>>^^
>^>>>>>^

这条路径到达目标只需 29 步，是尽可能少的。

从任何海拔a开始移动到获得最佳信号的位置，所需的最少步骤是什么？

代码

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

12.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
use advent_of_code::{Point, SimpleGrid};
use advent_of_code::shortest_path::shortest_path;

type Input = ( SimpleGrid<char>, Point, Point);

fn parse(input: &str) -> Input {
    let mut start: Option<Point> = None;
    let mut end: Option<Point> = None;

    let grid: SimpleGrid<char> = SimpleGrid::from_str(input, &mut |c, x, y| match c {
        'S' => {
            start = Some(Point {
                x: x as isize,
                y: y as isize,
            });
            'a'
        }
        'E' => {
            end = Some(Point {
                x: x as isize,
                y: y as isize,
            });
            'z'
        }
        c => c,
    });

    (grid, start.unwrap(), end.unwrap())
}

pub fn part_one(input: Input) -> Option<usize> {
    let (grid, start, end) = input;
    shortest_path(&grid, &vec![start], &end, |_| 1, |a, b| (*grid.get(b) as isize - *grid.get(a) as isize) < 2)
}

pub fn part_two(input: Input) -> Option<usize> {
    let (grid, _start, end) = input;
    let start_points: Vec<Point> = grid
        .points()
        .into_iter()
        .filter(|point| *grid.get(point) == 'a' &&
            grid
                .cardianal_neighbours(point)
                .iter()
                .any(|c| *grid.get(c) == 'b'))
        .collect();
    shortest_path(&grid, &start_points, &end, |_| 1, |a, b| (*grid.get(b) as isize - *grid.get(a) as isize) < 2)
}

解析器

没啥好说的，就是把输入变成一个 Grid。

第一部分

这里使用了 dijkstra 寻路算法，详细实现请到 github 去看就不在这里解释了，shortest_path 就是给出起点终点，找出符合限制条件的最短一条路，基本原理是根据限制条件构造一个图，找出cost最小的一个分支。

第二部分

这里你可以直接对所有 a 点进行遍历，这是没问题的，就是运行时间有点长，但是如果你观察输入，有很多的最低点都被 c 包围了。

对于所有旁边没有 b 的最低点，只有两种可能：

  • 如果周围的都是 a ，这代表必定有一个起点 a 比较近。
  • 如果周围都高到无法前往，这代表一定有另一条路比较近。

因此只有当周围有至少一个 b 的时候，这个起点才有可能是最近的。我们可以排除所有符合这个判断的起点，在预先排除了之后运行时间也不会太长。

运行时间

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

1
2
3
4
5
Day 12
------
Parser: ✓ (61.1µs)
Part 1: 468 (778.4µs)
Part 2: 459 (951.6µs)