11
\$\begingroup\$

Introduction

Imagine you are on a two dimensional cartesian plane and want to determine your position on it. You know 3 points on that plane and your distance to each of them. While it is always possible to calculate your position from that, doing that in your head is pretty hard. So you decide to write a program for that.

The Challenge

Given 3 points and your distance to them, output the cordinates of your position.

  • Input and output may be in any convenient format, including using complex instead of real numbers. Please clarify in your answer which format you use.
  • You will always get exactly 3 distinct points with their distance to you.
  • The coordinates and distances will be floats with arbitrary precision. Your output has to be correct to 3 decimal places. Rounding is up to you. Please clarify in your answer.
  • You may assume that the three points are not collinear, so there will be always an unique solution.
  • You are not allowed to bruteforce the solution.
  • You may not use any builtins that trivialize this particular problem. Builtins for vector norms, etc. are allowed though.

Hint to get started:

Think about a circle around each of those 3 points with their distance to you as radius.

Rules

Test cases

Input format for one point here is [[x,y],d] with x and y being the coordinates and d being the distance to this point. The 3 of those points are arranged in a list. Output will be x and then y in a list.

[[[1, 2], 1.414], [[1, 1], 2.236], [[2, 2], 1.0]] -> [2, 3]
[[[24.234, -13.902], 31.46], [[12.3242, 234.12], 229.953], [[23.983, 0.321], 25.572]] -> [-1.234, 4.567]
[[[973.23, -123.221], 1398.016], [[-12.123, -98.001], 990.537], [[-176.92, 0], 912.087]] -> [12.345, 892.234]

You can generate additional test cases with this Pyth program. Location goes on the first line of the input and the 3 points are on the following 3 lines.

Happy Coding!

\$\endgroup\$
  • \$\begingroup\$ Because it needs to fit onto a two-dimensional Cartesian plane, the code needs to be as short as possible. \$\endgroup\$ – wizzwizz4 Mar 20 '16 at 8:31
  • \$\begingroup\$ You are obviously using inexact results which still can result in ambiguity, how should we handle this? \$\endgroup\$ – flawr Mar 20 '16 at 13:16
  • \$\begingroup\$ @flawr Just assume that all results are exact und unique. Your program should work for cases with very few decimal places, don't worry about ambiguity. I will clean the challenge up when I'm home. \$\endgroup\$ – Denker Mar 20 '16 at 14:09
  • \$\begingroup\$ Since the accepted answer is effectively just a graphing calculator, I'll mention that there's a 96-byte solution in TI-Basic (68k version). To clarify, is solve (given three circle equations) trivializing the problem? I thought it was, but if you're okay with such things I'll go ahead and post it. \$\endgroup\$ – Fox Mar 27 '16 at 18:46
4
\$\begingroup\$

Desmos, 122 bytes

Online use. Copy+paste each equation into an equation box, click "add all" for each box, then click on the point of intersection, then enter in each value as appropriate. each of A, B, and C are the distances for the points (a,b), (c,d), and (E,f), respectively. To get a square root in the value, type sqrt then the value in the box.

\left(x-a\right)^2+\left(y-b\right)^2=AA
\left(x-c\right)^2+\left(y-d\right)^2=BB
\left(x-E\right)^2+\left(y-f\right)^2=CC

Verify the first test case.

Or you can take a look here:

circles!

\$\endgroup\$
  • \$\begingroup\$ This looks pretty nice, but does this satisfy our criteria for programming languages? This looks just like a plotting tool for me, never used it tho, so I might be wrong. \$\endgroup\$ – Denker Mar 19 '16 at 0:30
  • 1
    \$\begingroup\$ @DenkerAffe I actually asked a question about it on meta before, and it does indeed count. \$\endgroup\$ – Conor O'Brien Mar 19 '16 at 0:33
  • 2
    \$\begingroup\$ Alright, have my upvote then :) \$\endgroup\$ – Denker Mar 19 '16 at 0:36
  • \$\begingroup\$ I dispute the byte count. You get clicking the point of intersection for free, which doesn't seem right. \$\endgroup\$ – lirtosiast Mar 21 '16 at 22:04
  • \$\begingroup\$ @lirtosiast I would argue that the point is always there by definition and further state that the OP said that this sort of interaction was okay. If, however, you believe there should be some penalty, I'm open to suggestions. \$\endgroup\$ – Conor O'Brien Mar 21 '16 at 22:10
4
\$\begingroup\$

C, 362 348 345 bytes

Input is given as a sequence of space-separated floats on stdin: x1 y1 d1 x2 y2 d2 x3 y3 d3. Output is similar on stdout: x y.

#define F"%f "
#define G float
#define T(x)(b.x*b.x-a.x*a.x)
typedef struct{G a;G b;G c;}C;G f(C a,C b,G*c){G x=b.b-a.b;*c=(T(a)+T(b)-T(c))/x/2;return(a.a-b.a)/x;}main(){C a,b,c;G x,y,z,t,m;scanf(F F F F F F F F F,&a.a,&a.b,&a.c,&b.a,&b.b,&b.c,&c.a,&c.b,&c.c);x=f(a,a.b==b.b?c:b,&y);z=f(b.b==c.b?a:b,c,&t);m=t-y;m/=x-z;printf(F F"\n",m,x*m+y);}

C is a structure type whose members are an x-coordinate a, a y-coordinate b, and a distance (radius) c. The function f takes two C structures and a pointer to a float, and determines the line at which the C (circles) intersect. The y-intercept of this line is placed into the pointed-to float, and the slope is returned.

The program calls f on two pairs of circles, then determines the intersection of the produced lines.

\$\endgroup\$
  • \$\begingroup\$ Since we've clarified that the inputs are not collinear, the lines f produces will never be parallel. The tests are to ensure they are also not vertical, since I'm using slope-intercept form. This way, there is always exactly one answer. \$\endgroup\$ – Fox Mar 20 '16 at 7:39
2
\$\begingroup\$

Python - 172

Takes input as a list of tuples of form (x,y,d). Let me know if you see a way to golf this further, I feel like there must be but I can't figure it out!

import numpy as N
def L(P):
    Z=[p[2]**2-p[0]**2-p[1]**2 for p in P];return N.linalg.solve([[P[i][0]-P[0][0],P[i][1]-P[0][1]]for i in[1,2]],[(Z[0]-Z[i])*0.5 for i in [1,2]])
\$\endgroup\$
  • \$\begingroup\$ You can omit some whitespaces here. Something like -1 if 1 else 1 can become -1if 1else 1 for example. This also works with brackets.There are a few places where you can take advantage of that. Also .5 is the same as 0.5. \$\endgroup\$ – Denker Mar 22 '16 at 13:57

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.