I am hidden in the shortest route through this maze.
Twice, if you know what you're looking for.
More clues to follow (although I'm sure you're unlikely to need them)...
$\begingroup$
$\endgroup$
3
-
2$\begingroup$ shortest route from Start to End I assume, and the numbers represent the 'distance' ? $\endgroup$– AlexSep 17, 2015 at 20:45
-
$\begingroup$ You are correct on both counts $\endgroup$– Dr XorileSep 17, 2015 at 20:49
-
2$\begingroup$ Where's Edsger when I need him... $\endgroup$– Mark PetersSep 17, 2015 at 20:49
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
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:
Now, beginning from Start, there is only one shortest path to End:
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$.
answered Sep 17, 2015 at 20:49
-
$\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$ Sep 17, 2015 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$ Sep 17, 2015 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$ Sep 17, 2015 at 23:25
$\begingroup$
$\endgroup$
1
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):
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.
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:
And so on, until step 10:
And so on, until step 24:
And finally:
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$.
answered Sep 17, 2015 at 22:52
-
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$– BmyGuestJul 23, 2016 at 16:00