9
$\begingroup$

I am hidden in the shortest route through this maze.

Maze - find the shortest route

Twice, if you know what you're looking for.

More clues to follow (although I'm sure you're unlikely to need them)...

$\endgroup$
  • 2
    $\begingroup$ shortest route from Start to End I assume, and the numbers represent the 'distance' ? $\endgroup$ – Alex Sep 17 '15 at 20:45
  • $\begingroup$ You are correct on both counts $\endgroup$ – Dr Xorile Sep 17 '15 at 20:49
  • 2
    $\begingroup$ Where's Edsger when I need him... $\endgroup$ – Mark Peters Sep 17 '15 at 20:49
8
$\begingroup$

Working right to left, we can label each vertex with the length of the shortest path to the End, eliminating edges that are not part of such a path. It is not too hard to find the label for a vertex once we have found the labels for that vertex's neighbors to the right. I ended up with this diagram:

enter image description here

Now, beginning from Start, there is only one shortest path to End:

enter image description here This path uses edge lengths $2$, $7$, $1$, $8$, $2$, $8$, $1$, $8$, $2$. This is the beginning of the decimal expansion the mathematical constant $e\approx 2.71828182\ldots$.

$\endgroup$
  • $\begingroup$ Have you found the second clue that's in the maze? I'm clearly going to have to make this harder next time... $\endgroup$ – Dr Xorile Sep 17 '15 at 20:52
  • $\begingroup$ If there were another horizontal line off to the left, it would be even more awesome because it would almost form the shape of Wonder Woman's "W" logo. $\endgroup$ – Kingrames Sep 17 '15 at 23:05
  • 2
    $\begingroup$ @Kingrames, there is a line to the left, but since the length of it must be zero, you just can't see it. :) $\endgroup$ – James Webster Sep 17 '15 at 23:25
2
$\begingroup$

A common way to solve a maze like this is with dijkstra's algorithm. If you print out the maze, you can solve it with pen and paper in a few minutes

You start by marking all the nodes as infinite (inf in the diagrams). Then go to the first point and mark it as 0. Then fill in the distances to the adjacent nodes and mark the first node as visited (red in the below):

Dijkstra-step 1

Then you go to the unvisited node (green in the diagram) with the smallest distance on it, and repeat the same steps as before: you consider the distance to the adjacent unvisited nodes, and mark those with the total distance (if it's smaller than whatever distance is there already). In this case, $6(=2+4)$ and $9(=2+7)$ are both less than infinity, so in they go.

Dijkstra-step 2

Repeating, the smallest unvisited node is now the one labelled $5$. $5+5=10>9$, so the $9$ stays. But $5+8=13<\infty$, so we change that one to 13:

Dijkstra-step 3

And so on, until step 10:

Dijkstra-step 10

And so on, until step 24:

Dijkstra-step 24

And finally:

Dijkstra-step 25

This yields the length of the smallest path. However, you can figure out what the path was, by working backwards from the 39, and choosing edges which, when subtracted give the number in the node. For example, $39-6=33\neq 34$ so that's not the path, $39-2=37$ so that is a path, and $39-5=34\neq 35$ so that's not the path. So the last step of the shortest path is the $2$.

$\endgroup$
  • 1
    $\begingroup$ Thanks for bringing that one up again. I totally missted it the first time around, but like it! Your systematic "guide" is very helpful as well. $\endgroup$ – BmyGuest Jul 23 '16 at 16:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.