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
|
--- Part Two ---
You arrive at the vault only to discover that there is not one vault, but [1m[97mfour[0m - each with its own
entrance.
On your map, find the area in the middle that looks like this:
...
.@.
...
Update your map to instead use the correct data:
@#@
###
@#@
This change will split your map into four separate sections, each with its own entrance:
####### #######
#a.#Cd# #a.#Cd#
##...## ##[1m[97m@#@[0m##
##.@.## --> ##[1m[97m###[0m##
##...## ##[1m[97m@#@[0m##
#cB#Ab# #cB#Ab#
####### #######
Because some of the keys are for doors in other vaults, it would take much too long to collect all
of the keys by yourself. Instead, you deploy four remote-controlled robots. Each starts at one of
the entrances (@).
Your goal is still to [1m[97mcollect all of the keys in the fewest steps[0m, but now, each robot has its own
position and can move independently. You can only remotely control a single robot at a time.
Collecting a key instantly unlocks any corresponding doors, regardless of the vault in which the key
or door is found.
For example, in the map above, the top-left robot first collects key a, unlocking door A in the
bottom-right vault:
#######
#@.#Cd#
##.#@##
#######
##@#@##
#cB#.b#
#######
Then, the bottom-right robot collects key b, unlocking door B in the bottom-left vault:
#######
#@.#Cd#
##.#@##
#######
##@#.##
#c.#.@#
#######
Then, the bottom-left robot collects key c:
#######
#@.#.d#
##.#@##
#######
##.#.##
#@.#.@#
#######
Finally, the top-right robot collects key d:
#######
#@.#.@#
##.#.##
#######
##.#.##
#@.#.@#
#######
In this example, it only took [1m[97m8[0m steps to collect all of the keys.
Sometimes, multiple robots might have keys available, or a robot might have to wait for multiple
keys to be collected:
###############
#d.ABC.#.....a#
######@#@######
###############
######@#@######
#b.....#.....c#
###############
First, the top-right, bottom-left, and bottom-right robots take turns collecting keys a, b, and c, a
total of 6 + 6 + 6 = 18 steps. Then, the top-left robot can access key d, spending another 6 steps;
collecting all of the keys here takes a minimum of [1m[97m24[0m steps.
Here's a more complex example:
#############
#DcBa.#.GhKl#
#.###@#@#I###
#e#d#####j#k#
###C#@#@###J#
#fEbA.#.FgHi#
#############
- Top-left robot collects key a.
- Bottom-left robot collects key b.
- Top-left robot collects key c.
- Bottom-left robot collects key d.
- Top-left robot collects key e.
- Bottom-left robot collects key f.
- Bottom-right robot collects key g.
- Top-right robot collects key h.
- Bottom-right robot collects key i.
- Top-right robot collects key j.
- Bottom-right robot collects key k.
- Top-right robot collects key l.
In the above example, the fewest steps to collect all of the keys is [1m[97m32[0m.
Here's an example with more choices:
#############
#g#f.D#..h#l#
#F###e#E###.#
#dCba@#@BcIJ#
#############
#nK.L@#@G...#
#M###N#H###.#
#o#m..#i#jk.#
#############
One solution with the fewest steps is:
- Top-left robot collects key e.
- Top-right robot collects key h.
- Bottom-right robot collects key i.
- Top-left robot collects key a.
- Top-left robot collects key b.
- Top-right robot collects key c.
- Top-left robot collects key d.
- Top-left robot collects key f.
- Top-left robot collects key g.
- Bottom-right robot collects key k.
- Bottom-right robot collects key j.
- Top-right robot collects key l.
- Bottom-left robot collects key n.
- Bottom-left robot collects key m.
- Bottom-left robot collects key o.
This example requires at least [1m[97m72[0m steps to collect all keys.
After updating your map and using the remote-controlled robots, [1m[97mwhat is the fewest steps necessary
to collect all of the keys?[0m
|
