18
\$\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\$
13
  • 3
    \$\begingroup\$ Restricting to a single language is hardly ever a good idea. Competition is within each language anyway \$\endgroup\$
    – Luis Mendo
    Nov 20, 2020 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, 2020 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\$ Nov 20, 2020 at 22:35
  • 5
    \$\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, 2020 at 2:59
  • 4
    \$\begingroup\$ Adding some more testcases would be nice. \$\endgroup\$
    – Razetime
    Nov 21, 2020 at 4:19

23 Answers 23

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
  • 2
    \$\begingroup\$ Looks like exactly right tool for this task. \$\endgroup\$ Nov 22, 2020 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\$ Nov 25, 2020 at 8:44
9
\$\begingroup\$

Wolfram Language (Mathematica), 33 bytes

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

Try it online!

\$\endgroup\$
7
\$\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\$
2
  • \$\begingroup\$ You can use ÆḊ as the norm if that helps you? Perhaps change ²§Ṃ½ to ÆḊṂ? \$\endgroup\$ Nov 21, 2020 at 3:14
  • 2
    \$\begingroup\$ @cairdcoinheringaahing Unfortunately ÆḊ doesn't vectorize, so I would have to use ÆḊ€Ṃ for the same number of bytes \$\endgroup\$ Nov 21, 2020 at 3:18
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\$
4
  • \$\begingroup\$ WLOG, let p<q \$\endgroup\$ Nov 21, 2020 at 3:12
  • \$\begingroup\$ My suggestion was to take p in range(q), removing the need for the not-equal check. \$\endgroup\$ Nov 21, 2020 at 3:21
  • \$\begingroup\$ Save two with enumerate, TIO. \$\endgroup\$ Nov 21, 2020 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\$ Nov 27, 2020 at 17:52
6
\$\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\$
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\$
2
  • 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, 2020 at 10:02
  • \$\begingroup\$ @Sisyphus - didn't knew about that syntax! \$\endgroup\$
    – vrintle
    Nov 21, 2020 at 13:20
4
\$\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\$

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\$
1
  • \$\begingroup\$ How did I not know there was a Math.hypot function?! Thanks! \$\endgroup\$
    – ashleedawg
    Feb 2, 2022 at 22:26
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\$

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
  • 2
    \$\begingroup\$ 74 bytes. Had the insane idea of getting rid of that lambda, and it happened to work \$\endgroup\$ Nov 21, 2020 at 20:18
  • 1
    \$\begingroup\$ I say very insane @Unrelated String! Thanks! \$\endgroup\$
    – AZTECCO
    Nov 21, 2020 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\$

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\$
1
  • \$\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, 2020 at 4:12
2
\$\begingroup\$

C (gcc), 155 147 bytes

Thanks to ceilingcat for -8 and an interesting (ab)use of hypot!

Takes a counted array of coordinates.

#define g(x)hypot(c[x+j]-c[x+i],
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;(j+=3)<s;l=l<0|d<l?d:l)d=g(2)g(1)g()0)));s=l;}

Try it online!

\$\endgroup\$
0
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\$

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\$
1
\$\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\$
1
\$\begingroup\$

Vyxal , 9 bytes

∪2ḋƛ÷∆d;g
∪           # Delete duplicates
 2ḋ         # All subsets of length 2
   ƛ÷∆d;    # Euclidean distance of every subset
        g   # Minimum

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

Fortran (GFortran), 206 182 148 144 bytes

function d(A,n);real A(3,n);t=0
do 5 k=1,n-1;do 5 j=2,n;s=0;do i=1,3;s=s+(A(i,k)-A(i,j))**2;enddo
5 if(t==0)t=s;if(s>0.and.t>s)t=s;d=sqrt(t);end

try it online!  148bytes  182bytes  206bytes

*line 1: sets up array, reads in data
*line 2: iterates over rows j,k, and sums the difference-squares
*line 3: initialises min distance t, compares current Euclidean squared distance s, taking the lower number, and ignores a distance of 0 (dupe points)

Saved 24 bytes by removing the allocate stuff and giving the array preset dimensions. A possible improvement for my other Fortran answers!
Saved another 34 bytes by using a subroutine and moving I/O to the main program. Replaced repeated enddos with a line number. Removed a placeholder variable q. Some inspiration taken from this fortran golf. I went looking for a useful intrinsic like NORM2 or HYPOT but couldn't find one for this problem.
Saved 4 bytes by replacing the subroutine with a function

\$\endgroup\$
2
  • \$\begingroup\$ Unfortunately there's a Heisenbug in this code, it occasionally spits out something insane. Looks like a floating point error. Can't pinpoint it \$\endgroup\$
    – roblogic
    Mar 6, 2023 at 23:41
  • \$\begingroup\$ Fixed it by setting t=0 in the first line. :) \$\endgroup\$
    – roblogic
    Mar 6, 2023 at 23:45
0
\$\begingroup\$

Julia 1.8, 52 bytes

a>b...=min(>(b...),@.splat(hypot)(b-[a])...)
>()=Inf

Try it online!

I feel like there is a better way but I can't figure it out. This will work for bigger dimensions as well

Julia 1.0, 53 bytes

a>b...=min(>(b...),(b.|>i->hypot(a-i...))...)
>()=Inf

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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