GPS: Golfed Positioning System

3

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

user16402

Posted 2014-10-03T18:32:20.820

Reputation:

2I 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. – stokastic – 2014-10-03T19:24:00.700

Why not one more satellite but without the current time? Normally you do not have a perfectly synced timer on your GPS. – flawr – 2014-10-03T20:47:01.293

@flawr Does that work? Thanks, but I won't change it now – None – 2014-10-03T20:55:56.297

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... – flawr – 2014-10-03T21:36:53.800

I tried a few different methods now but all result in about 200 to 300m off in the z coordinate. – flawr – 2014-10-03T21:55:16.627

1PS: Should we count bytes as score? – flawr – 2014-10-03T22:06:15.440

@professorfish actually 4 satellites is enough without prior knowledge of the time. There will only be one consistent solution for time and position together (or put another way, only one time that lets you get a consistent solution for position). This is more-or-less how GPS time transfer works. – hobbs – 2014-10-04T06:54:04.310

@hobbs Also true. I'll add a rule that your solution doesn't need to take time if it doesn't want to – None – 2014-10-04T07:24:33.687

@flawr Yes, score is in bytes – None – 2014-10-04T13:54:24.277

Answers

2

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

flawr

Posted 2014-10-03T18:32:20.820

Reputation: 40 560

1"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? – edc65 – 2014-10-03T22:58:52.113

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 =. – COTO – 2014-10-04T06:47:11.743

What does MatLab/Octave mean? Will the code run in both? Only Octave? – None – 2014-10-04T07:29:09.563

1@professorfish Octave is the open source version of MATLAB. Generally any MATLAB program should work on Octave. – Beta Decay – 2014-10-04T08:58:53.547

1I 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. – flawr – 2014-10-04T09:28:05.957

@flawr I'm downloading Octave for Cygwin - I'll test your solution when the download finishes – None – 2014-10-04T10:33:15.037

1@professorfish You do not need to, there are many online interpreters! – flawr – 2014-10-04T11:57:31.420

@flawr Ok, I've tested it, it works. Thanks – None – 2014-10-04T13:42:00.637