part1 (3683B)
1--- Day 20: Donut Maze --- 2 3You notice a strange pattern on the surface of Pluto and land nearby to get a closer look. Upon 4closer inspection, you realize you've come across one of the famous space-warping mazes of the 5long-lost Pluto civilization! 6 7Because there isn't much space on Pluto, the civilization that used to live here thrived by 8inventing a method for folding spacetime. Although the technology is no longer understood, mazes 9like this one provide a small glimpse into the daily life of an ancient Pluto citizen. 10 11This maze is shaped like a donut. Portals along the inner and outer edge of the donut can instantly 12teleport you from one side to the other. For example: 13 14 A 15 A 16 #######.######### 17 #######.........# 18 #######.#######.# 19 #######.#######.# 20 #######.#######.# 21 ##### B ###.# 22BC...## C ###.# 23 ##.## ###.# 24 ##...DE F ###.# 25 ##### G ###.# 26 #########.#####.# 27DE..#######...###.# 28 #.#########.###.# 29FG..#########.....# 30 ###########.##### 31 Z 32 Z 33 34This map of the maze shows solid walls (#) and open passages (.). Every maze on Pluto has a start 35(the open tile next to AA) and an end (the open tile next to ZZ). Mazes on Pluto also have portals; 36this maze has three pairs of portals: BC, DE, and FG. When on an open tile next to one of these 37labels, a single step can take you to the other tile with the same label. (You can only walk on . 38tiles; labels and empty space are not traversable.) 39 40One path through the maze doesn't require any portals. Starting at AA, you could go down 1, right 418, down 12, left 4, and down 1 to reach ZZ, a total of 26 steps. 42 43However, there is a shorter path: You could walk from AA to the inner BC portal (4 steps), warp to 44the outer BC portal (1 step), walk to the inner DE (6 steps), warp to the outer DE (1 step), walk to 45the outer FG (4 steps), warp to the inner FG (1 step), and finally walk to ZZ (6 steps). In total, 46this is only [1m[97m23[0m steps. 47 48Here is a larger example: 49 50 A 51 A 52 #################.############# 53 #.#...#...................#.#.# 54 #.#.#.###.###.###.#########.#.# 55 #.#.#.......#...#.....#.#.#...# 56 #.#########.###.#####.#.#.###.# 57 #.............#.#.....#.......# 58 ###.###########.###.#####.#.#.# 59 #.....# A C #.#.#.# 60 ####### S P #####.# 61 #.#...# #......VT 62 #.#.#.# #.##### 63 #...#.# YN....#.# 64 #.###.# #####.# 65DI....#.# #.....# 66 #####.# #.###.# 67ZZ......# QG....#..AS 68 ###.### ####### 69JO..#.#.# #.....# 70 #.#.#.# ###.#.# 71 #...#..DI BU....#..LF 72 #####.# #.##### 73YN......# VT..#....QG 74 #.###.# #.###.# 75 #.#...# #.....# 76 ###.### J L J #.#.### 77 #.....# O F P #.#...# 78 #.###.#####.#.#####.#####.###.# 79 #...#.#.#...#.....#.....#.#...# 80 #.#####.###.###.#.#.#########.# 81 #...#.#.....#...#.#.#.#.....#.# 82 #.###.#####.###.###.#.#.####### 83 #.#.........#...#.............# 84 #########.###.###.############# 85 B J C 86 U P P 87 88Here, AA has no direct path to ZZ, but it does connect to AS and CP. By passing through AS, QG, BU, 89and JO, you can reach ZZ in [1m[97m58[0m steps. 90 91In your maze, [1m[97mhow many steps does it take to get from the open tile marked AA to the open tile 92marked ZZ?[0m 93 94