Euclidean Distance Between Two Matrices

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!

• 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? – ngn Nov 17 '19 at 14:04
• Banning built-in functions is generally discouraged. Also, this previous challege is very similar – Luis Mendo Nov 17 '19 at 14:11
• Sorry everyone this is my first go at this! I'll clarify the post ASAP. – caseyk Nov 17 '19 at 14:31
• 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 :) – caseyk Nov 17 '19 at 14:44
• @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! – caseyk Nov 17 '19 at 15:06

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)

• Woah, can you explain what this is doing in human terms? – caseyk Nov 17 '19 at 18:25
• 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. – Unrelated String Nov 18 '19 at 0:36

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.

R, 57 bytes

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


Try it online!

• Clever use of internal assignment! Sometimes I forget how fun R can be :) – caseyk Nov 18 '19 at 0:40

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

• 6 bytes? – Quintec Nov 17 '19 at 16:35
• 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 ? – caseyk Nov 17 '19 at 18:04
• @caseyk, because it wasn't clear to me that b is a 2D-array. – Shaggy Nov 17 '19 at 18:35
• @caseyk, updated. Please update the challenge with that test case, plus a few more. – Shaggy Nov 17 '19 at 18:37
• I'm sorry that was my fault. I tried to clarify the prompt further. Nice updated solution! – caseyk Nov 17 '19 at 18:38

J, 15 13 bytes

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


Try it online!

• You can remove the parens for 13 bytes. – Bubbler Nov 18 '19 at 13:26
• Thanks Bubbler! – Traws Nov 18 '19 at 13:32

Charcoal, 16 bytes

ＩＥθＥη₂ΣＥιＸ⁻ν§λξ²


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

  θ                 First matrix
Ｅ                  Map over rows
η               Second matrix
Ｅ                Map over rows
ι           First matrix row
Ｅ            Map over entries
ν        First matrix entry
⁻         Subtract
λ      Second matrix row
§       Indexed by
ξ     Inner index
Ｘ     ²    Squared
Σ             Summed
₂              Square rooted
Ｉ                   Cast to string
Implicitly printed


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


05AB1E, 5 bytes

δ-nOt


Takes b as first input and a as second.

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)


Wolfram Language (Mathematica), 24 bytes

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


Try it online!

• By the way, DistanceMatrix works the same way – ybeltukov Nov 19 '19 at 9:32

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


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!

Pari/GP, 52 bytes

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


Try it online!

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)

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')

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

Python (with numpy), 87 bytes

from numpy import *
f=lambda a,b:linalg.norm(r_[a][:,None,:]-r_[b][None,:,:],axis=2)

• Thanks for the feedback! I have edited my submission to address the issues. – fakufaku Nov 20 '19 at 8:21

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!

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)

• Can you explain what is happening? This is really cryptic - but cool! – caseyk Nov 20 '19 at 11:35