9
\$\begingroup\$

Your task is to write the shortest algorithm in a language of your choosing that accomplishes the following:

Given two matrices it must return the euclidean distance matrix. The euclidean distance between two points in the same coordinate system can be described by the following equation: \$D = \sqrt{ (x_2-x_1)^2 + (y_2-y_1)^2 + ... + (z_2-z_1)^2 }\$

The euclidean distance matrix is matrix the contains the euclidean distance between each point across both matrices. A little confusing if you're new to this idea, but it is described below with an example.

Below is an example:

a = [ 1.0  2.0  3.0; 
     -4.0 -5.0 -6.0; 
      7.0  8.0  9.0] #a 3x3 matrix

b = [1. 2. 3.] #a 1x3 matrix/vector

EuclideanDistance(a, b)
[   0.0;
  12.4499;
  10.3923]] # a 3x1 matrix/vector see rules for relaxed scoring

In a typical matrix representation of data, or coordinates, the columns represent variables. These could by \$\text{X,Y,Z...,J}\$ coordinates. Most people think in terms of \$\text{XYZ}\$ for 3-D space(3 columns), or \$\text{XY}\$ for 2D space(2 columns). Each row of the matrix represents a different point, or object. The points are what is being compared.

Using the example, matrix b is a single point at positions \$X= 1,Y = 2\$ and \$Z = 3\$. Matrix a contains three points in the same set of coordinates. The first point in a is the same as the point contained in b so the euclidean distance is zero(the first row of the result).

Not to be confusing, but, the matrices can be of any size(provided they fit into RAM). So a 7 by 11 matrix being compared with a 5 by 11 matrix is possible. Instead of X,Y,Z we would then have 11 coordinates(or columns) in both input matrices. The output would either be a 7x5 or a 5x7 matrix (depending on what way the points are compared). Make sense? Please ask for further clarifications.

Here's a 4 dimensional matrix example

a = [ [1. 2. 3. 4.]; 
      [ -4. -5. -6. -7. ]; 
      [ 6. 7. 8. 9. ] ] #a 3x4 matrix
b = [ [1. 2. 3. 4.]; 
      [1. 1. 1. 1.] ] #a 2x4 matrix

EuclideanDistance(a, b)
[  0.0    3.74166;
 16.6132 13.1909; 
 10.0    13.1909] #a 3x2 matrix

And another example for soundness:

a = [ [1.  2.];
     [ 3.3 4.4 ] ] #a 2x2 matrix

b = [ [5.5 6.6];
      [7.  8. ];
      [9.9 10.1] ] #a 3x2 matrix

EuclideanDistance(a, b)
[6.43506 8.48528 12.0341;
 3.11127 5.16236 8.72067] #a 2x3 matrix

Rules:

  1. If this function is included in your base language you can use it. You can import the direct function to do this as well. But you sacrifice style and honor! You will not be evaluated on style or honor but your street cred. will be - your call :P .

  2. Your submission should be evaluated in bytes. So save off your code to plain text and read the file size. Less bytes is best!

  3. No printing necessary, just a function, lambda, whatever, that computes this operation.

  4. Reasonable round-off error is fine, and the transpose of the correct solutions is also fine.

  5. This must work for matrices!

Happy golfing!

\$\endgroup\$
  • 3
    \$\begingroup\$ welcome to codegolf! i have a question. wikipedia describes the input as "a set of points". how are their coordinates encoded in the two matrices? \$\endgroup\$ – ngn Nov 17 at 14:04
  • 6
    \$\begingroup\$ Banning built-in functions is generally discouraged. Also, this previous challege is very similar \$\endgroup\$ – Luis Mendo Nov 17 at 14:11
  • \$\begingroup\$ Sorry everyone this is my first go at this! I'll clarify the post ASAP. \$\endgroup\$ – caseyk Nov 17 at 14:31
  • \$\begingroup\$ Okay I tried to clarify more, and adopted the rules to be more flexible. Please let me know if anything is still unclear or goes against tradition :) \$\endgroup\$ – caseyk Nov 17 at 14:44
  • \$\begingroup\$ @luis mendo - that previous challenge is similar but sufficiently different to me. This is an extension. We do not want to compare just 2 points, but a series of points across 2 sets. There are a lot of ways to accomplish this from brute force to elegant math! \$\endgroup\$ – caseyk Nov 17 at 15:06

17 Answers 17

12
\$\begingroup\$

Jelly, 5 bytes

_þ²§½

Try it online!

A dyadic link that takes a matrix as each argument and returns a matrix.

Explanation

_þ    | Outer table using subtract
  ²   | Square (vectorises)
   §  | Sum (vectorises)
    ½ | Square root (vectorises)
\$\endgroup\$
  • \$\begingroup\$ Woah, can you explain what this is doing in human terms? \$\endgroup\$ – caseyk Nov 17 at 18:25
  • 3
    \$\begingroup\$ Given a list of length a and a list of length b, creates an a*b matrix of each element from the first list minus each element from the second list. Since the elements are themselves lists, subtraction vectorizes by subtracting corresponding elements from its arguments and resulting in a list of the results. ² then squares every element of every sublist, § replaces each sublist with its sum, and ½ takes the square root of each sum. \$\endgroup\$ – Unrelated String Nov 18 at 0:36
6
\$\begingroup\$

Haskell, 45 43 bytes

a#b=[sqrt.sum.map(^2).zipWith(-)l<$>b|l<-a]

Try it online!

I've been trying pretty hard to make this pointfree, and I think it would be shorter but I cannot get it down for some reason.

\$\endgroup\$
6
\$\begingroup\$

R, 57 bytes

function(x,y)as.matrix(dist(rbind(x,y)))[a<-1:nrow(x),-a]

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Clever use of internal assignment! Sometimes I forget how fun R can be :) \$\endgroup\$ – caseyk Nov 18 at 0:40
5
\$\begingroup\$

Japt -m, 10 8 bytes

Takes b as the first input and a as the second.

V£MhUí-X

Try it

V£MhUí-X     :Implicit input of 2d-arrays b & V=a and map each U in b
V£           :Map each X in V
  Mh         :  Hypotenuse of
    Uí-X     :    U interleaved with X with each pair reduced by subtraction
\$\endgroup\$
  • \$\begingroup\$ 6 bytes? \$\endgroup\$ – Quintec Nov 17 at 16:35
  • \$\begingroup\$ Never heard of Japt before! How's come when I make the input the following, [[1.0 2.0 3.0][-4.0 -5.0 -6.0][7.0 8.0 9.0]] [[1.0 2.0 3.0][-4.0 -5.0 -6.0]] I get NaN, NaN, NaN ? \$\endgroup\$ – caseyk Nov 17 at 18:04
  • \$\begingroup\$ @caseyk, because it wasn't clear to me that b is a 2D-array. \$\endgroup\$ – Shaggy Nov 17 at 18:35
  • \$\begingroup\$ @caseyk, updated. Please update the challenge with that test case, plus a few more. \$\endgroup\$ – Shaggy Nov 17 at 18:37
  • \$\begingroup\$ I'm sorry that was my fault. I tried to clarify the prompt further. Nice updated solution! \$\endgroup\$ – caseyk Nov 17 at 18:38
5
\$\begingroup\$

J, 15 13 bytes

+/&.:*:@:-"1/

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ You can remove the parens for 13 bytes. \$\endgroup\$ – Bubbler Nov 18 at 13:26
  • \$\begingroup\$ Thanks Bubbler! \$\endgroup\$ – Traws Nov 18 at 13:32
4
\$\begingroup\$

Charcoal, 16 bytes

IEθEη₂ΣEιX⁻ν§λξ²

Try it online! Link is to verbose version of code. Outputs each element on its own line, double-spacing between rows. Explanation:

  θ                 First matrix
 E                  Map over rows
    η               Second matrix
   E                Map over rows
        ι           First matrix row
       E            Map over entries
           ν        First matrix entry
          ⁻         Subtract
             λ      Second matrix row
            §       Indexed by
              ξ     Inner index
         X     ²    Squared
      Σ             Summed
     ₂              Square rooted
I                   Cast to string
                    Implicitly printed
\$\endgroup\$
4
\$\begingroup\$

J, 12 bytes

+/&.:*: .-|:

Try it online!

How it works

+/&.:*: .-|:  Left: a, Right: b
          |:  Transpose b to get bT
        .     Customized matrix multiply:
         -      Subtract bT's columns from a's rows
  &.:*:         Square each element
+/              Sum
  &.:*:         Sqrt the result
\$\endgroup\$
3
\$\begingroup\$

05AB1E, 5 bytes

δ-nOt

Takes b as first input and a as second.

Try it online or verify all test cases.

Explanation:

δ      # Outer product; apply double-vectorized on the (implicit) input-lists:
 -     #  Subtract
  n    # Then square each inner value
   O   # Sum each inner list
    t  # And root those sums
       # (after which the result is output implicitly)
\$\endgroup\$
3
\$\begingroup\$

Wolfram Language (Mathematica), 24 bytes

Outer[Norm[#-#2]&,##,1]&

Try it online!

\$\endgroup\$
  • 2
    \$\begingroup\$ By the way, DistanceMatrix works the same way \$\endgroup\$ – ybeltukov Nov 19 at 9:32
3
\$\begingroup\$

Perl 6, 27 25 bytes

{.&[XZ-]>>²>>.sum X**.5}

Try it online!

Returns the distance matrix as a flat list.

Explanation

{                      }  # Anonymous block
 .&[XZ-]  # Cartesian product using zip-with-minus operator
        >>²  # Square each value
           >>.sum  # Sum of vector elements
                  X**.5  # Square root of each value
\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES6), 61 bytes

Takes input as (a)(b).

a=>b=>a.map(a=>b.map(b=>Math.hypot(...a.map((v,i)=>v-b[i]))))

Try it online!

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

Pari/GP, 52 bytes

(a,b)->matrix(#a~,#b~,i,j,sqrt(norml2(a[i,]-b[j,])))

Try it online!

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

R, 55 bytes

Inspired by @Nick Kennedy's answer, saving 2 bytes;

function(x,y)fields::rdist(rbind(x,y))[a<-1:nrow(x),-a]

(Sadly doesn't work on tio but does on a local R install with the fields package)

\$\endgroup\$
1
\$\begingroup\$

Julia, 45 bytes

Using the kernel trick! With broadcasting, starting from here(59 bytes)

D(X,Y)=sqrt.((sum(X.^2,dims=2).+sum(Y.^2,dims=2)').-2X*Y')

we can sneak by a bit here by condensing this down using ascii operators

58 bytes

D(X,Y)=.√((sum(X.^2,dims=2).+sum(Y.^2,dims=2)').-2X*Y')

and by adding a second function(could be a lambda or anonymous fn) 54 bytes

f(S)=sum(S.^2,dims=2)
D(X,Y)=.√(f(X).+f(Y)'.-2X*Y')

It may be tacky to submit an answer to your own question but I ensured I wouldn't win first and figured I'd share this approach. Maybe someone can condense it down further?

Update: Thanks to @lyndonwhite we can shave this down to 45 bytes after operator overloading!

!S=sum(S.^2,dims=2)
X|Y=.√(!X.+!Y'.-2X*Y')
\$\endgroup\$
  • \$\begingroup\$ shorter: !S=sum(S.^2,dims=2) X|Y=.√(!X.+!Y'.-2X*Y') \$\endgroup\$ – Lyndon White Nov 18 at 22:36
  • \$\begingroup\$ Submit it as an answer! :) \$\endgroup\$ – caseyk Nov 18 at 22:51
  • \$\begingroup\$ nah, it is just a trival change to yours. Update your answer and credit me \$\endgroup\$ – Lyndon White Nov 18 at 22:59
  • \$\begingroup\$ I don't know how to call that type of function from the REPL! never seen that before. \$\endgroup\$ – caseyk Nov 18 at 23:07
  • \$\begingroup\$ This is operator overloading, to call it enter in the REPL: for example rand(3,3) | rand(3,3) \$\endgroup\$ – Lyndon White Nov 18 at 23:51
1
\$\begingroup\$

Python (with numpy), 87 bytes

from numpy import *
f=lambda a,b:linalg.norm(r_[a][:,None,:]-r_[b][None,:,:],axis=2)
\$\endgroup\$
  • \$\begingroup\$ Thanks for the feedback! I have edited my submission to address the issues. \$\endgroup\$ – fakufaku Nov 20 at 8:21
1
\$\begingroup\$

Ruby, 59 bytes

->m,n{m.map{|i|n.map{|j|i.zip(j).sum{|a,b|(a-b)**2}**0.5}}}

Try it online!

\$\endgroup\$
1
\$\begingroup\$

APL(NARS), chars 35, bytes 70

{⊃√+/¨2*⍨⍵∘-¨(⍴⍵)∘⍴¨{a[⍵;]}¨⍳↑⍴a←⍺}

test:

  f←{⊃√+/¨2*⍨⍵∘-¨(⍴⍵)∘⍴¨{a[⍵;]}¨⍳↑⍴a←⍺}
  a1←3 3⍴ 1 2 3 ¯4 ¯5 ¯6 7 8 9
  b1←1 3⍴ 1 2 3
  a2←3 4⍴1 2 3 4 ¯4 ¯5 ¯6 ¯7 6 7 8 9
  b2←2 4⍴1 2 3 4 1 1 1 1
  a3←⊃(1 2)(3.3 4.4) 
  b3←⊃(5.5 6.6)(7 8)(9.9 10.1)
  a1 f b1
 0         
12.4498996 
10.39230485
  b1 f a1
0 12.4498996 10.39230485 
  a2 f b2
 0           3.741657387
16.61324773 13.19090596 
10          13.19090596 
  a3 f b3
6.435060217 8.485281374 12.03411816 
3.111269837 5.1623638    8.720665112

{⊃√+/¨2*⍨⍵∘-¨(⍴⍵)∘⍴¨{a[⍵;]}¨⍳↑⍴a←⍺}
                            ⍳↑⍴a←⍺    gets the number of rows and return 1..Nrows
                    {a[⍵;]}¨          for each number of row return the row
             (⍴⍵)∘⍴¨                  for each row build one matrix has same apparence of ⍵ (the arg of main function) and return it as a list of matrix
                                      so we have the same row that repeat itself until has the same nxm of the ⍵ arg
         ⍵∘-¨                         make the difference with the ⍵ arg
      2*⍨                             make the ^2
 ⊃√+/¨                                sum each doing √ and (in what seems to me) make as colums the element (that are rows) 
\$\endgroup\$
  • \$\begingroup\$ Can you explain what is happening? This is really cryptic - but cool! \$\endgroup\$ – caseyk Nov 20 at 11:35

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.