Эрни и Пираты Карибского моря
Несколько недель назад я зашел к Эрни, чтобы спросить, готов ли он ухаживать за кошкой, когда я был в отпуске в Карибском бассейне. «Нет проблем», - ответил он, затем показал мне старую книгу, покрытую кожей: «Но вот интересное совпадение. Вчера я убирал чердак у тети Бисмаркии, и я нашел дневник, написанный моим великим великим великим великим великим великим великим великим дядей Эрнестом. Он встретился с пиратами и сделал семейное счастье в Карибском море », и начал читать из разбитой старой книги следующим образом:
*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.
«Вы 3-х, - спросил я, - печально известный« Тройственный трофей Пирата »?« Мы - они », - сказал 1 -« и еще более страшен, чем даже заявляют легенды. Покажите нам, где вы спрятали свой другой жемчуг, или мы будем мучить вас больше всего », - и один пират показал мне жестокий кинжал.
«Не вреди меня», я умолял: «Я нарисую крест на диаграмме». Но они сдержали мою руку. «Ничья не знак, и не говорите, что место для нашей команды - подлецы. Если, возможно, они шпионили карту или подслушивали, они могли бы воспользоваться самими сокровищами перед нами. Тогда мы будем мучить вас больше всего »или
“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”.
«Если это все будет правдой», сказал я, «тогда сокровище принадлежит вам.
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.
«Еще больше совпадения», - ответил я в волнении. «Курорт находится на месте, называемом Square Island, всего в нескольких сотнях километров от побережья Ямайки. Считаете ли вы, что это может быть одно и то же место - и разве жемчужины все еще могут быть спрятаны там? »(G 8). Дядя Эрнест никогда не предоставлял широту или долготу, поэтому, я думаю, мы никогда не сможем сказать», - ответил Эрни. «Но пока вы в отпуске, вы всегда можете посмотреть и посмотреть». И он передал мне оригинальную ручную диаграмму Эрнеста.
Честно говоря, Эрни не считает, что у него много шансов - он даже не уверен, что он действительно верит в старую историю - поэтому он не хотел «юморить меня», если в дневнике есть достаточная информация для поиска жемчуг. Итак, вот сделка - если кто-нибудь может подтвердить, где искать, и я нахожу кеш Earnest, я обещаю вам получить равную долю прибыли с Эрни и мной!
Чтобы решить эту проблему, я использовал комбинацию алгоритма заполнения заливки и алгоритм Дейкстры .
Я установил большую карту ячеек по карте. Каждая ячейка запоминает свое текущее расстояние и его «последний источник». Начальная ячейка (местоположение судна) начинается с нулевого расстояния, а источник равен самому себе. Все остальные ячейки неинициализированы.
Алгоритм отслеживает список ячеек с приоритетной очередью . Каждая итерация исследует ячейку в очереди с наименьшим расстоянием. Он проверяет, находится ли ранее посещаемый источник ячейки в том же регионе, что и текущая ячейка, и имеет «прямую видимость» текущей ячейки (т. Е. Прямой путь между текущей ячейкой и предыдущей ячейкой источника не проходят через любые другие регионы). Если это так, источник текущей ячейки установлен на предыдущий источник, в противном случае источник текущей ячейки устанавливается на ранее посещенную ячейку.
Расстояние текущей ячейки затем рассчитывается как расстояние от источника ячейки, плюс евклидово расстояние от источника до текущей ячейки, деленное на скорость пирата над текущим рельефом. Если это расстояние меньше расстояния текущей ячейки, расстояние и источник текущей ячейки обновляются, и все ее соседи добавляются в очередь приоритетов.
Запуск этого алгоритма с тремя скоростями пирата ( как указано Джо Z. ) приводит к следующим трем графикам контуров расстояния :
Если я беру максимальную разницу между расстояниями в каждой точке, я получаю следующее:
Есть три разные точки кандидата, если мы игнорируем сам корабль. Один находится на западном берегу острова. Второй находится в воде к востоку от острова. Наконец, есть один в воде к северо-востоку от острова.
Теперь, поскольку используемый мною алгоритм отслеживает «исходную» ячейку для каждого расчета расстояния, мы можем показать пути, которые каждый пират использовал для достижения каждой точки (пути красные, зеленые и синие для первого, второго и третий пират, соответственно):
Я полагаю, из-за строки из дневника:
[жемчужина] скрыта с великой хитростью в некоторых лигах к востоку отсюда
То, что фактическое местоположение находится на восточном побережье острова. Зная примерно кратчайшие пути для каждого пирата, решение становится утомительной проблемой оптимизации в нескольких переменных. Решение системы уравнений дает оранжевую точку на приведенной выше диаграмме, которая расположена:
4.068527 лиг на восток и 5.250636 лиг к северу от юго-восточного угла острова.
Кроме того, если вы хотите найти и северо-восточную точку, она находится:
3.507273 лиги на восток и 2.329233 лиги к северу от северо-восточного угла острова.
Наконец, пункты (два!) Кандидата на западном берегу расположены:
0.503264 лиги внутри страны, 2.267151 лиги к северу и югу от корабля.
Bonus
Вот анимация «кругов доступности», упомянутых в ответе Джо З.:
Частичное решение для сбора информации:
Существенными частями этой головоломки являются просто скорости, с которыми каждый пират может пересекать каждый тип местности, который может быть представлен в таблице:
\begin{array}{c|c|c|c} & \text{Water} & \text{Swamp} & \text{Jungle}\\ \hline \text{Pirate 1} & 12 & 3 & 6\\ \hline \text{Pirate 2} & 7 & 14 & 3.5\\ \hline \text{Pirate 3} & 9.5 & 4.75 & 19\\ \end{array}
И проблема состоит в том, чтобы найти точку, где оптимальные пути для каждой из этих скоростей являются точно такими же расстоянием.
Один из способов, который я могу придумать, - это моделировать проблему как «круги доступности», которые растут с разной скоростью, в зависимости от скорости каждого пирата, и ответ заключается в том, где три круга пересекаются в одной точке.
Жемчуг:
Внутри (поддельный) большой жемчуг.
Если предположить,
It's an extremely large (and therefore fake) pearl. Regardless of the pirates' ability (or inefficiency) to traverse water, swamp and jungle, they traverse the decks of the pirate ship at exactly the same rate. They could run to the pearl (which is on the eastern side of the ship) in equal time, but they thought that the pearls were buried on the island. The pirate ship "was mortal damaged & did sink thereafter," so a little scuba diving on the "X" on the map would find the wreckage of the ship, the fake Large Pearl and the pearly treasures inside!
Жемчужина
В верхней строке пересечений 5-го пересечения справа или 11-го пересечения слева, если вы предпочитаете.
аргументация
Я включил возможный путь каждого пирата в таблицу Excel (я сопоставил пересечения лиг) и нашел место, где они наименее отличались.
Here are the maps for each pirate. [Water Pirate] [Swamp Pirate] [Jungle Pirate]
Я не наметил их фактические пути, но я могу сделать это по запросу.
![[Water Pirate]](https://i.stack.imgur.com/Z2Gmd.png){kind=link}
![[Swamp Pirate]](https://i.stack.imgur.com/ZDZXQ.png){kind=link}
![[Jungle Pirate]](https://i.stack.imgur.com/T5k77.png){kind=link}