Maze
by Derek Kisman
Answer: NINEPIN


The first instinct you should have, of course, is to explore the maze.
You shouldn't have much difficulty navigating deeper, but it will
quickly become clear that the sucker is BIG.  Also, the fact that
steps are counted at the bottom of the applet, beside an encoded
message, strongly implies that you need to determine the (shortest)
distance through the maze.  The message encoded by this shortest
distance will be the desired word.  So, hopefully it's possible to
figure this value out without actually traversing the maze!

The message encoding is a pretty easy thing to figure out.  The number
of steps taken is simply written out in base 9, with the digits
012345678 replaced by the letters AEILNPRSW (from the Meta puzzle,
incidentally).  It should be no problem figuring out what word
corresponds to the distance, once you've calculated it.

Of course, figuring the distance out, without specifically solving the
maze, requires discerning its global structure.  One thing is obvious:
it's divided into 9x9 tiles, with inter-tile connections only in the
middle of each wall.  Explore a little and you'll quickly discover
that these tiles repeat often; if you map them out, you'll find that
there are exactly 15 types, one for each possible set of external
exits.

Now that you know that, mapping one "level" up seems reasonable,
compressing a 9x9 tile into one square using its exits, which still
preserves the larger shape of the maze.  We'll call this the
second-level map.  If you do this, you'll notice that this
second-level map has the same 9x9 tiled structure, and the same
component tiles!  However, the second-level tile you start in (NWS,
named for its exits) is different from the first-level tile you start
in (ENW).

If compressing the maze leads to a similar-structured maze (that is,
it has "fractal" structure), we might expect the same thing to happen
after a second compression.  It's difficult to verify this for sure,
since tiles in the third- level maze are very large.  Also, if the
second-level starting tile is NWS, there are several possibilities for
the third-level starting tile: W, WS, and EWS.  However, some directed
exploration will verify that the second-level tiles to the North,
East, and South are all NS.  This is consistent with a third-level
tile of WSE, so that's a reasonable assumption to make.

What about a fourth-level tile, if it exists?  Since the third level
is WSE, the only fourth-level possibility is NW.  (This is very
fortunate, as exploring any distance into the third-level maze would
take forever!)

And the fifth-level tile, if any?  The only possibility is EW.

Now, there is no tile that has EW at its West edge, so there must be
at most five levels, or fewer, in this maze.  But EW seems like the
most satisfying final structure for the maze, placing the entrance to
the maze directly opposite its exit.  And the logical chain that
forces the fourth- and fifth- level tiles should make it clear that
this is the intended structure.  The maze is in fact 59,049 x 59,049
with a single entrance to the West and a single exit to the East, and
five levels of fractal structure!

Yikes.  No wonder you weren't expected to traverse it.  But, because
of the fractal structure, you CAN calculate the minimum distance
across it with some mathematical work (and possibly a computer
program).  For each tile and desired start/exit from that tile, you
can all describe the tiles traversed along that path.  There are 24
such paths, so you can calculate them - by hand or by computer - and
plug them into a matrix:

                                             E E E E E E
                     E E E N N N W W W S S S N N N N N N
                     N N N W W W S S S E E E W W W W W W
                     W W W S S S E E E N N N S S S S S S
                     ( ( ( ( ( ( ( ( ( ( ( ( ) ) ) ) ) )
                     E E N N N W W W S S S E E E E N N W
         E N E N W S N W W W S S S E E E N N N W S W S S
         W S N W S E ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) )

EW       1 0 2 2 2 2 0 2 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0
NS       1 4 2 4 2 5 1 3 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
EN       2 2 1 3 1 3 0 0 0 1 2 1 0 0 1 0 0 2 0 0 0 0 0 0
NW       1 1 1 0 0 0 1 0 0 1 1 1 0 3 0 0 2 0 0 0 0 0 0 1
WS       2 3 2 4 1 5 1 0 0 2 2 1 2 0 0 1 0 0 0 1 0 0 0 0
SE       1 4 1 2 4 2 2 0 0 1 0 0 0 0 1 0 0 1 0 0 1 0 1 0
ENW(EN)  1 2 2 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1
ENW(EW)  4 3 5 2 3 1 0 1 1 0 0 0 1 1 2 1 2 0 0 0 0 1 0 1
ENW(NW)  3 3 3 2 2 1 0 1 1 0 0 0 1 0 2 0 3 0 0 0 0 1 0 0
NWS(NW)  1 0 0 0 0 1 0 1 2 1 0 0 0 0 1 0 2 0 0 0 0 0 0 0
NWS(NS)  3 0 2 1 3 2 0 0 2 1 0 0 0 1 1 1 2 1 0 1 0 0 0 0
NWS(WS)  2 0 2 1 3 1 0 1 0 2 0 0 0 1 0 2 1 0 0 1 0 0 0 0
WSE(WS)  2 5 2 1 1 2 0 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 1 1
WSE(WE)  3 9 3 2 1 3 0 0 0 1 1 1 1 0 1 0 1 0 0 1 0 1 0 0
WSE(SE)  1 4 1 1 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 2 0
SEN(SE)  1 1 0 1 0 1 0 0 1 0 1 0 0 0 0 2 0 0 0 1 0 0 0 0
SEN(SN)  3 4 2 2 1 4 0 0 2 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0
SEN(EN)  4 3 2 3 1 3 0 0 1 1 1 0 0 1 0 2 0 0 0 1 0 0 0 0
ENWS(EN) 0 4 2 4 3 2 1 1 0 0 0 0 0 1 1 1 1 0 1 1 0 0 0 0
ENWS(EW) 4 4 4 6 5 3 1 2 0 0 0 0 0 2 2 1 1 0 0 2 0 0 0 0
ENWS(ES) 0 1 2 2 2 1 0 1 0 0 0 0 0 0 1 1 1 0 0 1 0 0 0 0
ENWS(NW) 4 0 2 2 2 1 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0
ENWS(NS) 0 5 0 2 1 1 1 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0
ENWS(WS) 4 5 2 4 3 2 1 1 0 0 0 0 1 1 2 0 0 0 0 1 0 0 0 0

For instance, going from W to E or E to W in the WE tile involves
crossing 1 EW, 2 EN, 2 NW, 2 WS, 2 SE, 2 ENW (between E and W), 1 WSE
(between E and W), and 1 ENWS (between E and W).  The sum of the EW
row gives the distance across a one-level EW maze.  If we SQUARE the
matrix, then we get the number of tiles crossed when traversing a
level-two tile; so the sum of the EW row gives the distance across a
two-level EW maze.  Thus, to find the final distance across the maze,
we take the FIFTH power of the matrix, and sum the EW row.  (We also
need to add 1, since we use an extra move to exit to the final green
square) Whew!

This gives us the number 2271262, the least number of steps we can use
to exit on the far side of the maze.  Written in base 9, this is
4241524, so the final answer is NINEPIN.  An answer with NINE in it is
apt: the maze dimensions are always powers of 9, and the message is
encoded in base 9...