23
\$\begingroup\$

Euclidean distance between two lattice points \$(x_1, y_1)\$ and \$(x_2, y_2)\$ on a plane is: \$\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}\$.

Imagine now a lattice N x N replicated infinitely many times next to itself. The two points \$(x_1, y_1)\$ and \$(x_2, y_2)\$ also get replicated. Euclidean distance on a torus is then the minimal distance between all these points.

Input: x1, y1, x2, y2 and N. Arrange these in any convenient order or way (e.g. represent \$(3,4)\$, \$(5,6)\$ as 4 arguments 3, 4, 5, 6, two complex numbers \$3+4j\$, \$5+6j\$, a list [[3,4],[5,6]], a list [3,4,5,6] or anything that's not too bizarre). Coordinates must be integers in the range 0..N-1 or 1..N. The size of the torus (N) must be an integer (you can assume 1 < N < 100).

Output: a real number, with precision better than \$1\%\$.

Test cases:

x1 y1 x2 y2 N Result
1 0 1 1 2 1.00
2 3 2 3 4 0.00
0 0 2 2 4 2.83
0 9 1 1 10 2.24
9 0 9 8 10 2.00
12 34 56 78 99 62.23
0 0 98 98 99 1.41
\$\endgroup\$
0

20 Answers 20

10
\$\begingroup\$

R, 40 bytes

\(a,b,N)sum(pmin((d=a-b)%%N,-d%%N)^2)^.5

Attempt This Online!

Input the two points as vectors a and b.

\$\endgroup\$
2
  • 3
    \$\begingroup\$ \(a,b,N)sum(((a-b+N/2)%%N-N/2)^2)^.5 (36 bytes) is a small improvement on this idea based on finding the distance from (a - b + N/2) to (N/2, N/2) \$\endgroup\$ May 8, 2023 at 3:59
  • \$\begingroup\$ @DamianPavlyshyn - that's more than just an improvement, I think, and a good byte-save, too. Please post it yourself and take all the credit! Well done! \$\endgroup\$ May 8, 2023 at 6:29
7
\$\begingroup\$

K (ngn/k), 18 16 bytes

-2 bytes thanks to @ngn.

Function taking input as f[N;(x1,y1;x2,y2)].

{%+/&/x*x!:y-|y}

Try it online!

y-|y Subtract the reversed list of points from the list of points. This results in component-wise distances in both directions.
x!: Take all values mod N. Updates x.
x* Square each value.
&/ take the element-wise minimum between positive and negative difference.
%+/ Sum, then take the square root.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ shorter if you take ((x1;y1);(x2;y2)) as a single argument: {%+/&/x*x!:y-|y} \$\endgroup\$
    – ngn
    May 17, 2023 at 13:21
6
\$\begingroup\$

Jelly,  8  7 bytes

ạ/«ạ¥ÆḊ

A dyadic Link that accepts the coordinates as a pair of pairs* of integers** on the left and the size as an integer** on the right and yields the Euclidean toroidal distance.

* I guess this will work in any integer number of dimensions too.

** Will work with floats too (up to floating point inaccuracies, of course).

Try it online! Or see the test-suite.

How?

\$\text{Distance} = \sqrt{\left (|x_1-x_2| \land ||x_1-x_2|-N| \right )^2 + \left (|y_1-y_2| \land ||y_1-y_2|-N| \right )^2}\$

ạ/«ạ¥ÆḊ - Link: Coordinates=[[x1, y1], [x2, y2]]; Size=N
 /      - reduce (Coordinates) by:
ạ       -   ([x1, y1]) absolute difference ([x2, y2])
              -> D = [|x1-x2|, |y1-y2|]
    ¥   - last two links as a dyad - f(D, N):
   ạ    -   (D) absolute difference (N) (vectorises)
              -> D2 = [||x1-x2|-N|, ||y1-y2|-N|]
  «     -   (D) minimum (D2) (vectorises)
              -> M = [min(|x1-x2|, ||x1-x2|-N|), min(|y1-y2|, ||y1-y2|-N|)]
     ÆḊ - norm = vector_length = square_root(sum(squared_values)))
            -> (min(|x1-x2|, ||x1-x2|-N|)^2 + min(|y1-y2|, ||y1-y2|-N|)^2)^(1/2)
\$\endgroup\$
6
\$\begingroup\$

julia, 43 bytes

Notice that for any point \$x\$, the \$N\$-toroidal distance from \$x\$ to \$(N/2, N/2)\$ is the Euclidean distance from \$\mathrm{mod}(x, N)\$ to \$(N/2, N/2)\$.

Hence, we can find the \$N\$-toroidal distance between \$a\$ and \$b\$ by computing the Euclidean distance from \$\mathrm{mod}(a-b+(N/2, N/2), N)\$ to \$(N/2, N/2)\$.

d(a,b,N)=sum(@. (mod1(a-b+N/2,N)-N/2)^2)^.5

Attempt This Online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Welcome to Code Golf, and nice answer! \$\endgroup\$ May 9, 2023 at 2:00
5
\$\begingroup\$

Wolfram Language (Mathematica), 38 33 bytes

nNorm[Min[#,n-#]&/@Abs[#-#2]]&

Thanks to @att!
Where stands for \[Function]

Try it online!

Input: [N][{x1,y1}, {x2,y2}]

\$\endgroup\$
1
  • \$\begingroup\$ 33 inputting [N][{x1,y1}, {x2,y2}] \$\endgroup\$
    – att
    May 7, 2023 at 19:35
5
\$\begingroup\$

05AB1E, 11 10 bytes

αDŠ-ø€ßnOt

Try it online!

-1 thanks to @KevinCruijssen

Explanation

αDŠ-ø€ßnOt  # Implicit input
α           # Absolute difference between the first two inputs
 D          # Duplicate this pair
  Š         # Triple swap so the input is second
   -        # Subtract the absolute difference between the
            # first two inputs from the third input
    ø       # Zip this with the absolute difference
     ۧ     # Minimum of each inner pair
       n    # Square each
        O   # Sum the list
         t  # Square root the sum
            # Implicit output
\$\endgroup\$
5
  • \$\begingroup\$ D³s- can be DŠ- or ©-® for -1 byte. \$\endgroup\$ May 8, 2023 at 9:18
  • \$\begingroup\$ @KevinCruijssen thanks, updated. Btw, is there a command for nOt (Jelly and Vyxal have it, but I don't see one in 05AB1E). \$\endgroup\$
    – The Thonnu
    May 8, 2023 at 9:21
  • 1
    \$\begingroup\$ Unfortunately not. I've used nOt multiple times in other challenges before, so a 2-byte builtin for it would have been nice to have indeed.. \$\endgroup\$ May 8, 2023 at 9:30
  • 1
    \$\begingroup\$ @KevinCruijssen Don't you mean "Unfortunately nOt"? \$\endgroup\$
    – Neil
    May 8, 2023 at 11:46
  • \$\begingroup\$ @Neil Haha, I guess so indeed. :D \$\endgroup\$ May 8, 2023 at 11:55
4
\$\begingroup\$

JavaScript (ES7), 64 bytes

Expects (x1,y1,x2,y2,N).

(x,y,X,Y,n)=>((g=d=>(d*=d)<(q=n-d**.5)*q?d:q*q)(X-x)+g(Y-y))**.5

Try it online!

Commented

( x, y,       // (x, y) = coordinates of the 1st point
  X, Y,       // (X, Y) = coordinates of the 2nd point
  n           // n = size of the torus
) => (        //
  ( g = d =>  // g is a helper function taking d
    (d *= d)  // square d
    <         // and compare it with
    ( q =     // q defined as:
      n -     //   the difference between n and
      d ** .5 //   the square root of d (which is the
              //   absolute value of the original d)
    ) * q     // multiplied by itself
    ?         // if d is less than q²:
      d       //   return d
    :         // else:
      q * q   //   return q²
  )(X - x) +  // 1st call to g with d = X - x
  g(Y - y)    // 2nd call to g with d = Y - y
) ** .5       // square root of the sum
\$\endgroup\$
4
\$\begingroup\$

Factor, 52 bytes

[ v- 2dup n-v rot '[ [ _ rem ] map ] bi@ vmin norm ]

Try it online!

Takes input as N { x1 y1 } { x2 y2 }.

                   ! 10 { 9 0 } { 9 8 }
v-                 ! 10 { 0 -8 }
2dup               ! 10 { 0 -8 } 10 { 0 -8 }
n-v                ! 10 { 0 -8 } { 10 18 }
rot                ! { 0 -8 } { 10 18 } 10
'[ [ _ rem ] map ] ! { 0 -8 } { 10 18 } [ [ 10 rem ] map ]
bi@                ! { 0 2 } { 0 8 }   (apply quot to both points)
vmin               ! { 0 2 }
norm               ! 2.0
\$\endgroup\$
4
\$\begingroup\$

Python, 63 59 57 bytes

Edit: -4 bytes thanks to @Neil and -2 thanks to @xnor.

lambda x,y,X,Y,N:abs((x-X+(k:=N/2))%N-k+((y-Y+k)%N-k)*1j)

Attempt This Online!

Port of Damian Pavlyshyn's comment.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Bah, I was toying with that approach for my Charcoal answer but it turned out to be longer; I didn't think to try other languages. \$\endgroup\$
    – Neil
    May 8, 2023 at 11:44
  • \$\begingroup\$ abs(((x-X+(k:=N/2))%N-k)+((y-Y+k)%N-k)*1j) saves 4 bytes. \$\endgroup\$
    – Neil
    May 8, 2023 at 11:48
  • \$\begingroup\$ You can remove one of the paren pairs: TIO \$\endgroup\$
    – xnor
    May 8, 2023 at 19:35
  • \$\begingroup\$ Indeed, thanks! \$\endgroup\$
    – pajonk
    May 8, 2023 at 19:51
3
\$\begingroup\$

Ruby, 60 56 bytes

->a,b,n{(-4..4).map{|c|(a-b-n*(c%3-1+1i*c/=3)).abs}.min}

Try it online!

How?

Input as complex numbers.

(a-b).abs is the distance between a and b on the complex plane. We have to move b into the 8 adjacent spaces, and calculate distance between the original a and the new b, then take the minimum.

Iterating from -4 to +4 we get the offset table using c%3-1 for the real part, and c/3 for the imaginary part:

+-----+-----+-----+
| -4  | -3  | -2  |
|-1-i | -i  | 1-i |
+-----+-----+-----+
| -1  |  0  |  1  |
| -1  |  0  |  1  |
+-----+-----+-----+
|  2  |  3  |  4  |
|-1+i |  i  | 1+i |
+-----+-----+-----+
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Looks really obfuscated. How does it work? \$\endgroup\$
    – anatolyg
    May 8, 2023 at 9:00
2
\$\begingroup\$

Python3, 79 bytes:

lambda x,y,X,Y,n:(min(abs(x-X),n-abs(x-X))**2+min(abs(y-Y),n-abs(y-Y))**2)**0.5

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ 76 bytes \$\endgroup\$
    – The Thonnu
    May 7, 2023 at 16:34
  • \$\begingroup\$ @TheThonnu A(min(A(x-X),n-A(x-X))+min(A(y-Y),n-A(y-Y))*1j) is only 70 bytes. \$\endgroup\$
    – Neil
    May 8, 2023 at 11:51
2
\$\begingroup\$

Thunno 2, 9 bytes

-AD⁶_Ọ²Sƭ

Explanation

-AD⁶_Ọ²Sƭ  # Implicit input
-A         # Absolute difference between first two inputs
  D        # Duplicate the pair
   ⁶_      # Subtract from the third input
     Ọ     # Elementwise dyadic minimum
      ²    # Square each
       S   # Sum the list
        ƭ  # Square root the sum
           # Implicit output

Screenshot

Screenshot

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

Vyxal , 10 9 bytes

ε:?$-Þ∵∆/

Thanks @TheThonnu!

Try it Online!

Input: [x1, y1] \n [x2, y2] \n N

\$\endgroup\$
3
  • \$\begingroup\$ There is a strong conjecture that any Vyxal code can be golfed into 3.1415926 bytes, so please edit it! \$\endgroup\$
    – lesobrod
    May 7, 2023 at 16:13
  • 3
    \$\begingroup\$ 9 bytes (or 7.875 bytes in Vyncode) \$\endgroup\$
    – The Thonnu
    May 7, 2023 at 16:18
  • \$\begingroup\$ 8 bytes (jelly port) \$\endgroup\$
    – emanresu A
    May 9, 2023 at 20:51
2
\$\begingroup\$

Charcoal, 19 bytes

I₂ΣEθ⌊X⁻↔⁻ι§ηκ⟦⁰ζ⟧²

Try it online! Link is to verbose version of code. Takes input as two pairs of coordinates and a number. Explanation:

    θ               First input
   E                Map over coordinates
          ι         Corrent coordinate
         ⁻          Subtract
            η       Second input
           §        Indexed by
             κ      Current index
        ↔           Absolute value
       ⁻            Vectorised subtract
              ⟦  ⟧  List of
               ⁰    Literal integer `0` and
                ζ   Third input
      X             Vectorised raise to power
                  ² Literal integer `2`
     ⌊              Take the minimum
  Σ                 Take the sum
 ₂                  Take the square root
I                   Cast to string
                    Implicitly print
\$\endgroup\$
2
\$\begingroup\$

SAS 4GL, 71 bytes (or 57)

  1. The answer (in short, just "the point"):
data;set;a=abs(x-p);b=abs(y-q);d=sqrt((a><(N-a))**2+(b><(N-b))**2);run;

  1. The answer and all details [with details ;-)]:

Input:

data input;
/* x1 y1 x2 y2 N Result */
input x y p q n r;
cards;
1   0   1   1   2   1.00
2   3   2   3   4   0.00
0   0   2   2   4   2.83
0   9   1   1   10  2.24
9   0   9   8   10  2.00
12  34  56  78  99  62.23
0   0   98  98  99  1.41
;
run;
/* to print input data */
proc print data=input;
run;

Immediately after "input code" run: Code:

data;set;a=abs(x-p);b=abs(y-q);d=sqrt((a><(N-a))**2+(b><(N-b))**2);run;

The:

data;set;...run;

part is mandatory for every SAS 4GL code so if we select only the "calculation" part:

a=abs(x-p);b=abs(y-q);d=sqrt((a><(N-a))**2+(b><(N-b))**2);

it is 57 bytes ;-)

Code formatted:

data;
  set;
  a = abs(x - p);
  b = abs(y - q);

  d = sqrt(                   
            (a >< (N - a))**2 
          + (b >< (N - b))**2 
          );
run;

Comments:

  • i><j is minimum of i and j, i**j is i to power j
  • sqrt(expression) is the same number of bytes as (expression)**.5,
  • brackets arounf N-b are necessary because >< takes precedence over substraction,
  • result dataset is named DataX where X is the first integer not yet used for naming default dataset.

Log:

1    data;set;a=abs(x-p);b=abs(y-q);d=sqrt((a><(N-a))**2+(b><(N-b))**2);run;

NOTE: There were 7 observations read from the data set WORK.INPUT.
NOTE: The data set WORK.DATA4 has 7 observations and 9 variables.
NOTE: DATA statement used (Total process time):
      real time           0.00 seconds
      cpu time            0.00 seconds


\$\endgroup\$
3
  • 1
    \$\begingroup\$ This might be easier to parse/score if you put the scored part of the code at the top and put the rest under a separate heading. Nice answer \$\endgroup\$
    – mousetail
    May 9, 2023 at 11:36
  • \$\begingroup\$ I do not know SAS, but it feels like this needs to accept the input (either as a function or as a full program). Maybe making it a macro would do that? At present it looks like a snippet. Perhaps there will be no other SAS answers, but requiring answers to take input levels the playing field for if/when another SAS answer comes along. \$\endgroup\$ May 9, 2023 at 13:43
  • \$\begingroup\$ In SAS 4GL a dataset is the standard "data carrier" for data steps. It is like R or Python dataframe. The set statement takes it as an argument (in this case set; [only set and semicolon] means "take the last dataset created"). The same as in R you would write a function but without writing a vector of values, in SAS you would write a data step taking dataset as input but without the process of creating the dataset. \$\endgroup\$ May 9, 2023 at 14:16
2
\$\begingroup\$

Scala, 137 96 bytes

Saved 41 bytes thanks to the comment of @corvus_192


Try it online!

import math._
(x,y,X,Y,n)=>sqrt(pow(min(abs(x-X),n-abs(x-X)),2)+pow(min(abs(y-Y),n-abs(y-Y)),2))
\$\endgroup\$
1
2
\$\begingroup\$

Japt, 13 bytes

íaV ËmDaWÃx²¬

Try it

íaV ËmDaWÃx²¬     :Implicit input of arrays U=[x1,y1] & V=[x2,y2] and integer W=N
í V               :Interleave U & V
 a                :  Reducing each pair by absolute difference
    Ë             :Map each D
     m            :  Minimum with
      DaW         :    Absolute difference of D & W
         Ã        :End map
          x       :Reduce by addition after
           ²      :  Squaring each
            ¬     :Square root
\$\endgroup\$
1
\$\begingroup\$

Arturo, 57 bytes

$=>[x:abs&-&y:abs&-&n:&sqrt+^min@[x,n-x]2(min@[y,n-y])^2]

Try it

Takes input as x1 x2 y1 y2 N.

$=>[                 ; a function
    x:abs&-&         ; assign absolute value of first arg minus second arg to x
    y:abs&-&         ; assign absolute value of third arg minus fourth arg to y
    n:&              ; assign fifth arg to n
    (min@[y,n-y])^2  ; minimum of y and n-y squared
    ^min@[x,n-x]2    ; minimum of x and n-x squared
    +                ; add
    sqrt             ; square root
]                    ; end function
\$\endgroup\$
1
\$\begingroup\$

BQN, 17 bytes

{√+´×˜⌊´𝕨|-⊸⋈-´𝕩}

Try it at BQN REPL

{√+´×˜⌊´𝕨|-⊸⋈-´𝕩}  # function taking N as left arg (𝕨)
                    # and [[x1,y1],[x2,y2]] as right arg (𝕩):
              -´𝕩   # vectorized fold-subtract: [x1-x2,y1-y2]
          -⊸⋈      # joined to negative of itself: [[x1-x2,y1-y2],[x2-x1],[y2-y1]]
        𝕨|          # all modulo N
      ⌊´            # vectorized fold-minimum
    ט              # vectorized multiply each element by itself
  +´                # sum (fold-addition)
 √                  # square-root
\$\endgroup\$
0
\$\begingroup\$

Scala, 104 bytes

Golfed version. Try it online!

(a,b,N)=>{val d=a.zip(b).map{case(p,q)=>(p-q+N)%N};math.sqrt(d.map(r=>math.pow(math.min(r,N-r),2)).sum)}

Ungolfed version. Try it online!

object Main {

  def main(args: Array[String]): Unit = {
    println(toroidal_dist(Array(1, 0), Array(1, 1), 2))    // 1
    println(toroidal_dist(Array(2, 3), Array(2, 3), 4))    // 0
    println(toroidal_dist(Array(0, 0), Array(2, 2), 4))    // 2.83
    println(toroidal_dist(Array(0, 9), Array(1, 1), 10))   // 2.24
    println(toroidal_dist(Array(9, 0), Array(9, 8), 10))   // 2
    println(toroidal_dist(Array(12, 34), Array(56, 78), 99)) // 62.23
    println(toroidal_dist(Array(0, 0), Array(98, 98), 99)) // 1.41
  }

  def toroidal_dist(a: Array[Int], b: Array[Int], N: Int): Double = {
    val d = a.zip(b).map { case (ai, bi) => (ai - bi + N) % N }
    math.sqrt(d.map(di => math.pow(math.min(di, N - di), 2)).sum)
  }
}
\$\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.