17
\$\begingroup\$

Your task is to take \$n \ge 2\$ points in 3D space, represented as 3 floating point values, and output the Euclidean distance between the two closest points. For example

$$A = (0, 0, 0) \\ B = (1, 1, 1) \\ C = (4, 0, 2)$$

would output \$\sqrt3 = 1.7320508075688772...\$, the distance between \$A\$ and \$B\$.

The Euclidean distance, \$E\$, between any two points in 3D space \$X = (a_1, b_1, c_1)\$ and \$Y = (a_2, b_2, c_2)\$ is given by the formula

$$E = \sqrt{(a_2 - a_1)^2 + (b_2 - b_1)^2 + (c_2 - c_1)^2}$$

This is so the shortest code in bytes wins

\$\endgroup\$
  • 3
    \$\begingroup\$ Restricting to a single language is hardly ever a good idea. Competition is within each language anyway \$\endgroup\$ – Luis Mendo Nov 20 '20 at 19:44
  • 1
    \$\begingroup\$ @LuisMendo sorry, I didn't know that, this is my second question yet. I will edit the question. \$\endgroup\$ – forever Nov 20 '20 at 21:14
  • 14
    \$\begingroup\$ I would recommend restricting the input to positive (or non-negative) integers, as requiring float handling just complicates the challenge unnecessarily. Furthermore, why isn't the output for those three points \$\sqrt3\$ between \$(1,1,1)\$ and \$(0,0,0)\$? \$\endgroup\$ – caird coinheringaahing Nov 20 '20 at 22:35
  • 4
    \$\begingroup\$ Suggested test case: [[0,0,0],[0,0,0],[1,1,1]] (looping over all n^2 combinations and filtering zero distance is not sufficient) \$\endgroup\$ – Sisyphus Nov 21 '20 at 2:59
  • 4
    \$\begingroup\$ Adding some more testcases would be nice. \$\endgroup\$ – Razetime Nov 21 '20 at 4:19

20 Answers 20

4
\$\begingroup\$

05AB1E, 8 bytes

œ€ü-nOtß

Try it online!

Commented:

œ         # take all permutations of the input
 €        # for each permutation:
   -      #   take the element-wise difference
  ü       #   between each pair of adjacent points
    n     # square each number
     O    # sum all difference-lists
      t   # take the square root of every sum
       ß  # take the minimum
\$\endgroup\$
11
\$\begingroup\$

R, 34 bytes

function(...)min(dist(rbind(...)))

Try it online!

This is a nice opportunity to use R's ... syntax to define a function that can accept a variable number of arguments; in this case, the x,y,z coordinates of each point.

The dist function calculates the pairwise distance between all rows of a matrix, using a chosen method - luckily, the default is 'euclidean' and so isn't specified in this case.

Of course, it could be even shorter if we allow the input to already be combined-together as a matrix, but this wouldn't be so neat...

R, 23 bytes

function(m)min(dist(m))

Try it online!

\$\endgroup\$
  • 2
    \$\begingroup\$ Looks like exactly right tool for this task. \$\endgroup\$ – val says Reinstate Monica Nov 22 '20 at 10:54
  • \$\begingroup\$ I don't think I'd seen the ... syntax used for golfing before. You should add it to the tips thread! \$\endgroup\$ – Robin Ryder Nov 25 '20 at 8:44
8
\$\begingroup\$

Wolfram Language (Mathematica), 33 bytes

Min[Norm[#-#2]&@@@#~Subsets~{2}]&

Try it online!

\$\endgroup\$
7
\$\begingroup\$

Python 3, 106 95 93 bytes

Saved 11 bytes thanks to fireflame241!!!
Saved 2 bytes thanks to Jonathan Allan!!!

lambda l:min(sum((a-b)**2for a,b in zip(l[p],v))**.5for q,v in enumerate(l)for p in range(q))

Try it online!

Inputs a list of points as tuples and returns the Euclidean distance between the two closest points.
Works with points of any dimension so long as they are consistent within the list.

\$\endgroup\$
  • \$\begingroup\$ WLOG, let p<q \$\endgroup\$ – fireflame241 Nov 21 '20 at 3:12
  • \$\begingroup\$ My suggestion was to take p in range(q), removing the need for the not-equal check. \$\endgroup\$ – fireflame241 Nov 21 '20 at 3:21
  • \$\begingroup\$ Save two with enumerate, TIO. \$\endgroup\$ – Jonathan Allan Nov 21 '20 at 19:34
  • \$\begingroup\$ You can use zip(p,v) and for p in l[:q] to save 6 more bytes, Try it online! \$\endgroup\$ – Tipping Octopus Nov 27 '20 at 17:52
6
\$\begingroup\$

Jelly, 9 bytes

ŒcZ_/²§Ṃ½

Try it online!

Works with points of any dimension

Explanation

ŒcZ_/²§Ṃ½ # Take as input a list of points, where each point is a list of coordinates
Œc        # All pairs of two distinct points [(p1,p2),(p1,p3),...]
  Z       # Transpose to get two lists of points [[p1,p1,...],[p2,p3,...]]
   _/     # Depth-1 vectorizing difference [p1-p2, p1-p3, ...]
     ²§   # Square coordinates and sum each
       Ṃ  # Minimum
        ½ # Square root
\$\endgroup\$
  • \$\begingroup\$ You can use ÆḊ as the norm if that helps you? Perhaps change ²§Ṃ½ to ÆḊṂ? \$\endgroup\$ – caird coinheringaahing Nov 21 '20 at 3:14
  • 2
    \$\begingroup\$ @cairdcoinheringaahing Unfortunately ÆḊ doesn't vectorize, so I would have to use ÆḊ€Ṃ for the same number of bytes \$\endgroup\$ – fireflame241 Nov 21 '20 at 3:18
6
\$\begingroup\$

Ruby 2.7, 79 65 bytes

Saved a whooping 14 bytes, thanks to Sisyphus!

->s{s.combination(2).map{_1.zip(_2).sum{|a,b|(a-b)**2}**0.5}.min}

Try it online!

  • Expects an array of points!
  • TIO uses an older version of Ruby, so |p,q|p,q is replaced by _1,_2 to save three bytes (as suggested by Dingus).
\$\endgroup\$
  • 3
    \$\begingroup\$ Nice solution! 68 by using |a,b| syntax and using the fact that sum takes a block: Try it online!. Even less in 2.7 since you can use _1 and _2 instead of |p,q|... \$\endgroup\$ – Sisyphus Nov 21 '20 at 10:02
  • \$\begingroup\$ @Sisyphus - didn't knew about that syntax! \$\endgroup\$ – vrintle Nov 21 '20 at 13:20
3
\$\begingroup\$

Husk, 10 bytes

▼ṁẊȯ√ṁ□z-Ṗ

Try it online!

▼           # minimum of
 ṁ          # sums of applying function to
         Ṗ  # all subsets of input
            # (this may include subsets of >2 points,
            # but that's ok...)
  Ẋȯ√ṁ□z-   # the function:
  Ẋȯ        # apply to all adjacent pairs
            # (...that's why it was ok if there were >2 points
            # in any sublist)
    √       # square root of
     ṁ□     # sum of squres of
       z-   # element-wise differences
\$\endgroup\$
3
\$\begingroup\$

Brachylog, 14 bytes

{⊇Ċz-ᵐ^₂ᵐ+√}ᶠ⌋

Try it online!

Boring and straightforward.

             ⌋    The output is the minimum of
{          }ᶠ     every possible
          √       square root of
         +        a sum of
      ^₂ᵐ         the squares of
    -ᵐ            the differences between
   z              the coordinates for each axis
 ⊇                for a sublist of the input
  Ċ               containing two elements.
\$\endgroup\$
3
\$\begingroup\$

Haskell, 75 74 bytes

g[]=[]
g(x:t)=[(sum$zipWith((**2).)(map(-)x)z)**0.5|z<-t]++g t
f=minimum.g

Try it online!

g[]=[]        - edge case for combinations   
g(x:t)=[ ... |z<-t]++g t  
              - combinations
(sum$zipWith(\a b->(a-b)**2)x z)**0.5
              - compute hypo..
f=minimum.g   - return minimum value found
  • Saved 1 thanks to @Unrelated String insane idea (sum$zipWith(\a b->(a-b)**2)x z)**0.5 becomes (sum$zipWith((**2).)(map(-)x)z)**0.5 e.g. we first map x to obtain a list of partially applied subtractions , then we zipWith (**2). (read "compose with square") which firstly finishes the subtraction and then computes the square. If I understood correctly O.o
\$\endgroup\$
  • 2
    \$\begingroup\$ 74 bytes. Had the insane idea of getting rid of that lambda, and it happened to work \$\endgroup\$ – Unrelated String Nov 21 '20 at 20:18
  • 1
    \$\begingroup\$ I say very insane @Unrelated String! Thanks! \$\endgroup\$ – AZTECCO Nov 21 '20 at 20:49
2
\$\begingroup\$

Octave/MATLAB with Statistics package/toolbox, 17 bytes

@(x)min(pdist(x))

Try it online!

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

Japt -g, 15 14 bytes

The spec asks us to get the minimum but the lone test case gets the maximum so I don't know which to output. I've gone with the former but if that's not right then use the -h flag instead.

à2 ËÕËrnÃx²¬ÃÍ

Try it

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

JavaScript (ES6), 86 bytes

a=>a.map(m=([x,y,z],i)=>a.map(([X,Y,Z])=>m=!i--|(d=Math.hypot(x-X,y-Y,z-Z))>m?m:d))&&m

Try it online!

Commented

a =>                          // a[] = list of triplets
  a.map(m = ([x, y, z], i) => // for each triplet (x,y,z) at position i in a[]:
    a.map(([X, Y, Z]) =>      //   for each triplet (X,Y,Z) in a[]:
      m =                     //     update the minimum distance m:
        !i-- | (              //       decrement i; if it was equal to 0
          d = Math.hypot(     //       or the Euclidean distance d:
            x - X,            //         between (x,y,z)
            y - Y,            //         and (X,Y,Z)
            z - Z             //
        )) > m ?              //       is greater than m:
          m                   //         leave m unchanged
        :                     //       else:
          d                   //         update m to d
    )                         //   end of inner map()
  ) && m                      // end of outer map(); return m
\$\endgroup\$
2
\$\begingroup\$

Scala 3, 72 bytes

s=>math.sqrt((for> <-s;| <-s- >yield(>zip|map(_-_)map(x=>x*x)).sum).min)

Try it online!

Accepts a Set[List[Int]] so that it can use - to ensure a point is not compared to itself.

This is my first time using Scala 3's new control syntax to save 2 bytes.

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

J, 29 bytes

[:<./@,+/&.:*:@:-"1/~+_*[:=#\

Try it online!

[:<./@,+/&.:*:@:-"1/~+_*[:=#\
                           #\ 1…N
                        [:=   identity matrix NxN
                      _*      times infinity
                     +        plus
                 "1/~         the table with the coordinate triples:
              @:-             a - b and
         &.:*:                under square
       +/                     summed
         &.:*:                reverse square
[:<./@,                       flatten the table and get the min entry
\$\endgroup\$
2
\$\begingroup\$

Perl 5 -MList::Util=min,sum, 81 77 bytes

@KjetilS shaved 4 bytes.

sub f{min map{@b=@$_;map{sqrt sum map($_-$b[$j++%3])**2,@$_}@_[++$i..$#_]}@_}

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Nice answer. Can loose 4 bytes with: Try it online! No need to generalize to x dimensions when question says 3. \$\endgroup\$ – Kjetil S. Nov 22 '20 at 4:12
1
\$\begingroup\$

Charcoal, 22 bytes

I₂⌊ΦEθ⌊E…θκΣXEλ⁻ν§ιξ²κ

Try it online! Link is to verbose version of code. Takes n-dimensional vectors. Explanation:

     θ                  Input list
    E                   Map over vectors
         θ              Input list
        …               Truncate to length
          κ             Outer index
       E                Map over remaining vectors
              λ         Inner vector
             E          Map over coordinates
                 §ιξ    Coordinate of outer vector
                ν       Current coordinate
               ⁻        Difference
            X       ²   Squared
           Σ            Summed
      ⌊                 Take the minimum square sum
   Φ                 κ  Filter out minimum of empty list
  ⌊                     Take the minimum
 ₂                      Take the square root
I                       Cast to string
                        Implicitly print
\$\endgroup\$
1
\$\begingroup\$

C (gcc), 155 bytes

Takes a counted array of coordinates.

#define q(a)pow(c[j+a]-c[i+a],2)
i,j;float f(s,c,d,l)float*c,d,l;{for(l=-1,s*=3,i=0;i<s;i+=3)for(j=i+3;j<s;l<0|d<l&&(l=d),j+=3)d=sqrt(q(0)+q(1)+q(2));s=l;}

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Python 3, 82 bytes

f=lambda a,*b:[*b]and[min([sum((x-y)**2for x,y in zip(a,q))**.5for q in b]+f(*b))]

Try it online!


Python 3 with SciPy, 58 bytes

lambda*a:min(pdist(a))
from scipy.spatial.distance import*

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Factor, 67 bytes

[ dup [ v- norm ] cartesian-map [ head ] map-index concat infimum ]

Try it online!

Evaluates self-cartesian-product by vector distance, takes the lower triangular matrix (without diagonals), and evaluates the minimum of all values.

[                                ! anonymous lambda
  dup [ v- norm ] cartesian-map  ! self-cartesian-product by vector distance
  [ head ] map-index             ! for each array at index i, take first i elems
  concat infimum                 ! minimum of all values
]

Factor, 73 bytes

USE: math.combinatorics
[ 2 [ first2 v- norm ] map-combinations infimum ]

Try it online!

Factor has a built-in for generating combinations, but it is way too long (USE: math.combinatorics map-combinations is already 40 bytes).

\$\endgroup\$
0
\$\begingroup\$

Python 3, 79 bytes

I'm new here and not completely sure this follows the rules, LMK if this isn't valid!

lambda p:min(sum((a-b)**2for a,b in zip(x,y))**.5for x in p for y in p if x!=y)
\$\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.