23
\$\begingroup\$

Brief Problem Explanation

Write a program to find the minimum distance between two points traveling only on rays emanating from the origin and circles centered on the origin.

Explanation of Premise

Now let's imagine we are on a plane, and on this plane we are only allowed to travel in special ways. We are allowed to travel on any ray emanating from the origin.

Rays we can travel on

We can also travel on any circle centered at a circle

Circles we can travel on

Now our goal is to travel from one point on this plane to another. However, we can't just travel in a simple Euclidian path, we can only do this if the points happen to fall on a ray emanating from the center.

enter image description here

We can travel on this one because it falls on a one of our rays.

enter image description here

We can also travel on circles centered at the origin.

enter image description here

Examples

Now here is the challenge:

We've got to get from one point to another in the shortest path; often this is a combination of traveling on circles and rays.

enter image description here

This, however, it could also be traveling on two rays.

enter image description here

Sometimes there exist two paths that travel the minimum distance.

enter image description here

Problem

Your challenge is to write a program that when given two points will give us the minimum distance between them if we follow these rules. The inputs can be given in either rectangular or polar forms and the output ought to be one number, the distance between.

Test Cases

(with rectangular input)

(1,1) (1,-1) -> ~ 2.22144
(0,0) (1, 1) -> ~ 1.41421
(1,0) (-0.4161 , 0.90929) -> ~ 2
(1,1) (1, 0) -> ~ 1.19961
(1,2) (3, 4) -> ~ 3.16609
\$\endgroup\$
  • \$\begingroup\$ Are the example test cases in rectangular or polar forms? Also: bewteen \$\endgroup\$ – Angs Nov 20 '16 at 19:28
  • \$\begingroup\$ They are in the rectangular form, I ought to clarify that \$\endgroup\$ – Ando Bando Nov 20 '16 at 19:30
  • \$\begingroup\$ Is the last example correct? I'm getting ~3.166 \$\endgroup\$ – Angs Nov 20 '16 at 20:14
  • 6
    \$\begingroup\$ @Peter Taylor Because they are not really the same path. In a similar way a path from 0,0 to 1,1 on the xy plane via small steps alternating in the x and y directions appears identical to a direct diagonal path as the step length tends to zero. But the diagonal path has length sqrt(2) while the step path will always have length 2. \$\endgroup\$ – Penguino Nov 20 '16 at 21:26
  • 1
    \$\begingroup\$ I think the challenge would look better if the images were not so large. Currently they make it hard to follow the text \$\endgroup\$ – Luis Mendo Nov 21 '16 at 10:06
5
\$\begingroup\$

Haskell, 49 48 bytes

(a!q)c r=min(q+r)$abs(q-r)+acos(cos$a-c)*min q r

Usage:

> let rect2polar (x,y)=(atan2 y x, sqrt(x^2+y^2))
> let test c1 c2=let [(a1,r1),(a2,r2)]=rect2polar<$>[c1,c2] in (a1!r1)a2 r2
> test (1,0) (-0.4161, 0.90929)
1.9999342590038496

Thanks to @Zgarb for saving a byte

\$\endgroup\$
  • \$\begingroup\$ You can save a byte by defining (a!q)c r instead of d a q c r. \$\endgroup\$ – Zgarb Nov 23 '16 at 12:48
4
\$\begingroup\$

JavaScript (ES6), 65 bytes

with(Math)(r,t,s,u,v=acos(cos(t-u)))=>v<2?abs(r-s)+v*min(r,s):r+s

Takes polar coordinates. Uses @Angs' trick for reducing an angle to between 0 and π. For rectangular coordinates, something like this works:

with(Math)g=(r,t,s,u,v=acos(cos(t-u)))=>v<2?abs(r-s)+v*min(r,s):r+s
with(Math)f=(x,y,v,w)=>g(hypot(y,x),atan2(y,x),hypot(w,v),atan2(y,v))
\$\endgroup\$
3
\$\begingroup\$

MATL, 22 bytes

|ttsGZ}/X/bX<*|bd|+hX<

Input is an array of two complex numbers.

Try it online! Or verify all test cases.

Explanation

|       % Implicitly input array and take absolute value of its entries
tt      % Duplicate twice
s       % Sum. This is the length of the path that follows the two radii
GZ}     % Push input again and split into the two numbers
/X/     % Divide and compute angle. This gives the difference of the angles
        % of the two points, between -pi and pi
bX<     % Bubble up a copy of the array of radii and compute minimum
*|      % Multiply and take absolute value. This is the arc part of the
        % path that follows one arc and the difference of radii
bd|     % Bubble up a copy of the array of radii and compute absolute
        % difference. This is the other part of the second path
+       % Add. This gives the length of second path
hX<     % Concatenate and take minimum to produce the smallest length.
        % Implicitly display
\$\endgroup\$
2
\$\begingroup\$

Ruby, 64 bytes

First, my submission. Lambda function with arguments distance 1, angle 1, distance 2, angle2.

->r,a,s,b{([d=(b-a).abs,?i.to_c.arg*4-d,2].min-2)*[r,s].min+s+r}

Now here's two different solutions of 66 bytes (excluding assignment f=) followed by my actual submission again at 64 bytes.

Solution 1:Using include Math, 66 bytes excluding f=
include Math;f=->r,a,s,b{[acos(cos(b-a)),2].min*[r,s].min+(s-r).abs}

Solution 2:Using complex number to define PI instead, 66 bytes excluding f=
f=->r,a,s,b{[d=(b-a).abs,?i.to_c.arg*4-d,2].min*[r,s].min+(s-r).abs}

SUBMISSION AGAIN, 64 bytes excluding f=
f=->r,a,s,b{([d=(b-a).abs,?i.to_c.arg*4-d,2].min-2)*[r,s].min+s+r}

The Submission is based on solution 2, but uses the identity (s-r).abs=s+r-[s,r].min*2 to shorten the code by 2 bytes, hence the -2 inside the brackets.

The other notable feature is the expression ?i.to_c.arg*4 = 2*PI without using include Math. If lower precision is acceptable this can be replaced by a literal.

Solution 2 commented in test program

f=->r,a,s,b{          #r,s are distances, a,b are angles for points 1 and 2 respectively.                       
    [d=(b-a).abs,       #From nearer point we can take arc of length d radians perhaps crossing zero angle to the ray of the further point
    ?i.to_c.arg*4-d,    #or go the other way round which may be shorter (?i.to_c.arg*4 == 2*PI, subtract d from this.)
    2].min*             #or go through the centre if the angle exceeds 2 radians.
  [r,s].min+          #Multiply the radians by the distance of the nearer point from the origin to get the distance travelled. 
  (s-r).abs           #Now add the distance to move along the ray out to the further point.
}

#test cases per question (given as complex numbers, converted to arrays of [distance,angle]+[distance,angle] (+ concatenates.)
#the "splat" operator * converts the array to 4 separate arguments for the function.
p f[*("1+i".to_c.polar + "1-i".to_c.polar)]
p f[*("0".to_c.polar + "1+i".to_c.polar)]
p f[*("1".to_c.polar + "-0.4161+0.90929i".to_c.polar)]
p f[*("1+i".to_c.polar + "1".to_c.polar)]
p f[*("1+2i".to_c.polar + "3+4i".to_c.polar)]

Output

2.221441469079183
1.4142135623730951
1.9999342590038496
1.1996117257705434
3.1660966740274357
\$\endgroup\$
1
\$\begingroup\$

Python 2, 164 126 125 132 bytes:

def A(a,b,c,d,p=3.1415926535):z=abs(a-c);M=lambda f:2*p*f*abs(b-d)/360.0;print min((a==c)*min(a+c,M(a))+(b==d)*z or'',M(a)+z,M(c)+z)

I am currently looking into golfing this more, though. Accepts polar coordinates. Should be called in the format A(r1,θ1,r2,θ2). Outputs a floating point value accurate up to 12 significant figures.

Try It Online! (Ideone)

A simple, straightforward implementation that calculates and outputs to STDOUT the minimum value out of an array of at most 3 values containing:

  1. the minimum value out of either the sum of the two lengths (r1+r2) or the length of the arc connecting the two points iff r1==r2;
  2. the difference between the two distances (abs(r1-r2)) iff θ1==θ2 (i.e. the two points are collinear);
  3. if none of the previous 2 items are added, then an empty string ('') as apparently in Python a string is greater than any integer;
  4. and 2 final values given from the distances traveled along a circle and a ray and vice-versa between the two points.
\$\endgroup\$
  • \$\begingroup\$ Why not math.pi? \$\endgroup\$ – user202729 Jan 28 '18 at 8:22
2
\$\begingroup\$

Mathematica 66 Bytes

This takes rectangular coordinates and can output an exact symbolic solution

Min[If[(m=Min[{p,q}=Norm/@#])>0,m*VectorAngle@@#,0]+Abs[p-q],p+q]&

Usage:

%/@{
{{1,1},{1,-1}},
{{0,0},{1,1}},
{{1,0},{-.4161,.90929}},
{{1,1},{1,0}},
{{1,2},{3,4}}
}

yields: symbolic result

N@% yields:

{2.221441469, 1.414213562, 1.999934259, 1.199611726, 3.166096674}

\$\endgroup\$
  • 1
    \$\begingroup\$ Nifty! if you're going the symbolic route you can replace test case {1,0}{-.4161,.90929} with {1,0}{cos(2),sin(2)} \$\endgroup\$ – Ando Bando Nov 22 '16 at 13:45
0
\$\begingroup\$

Wolfram Language (Mathematica), 47 bytes

MinMax@Abs@{##}.{Min[Abs[Arg@#-Arg@#2]-1,1],1}&

Try it online!

(beats the current 66-byte answer)

Take input as 2 complex numbers.

May have some issues if the input is symbolic. (e.g., Cos@2 + I Sin@2)

\$\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.