8
\$\begingroup\$

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!

\$\endgroup\$
10
  • 13
    \$\begingroup\$ Could we get some test cases? \$\endgroup\$
    – xigoi
    Jan 26, 2021 at 20:39
  • 1
    \$\begingroup\$ I replaced 'line' with 'path'. Please clarify if this is not what you intended. \$\endgroup\$
    – Dingus
    Jan 26, 2021 at 20:53
  • 4
    \$\begingroup\$ FYI this is like the Travelling salesman problem except you don't return to the initial point to complete the loop. \$\endgroup\$
    – xnor
    Jan 26, 2021 at 21:00
  • 3
    \$\begingroup\$ 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). \$\endgroup\$ Jan 27, 2021 at 0:06
  • 2
    \$\begingroup\$ @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. \$\endgroup\$ Jan 27, 2021 at 12:36

8 Answers 8

6
\$\begingroup\$

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.

\$\endgroup\$
5
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

Haskell, 107 100 bytes

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

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Can you remove the sqrt? - I think sort order will still be preserved \$\endgroup\$ Jan 26, 2021 at 21:45
  • 2
    \$\begingroup\$ foldr seems like overkill. I'd expect zipWith and sum would be shorter. \$\endgroup\$
    – xnor
    Jan 26, 2021 at 21:47
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – benrg
    Jan 27, 2021 at 3:01
  • 5
    \$\begingroup\$ @DigitalTrauma Not when you're summing it up afterward. 9+16 < 1+25, but √9+√16 > √1+√25. \$\endgroup\$
    – xigoi
    Jan 27, 2021 at 6:13
3
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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[]
\$\endgroup\$
0
2
\$\begingroup\$

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.

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

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

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!

\$\endgroup\$
5
  • \$\begingroup\$ You can save 3 bytes by making the whole answer a lambda like this. \$\endgroup\$
    – Noodle9
    Jan 27, 2021 at 13:04
  • \$\begingroup\$ Yeah, makes sense. But a sqrt is needed. I mistakenly believed it wasn't needed but I saw a comment explaining that it was. \$\endgroup\$
    – qwatry
    Jan 27, 2021 at 13:14
  • \$\begingroup\$ You'll have to add sqrt to your original answer too so what does that have to do with my suggested golf? \$\endgroup\$
    – Noodle9
    Jan 27, 2021 at 13:16
  • \$\begingroup\$ @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. \$\endgroup\$
    – qwatry
    Jan 27, 2021 at 13:18
  • \$\begingroup\$ np.That's an interesting point about the order of the sums of the sqrts being different to the order of the sums. \$\endgroup\$
    – Noodle9
    Jan 27, 2021 at 13:33

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.