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
|
--- Day 18: Many-Worlds Interpretation ---
As you approach Neptune, a planetary security system detects you and activates a giant tractor beam
on Triton! You have no choice but to land.
A scan of the local area reveals only one interesting feature: a massive underground vault. You
generate a map of the tunnels (your puzzle input). The tunnels are too narrow to move diagonally.
Only one [1m[97mentrance[0m (marked @) is present among the [1m[97mopen passages[0m (marked .) and [1m[97mstone walls[0m (#), but
you also detect an assortment of [1m[97mkeys[0m (shown as lowercase letters) and [1m[97mdoors[0m (shown as uppercase
letters). Keys of a given letter open the door of the same letter: a opens A, b opens B, and so on.
You aren't sure which key you need to disable the tractor beam, so you'll need to [1m[97mcollect all of
them[0m.
For example, suppose you have the following map:
#########
#b.A.@.a#
#########
Starting from the entrance (@), you can only access a large door (A) and a key (a). Moving toward
the door doesn't help you, but you can move 2 steps to collect the key, unlocking A in the process:
#########
#b.....@#
#########
Then, you can move 6 steps to collect the only other key, b:
#########
#@......#
#########
So, collecting every key took a total of [1m[97m8[0m steps.
Here is a larger example:
########################
#f.D.E.e.C.b.A.@.a.B.c.#
######################.#
#d.....................#
########################
The only reasonable move is to take key a and unlock door A:
########################
#f.D.E.e.C.b.....@.B.c.#
######################.#
#d.....................#
########################
Then, do the same with key b:
########################
#f.D.E.e.C.@.........c.#
######################.#
#d.....................#
########################
...and the same with key c:
########################
#f.D.E.e.............@.#
######################.#
#d.....................#
########################
Now, you have a choice between keys d and e. While key e is closer, collecting it now would be
slower in the long run than collecting key d first, so that's the best choice:
########################
#f...E.e...............#
######################.#
#@.....................#
########################
Finally, collect key e to unlock door E, then collect key f, taking a grand total of [1m[97m86[0m steps.
Here are a few more examples:
- ########################
#...............b.C.D.f#
#.######################
#.....@.a.B.c.d.A.e.F.g#
########################
Shortest path is 132 steps: b, a, c, d, f, e, g
- #################
#i.G..c...e..H.p#
########.########
#j.A..b...f..D.o#
########@########
#k.E..a...g..B.n#
########.########
#l.F..d...h..C.m#
#################
Shortest paths are 136 steps;one is: a, f, b, j, g, n, h, d, l, o, e, p, c, i, k, m
- ########################
#@..............ac.GI.b#
###d#e#f################
###A#B#C################
###g#h#i################
########################
Shortest paths are 81 steps; one is: a, c, f, i, d, g, b, e, h
[1m[97mHow many steps is the shortest path that collects all of the keys?[0m
|
