24
\$\begingroup\$

There are n people on a 2D plane. Using distances between them we're going to find their positions. To get a unique answer you must make four assumptions:

  1. There are at least 3 people.
  2. The first person is at position (0, 0).
  3. The second person is at position (x, 0) for some x > 0.
  4. The third person is at position (x, y) for some y > 0.

So your challenge is to write a program or function that given a 2D array of distances (where D[i][j] gives the distance between person i and j) returns a list of their coordinates. Your answer must be accurate to at least 6 significant figures. Shortest solution in bytes wins.


Examples

[[0.0, 3.0, 5.0], [3.0, 0.0, 4.0], [5.0, 4.0, 0.0]]

=>

[[0.0, 0.0], [3.0, 0.0], [3.0, 4.0]]


[[0.0, 0.0513, 1.05809686, 0.53741028, 0.87113533], [0.0513, 0.0, 1.0780606,
0.58863967, 0.91899559], [1.05809686, 1.0780606, 0.0, 0.96529704,
1.37140397], [0.53741028, 0.58863967, 0.96529704, 0.0, 0.44501955],
[0.87113533, 0.91899559, 1.37140397, 0.44501955, 0.0]]

=>

[[0.0, 0.0], [0.0513, 0.0], [-0.39, 0.9836], [-0.5366, 0.0295], [-0.8094, -0.3221]]


[[0.0, 41.9519, 21.89390815, 108.37048253, 91.40006121, 49.35063671,
82.20983622, 83.69080223, 80.39436793, 86.5204431, 91.24484876, 22.32327813,
99.5351474, 72.1001264, 71.98278813, 99.8621559, 104.59071383, 108.61475753,
94.91576952, 93.20212636], [41.9519, 0.0, 24.33770482, 144.67214389,
132.28290899, 49.12079288, 85.34321428, 117.39095617, 103.60848008,
79.67795144, 69.52024038, 42.65007733, 105.60007249, 110.50120501,
89.92218111, 60.03623019, 133.61394005, 76.26668715, 130.54041305,
122.74547069], [21.89390815, 24.33770482, 0.0, 130.04213984, 112.98940283,
54.26427666, 71.35378232, 104.72088677, 81.67425703, 90.26668791,
71.13288376, 18.74250061, 109.87223765, 93.96339767, 69.46698314,
84.37362794, 124.38527485, 98.82541733, 116.43603102, 113.07526035],
[108.37048253, 144.67214389, 130.04213984, 0.0, 37.8990613, 111.2161525,
176.70411028, 28.99007398, 149.1355788, 124.17549005, 198.6298252,
126.02950495, 101.55746829, 37.24713176, 152.8114446, 189.29178553,
34.96711005, 180.83483984, 14.33728853, 35.75999058], [91.40006121,
132.28290899, 112.98940283, 37.8990613, 0.0, 111.05881157, 147.27385449,
44.12747289, 115.00173099, 134.19476383, 175.9860033, 104.1315771,
120.19673135, 27.75062658, 120.90347767, 184.88952087, 65.64187459,
183.20903265, 36.35677531, 60.34864715], [49.35063671, 49.12079288,
54.26427666, 111.2161525, 111.05881157, 0.0, 125.59451494, 82.23823276,
129.68328938, 37.23819968, 118.38443321, 68.15130552, 56.84347674,
84.29966837, 120.38742076, 78.30380948, 91.88522811, 72.15031414,
97.00421525, 82.23460459], [82.20983622, 85.34321428, 71.35378232,
176.70411028, 147.27385449, 125.59451494, 0.0, 158.1002588, 45.08950594,
161.43320938, 50.02998891, 59.93581537, 180.43028005, 139.95387244,
30.1390519, 133.42262669, 182.2085151, 158.47101132, 165.61965338,
170.96891788], [83.69080223, 117.39095617, 104.72088677, 28.99007398,
44.12747289, 82.23823276, 158.1002588, 0.0, 136.48099476, 96.57856065,
174.901291, 103.29640959, 77.53059476, 22.95598599, 137.23185588,
160.37639016, 26.14552185, 152.04872054, 14.96145727, 17.29636403],
[80.39436793, 103.60848008, 81.67425703, 149.1355788, 115.00173099,
129.68328938, 45.08950594, 136.48099476, 0.0, 166.89727482, 92.90019808,
63.53459104, 177.66159356, 115.1228903, 16.7609065, 160.79059188,
162.35278463, 179.82760993, 140.44928488, 151.9058635], [86.5204431,
79.67795144, 90.26668791, 124.17549005, 134.19476383, 37.23819968,
161.43320938, 96.57856065, 166.89727482, 0.0, 148.39351779, 105.1934756,
34.72852943, 106.44495924, 157.55442606, 83.19240274, 96.09890812,
61.77726814, 111.24915274, 89.68625779], [91.24484876, 69.52024038,
71.13288376, 198.6298252, 175.9860033, 118.38443321, 50.02998891,
174.901291, 92.90019808, 148.39351779, 0.0, 72.71434547, 175.07913091,
161.59035051, 76.3634308, 96.89392413, 195.433818, 127.21259331,
185.63246606, 184.09218079], [22.32327813, 42.65007733, 18.74250061,
126.02950495, 104.1315771, 68.15130552, 59.93581537, 103.29640959,
63.53459104, 105.1934756, 72.71434547, 0.0, 121.04924013, 88.90999601,
52.48935172, 102.51264644, 125.51831504, 117.54806623, 113.26375241,
114.12813777], [99.5351474, 105.60007249, 109.87223765, 101.55746829,
120.19673135, 56.84347674, 180.43028005, 77.53059476, 177.66159356,
34.72852943, 175.07913091, 121.04924013, 0.0, 93.63052717, 171.17130953,
117.77417844, 69.1477611, 95.81237385, 90.62801636, 65.7996984],
[72.1001264, 110.50120501, 93.96339767, 37.24713176, 27.75062658,
84.29966837, 139.95387244, 22.95598599, 115.1228903, 106.44495924,
161.59035051, 88.90999601, 93.63052717, 0.0, 117.17351252, 159.88686894,
48.89223072, 156.34374083, 25.76186961, 40.13509273], [71.98278813,
89.92218111, 69.46698314, 152.8114446, 120.90347767, 120.38742076,
30.1390519, 137.23185588, 16.7609065, 157.55442606, 76.3634308, 52.48935172,
171.17130953, 117.17351252, 0.0, 145.68608389, 162.51692098, 166.12926334,
142.8970605, 151.6440003], [99.8621559, 60.03623019, 84.37362794,
189.29178553, 184.88952087, 78.30380948, 133.42262669, 160.37639016,
160.79059188, 83.19240274, 96.89392413, 102.51264644, 117.77417844,
159.88686894, 145.68608389, 0.0, 169.4299171, 33.39882791, 175.00707479,
160.25054951], [104.59071383, 133.61394005, 124.38527485, 34.96711005,
65.64187459, 91.88522811, 182.2085151, 26.14552185, 162.35278463,
96.09890812, 195.433818, 125.51831504, 69.1477611, 48.89223072,
162.51692098, 169.4299171, 0.0, 156.08760216, 29.36259602, 11.39668734],
[108.61475753, 76.26668715, 98.82541733, 180.83483984, 183.20903265,
72.15031414, 158.47101132, 152.04872054, 179.82760993, 61.77726814,
127.21259331, 117.54806623, 95.81237385, 156.34374083, 166.12926334,
33.39882791, 156.08760216, 0.0, 167.00907734, 148.3962894], [94.91576952,
130.54041305, 116.43603102, 14.33728853, 36.35677531, 97.00421525,
165.61965338, 14.96145727, 140.44928488, 111.24915274, 185.63246606,
113.26375241, 90.62801636, 25.76186961, 142.8970605, 175.00707479,
29.36259602, 167.00907734, 0.0, 25.82164171], [93.20212636, 122.74547069,
113.07526035, 35.75999058, 60.34864715, 82.23460459, 170.96891788,
17.29636403, 151.9058635, 89.68625779, 184.09218079, 114.12813777,
65.7996984, 40.13509273, 151.6440003, 160.25054951, 11.39668734,
148.3962894, 25.82164171, 0.0]]

=>

[[0.0, 0.0], [41.9519, 0.0], [19.6294, 9.6969], [-88.505, -62.5382],
[-88.0155, -24.6423], [21.2457, -44.5433], [14.7187, 80.8815], [-59.789,
-58.5613], [-29.9331, 74.6141], [34.5297, -79.3315], [62.6017, 66.3826],
[5.2353, 21.7007], [6.1479, -99.3451], [-62.597, -35.7777], [-13.6408,
70.6785], [96.8736, -24.2478], [-61.4216, -84.6558], [92.2547, -57.3257],
[-74.7503, -58.4927], [-55.0613, -75.199]]
\$\endgroup\$
  • 2
    \$\begingroup\$ So basically you are looking for the inverse function of DistanceMatrix in mathematica ;-) \$\endgroup\$ – J42161217 Sep 29 '17 at 13:25
  • \$\begingroup\$ In your first example, the third point could be either (3,4) or (3,-4). \$\endgroup\$ – DavidC Sep 29 '17 at 13:25
  • \$\begingroup\$ @DavidC You didn't read the assumptions closely enough. \$\endgroup\$ – orlp Sep 29 '17 at 13:25
  • \$\begingroup\$ Yes. I now see. \$\endgroup\$ – DavidC Sep 29 '17 at 13:28
  • 2
    \$\begingroup\$ Can there be more than one correct answer or am I doing something wrong? I'm getting +0.322 for the last coordinate of the 2nd example. \$\endgroup\$ – Emigna Sep 29 '17 at 14:23
5
\$\begingroup\$

Python 2, 183 178 166 161 160 159 158 156 bytes

Saved 1 byte thanks to @Giuseppe and 2 bytes thanks to @JonathanFrech.

def f(D):
 X=D[0][1];o=[0,X];O=[0,0];n=2
 for d in D[2:]:y=d[0]**2;x=(y-d[1]**2)/X/2+X/2;y-=x*x;o+=x,;O+=y**.5*(y>d[2]**2-(x-o[2])**2or-1),;n+=1
 return o,O

Try it online!

Uses the first 3 points to calculate the rest. Returns a pair of x-coords, y-coords as allowed in comments.

\$\endgroup\$
  • \$\begingroup\$ O+=[...] can be O+=..., and o+=[x] can be o+=x,. \$\endgroup\$ – Jonathan Frech Sep 30 '17 at 14:29
  • \$\begingroup\$ @JonathanFrech Doesn't work. Python only allows adding lists to lists. TIO \$\endgroup\$ – PurkkaKoodari Oct 2 '17 at 11:20
  • \$\begingroup\$ @Pietu1998 I did not mean o+=x, but rather o+=x,. \$\endgroup\$ – Jonathan Frech Oct 2 '17 at 11:25
4
+100
\$\begingroup\$

R, 107

function(d){y=t(cmdscale(d))
y=y-y[,1]
p=cbind(c(y[3],-y[4]),y[4:3])%*%y/sum(y[,2]^2)^.5
p*c(1,sign(p[6]))}

The big head start is on line 1 where I use R's function for Multi-Dimensional Scaling (MDS). The rest is probably inefficient (thanks for making suggestions on how to improve): line 2 translates the data so that the first point is at (0, 0); line 3 rotates the points so that the second point is at (0,x); line 4 flips everything so that the third point is at y>0.

\$\endgroup\$
  • \$\begingroup\$ R has a built-in for this??? Dang. \$\endgroup\$ – Giuseppe Sep 30 '17 at 14:15
3
\$\begingroup\$

R, 227 215 209 176 169 bytes

function(d){x=y=c(0,0)
x[2]=a=d[1,2]
d=d^2
i=3:nrow(d)
D=d[1,i]
x[i]=(D+a^2-d[2,i])/2/a
y[3]=e=sqrt(d[1,3]-x[3]^2)
y[i]=(D-d[3,i]+x[3]^2+e^2-2*x[3]*x[i])/2/e
Map(c,x,y)}

Try it online!

Once upon a time, I took a course in Computational Geometry. I'd like to say that helped, but I clearly learned nothing.

Input is an R matrix, with the output a list of 2-element vectors (x,y) (which is closer to the spec and saves bytes).

The problem here is, of course, the first three points. Once you fix three points, you can compute all the others based on those.

I just used a bit of algebra to simplify things and then noticed that since I'm only using the first 3 points to solve for the others, this all vectorized very neatly.

Outgolfed by flodel

\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES7), 202 193 bytes

d=>{for(k=7;(a=d.map((r,i)=>[x=(r[0]**2-r[1]**2+a*a)/2/a,(d[0][i]**2-x*x)**.5*(k>>i&1||-1)],a=d[0][1])).some(([x,y],i)=>a.some(([X,Y],j)=>(Math.hypot(x-X,y-Y)-d[i][j])**2>1e-6));k+=8);return a}

Test cases

let f =

d=>{for(k=7;(a=d.map((r,i)=>[x=(r[0]**2-r[1]**2+a*a)/2/a,(d[0][i]**2-x*x)**.5*(k>>i&1||-1)],a=d[0][1])).some(([x,y],i)=>a.some(([X,Y],j)=>(Math.hypot(x-X,y-Y)-d[i][j])**2>1e-6));k+=8);return a}

format = a => a.map(JSON.stringify).join`\n`

console.log(format(f([[0.0,3.0,5.0],[3.0,0.0,4.0],[5.0,4.0,0.0]])))
console.log(format(f([[0.0,0.0513,1.05809686,0.53741028,0.87113533],[0.0513,0.0,1.0780606,0.58863967,0.91899559],[1.05809686,1.0780606,0.0,0.96529704,1.37140397],[0.53741028,0.58863967,0.96529704,0.0,0.44501955],[0.87113533,0.91899559,1.37140397,0.44501955,0.0]])))
console.log(format(f([[0.0,41.9519,21.89390815,108.37048253,91.40006121,49.35063671,82.20983622,83.69080223,80.39436793,86.5204431,91.24484876,22.32327813,99.5351474,72.1001264,71.98278813,99.8621559,104.59071383,108.61475753,94.91576952,93.20212636],[41.9519,0.0,24.33770482,144.67214389,132.28290899,49.12079288,85.34321428,117.39095617,103.60848008,79.67795144,69.52024038,42.65007733,105.60007249,110.50120501,89.92218111,60.03623019,133.61394005,76.26668715,130.54041305,122.74547069],[21.89390815,24.33770482,0.0,130.04213984,112.98940283,54.26427666,71.35378232,104.72088677,81.67425703,90.26668791,71.13288376,18.74250061,109.87223765,93.96339767,69.46698314,84.37362794,124.38527485,98.82541733,116.43603102,113.07526035],[108.37048253,144.67214389,130.04213984,0.0,37.8990613,111.2161525,176.70411028,28.99007398,149.1355788,124.17549005,198.6298252,126.02950495,101.55746829,37.24713176,152.8114446,189.29178553,34.96711005,180.83483984,14.33728853,35.75999058],[91.40006121,132.28290899,112.98940283,37.8990613,0.0,111.05881157,147.27385449,44.12747289,115.00173099,134.19476383,175.9860033,104.1315771,120.19673135,27.75062658,120.90347767,184.88952087,65.64187459,183.20903265,36.35677531,60.34864715],[49.35063671,49.12079288,54.26427666,111.2161525,111.05881157,0.0,125.59451494,82.23823276,129.68328938,37.23819968,118.38443321,68.15130552,56.84347674,84.29966837,120.38742076,78.30380948,91.88522811,72.15031414,97.00421525,82.23460459],[82.20983622,85.34321428,71.35378232,176.70411028,147.27385449,125.59451494,0.0,158.1002588,45.08950594,161.43320938,50.02998891,59.93581537,180.43028005,139.95387244,30.1390519,133.42262669,182.2085151,158.47101132,165.61965338,170.96891788],[83.69080223,117.39095617,104.72088677,28.99007398,44.12747289,82.23823276,158.1002588,0.0,136.48099476,96.57856065,174.901291,103.29640959,77.53059476,22.95598599,137.23185588,160.37639016,26.14552185,152.04872054,14.96145727,17.29636403],[80.39436793,103.60848008,81.67425703,149.1355788,115.00173099,129.68328938,45.08950594,136.48099476,0.0,166.89727482,92.90019808,63.53459104,177.66159356,115.1228903,16.7609065,160.79059188,162.35278463,179.82760993,140.44928488,151.9058635],[86.5204431,79.67795144,90.26668791,124.17549005,134.19476383,37.23819968,161.43320938,96.57856065,166.89727482,0.0,148.39351779,105.1934756,34.72852943,106.44495924,157.55442606,83.19240274,96.09890812,61.77726814,111.24915274,89.68625779],[91.24484876,69.52024038,71.13288376,198.6298252,175.9860033,118.38443321,50.02998891,174.901291,92.90019808,148.39351779,0.0,72.71434547,175.07913091,161.59035051,76.3634308,96.89392413,195.433818,127.21259331,185.63246606,184.09218079],[22.32327813,42.65007733,18.74250061,126.02950495,104.1315771,68.15130552,59.93581537,103.29640959,63.53459104,105.1934756,72.71434547,0.0,121.04924013,88.90999601,52.48935172,102.51264644,125.51831504,117.54806623,113.26375241,114.12813777],[99.5351474,105.60007249,109.87223765,101.55746829,120.19673135,56.84347674,180.43028005,77.53059476,177.66159356,34.72852943,175.07913091,121.04924013,0.0,93.63052717,171.17130953,117.77417844,69.1477611,95.81237385,90.62801636,65.7996984],[72.1001264,110.50120501,93.96339767,37.24713176,27.75062658,84.29966837,139.95387244,22.95598599,115.1228903,106.44495924,161.59035051,88.90999601,93.63052717,0.0,117.17351252,159.88686894,48.89223072,156.34374083,25.76186961,40.13509273],[71.98278813,89.92218111,69.46698314,152.8114446,120.90347767,120.38742076,30.1390519,137.23185588,16.7609065,157.55442606,76.3634308,52.48935172,171.17130953,117.17351252,0.0,145.68608389,162.51692098,166.12926334,142.8970605,151.6440003],[99.8621559,60.03623019,84.37362794,189.29178553,184.88952087,78.30380948,133.42262669,160.37639016,160.79059188,83.19240274,96.89392413,102.51264644,117.77417844,159.88686894,145.68608389,0.0,169.4299171,33.39882791,175.00707479,160.25054951],[104.59071383,133.61394005,124.38527485,34.96711005,65.64187459,91.88522811,182.2085151,26.14552185,162.35278463,96.09890812,195.433818,125.51831504,69.1477611,48.89223072,162.51692098,169.4299171,0.0,156.08760216,29.36259602,11.39668734],[108.61475753,76.26668715,98.82541733,180.83483984,183.20903265,72.15031414,158.47101132,152.04872054,179.82760993,61.77726814,127.21259331,117.54806623,95.81237385,156.34374083,166.12926334,33.39882791,156.08760216,0.0,167.00907734,148.3962894],[94.91576952,130.54041305,116.43603102,14.33728853,36.35677531,97.00421525,165.61965338,14.96145727,140.44928488,111.24915274,185.63246606,113.26375241,90.62801636,25.76186961,142.8970605,175.00707479,29.36259602,167.00907734,0.0,25.82164171],[93.20212636,122.74547069,113.07526035,35.75999058,60.34864715,82.23460459,170.96891788,17.29636403,151.9058635,89.68625779,184.09218079,114.12813777,65.7996984,40.13509273,151.6440003,160.25054951,11.39668734,148.3962894,25.82164171,0.0]])))

How?

Let di,j be the input and xi, yi be the expected output.

By the challenge rules, we know that:

  • For any pair (i, j): di,j = √((xi - xj)² + (yi - yj)²)
  • x0 = y0 = y1 = 0

We can immediately deduce that:

  1. x1 = d0,1

  2. d0,j = √((x0 - xj)² + (y0 - yj)²) = √(xj² + yj²)
    d0,j² = xj² + yj²

  3. d1,j = √((x1 - xj)² + (y1 - yj)²) = √((x1 - xj)² + yj²)
    d1,j² = (x1 - xj)² + yj² = x1² + xj² + 2x1xj + yj² = d0,1² + xj² + 2d0,1xj + yj²

Computing xj

By using 2 and 3, we get:

xj² - (d0,1² + xj² - 2d0,1xj) = d0,j² - d1,j²

Which leads to:

xj = (d0,j² - d1,j² + d0,1²) / 2d0,1

Computing yj

Now that xj is known, we have:

yj² = d0,j² - xj²

Which gives:

yj = ±√(d0,j² - xj²)

We determine the sign of each yj by simply trying all possible combinations until we match the original distances. We also have to make sure that we have y2 > 0.

We do that by using the bitmask k where 1's are interpreted as positive and 0's are interpreted as negative. We start with k = 7 (111 in binary) and add 8 at each iteration. This way, positive values of yj are guaranteed to be selected for 0 ≤ j ≤ 2. (We could start with k = 4 just as well, because y0 = y1 = 0 anyway. But using 7 prevents negative zeros from appearing.)

\$\endgroup\$
  • \$\begingroup\$ I'm not sure whether it'd be shorter, but the correct way to calculate the sign of y (after the initial 3) for element k is to find p = (x, y) with two points, set p' = (x, -y), and take a third already-known point j and compare distance d[i][j] with dist(p, j) and dist(p', j). I don't consider negative zeroes an incorrect answer by the way. \$\endgroup\$ – orlp Sep 29 '17 at 20:47
  • \$\begingroup\$ @orlp Removing negative zeros doesn't cost any byte, so it's a purely aesthetic consideration. :-) (And you're right: this method is a rather inefficient fix on an initially non-working solution. But I thought it was still worth posting.) \$\endgroup\$ – Arnauld Sep 29 '17 at 21:04
2
\$\begingroup\$

JavaScript (ES7), 140 139 126 121 118 117 bytes

Saved 1 byte thanks to @Giuseppe.

/* this line for testing only */ f =
D=>D.map((d,n)=>n>1?(y=d[0]**2,D[n]=x=(y-d[1]**2)/X/2+X/2,y-=x*x,[x,y**.5*(y>d[2]**2-(x-D[2])**2||-1)]):[X=n*d[0],0])
<!-- HTML for testing only --><textarea id="i" oninput="test()">[[0.0, 0.0513, 1.05809686, 0.53741028, 0.87113533], [0.0513, 0.0, 1.0780606, 0.58863967, 0.91899559], [1.05809686, 1.0780606, 0.0, 0.96529704, 1.37140397], [0.53741028, 0.58863967, 0.96529704, 0.0, 0.44501955], [0.87113533, 0.91899559, 1.37140397, 0.44501955, 0.0]]</textarea><pre id="o"></pre><script>window.onload=test=function(){try{document.querySelector("#o").innerHTML=JSON.stringify(f(JSON.parse(document.querySelector("#i").value)))}catch(e){}}</script>

Works somewhat like my Python answer. Returning [x,y] pairs turned out much shorter than separate X and Y lists in JS. Overwrites the argument list, so don't use it as input multiple times.

\$\endgroup\$
  • 2
    \$\begingroup\$ @Giuseppe Actually, I can just not score the f= and fit it in one. :P \$\endgroup\$ – PurkkaKoodari Sep 29 '17 at 20:54
  • \$\begingroup\$ well I don't know JavaScript so I'm not surprised I missed that. \$\endgroup\$ – Giuseppe Sep 29 '17 at 20:55
2
\$\begingroup\$

Mathematica, 160 bytes

(s=Table[0{,},n=Tr[1^#]];s[[2]]={#[[1,2]],0};f@i_:=RegionIntersection~Fold~Table[s[[j]]~Circle~#[[j,i]],{j,i-1}];s[[3]]=Last@@f@3;Do[s[[i]]=#&@@f@i,{i,4,n}];s)&

The program use built-in RegionIntersection to calculate intersection point of circles. Program requires exact coordinate to work.

This assumes RegionIntersection always make the point with higher y-coordinate the last one in its result if the x-coordinate is equal. (at least it is true on Wolfram Sandbox)

For some reason RegionIntersection doesn't work if there is too many circles in its input so I have to process each pair once by using Fold.

Demonstrate screenshot:Screenshot

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.