Coordinate Connecting

Input:

Ten unique integer coordinates, between (0,0) and (100,100).

Output:

The coordinates arranged in the order/an order such that a path drawn between the coordinates in that order is the shortest path possible.

This is code golf so the shortest code wins!

• Could we get some test cases? Jan 26, 2021 at 20:39
• I replaced 'line' with 'path'. Please clarify if this is not what you intended. Jan 26, 2021 at 20:53
• FYI this is like the Travelling salesman problem except you don't return to the initial point to complete the loop.
– xnor
Jan 26, 2021 at 21:00
• This is similar to the 'travelling salesman' problem, but it is not a duplicate of the previous code-golf 'travelling salesman' challenge (different format, different scoring). Jan 27, 2021 at 0:06
• @qazwsx I have some cases where floating point errors make the shortest path be shorter in one direction than in the reversed order, so no you'd have to count all the solutions to make sure. Case in point: (87, 3) (70, 20) (70, 22) (67, 39) (70, 44) (62, 89) (47, 59) (40, 40) (42, 31) (7, 15) has length 196.3336221458198 while the reverse (7, 15) (42, 31) (40, 40) (47, 59) (62, 89) (70, 44) (67, 39) (70, 22) (70, 20) (87, 3) has length 196.33362214581976. Jan 27, 2021 at 12:36

Wolfram Language (Mathematica), 40 bytes

MinimalBy[ArcLength@*Line]@*Permutations


Try it online! (7 points)

Times out for longer inputs.

Accepts a list of points with approximate-number coordinates.

To accept exact (Integer) input, +3 bytes:

MinimalBy[N@*ArcLength@*Line]@*Permutations


Try it online!

This is because MinimalBy uses Mathematica's canonical ordering, which compares objects structurally, rather than numerical ordering. Thus, for example, 3 is "less than" 1+Sqrt[2]. This is only an issue when using exact numbers, where the length can include Sqrts.

Husk, 12 11 bytes

Edit: -1 byte thanks to a tip from Leo

◄oṁ√Ẋδṁo□-P


Try it online (with only 8 points to avoid timing-out...)

How?

          P  # from all permutations of the input
◄o           # get the one that minimizes the result of
ṁ√         # sum of all the square roots of
Ẋ        # applying to all adjacent sets of coordinates
δṁo     # sum of all the
□-   # squares of the differences


import Data.List
f=head.sortOn(sum.(zipWith(\(x,y)(m,n)->sqrt$(x-m)^2+(y-n)^2)<*>tail)).permutations  Try it online! -7 by @xnor and @benrg • Can you remove the sqrt? - I think sort order will still be preserved Jan 26, 2021 at 21:45 • foldr seems like overkill. I'd expect zipWith and sum would be shorter. – xnor Jan 26, 2021 at 21:47 • f=head.sortOn(sum.(zipWith(\(x,y)(m,n)->sqrt$(x-m)^2+(y-n)^2)<*>tail)).permutations saves 7 bytes (as suggested by xnor). f=head.sortOn(\p->sum[sqrt\$(x-m)^2+(y-n)^2|(m,n)<-p|(x,y)<-tail p]).permutations saves another 3 bytes but requires -XParallelListComp and I don't know if that has to be counted. Jan 27, 2021 at 3:01
• @DigitalTrauma Not when you're summing it up afterward. 9+16 < 1+25, but √9+√16 > √1+√25. Jan 27, 2021 at 6:13

05AB1E, 10 bytes

œΣü-nOtO}н


Try it online! Times out on TIO with 10 coordinates.

Commented:

œ             # all permutations of the coordinates
Σ       }    # sort on ...
ü           #   for each pair of adjacent coordinates ...
-          #     take the element-wise difference
nOt       #   Euclidean norm for each difference (square, sum, square root)
O      #   sum all distances
н    # take the first element


JavaScript (ES6), 124 bytes

Processing 10 points on TIO takes about 35 seconds.

f=(a,X,Y,d=m=1/0,p=[])=>a.map(([x,y],i)=>f(a.filter(_=>i--),x,y,1/d&&d+Math.hypot(x-X,y-Y),[...p,[x,y]]))+a?o:d>m||(m=d,o=p)


Try it online!

Commented

A recursive function that tries all permutations of the input points, computing the length of the path for each of them and keeping track of the shortest one.

f = (                   // f is a recursive function taking:
a,                    //   a[] = input
X, Y,                 //   (X, Y) = coordinates of the previous point
d = m = 1 / 0,        //   d = total distance, m = minimum distance
//   (both initialized to +Infinity)
p = []                //   p[] = current path
) =>                    //
a.map(([x, y], i) =>    // for each point (x, y) at position i in a[]:
f(                    //   do a recursive call:
a.filter(_ => i--), //     with the i-th entry removed from a[]
x, y,               //     using (x, y) as the previous point
1 / d               //     set the distance d to 0 if this is the 1st point
&&                  //     otherwise:
d +               //       update d by adding
Math.hypot(       //       the Euclidean distance between
x - X, y - Y    //       the points (X, Y) and (x, y)
),                //
[...p, [x, y]]      //     append the point (x, y) to the path
)                     //   end of recursive call
)                       // end of map()
+ a ?                   // if a[] is not empty:
o                     //   just return o[]
:                       // else (complete path):
d > m                 //   unless the new distance is greater than m,
|| (m = d, o = p)     //   update m to d and set the output o[] to p[]


Java (JDK), 213 bytes

l->{double d=1e9,e;var r=l.clone();for(int i=0,z,x[]=new int[10];i<10;)if(x[i]<i){var t=l[z=i%2*x[i]++];l[z]=l[i];l[i]=t;for(e=z=i=0;z<9;)e+=l[z].distance(l[++z]);if(e<d){d=e;r=l.clone();}}else x[i++]=0;return r;}


Try it online!

It takes roughly 1 second to process.

Explanations

This is basically the iterative heap's algorithm with the distance computation and comparison integrated, because there are no native way to get permutations and because recursion in Java is expensive, byte-wise.

I'm using java.awt.geom.Point2D which has a distance(Point2D) method but it's not reflected in the code since I try by all means to avoid writing such a long class name to spare bytes. This is why I use l.clone() twice and var t.

• I can't verify it's correct because there are no test cases. Jan 27, 2021 at 11:52

Jelly, 10 bytes

Œ!ÆịạƝSƊÞḢ


Try it online!

Test case is 8 points arranged into a pseudo-regular octagon. TIO times out on 10 points, but the program should work in theory.

Explanation

Œ!ÆịạƝSƊÞḢ   Main monadic link
Œ!           Permutations
Þ    Sort by
Ɗ     (
Æị           Convert to complex numbers
ạ          Absolute difference
Ɲ           of each neighboring pair
S        Sum
Ɗ     )
Ḣ   First element


Python 2, 138, 135 bytes

Saved 3 Bytes due to a suggestion from Noodle9 to use lambda instead of print!

lambda a:min(permutations(a),key=lambda p:sum([sum([(p[i][j]-p[i+1][j])**2for j in 0,1])**.5for i in range(9)]))
from itertools import*


Essentially, this program loops through all possible permutations of the path and prints the path with the minimum length. The key argument of the min function is a lambda function that calculates the sum of the "distance" between consecutive points in p.

Try it online!

• You can save 3 bytes by making the whole answer a lambda like this. Jan 27, 2021 at 13:04
• Yeah, makes sense. But a sqrt is needed. I mistakenly believed it wasn't needed but I saw a comment explaining that it was. Jan 27, 2021 at 13:14
• You'll have to add sqrt to your original answer too so what does that have to do with my suggested golf? Jan 27, 2021 at 13:16
• @Noodle9 Just added it right before I read your comment. Sorry, I wasn't trying to criticise. I was just saying that I wouldn't be able to use your exact answer. Jan 27, 2021 at 13:18
• np.That's an interesting point about the order of the sums of the sqrts being different to the order of the sums. Jan 27, 2021 at 13:33