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 - lat1Use 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.
b = pi/2 - lat2
c = sqrt(a^2 + b^2 - 2 * a * b * cos(lon2 - lon1)
d = R * c
Input Files
- Download treasures.txt
- Download hunters.txt
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.- Michael Chock - C++ Time(secs) = 0.0358
- Pedro Graca (Portugal) - C Time(secs) = 0.0406
- James C (Canada) - C# Time(secs) = 0.078307252
- Robert Borkowski - C Time(secs) = 0.093
- Kovacs Domi (Germany) - C# Time(secs) = 0.096
- Kenneth D Weinert (USA) - C Time(secs) = 0.1535
- Stole (India) - C++ Time(secs) = 0.156241
- Adam Carr (USA, 28) - C# Time(secs) = 0.161
- Chris Bregg - C# Time(secs) = 0.1923796
- Raymond Tong - C++ Time(secs) = 0.199388
- Stuart Highman - C# Time(secs) = 0.248
- Mathew Weaver (USA, 39) - C# Time(secs) = 0.33
- John Downey (USA, 23) - C# Time(secs) = 0.445
Timing Code
More Programming Challenges
- Link to Rock, Scissors and Paper Bot Ongoing Programming Challenge - Runs weekly.
- Link to Programming Challenge 2 - Count the Islands. (Finished)
- Link to Programming Challenge 3 - Manage Elevators. (Finished)
- Link to Programming Challenge 4 - Guess the Mastermind Code - (Finished)
- Link to Programming Challenge 5 - Squeeze words into a crossword grid - (Finished)
- Link to Programming Challenge 6 - Guess the Mastermind Code - (Finished)
- Link to Programming Challenge 7 - Validate Chess Positions - (Finished)
- Link to Programming Challenge 8 - Score Poker Hands - (Finished)
- Link to Programming Challenge 9 - Manage a Data structure - (Finished)
- Link to Programming Challenge 10 - Hide Text (Finished)
- Link to Programming Challenge 11 - Match Sets of Cards (Finished)
- Link to Programming Challenge 12 - Calculate Shortest Path - Completed)
- Link to Programming Challenge 13 - Play Battleships (Finished)
- Link to Programming Challenge 14 - Multiply Large Numbers(Completed)
- Link to Programming Challenge 15 - Generate a Dungeon (Completed)
- Link to Programming Challenge 16 - Solve 1,000 Sliding Puzzles ( Completed)
- Link to Programming Challenge 17 - Implement Life (Completed)
- Link to Programming Challenge 18 - Generate a Map (Completed)
- Link to Programming Challenge 19 - Fill a grid of tiles (Completed)
- Link to Programming Challenge 20 - Sieve of Erasthotenes (Completed)
- Link to Programming Challenge 21 - Data Preparation (Completed)
- Link to Programming Challenge 22 - Make Hexagons (Completed)
- Link to Programming Challenge 23 - Reassemble Numbered Tiles (Completed)
- Link to Programming Challenge 24 - MineSweeper Redux (Completed)
- Link to Programming Challenge 25 - Count the Ones (Completed)
- Link to Programming Challenge 26 - Text Processing(Completed)
- Link to Programming Challenge 27 - Pack them in (Completed)
- Link to Programming Challenge 28 - An Optimization Problem (Completed)
