part2 (6035B)
1--- Part Two --- 2 3Strangely, the exit isn't open when you reach it. Then, you remember: the ancient Plutonians were 4famous for building [1m[97mrecursive spaces[0m. 5 6The marked connections in the maze aren't portals: they [1m[97mphysically connect[0m to a larger or smaller 7copy of the maze. Specifically, the labeled tiles around the inside edge actually connect to a 8smaller copy of the same maze, and the smaller copy's inner labeled tiles connect to yet a 9[1m[97msmaller[0m copy, and so on. 10 11When you enter the maze, you are at the outermost level; when at the outermost level, only the outer 12labels AA and ZZ function (as the start and end, respectively); all other outer labeled tiles are 13effectively walls. At any other level, AA and ZZ count as walls, but the other outer labeled tiles 14bring you one level outward. 15 16Your goal is to find a path through the maze that brings you back to ZZ at the outermost level of 17the maze. 18 19In the first example above, the shortest path is now the loop around the right side. If the starting 20level is 0, then taking the previously-shortest path would pass through BC (to level 1), DE (to 21level 2), and FG (back to level 1). Because this is not the outermost level, ZZ is a wall, and the 22only option is to go back around to BC, which would only send you even deeper into the recursive 23maze. 24 25In the second example above, there is no path that brings you to ZZ at the outermost level. 26 27Here is a more interesting example: 28 29 Z L X W C 30 Z P Q B K 31 ###########.#.#.#.#######.############### 32 #...#.......#.#.......#.#.......#.#.#...# 33 ###.#.#.#.#.#.#.#.###.#.#.#######.#.#.### 34 #.#...#.#.#...#.#.#...#...#...#.#.......# 35 #.###.#######.###.###.#.###.###.#.####### 36 #...#.......#.#...#...#.............#...# 37 #.#########.#######.#.#######.#######.### 38 #...#.# F R I Z #.#.#.# 39 #.###.# D E C H #.#.#.# 40 #.#...# #...#.# 41 #.###.# #.###.# 42 #.#....OA WB..#.#..ZH 43 #.###.# #.#.#.# 44CJ......# #.....# 45 ####### ####### 46 #.#....CK #......IC 47 #.###.# #.###.# 48 #.....# #...#.# 49 ###.### #.#.#.# 50XF....#.# RF..#.#.# 51 #####.# ####### 52 #......CJ NM..#...# 53 ###.#.# #.###.# 54RE....#.# #......RF 55 ###.### X X L #.#.#.# 56 #.....# F Q P #.#.#.# 57 ###.###########.###.#######.#########.### 58 #.....#...#.....#.......#...#.....#.#...# 59 #####.#.###.#######.#######.###.###.#.#.# 60 #.......#.......#.#.#.#.#...#...#...#.#.# 61 #####.###.#####.#.#.#.#.###.###.#.###.### 62 #.......#.....#.#...#...............#...# 63 #############.#.#.###.################### 64 A O F N 65 A A D M 66 67One shortest path through the maze is the following: 68 69 70 - Walk from AA to XF (16 steps) 71 72 - Recurse into level 1 through XF (1 step) 73 74 - Walk from XF to CK (10 steps) 75 76 - Recurse into level 2 through CK (1 step) 77 78 - Walk from CK to ZH (14 steps) 79 80 - Recurse into level 3 through ZH (1 step) 81 82 - Walk from ZH to WB (10 steps) 83 84 - Recurse into level 4 through WB (1 step) 85 86 - Walk from WB to IC (10 steps) 87 88 - Recurse into level 5 through IC (1 step) 89 90 - Walk from IC to RF (10 steps) 91 92 - Recurse into level 6 through RF (1 step) 93 94 - Walk from RF to NM (8 steps) 95 96 - Recurse into level 7 through NM (1 step) 97 98 - Walk from NM to LP (12 steps) 99 100 - Recurse into level 8 through LP (1 step) 101 102 - Walk from LP to FD (24 steps) 103 104 - Recurse into level 9 through FD (1 step) 105 106 - Walk from FD to XQ (8 steps) 107 108 - Recurse into level 10 through XQ (1 step) 109 110 - Walk from XQ to WB (4 steps) 111 112 - Return to level 9 through WB (1 step) 113 114 - Walk from WB to ZH (10 steps) 115 116 - Return to level 8 through ZH (1 step) 117 118 - Walk from ZH to CK (14 steps) 119 120 - Return to level 7 through CK (1 step) 121 122 - Walk from CK to XF (10 steps) 123 124 - Return to level 6 through XF (1 step) 125 126 - Walk from XF to OA (14 steps) 127 128 - Return to level 5 through OA (1 step) 129 130 - Walk from OA to CJ (8 steps) 131 132 - Return to level 4 through CJ (1 step) 133 134 - Walk from CJ to RE (8 steps) 135 136 - Return to level 3 through RE (1 step) 137 138 - Walk from RE to IC (4 steps) 139 140 - Recurse into level 4 through IC (1 step) 141 142 - Walk from IC to RF (10 steps) 143 144 - Recurse into level 5 through RF (1 step) 145 146 - Walk from RF to NM (8 steps) 147 148 - Recurse into level 6 through NM (1 step) 149 150 - Walk from NM to LP (12 steps) 151 152 - Recurse into level 7 through LP (1 step) 153 154 - Walk from LP to FD (24 steps) 155 156 - Recurse into level 8 through FD (1 step) 157 158 - Walk from FD to XQ (8 steps) 159 160 - Recurse into level 9 through XQ (1 step) 161 162 - Walk from XQ to WB (4 steps) 163 164 - Return to level 8 through WB (1 step) 165 166 - Walk from WB to ZH (10 steps) 167 168 - Return to level 7 through ZH (1 step) 169 170 - Walk from ZH to CK (14 steps) 171 172 - Return to level 6 through CK (1 step) 173 174 - Walk from CK to XF (10 steps) 175 176 - Return to level 5 through XF (1 step) 177 178 - Walk from XF to OA (14 steps) 179 180 - Return to level 4 through OA (1 step) 181 182 - Walk from OA to CJ (8 steps) 183 184 - Return to level 3 through CJ (1 step) 185 186 - Walk from CJ to RE (8 steps) 187 188 - Return to level 2 through RE (1 step) 189 190 - Walk from RE to XQ (14 steps) 191 192 - Return to level 1 through XQ (1 step) 193 194 - Walk from XQ to FD (8 steps) 195 196 - Return to level 0 through FD (1 step) 197 198 - Walk from FD to ZZ (18 steps) 199 200 201This path takes a total of [1m[97m396[0m steps to move from AA at the outermost layer to ZZ at the outermost 202layer. 203 204In your maze, when accounting for recursion, [1m[97mhow many steps does it take to get from the open tile 205marked AA to the open tile marked ZZ, both at the outermost layer?[0m 206 207