It’s A Small World¶
As a popular engineer, you know many people in your home city. While traveling around town, visiting your friends, you realize it would be really handy to have a program that tells you which of your friends are closest based upon which friend you are currently visiting.
Being an engineer who is interested in writing software that is useful to everyone, you decide to write a general solution to your quandary. Each of your friends lives at a unique latitude and longitude. For the purposes of this program, the world is flat, and the latitude and longitude are for all intents and purposes Cartesian coordinates on a flat plane. For example, in our flat world, lat 45, long -179 is not as close to lat 45, long 179 when compared to lat 45, long 170.
Write a program that takes a single argument on the command line. This argument must be a file name which contains the input data. Your program should output the nearest three other friends for each friend in the list. You are virtually a celebrity and your friend list can be astoundingly huge. Your program must exhibit better than quadratic asymptotic growth in runtime as a function of the size of your friend list, and be robust and resource efficient.
Input specifications¶
The input file consists of multiple lines, all of which follow the same format. Each line has three values separated by an amount of white space. The first value is the unique id number of that friend, expressed as an integer. The second value is the latitude of that friend, expressed as a rational number. The third and last value is the longitude of that friend, expressed as a rational number. Every friend lives at a unique combination of latitude and longitude (e.g. no two friends will ever share the exact same values). Each line ends with a single new line, except for the last line of the file, which may or may not have a terminating new line.
Example input file:
1 0.0 0.0
2 10.1 -10.1
3 -12.2 12.2
4 38.3 38.3
5 79.99 179.99
You are guaranteed that your program will run against an input file that is well formed, and has at least four lines. You are also guaranteed that your list of friends have unique distances between one another; no two distinct pairs of friends will have the same distance between them.
Output specifications¶
In the order presented in the input file, output the nearest three friends for each friend. Each line of output should start with the integer id of the friend followed by a single space character, and then the list of three nearest other friend ids followed by a single new line. Even the last line of the output should terminate in a new line. This list should be comma-delimited, with no spaces. The list must be in order of proximity, with the closest of the three being first, and the farthest of the three being last.
Example output:
1 2,3,4
2 1,3,4
3 1,2,4
4 1,2,3
5 4,3,1