Here comes the new chapter of the tale brought to us by Vladimir V. Zelevinsky - thanks a lot!
"Something is not right," says the adjunct archeologist Alabama Adams.
"Something is not right," says Alabama Adams.
"Huh?" says Alabama.
"Huh?" says her reflection.
"Aaaaaa!" yell Alabama and her reflection at the same time.
Welcome to the latest episode of "The Amazing Adventures of Alabama Adams, the Adjunct Archeologist (AAAAAA)!"
All she wants to do is to return a priceless relic, the Mirror of Ror Rim, to its owner, the learned sage Ezam Ror Rim. The sage, however, is not an easy person to visit, due to the fact that his tower is located in the center of the infamous Mirror Maze.
"I wonder why they call it the Mirror Maze," wonders Alabama as she approaches the labyrinth. "The walls are regular walls. I don't see any reflective surfaces whatsoever."
Then she steps inside.
And then she hears her own voice from the opposite end of the maze.
"This will be a challenge," she sighs.
Here's what makes this challenging. As soon as you enter the maze from the northwest (upper-left) corner
(the coordinates are 1, 1, if the top left corner is taken to be 0, 0), your reflection enters from the
bottom-right corner. As you walk through the maze, your reflection mirrors your moves: if you move to the South
(S), it moves to the North; your move to the East (E) is reflected by its move to the West; the North (N)
move makes your reflection move South; finally, a West (W) move makes your reflection go East. This means
that your moves and your reflection's moves are symmetric. The challenge lies in the fact that the maze
itself is not.
Running into the wall, however, is not a problem (it's only slightly painful). If you can move but your reflection's opposite move is blocked by a wall, then only you move while the reflection stays where it was. The reverse is also true: if you attempt to move but are blocked while your reflection is not, then just your reflection makes the reverse move. Obviously, the moves where both of you are blocked are a waste of time and should be avoided.
Let's look at a few small examples. In the charts below, # is the wall, A is Alabama, and a is her
reflection. Each move is two chars per turn.
starting position:
###
A
###
a
###
after an `E` move (the reflection goes West):
###
A
###
a
###
If the reflection is blocked, only Alabama moves:
starting position:
###
A
###
a#
###
after a `W` move (the reflection cannot go East):
###
A
###
a#
###
If Alabama is blocked, only the reflection moves:
starting position:
#A# #
### #
# #a#
after an `S` move (Alabama is blocked, but her reflection successfully moves North):
#A#a#
### #
# # #
Alabama and her reflection are allowed to share a location in the maze at any point(s) of their journey or pass through each other:
starting position:
###
A a
###
after an `E` move:
###
a A
###
The goal is to reach the tower located in the center of the maze (X, naturally, marks the spot). Alabama and
her reflection are allowed to reach the tower separately - but the tower doors will only open when both
Alabama and her reflection are there at the same time.
Here's a full sample run (for a tiny 7 by 7 maze). Here, one optimal solution is SENS.
starting position:
#######
#A # #
### # #
# #X #
# # # #
# #a#
#######
move 'S': Alabama is blocked, the reflection moves North
#######
#A # #
### # #
# #X a#
# # # #
# # #
#######
move 'E': both move; the reflection reaches the tower, which remains closed
#######
# A# #
### # #
# #a #
# # # #
# # #
#######
move 'N': Alabama blocked, reflection moves South
#######
# A# #
### # #
# #X #
# # # #
# a# #
#######
move 'S': both reach the tower
#######
# # #
### # #
# #A #
# # # #
# # #
#######
Here's another example (for a 11 by 11 maze):
input data:
###########
# # # #
# ##### # #
# #
##### #####
# # X #
# ### # ###
# # #
# ### #####
# # #
###########
answer:
SEESWSWE
Alabama has the map of the maze (it's your puzzle input). It's much bigger than the examples above:
51 by 51 chars. Alabama starts at 1, 1 (numbering from zero); her reflection starts at 49, 49. Your
response should be a sequence of letters, recording each one of Alabama's moves (whether she succeeds in moving
or not). Time is of the essence: only the shortest possible route will please the sage Ezam. There may be
several different optimal ways to solve a given maze; any one of them will be accepted.