1. Computing & Technology
About.com
C / C++ / C#

Discuss in my forum

Programming Challenge 29 - Treasure Hunting

Challenge Completed

By , About.com Guide

See More About:

This programming challenge is finding which treasure hunters are nearest the treasures. You're given two files holding the locations of 10,000 treasure hunters and 250 treasures. You must work out which hunters are within 100 miles of each of the treasures and output a ten closest list of the treasures with the nearest (ie lowest average distance) of hunters from that treasure.

As you are given just latitude and longitude you need to work out the distances on a sphere. There is a simplified algorithm which you must use and documented in the challenge text. Simple Pythagoras is not allowed as it would certainly be faster but is inaccurate; the distance between any two lines of longitude (at the same latitude) increases as you move towards the equator. It starts at 0 at the north pole and increases to about 69 miles per degree at the equator.

NW Latitude = 40.1661, Longitude = -117.6313 NE Latitude = 40.1661, Longitude = -73.8010
SW Latitude = 33.5780, Longitude = -117.6313 SE Latitude = 33.5780, Longitude = -73.8010

The "fastest answer" wins. There treasure hunters scattered across the USA in random locations from latitude 40.1661 in the north to 33.5780 in the south and longitude -117.6313 in the west to -73.8010 in the East. Latitudes run north from the equator so increase as you get further north. Longitudes start at 0 in London, UK; this is called the Greenwich Meridian and go negative as you head west. You are given a file of the 10,000 hunters called hunters.txt with latitude, longitude pairs

40.0001, -80.5090

The file holding a list of 250 random treasure locations in the US is called treasures.txt, again latitude and longitude. Determine the distance of people to their nearest treasure locations using this equation below which comes from Polar Coordinate Flat-Earth Formula. The distance is d below, with a, b and c just steps in the calculation and R = radius of the Earth.

 a = pi/2 - lat1
 b = pi/2 - lat2
 c = sqrt(a^2 + b^2 - 2 * a * b * cos(lon2 - lon1)
 d = R * c
Use R= 3956(miles).Note that trig functions are usually in radians not degrees so you need to convert. 1 radian = 180/pi degrees. Note If a person is more than 100 miles from a treasure then don't count them.

Input Files

Points are randomly generated and may not correspond to easily accessible places in the real world.

The Output

Create an output file distances.txt in the same location as the two input files (and also the same location as your exe) with a list of the 10 ten treasure locations sorted by lowest average distance from treasure hunters. If a location has 10 people within 100 miles of it and their total distances from it add up to 265 then the average distance for that treasure location is 265/10 = 26.5 miles. If this is the lowest average then output it first. However please exclude any treasure that has no hunters within 100 miles of it. Hunters should be counted for all treasures where they are within 100 miles of that treasure.

The distances.txt file should have the ten treasure locations (again 4 dp) and the average distance eg
40.0001, -80.5090, 26.5
72.6579, -95.7865, 26.9
... 40.7654, -100.876, 45.6

and finish of with this line: Average time to calculate once: 2.876 secs. If your code runs under 0.1 seconds please loop it (including time to read input files and write output file) enough times so that running time is in the range 1-10 seconds.

Final Results

A very close result with just 48 ms separating first and second place and the next three all coming in at under 1/10th of a second. Congratulations to Michael Chock and commiserations to Pedro Graca who came a very close second.
  1. Michael Chock - C++ Time(secs) = 0.0358
  2. Pedro Graca (Portugal) - C Time(secs) = 0.0406
  3. James C (Canada) - C# Time(secs) = 0.078307252
  4. Robert Borkowski - C Time(secs) = 0.093
  5. Kovacs Domi (Germany) - C# Time(secs) = 0.096
  6. Kenneth D Weinert (USA) - C Time(secs) = 0.1535
  7. Stole (India) - C++ Time(secs) = 0.156241
  8. Adam Carr (USA, 28) - C# Time(secs) = 0.161
  9. Chris Bregg - C# Time(secs) = 0.1923796
  10. Raymond Tong - C++ Time(secs) = 0.199388
  11. Stuart Highman - C# Time(secs) = 0.248
  12. Mathew Weaver (USA, 39) - C# Time(secs) = 0.33
  13. John Downey (USA, 23) - C# Time(secs) = 0.445

Timing Code

More Programming Challenges

©2012 About.com. All rights reserved.

A part of The New York Times Company.