CareerCup

if distance is the only thing we always want and we go with precomputed way.

lets say planets are abc and xyz(even god wont name the planets same :))
find a string abcxyz(i.e. concatenate both planet names) and store it as a key in hash table and distance as value.

Since its gonna be a huge hash table, we can have distributed hash table across n machines and deal with network latency.

Note: While concatenation always using Lexicographical smaller string first and larger string next, so that we don`t double the size of already huge hash table

We can make a graph while edges represent the distance between two planets.

Comment??

I would create a tree like structure by partitioning the galaxy into blocks, then those blocks into blocks, etc. while finally storing the planet at the lowest level. For instance, block knows the VECTOR to all of the other blocks in it's level. Then to find the distance from Planet A to Planet B, you first get the vector from Planet A to Planet A's parent, then sum the vectors from Planet A's parent up until the top level, then to Planet B's toplevel, down to planet B. Eventually you will be left with a vector from A to B, and the magnitude is the distance.

http://en.wikipedia.org/wiki/Closest_pair_of_points_problem

how about a 2-D array... But in this there will be 2x use of memory. Since it will be a symmetric array. So we can do a single 1-D array.. Lets assume that the planets are numbered.. So the index of planet number n will be n(n-1)/2 in the array.. and the next n elements will be distance of nth planet from all other planets.. This way we can reduce the memory usage to 1x.

1] project all the location from a 3-d to a 2-d plane.
2] Now consider one of the planet as the origin. Lets say earth :)
3] Store X and Y co-ordinate of each planet wrt to Origin. An array of structure.
struct Planet
{ char* name;
double x, y;
}
4] Use distance formula to calculate distance between any planets.

Opinions ?

struct planet {
planet_name;
double x, double y
}

vector: to store Planet type pointers
Hash Table: Key->value ==== planet_name -> index in vector
Algo:
1) Get planet_names;
2) lookup in hash and find index i and j resp for both planets
3) calculate distance simply using a simple mathematical formula.

you should use r* trees for spatial structures