3
\$\begingroup\$

Your mission, should you choose to accept it, is to write code for a GPS receiver.

Input

  • The current time, as nanoseconds from the Unix epoch. [EDIT: This is optional, please state whether you require it]
  • Four satellite signals, in the following format:
    • The time the signal was sent, as nanoseconds from the Unix epoch. You must be able to handle dates up to and including 2020.
    • The location of the satellite, as Cartesian coordinates, in metres. You must be able to handle values that fit into a signed 32-bit integer (-2,147,483,648 to 2,147,483,647). Only integer coordinates will be given. You may assume valid input (i.e. your position can be calculated)

Input can be provided from command-line arguments, standard input or equivalent, but not from a variable. The input can have any separator characters in it; please specify what your input format is.

Output

The coordinates of your receiver, to the nearest 1000 metres, using 299,792,458 m/s as the speed of light. Again, I will be lenient with the output format: any separators are acceptable.

Example

Input

1412349052664203400
[1412349052692915310,2267943, 13318342, 0]
[1412349052698278110,-3757960, 3500627, 0]
[1412349052691548521,4425976, -1533193, 3469445]
[1412349052687888295,10622179, 11246951, 84184]

Output

(6223615, 5673496, 0)

I have made a GeoGebra notebook for this example. Please excuse my extremely sloppy GeoGebra skills.

How GPS Works

Because the speed of light is finite, there will be a difference between your current time and the time the satellite sent the signal.

  1. Use the difference to calculate the distance to the satellite, d.
  2. You are clearly located somewhere on the surface of a sphere, centered on the satellite, with radius d.
  3. Once you have two satellites and two spheres, you have to be located somewhere on the intersection of the two sphere surfaces, which is a circle.
  4. Adding another satellite reduces the possible positions to just two points, where all three sphere surfaces intersect.
  5. The fourth satellite allows you to decide on a specific one of these points. Your task is to calculate the location of this point, where all four spheres intersect. Since you assume valid input, such a point does exist.

Rules

\$\endgroup\$
9
  • 2
    \$\begingroup\$ I have two programs written from testing, but neither are anywhere close to golfed solutions :D Hopefully I'll submit one in the next few days. \$\endgroup\$
    – stokastic
    Oct 3, 2014 at 19:24
  • \$\begingroup\$ Why not one more satellite but without the current time? Normally you do not have a perfectly synced timer on your GPS. \$\endgroup\$
    – flawr
    Oct 3, 2014 at 20:47
  • \$\begingroup\$ @flawr Does that work? Thanks, but I won't change it now \$\endgroup\$
    – user16402
    Oct 3, 2014 at 20:55
  • \$\begingroup\$ Thats the way it does works=) At the moment I am still getting 1.0e+006 *(6.2236,5.6735,0.0002) not sure whats wrong... \$\endgroup\$
    – flawr
    Oct 3, 2014 at 21:36
  • 1
    \$\begingroup\$ PS: Should we count bytes as score? \$\endgroup\$
    – flawr
    Oct 3, 2014 at 22:06

1 Answer 1

2
\$\begingroup\$

MatLab/Octave (164)

I assumed the values to be saved in variables. As I said the posed problem seems to result in something about 200 to 300m off in the z coordinate compared to the given solution so this entry does not work within the 100m precision assuming the given test case is correct.

How it works

You can interpret your position as the intersectionpoint of four spheres, since you can calculate the distance to each sattelite by the runtime. The points [x,y,z] on a sphere with center [x,y,z] and radius r can be written as an equation (so 4 satelites = 4 equations):

(x-x0)^2 + (y-y0)^2 + (z-z0)^2 = r^2

Or when expanded / transformed:

-2*x0*x -2*y0*y -2*z0*z = r^2 - x0^2 - y0^2 - z0^2 - x^2 - y^2 - z^2

As you have 4 equations that look like that you can substract one from the other three, which eliminates the x^2+y^2+z^2 and get a system of 3 linear equations that can easily be solved for x,y,z.

But 3 intersecting spheres would result in two possible points, so a fourth is only needed for choosing the right one of those two points. But if the intersectionpoint of the first three is not exactly on the fourth sphere you cannot get an accurate answer.

Normally for gps you have the earth as fourth sphere, so three satelites could give you a line on which your current position must be (when the current exact time is unknonw). The line intersected with the earth surface results in only two possible points. So by comparing the different timestamps you could estimate on which side of the earth you are.

Code

%input
1412349052664203400

[1412349052692915310,2267943, 13318342, 0;
1412349052698278110,-3757960, 3500627, 0;
1412349052691548521,4425976, -1533193, 3469445;
1412349052687888295,10622179, 11246951, 84184]

%actual code
t=input('');d=input('');
c=299792458e-9;
p=d(:,2:4);
r=(d(:,1)-t)*c;
o=ones(3,1);
q=p(1:3,:)-o*p(4,:);
b=p(1:3,:).^2-o*p(4,:).^2;
s=r(1:3).^2-o*r(4).^2;
(-2*q)\(s-sum(b,2))

Output:

  1.0e+006 *

   6.223565252948585
   5.673559409007432
   0.000291267494418
\$\endgroup\$
8
  • 1
    \$\begingroup\$ "Input can be provided from command-line arguments, standard input or equivalent, but not from a variable": is there as specific limitation of Mathlab, not having any way to do input? \$\endgroup\$
    – edc65
    Oct 3, 2014 at 22:58
  • \$\begingroup\$ MATLAB can receive command-line input from the input command, which includes input in the form of matrices and arrays. Also, submissions should produce output with disp or fprintf rather than omitting the trailing semicolon, since omitting the semicolon adds <variable> = or ans = . \$\endgroup\$
    – COTO
    Oct 4, 2014 at 6:47
  • 1
    \$\begingroup\$ @professorfish Octave is the open source version of MATLAB. Generally any MATLAB program should work on Octave. \$\endgroup\$
    – Beta Decay
    Oct 4, 2014 at 8:58
  • 1
    \$\begingroup\$ I changed it now, since I did not know about the input function. @professorfish Octave is basically the opensource clone of matlab, while it is slower in some cases, it does provide some different functoins or shorter commands like a*=b instead a=a*b but there are also some functionalities that are not available in octave. But the basics are the same. \$\endgroup\$
    – flawr
    Oct 4, 2014 at 9:28
  • 1
    \$\begingroup\$ @professorfish You do not need to, there are many online interpreters! \$\endgroup\$
    – flawr
    Oct 4, 2014 at 11:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.