Advent Of Code 2022 第九天 - 绳索桥

发表于 更新于 分类于 ，

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

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

问题

在头移动的时候移动绳子的绳段。

第一部分

当你在桥上行走时，这座绳索桥吱吱作响。你不确定它有多老，或者它是否能支撑你的体重。

不过，它似乎可以支撑精灵们的体重。这座桥横跨一个峡谷，这个峡谷是由远在你下面的大河开凿出来的。

你小心翼翼地走着；当你这样做时，绳索就会伸展和扭曲。你决定通过建立绳索物理模型来分散自己的注意力；也许你甚至可以想出 不 走上去的地方。

考虑到一根绳子的两端都有一个结；这些结标志着绳子的 头 和 尾 。如果头部离尾部足够远，尾部就会被拉向头部。

由于涉及普朗克长度的模糊推理，你应该能够在一个二维网格上建立结的位置模型。然后，通过对头部进行一系列 假设的运动 （你的谜题输入），你可以确定尾部将如何移动。

由于前面提到的普朗克长度，绳子必须相当短；事实上，头部（H）和尾部（T）必须 一直接触 （对角线相邻，甚至重叠都算作接触）：

1
2
3
4
5
6
7
8
9
10
11
12
13
....
.TH.
....

....
.H..
..T.
....

...
.H. (H 覆盖 T)
...

如果头离尾巴直接上、下、左、右两步，尾巴也必须朝这个方向移动一步，以便保持足够的距离：

1
2
3
4
5
6
7
8
9
10
.....    .....    .....
.TH.. -> .T.H. -> ..TH.
.....    .....    .....

...    ...    ...
.T.    .T.    ...
.H. -> ... -> .T.
...    .H.    .H.
...    ...    ...

否则，如果头和尾没有接触，而且不在同一行或同一列，尾巴总是斜着走一步来跟上：

1
2
3
4
5
6
7
8
9
10
11
12
.....    .....    .....
.....    ..H..    ..H..
..H.. -> ..... -> ..T..
.T...    .T...    .....
.....    .....    .....

.....    .....    .....
.....    .....    .....
..H.. -> ...H. -> ..TH.
.T...    .T...    .....
.....    .....    .....

你只需要计算出在头部做一系列动作时，尾巴的去向。假设头部和尾部都从同一位置开始，重叠在一起。

比如说：

1
2
3
4
5
6
7
8
R 4
U 4
L 3
D 1
R 4
D 1
L 5
R 2

这一系列的动作使头部 向右 四步，然后 向上 四步，然后 向左 三步，然后 向下 一步，如此反复。每一步之后，如果这一步意味着头部不再与尾部相邻，你就需要更新尾部的位置。从视觉上看，这些运动发生如下（s标志着作为参考点的起始位置）。

可视化

 
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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
== 初始态 ==

......
......
......
......
H.....  (H 覆盖 T, s)

== R 4 ==

......
......
......
......
TH....  (T 覆盖 s)

......
......
......
......
sTH...

......
......
......
......
s.TH..

......
......
......
......
s..TH.

== U 4 ==

......
......
......
....H.
s..T..

......
......
....H.
....T.
s.....

......
....H.
....T.
......
s.....

....H.
....T.
......
......
s.....

== L 3 ==

...H..
....T.
......
......
s.....

..HT..
......
......
......
s.....

.HT...
......
......
......
s.....

== D 1 ==

..T...
.H....
......
......
s.....

== R 4 ==

..T...
..H...
......
......
s.....

..T...
...H..
......
......
s.....

......
...TH.
......
......
s.....

......
....TH
......
......
s.....

== D 1 ==

......
....T.
.....H
......
s.....

== L 5 ==

......
....T.
....H.
......
s.....

......
....T.
...H..
......
s.....

......
......
..HT..
......
s.....

......
......
.HT...
......
s.....

......
......
HT....
......
s.....

== R 2 ==

......
......
.H....  (H 覆盖 T)
......
s.....

......
......
.TH...
......
s.....

模拟绳索后，你可以计算出 尾巴至少访问过一次的所有位置 。在这个图中，s再次标记了起始位置（尾巴也访问了这个位置），#标记了尾巴访问的其他位置：

1
2
3
4
5
..##..
...##.
.####.
....#.
s###..

因此，有 13 个位置的尾巴至少去过一次。

模拟你完整的运动。 绳子的尾巴至少去过多少个位置？

第二部分

绳索断裂了! 突然间，河水变得比你记忆中的要近得多。桥还在那里，但一些断裂的绳索现在正向你呼啸而来，你在空中坠落！这时，你必须抓住绳索。

绳索的移动速度太快，你无法抓住；你只有几秒钟的时间来选择如何拱起你的身体以避免被击中。幸运的是，你的模拟可以扩展到支持更长的绳索。

你现在必须模拟由 十个 结组成的绳子，而不是两个结。一个结仍然是绳子的头，并根据一系列的动作来移动。再往下的每一个绳结都按照之前的规则跟随前面的绳结。

使用与上例相同的运动系列，但标有 H, 1, 2, …, 9 的绳结，现在的运动情况如下。

可视化

 
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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
== 初始态 ==

......
......
......
......
H.....  (H 覆盖 1, 2, 3, 4, 5, 6, 7, 8, 9, s)

== R 4 ==

......
......
......
......
1H....  (1 覆盖 2, 3, 4, 5, 6, 7, 8, 9, s)

......
......
......
......
21H...  (2 覆盖 3, 4, 5, 6, 7, 8, 9, s)

......
......
......
......
321H..  (3 覆盖 4, 5, 6, 7, 8, 9, s)

......
......
......
......
4321H.  (4 覆盖 5, 6, 7, 8, 9, s)

== U 4 ==

......
......
......
....H.
4321..  (4 覆盖 5, 6, 7, 8, 9, s)

......
......
....H.
.4321.
5.....  (5 覆盖 6, 7, 8, 9, s)

......
....H.
....1.
.432..
5.....  (5 覆盖 6, 7, 8, 9, s)

....H.
....1.
..432.
.5....
6.....  (6 覆盖 7, 8, 9, s)

== L 3 ==

...H..
....1.
..432.
.5....
6.....  (6 覆盖 7, 8, 9, s)

..H1..
...2..
..43..
.5....
6.....  (6 覆盖 7, 8, 9, s)

.H1...
...2..
..43..
.5....
6.....  (6 覆盖 7, 8, 9, s)

== D 1 ==

..1...
.H.2..
..43..
.5....
6.....  (6 覆盖 7, 8, 9, s)

== R 4 ==

..1...
..H2..
..43..
.5....
6.....  (6 覆盖 7, 8, 9, s)

..1...
...H..  (H 覆盖 2)
..43..
.5....
6.....  (6 覆盖 7, 8, 9, s)

......
...1H.  (1 覆盖 2)
..43..
.5....
6.....  (6 覆盖 7, 8, 9, s)

......
...21H
..43..
.5....
6.....  (6 覆盖 7, 8, 9, s)

== D 1 ==

......
...21.
..43.H
.5....
6.....  (6 覆盖 7, 8, 9, s)

== L 5 ==

......
...21.
..43H.
.5....
6.....  (6 覆盖 7, 8, 9, s)

......
...21.
..4H..  (H 覆盖 3)
.5....
6.....  (6 覆盖 7, 8, 9, s)

......
...2..
..H1..  (H 覆盖 4; 1 覆盖 3)
.5....
6.....  (6 覆盖 7, 8, 9, s)

......
...2..
.H13..  (1 覆盖 4)
.5....
6.....  (6 覆盖 7, 8, 9, s)

......
......
H123..  (2 覆盖 4)
.5....
6.....  (6 覆盖 7, 8, 9, s)

== R 2 ==

......
......
.H23..  (H 覆盖 1; 2 覆盖 4)
.5....
6.....  (6 覆盖 7, 8, 9, s)

......
......
.1H3..  (H 覆盖 2, 4)
.5....
6.....  (6 覆盖 7, 8, 9, s)

现在，你需要跟踪新的尾巴9访问的位置。在这个例子中，尾巴从不移动，所以它只访问 1 的位置。然而， 要小心 比以前可能有更多的运动类型，所以你可能想把你模拟的绳子和上面的绳子进行视觉上的比较。

这里有一个更大的例子。

1
2
3
4
5
6
7
8
R 5
U 8
L 8
D 3
R 17
D 10
L 25
U 20

这些运动发生如下（个别步骤没有显示）：

可视化

 
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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
== 初始态 ==

..........................
..........................
..........................
..........................
..........................
..........................
..........................
..........................
..........................
..........................
..........................
..........................
..........................
..........................
..........................
...........H..............  (H 覆盖 1, 2, 3, 4, 5, 6, 7, 8, 9, s)
..........................
..........................
..........................
..........................
..........................

== R 5 ==

..........................
..........................
..........................
..........................
..........................
..........................
..........................
..........................
..........................
..........................
..........................
..........................
..........................
..........................
..........................
...........54321H.........  (5 覆盖 6, 7, 8, 9, s)
..........................
..........................
..........................
..........................
..........................

== U 8 ==

..........................
..........................
..........................
..........................
..........................
..........................
..........................
................H.........
................1.........
................2.........
................3.........
...............54.........
..............6...........
.............7............
............8.............
...........9..............  (9 覆盖 s)
..........................
..........................
..........................
..........................
..........................

== L 8 ==

..........................
..........................
..........................
..........................
..........................
..........................
..........................
........H1234.............
............5.............
............6.............
............7.............
............8.............
............9.............
..........................
..........................
...........s..............
..........................
..........................
..........................
..........................
..........................

== D 3 ==

..........................
..........................
..........................
..........................
..........................
..........................
..........................
..........................
.........2345.............
........1...6.............
........H...7.............
............8.............
............9.............
..........................
..........................
...........s..............
..........................
..........................
..........................
..........................
..........................

== R 17 ==

..........................
..........................
..........................
..........................
..........................
..........................
..........................
..........................
..........................
..........................
................987654321H
..........................
..........................
..........................
..........................
...........s..............
..........................
..........................
..........................
..........................
..........................

== D 10 ==

..........................
..........................
..........................
..........................
..........................
..........................
..........................
..........................
..........................
..........................
..........................
..........................
..........................
..........................
..........................
...........s.........98765
.........................4
.........................3
.........................2
.........................1
.........................H

== L 25 ==

..........................
..........................
..........................
..........................
..........................
..........................
..........................
..........................
..........................
..........................
..........................
..........................
..........................
..........................
..........................
...........s..............
..........................
..........................
..........................
..........................
H123456789................

== U 20 ==

H.........................
1.........................
2.........................
3.........................
4.........................
5.........................
6.........................
7.........................
8.........................
9.........................
..........................
..........................
..........................
..........................
..........................
...........s..............
..........................
..........................
..........................
..........................
..........................

现在，尾巴（9）访问了 36 个位置（包括s）至少一次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
..........................
..........................
..........................
..........................
..........................
..........................
..........................
..........................
..........................
#.........................
#.............###.........
#............#...#........
.#..........#.....#.......
..#..........#.....#......
...#........#.......#.....
....#......s.........#....
.....#..............#.....
......#............#......
.......#..........#.......
........#........#........
.........########.........

在一根有10个结的大绳上模拟你的一系列动作。 绳子的尾巴至少到过多少个位置？

代码

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

09.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
use std::cmp::{max, min};

use advent_of_code::{Direction, Point, SparseGrid};

type Input = Vec<(Direction, u32)>;

fn parse(input: &str) -> Input {
    input
        .lines()
        .map(|line| {
            let (dir, space) = line.split_once(" ").unwrap();
            (match dir {
                "U" => Direction::North,
                "R" => Direction::East,
                "D" => Direction::South,
                "L" => Direction::West,
                _ => unreachable!()
            }, space.parse::<u32>().unwrap())
        })
        .collect::<Input>()
}

fn knot_pos(head: &Point, knot: &Point) -> Point {
    Point {
        x: knot.x + max(min(head.x - knot.x, 1), -1),
        y: knot.y + max(min(head.y - knot.y, 1), -1),
    }
}

fn simulate_knot(steps: Input, knot_length: usize) -> usize {
    let mut knots = (0..knot_length).map(|_| Point { x: 0, y: 0 }).collect::<Vec<Point>>();
    let mut grid = SparseGrid::default();

    grid.insert(Point { x: 0, y: 0 }, ());

    steps.iter().for_each(|(dir, length)| {
        (0..*length).for_each(|_| {
            knots[0] = knots[0].get_neighbour(dir, 1);
            (0..(knots.len() - 1)).for_each(|i| {
                let head = &knots[i];
                let tail = &knots[i + 1];

                if head.chebyshev_distance(tail) > 1 {
                    knots[i + 1] = knot_pos(head, tail);
                    if i == knot_length - 2 {
                        grid.insert(knots[i + 1].clone(), ())
                    }
                }
            })
        })
    });

    grid.points.len()
}

pub fn part_one(input: Input) -> Option<usize> {
    Some(simulate_knot(input, 2))
}

pub fn part_two(input: Input) -> Option<usize> {
    Some(simulate_knot(input, 10))
}

解析器

将输入变成方向的 enum 和次数。

第一部分

每一次运动首先现将头往方向移动，然后判断之后的绳结是否超出了切比雪夫距离 1，这代表那个绳结需要移动。
如果需要移动就把绳结往头的方向移动最多 1 距离。

如果移动的绳结是最后一个，就把位置记录到一个 Grid 里面。

第二部分

和第一部分一样，只不过绳结长度比较长。

运行时间

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

1
2
3
4
5
Day 9
------
Parser: ✓ (152.1µs)
Part 1: 5735 (371.9µs)
Part 2: 2478 (417.0µs)