SPOILER ALERT. This post contains an answer to puzzle 11 Treasure Island from http://gurmeet.net/puzzles which appeared on Hacker News recently. If you want to solve it yourself first, check it out over there before reading on, or just don’t read too far down the page.
The Puzzle
Here is the wording of the puzzle:
An old parchment has directions to a treasure chest buried in an island:
There is an unmarked grave and two tall oak trees. Walk from the grave to the
left tree, counting the number of steps. Upon reaching the left tree, turn left
by 90 degrees and walk the same number of steps. Mark the point with a flag.
Return to the grave. Now, walk towards the right tree, counting the number of
steps. Upon reaching the right tree, turn right by 90 degrees and walk the same
number of steps. Mark this point with another flag. The treasure lies at the
midpoint of the two flags.
A party of sailors reached the island. They find a pair of tall oak trees
merrily swaying in the wind. However, the unmarked grave is nowhere to be
found. They are planning to dig up the entire island. It'll take a month. Can
they do any better?
My high school geometry is a little fuzzy so I thought I’d do a little empirical playing around with d3.js to get a sense of the answer before trying to work out the math. Almost a sort of graphical brute force method. If you’re new to d3.js this should hopefully act as a good introduction as well.
If you want to skip ahead, the full gist is at https://gist.github.com/azundo/5928203 and you can use Mike Bostock’s bl.ocks.org to view it at http://bl.ocks.org/azundo/5928203.
Brute Forcing
Set up
We’ll start with a little bit of d3 boilerplate to set things up. There are a
few g
elements to get our layers working properly but hopefully the comments
in the code make things clear.
1 2 3 4 5 6 7 8 9 10 |
|
Next lets set up some parameters for our treasure island.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
Plotting the Static Features
Now we’re ready to plot the static component of our map - the island and the trees.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
|
If we fire this code up you’ll see the following:
Looking good. A couple of trees. Time to get plotting our flags and ultimately the treasure chest location.
Adding Flags
The tricky part here is getting the geometry right when calculating the location of the flags for a given location of the grave. By filling in a couple of extra triangles it becomes clear how we can do it. Here’s a quick diagram for the left tree:
Remembering that the y-coordinate values increase downwards on our svg canvas, we can see a couple of equivalent triangles marked by the red, blue and black lines. The black lines are the path our pirate would mark out, the red is the y-difference between the grave and the tree, and and the blue is the x-difference between the grave and the tree. The coordinates of the left flag are then given by:
If we swap the grave and the flag in the above diagram, we can work out the case for the right tree, turning to the right instead of the left:
So we end up with the following function for calculating our flag placements:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
|
We’ll need to dynamically update the positions of these flags so lets create a
draw function and call it. At the same time we’ll draw our grave in as well as
the triangles that show the walking directions for illustrative purposes. Check
out the final version of the code to
see the full getPathPoints
function.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
|
We’re getting somewhere. Now lets connect our mouse position to the grave position and watch our flags dance around.
Making the Flags Move
1 2 3 4 5 6 7 8 9 |
|
Can you guess the answer to the riddle yet? Let’s add a calculation of the flags’ midpoint and plot our treasure chest on the map.
The Chest
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
|
Success! We’ve now got a clear answer - there’s only a single location where the chest could be. If you play around with the grave position it becomes obvious that the chest’s x-coordinate is the midpoint of the two trees’ x-coordinates and the y coordinate is simply that same midpoint distance added to the y-coordinate of the trees. Here we’re assuming the trees are at the same y-coordinate and remember that y increases in the downward direction on our screen. (The y-coordinate assumption is ok because we could always redraw our coordinate system so that the two trees are level in the y direction.)
The Math
Now that we’ve played around with getting the example to work and seen that it is a single point solution (not a line or other area function) we can take a more informed approach to the math.
The X-coordinate
We’ll use the trick that our x and y coordinates are independent. Lets work in the x-direction first. We know our final x-coordinate is the average of our two flags’ x-coordinates. Lets start with the left tree’s flag. Here we use as the left tree’s x-coordinate, as the left flag’s x-coordinate, as the grave’s x-coordinate and (since X marks the spot) as the chest’s x-coordinate. Going back to our earlier formulas:
Averaging these two we can see that our $g_{y}$ term cancels out.
In our case where we get as the average of and , not dependent on the graveyard location, as we saw in our brute force method.
The Y-coordinate
Now we can do the same for the y-coordinate.
In the case where then , the result we saw earlier in the brute force method.
One More Thing
We actually don’t have it quite right yet, there is an omission. In the cases where the grave lies above the trees (from our vantage point looking down at the map of the island) the left and right trees are actually reversed. Here’s the final implementation accounting for this possibility. Check out the gist at https://gist.github.com/azundo/5928203 for the full final version.
Conclusion
So that’s it. A quick prototype in D3 to brute force our solution so we’ve got some intution on how to go about solving the geometry. Great practice in getting simple things done using d3.js and jogging the old geometry proofs portion of the brain.
Attributions
Thanks to the folks over at The Noun Project for their svg icon sets. Here are the attributions: