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
|
--- Part Two ---
Strangely, the exit isn't open when you reach it. Then, you remember: the ancient Plutonians were
famous for building [1m[97mrecursive spaces[0m.
The marked connections in the maze aren't portals: they [1m[97mphysically connect[0m to a larger or smaller
copy of the maze. Specifically, the labeled tiles around the inside edge actually connect to a
smaller copy of the same maze, and the smaller copy's inner labeled tiles connect to yet a
[1m[97msmaller[0m copy, and so on.
When you enter the maze, you are at the outermost level; when at the outermost level, only the outer
labels AA and ZZ function (as the start and end, respectively); all other outer labeled tiles are
effectively walls. At any other level, AA and ZZ count as walls, but the other outer labeled tiles
bring you one level outward.
Your goal is to find a path through the maze that brings you back to ZZ at the outermost level of
the maze.
In the first example above, the shortest path is now the loop around the right side. If the starting
level is 0, then taking the previously-shortest path would pass through BC (to level 1), DE (to
level 2), and FG (back to level 1). Because this is not the outermost level, ZZ is a wall, and the
only option is to go back around to BC, which would only send you even deeper into the recursive
maze.
In the second example above, there is no path that brings you to ZZ at the outermost level.
Here is a more interesting example:
Z L X W C
Z P Q B K
###########.#.#.#.#######.###############
#...#.......#.#.......#.#.......#.#.#...#
###.#.#.#.#.#.#.#.###.#.#.#######.#.#.###
#.#...#.#.#...#.#.#...#...#...#.#.......#
#.###.#######.###.###.#.###.###.#.#######
#...#.......#.#...#...#.............#...#
#.#########.#######.#.#######.#######.###
#...#.# F R I Z #.#.#.#
#.###.# D E C H #.#.#.#
#.#...# #...#.#
#.###.# #.###.#
#.#....OA WB..#.#..ZH
#.###.# #.#.#.#
CJ......# #.....#
####### #######
#.#....CK #......IC
#.###.# #.###.#
#.....# #...#.#
###.### #.#.#.#
XF....#.# RF..#.#.#
#####.# #######
#......CJ NM..#...#
###.#.# #.###.#
RE....#.# #......RF
###.### X X L #.#.#.#
#.....# F Q P #.#.#.#
###.###########.###.#######.#########.###
#.....#...#.....#.......#...#.....#.#...#
#####.#.###.#######.#######.###.###.#.#.#
#.......#.......#.#.#.#.#...#...#...#.#.#
#####.###.#####.#.#.#.#.###.###.#.###.###
#.......#.....#.#...#...............#...#
#############.#.#.###.###################
A O F N
A A D M
One shortest path through the maze is the following:
- Walk from AA to XF (16 steps)
- Recurse into level 1 through XF (1 step)
- Walk from XF to CK (10 steps)
- Recurse into level 2 through CK (1 step)
- Walk from CK to ZH (14 steps)
- Recurse into level 3 through ZH (1 step)
- Walk from ZH to WB (10 steps)
- Recurse into level 4 through WB (1 step)
- Walk from WB to IC (10 steps)
- Recurse into level 5 through IC (1 step)
- Walk from IC to RF (10 steps)
- Recurse into level 6 through RF (1 step)
- Walk from RF to NM (8 steps)
- Recurse into level 7 through NM (1 step)
- Walk from NM to LP (12 steps)
- Recurse into level 8 through LP (1 step)
- Walk from LP to FD (24 steps)
- Recurse into level 9 through FD (1 step)
- Walk from FD to XQ (8 steps)
- Recurse into level 10 through XQ (1 step)
- Walk from XQ to WB (4 steps)
- Return to level 9 through WB (1 step)
- Walk from WB to ZH (10 steps)
- Return to level 8 through ZH (1 step)
- Walk from ZH to CK (14 steps)
- Return to level 7 through CK (1 step)
- Walk from CK to XF (10 steps)
- Return to level 6 through XF (1 step)
- Walk from XF to OA (14 steps)
- Return to level 5 through OA (1 step)
- Walk from OA to CJ (8 steps)
- Return to level 4 through CJ (1 step)
- Walk from CJ to RE (8 steps)
- Return to level 3 through RE (1 step)
- Walk from RE to IC (4 steps)
- Recurse into level 4 through IC (1 step)
- Walk from IC to RF (10 steps)
- Recurse into level 5 through RF (1 step)
- Walk from RF to NM (8 steps)
- Recurse into level 6 through NM (1 step)
- Walk from NM to LP (12 steps)
- Recurse into level 7 through LP (1 step)
- Walk from LP to FD (24 steps)
- Recurse into level 8 through FD (1 step)
- Walk from FD to XQ (8 steps)
- Recurse into level 9 through XQ (1 step)
- Walk from XQ to WB (4 steps)
- Return to level 8 through WB (1 step)
- Walk from WB to ZH (10 steps)
- Return to level 7 through ZH (1 step)
- Walk from ZH to CK (14 steps)
- Return to level 6 through CK (1 step)
- Walk from CK to XF (10 steps)
- Return to level 5 through XF (1 step)
- Walk from XF to OA (14 steps)
- Return to level 4 through OA (1 step)
- Walk from OA to CJ (8 steps)
- Return to level 3 through CJ (1 step)
- Walk from CJ to RE (8 steps)
- Return to level 2 through RE (1 step)
- Walk from RE to XQ (14 steps)
- Return to level 1 through XQ (1 step)
- Walk from XQ to FD (8 steps)
- Return to level 0 through FD (1 step)
- Walk from FD to ZZ (18 steps)
This path takes a total of [1m[97m396[0m steps to move from AA at the outermost layer to ZZ at the outermost
layer.
In your maze, when accounting for recursion, [1m[97mhow many steps does it take to get from the open tile
marked AA to the open tile marked ZZ, both at the outermost layer?[0m
|
