A few weeks ago, I dropped in to see Ernie to ask if he was willing to look after the cat while I was on holiday in the Caribbean. “No problem.” he replied then showed me an old leather-covered book, “But here’s an interesting coincidence. I was cleaning out the attic at Aunt Bismarkia’s place yesterday, and I found a diary written by my great-great-great-great-great-great-great-great-uncle Earnest. He met up with pirates and made the family fortune in the Caribbean.”, and began to read from the tattered old book as follows:
*Jan 13th 1769 uncharted in t’ Caribbean sea : Shipwreck’d & cast up on this desolat shore. But I have found sweet water, fruit &c. ‘tho the wild creaturs are fereful. & also I have made a shelter from the tempest.
Jan 23rd Sqare Isle : I have map’d the island & drawn a chart o’ it. It is 10 leagues exact on a side. Naming it Square Isle due to it’s particul’r shape & built a fine signal pyre betwixt beach and forest in hopes its smoke & flame &c. will bring rescuers.
Feb 1st Sqare Isle: In the reef to th’ north there are many oysters. To th’ most-part every shell hides a pearl of great beutie and size – I have hidd’n all but the largest 1 of them for fear of pyrates. The largest I wear on a string ‘bout my neck in the fashion of a savage.
Feb 14th Sqare Isle: A sail – I must hasten to light the signal fire...
3 year later after I find this diarie again: As the ship stopp’d I spied a black flag upon the main-mast – it was crew’d by pyrates. They took my pearl and my map (but showed no interest in my diary, pen &c.). & dragg’d me to the Cap’ns cabin, bound at wrist, where there were 3 pyrates most sanguinolent of aspect and each identical to the others.
“Are you 3”, I asked, “the infamous Dread Pyrate Triplets?” “We are they” – spoke 1 – “and more dread than even the legends claim. Shew us where you have hidden your other pearls or we will torture you most ‘orribly!” – and one pyrate shew’d me a cruel dagger.
“Do not harm me”, I implored, “I shall draw a cross on the chart forthwith”. But they held back my hand. “Draw not a mark, nor speak the location for our crew are scoundrels all. If perchance they spied the map or overhear they might avail theyselves of the treasure a’fore us. Then we would torture you most ‘orribly!”
“Do not harm me”, I implored again, “for I can whisper the location in your ear – each in turn”. But they stayed me to my chair. “Seal your lips. For each of us has no trust for his brothers & if the 1st to hear could avail themself of the treasure a’fore the others he would perchance take all. And the 2nd and 3rd would torture you most ‘orribly”.
“Do not harm me” I cried, “but answer these questions 3.
Show me 1st where the ship is harb’r’d” And they drew a rude cross on the chart signifying the anchorage.
“And you all are navigateurs?” I asked. And they replied “Navigateurs most skilled, but the crew have not this skill”.
*“Then tell me true – you are alike in visage and physiognomy, but is there any difference measurable betwixt you?“ * And the first replied “I swims at 12 leagues to the hour, but am only ½ as fast in jungle and ¼ as fast on swamp land.” And the second replied “Whereas I wades at 14 leagues in the hour on swamp land but am only ½ as fast in water and ¼ as fast in jungle”. And the third replied “And I sneaks through jungle at 19 leagues in the hour but am only ½ as fast in water and ¼ as fast on swamp land”.
“If that all be true”, said I “then the treasure is yours to share.
For it is sunken 3 fathoms down with great cunning some leagues to the ENE of here, but if each and every one o’ you departs from this very point at the same turn o’ the hour-glass, & each and every one o’ you takes his own best & fastest course using only the means given to your body by God, then each and every one o’ you will arrive at the treasure together – & not a pace will separate the 3 of you & not a heart-beat will pass between the first & the last to arrive”. But I warn’d them not of the great sharks & poisn snakes & sentipiedes & other divers creaturs that lurk’d in the sea, swamp, and jungle.
And the Dread Brothers arose as 1 & left in great haste. And I heard 3 splashes as 1, as the Dread Brothers threw themselves in the water to begin swimming to their goal – as each fear’d the others might get to the treasure 1st and take it all. In their awful haste they left the dagger and the 1 pearl on the table so I cut my bonds hencewith and took up my pearl & hid below decks in the bilges where the crew could not spy me. But less than 1 hour pass’d and there was a suddenlike cry and commotion & the sound of great guns and the ship gave a shaking & rending &c. most awful. I was in fear of my life & left my noisome hiding place and reach’d the fore-deck to spy the a 2-decker flying the Kings flag alongside with guns blazing, & the pyrate crew tore down their flag in surrender & the guns were silenced tho’ the pyrate ship was mortal damaged & did sink thereafter. The crew was clapp’t in irons but of the 3 Dread Brothers who had not returned from their mission nothing was found of them ever – mayhaps they were consum’d by the wild beasts a’fore reaching the treasure or whilst maroon’d. Perchance, I knew the Cap’n of HMS Blenheim from my time in Portsmouth so I was free’d. I ask’d time to recover my treasure but the Cap’n said we must sail as there was a g’t storm on the horizon – but I w’d be reward’d by the Crown as t’was my signal pyre that allowed capture of the pyrate band. And his word was good & I was rewarded 200 sovereign by HM Governor in Freeport and 100 more by Viscount Cranborne for my 1 last pearl. Thus I made my fortune.
“Even more of a coincidence”, I replied in excitement. “The resort is on a place called Square Island, just a couple of hundred km off the coast of Jamaica. Do you think it could be the same place – and could the pearls still be hidden there?” “(G^8)Uncle Earnest never provided a latitude or longitude so I guess we can never tell”, Ernie replied. “But while you are on holiday, you could always have a look and see”. And he passed me Earnest's original hand-drawn chart.
To be honest, Ernie doesn’t think there is much chance – he isn’t even sure he really believes the old tale – so he didn’t want to “humour me” working out if there is sufficient information in the diary to locate the pearls. So here is the deal – if anyone can confirm where to look, and I do find Earnest's cache – I promise to let you in on an equal share of the profits with Ernie and me!
Answer
In order to solve this problem, I used a combination of a flood-fill algorithm and Dijkstra's algorithm.
I set up a large grid of cells over the map. Each cell remembers its current distance and its "last source." The initial cell (the location of the ship) starts with zero distance, and source equal to itself. All other cells are uninitialized.
The algorithm keeps track of a list of cells with a priority queue. Each iteration it examines the cell in the queue with the smallest distance. It checks to see if the previously visited cell's source is both in the same region as the current cell, and has "line-of-sight" to the current cell (i.e. the straight-line path between current cell and previous source cell does not pass through any other regions). If is the case, the current cell's source is set to the previous source, otherwise the current cell's source is set to the previously visited cell.
The distance of the current cell is then calculated as the distance of the cell's source, plus the Euclidean distance from the source to the current cell divided by the pirate's speed over the current terrain. If this distance is less than the current cell's distance, the current cell's distance and source are updated and all its neighbors are added to the priority queue.
Running this algorithm with the three pirate's speeds (as given by Joe Z.) results in the following three distance contour plots:
If I take the maximum difference between distances at each point, I then obtain the following:
There are three different candidate points, if we ignore the ship itself. One is located on the west shore of the island. The second is in the water to the east of the island. Finally, there is one in the water to the northeast of the island.
Now because the algorithm I used keeps track of the "source" cell for each distance calculation, we can show the paths that each pirate used to arrive at each point (the paths are red, green, and blue for the first, second, and third pirate, respectively):
I assume, due to the line from the diary:
[the pearl] is hidden with great cunning some leagues to the East of here
That the actual location is the one off the east shore of the island. Knowing roughly the shortest paths for each pirate, the solution becomes a tedious optimization problem in a few variables. Solving the system of equations yields the orange point in the above diagram, which is located:
4.068527 leagues east and 5.250636 leagues north of the south-east corner of the island.
Alternatively, if you want to search the north-east point as well, it's located:
3.507273 leagues east and 2.329233 leagues north of the north-east corner of the island.
Finally, the (two!) candidate points on the west shore are located:
0.503264 leagues inland, 2.267151 leagues north and south of the ship.
Bonus
Here is an animation of the "circles of accessibility" mentioned in Joe Z.'s answer:
No comments:
Post a Comment