Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

The challenge is to, given a list of points, sort in a way that, when they are connected in this order, they never intersect.

Input format (read from stdin):

X Y
1 2
3 4
5 6
...

Output should be the same as input, but sorted.

Rules:

  • You can start from any point.
  • The last point must be same as first one, making a close circuit.
  • It should be done considering the Cartesian grid.
  • You may assume that the input points do not all lie on a single line.
  • The endpoints of each line do not count as intersecting.

For further help:

diagram

share|improve this question
2  
@Rusher Why are closed circuits guaranteed to intersect? (the OP's example doesn't) –  Martin Büttner Apr 17 at 22:48
2  
If it's just a line, then an elementary solution is sorting by first and second coordinate, a default sort for pairs, so it's just sorting and nothing more fancy here. –  swish Apr 17 at 23:27
3  
@Rusher: A closed circuit does not necessarily self-intersect, except in the trivial sense that the start and end points are the same: the "good" picture in the post shows a non-self-intersecting closed circuit. Further, without the closed circuit requirement, this challenge becomes completely trivial; I can solve it in six characters of GolfScript, five of which are I/O handling. –  Ilmari Karonen Apr 18 at 0:26
4  
@Rusher: You could equally well claim that any two successive lines in the path must always intersect, since they share an endpoint. Such "intersections" (of which the "intersection" at the endpoints of a closed loop is one example) are trivial, and cannot be counted in any meaningful definition of a "non-self-intersecting path". (Anyway, if you really want to be pedantic, just define each line segment to include its starting point but not its endpoint. Problem solved.) –  Ilmari Karonen Apr 18 at 4:15
2  
The question as edited deserved to be closed as too trivial. Edits should not remove all the challenge from a problem. I've therefore rolled it back. If anyone disagrees, I'll willingly discuss this on meta. –  Peter Taylor Apr 18 at 9:02
show 12 more comments

6 Answers 6

Mathematica - 20 30 chars

Just the sorting part

SortBy[%, ArcTan @@ # &]

Whole testing code, that consists of generating 100 random points and plotting the line

RandomReal[{-10, 10}, {100, 2}];
SortBy[%, ArcTan @@ # &];
ListPlot@% /. 
 Point[p_] :> {EdgeForm[Dashed], FaceForm[White], Polygon[p], 
   PointSize -> Large, Point[p]}

+26 chars

If you demand proper input/ouput, then

"0 0
 4 4
 0 4
 4 0";
Grid@SortBy[%~ImportString~"Table", ArcTan @@ # &]

+2 chars

Just adding N@

Grid@SortBy[%~ImportString~"Table", ArcTan @@ N @ # &]

because above code works only on real numbers and not on integers due to Mathematica's weird behavior when sorting symbolic expressions

N@Sort[{ArcTan[1], ArcTan[-2]}]
Sort[N@{ArcTan[1], ArcTan[-2]}]

{0.785398, -1.10715}
{-1.10715, 0.785398}

EDIT I just realized if the points are not around the origin it won't work, so it also requires shift to the center of points

SortBy[%, ArcTan @@ N[# - Mean@%] &]

enter image description here

share|improve this answer
    
I was trying to find a counter-example where you have three points in line with the "centre of mass". They would all have the same arctangent, so there order is not determined by your code, which might lead to their connections overlapping. However, your snippet always seems to sort those cases from inside out, although their ArcTan result is actually identical down to the last bit. Do you know why that is? (here is such a case if you want to play around with it {{1, 2}, {2, 4}, {3, 6}, {-5, 5}, {-6, -12}, {5, -5}}). –  Martin Büttner Apr 18 at 11:08
1  
@m.buettner From SortBy documentation: If some of the f[e_i] are the same, then the canonical order of the corresponding e_i is used. –  swish Apr 18 at 11:18
    
How convenient! :) –  Martin Büttner Apr 18 at 11:33
    
+1 for noticing the need of centering. –  Heiko Oberdiek Apr 18 at 13:09
add comment

The question has changed, thus this answer contains different versions, with and without a closed path.

Perl, open path, 69 bytes

print"@$_$/"for sort{$$a[0]<=>$$b[0]||$$a[1]<=>$$b[1]}map{[/\S+/g]}<>

Each point is expected in STDIN as line, with the coordinates separated by white space.

Any number format is supported that Perl interprets as number (including floating point numbers).

Example:

0 0
4 4
0 4
4 0
-2 1
2 -2
2 4
3.21 .56
.035e2 -7.8
0 2

Output:

-2 1
0 0
0 2
0 4
2 -2
2 4
3.21 .56
.035e2 -7.8
4 0
4 4

Result

Ungolfed:

print "@$_$/" for            # print output line      
    sort {                   # sort function for two points $a and $b
        $$a[0] <=> $$b[0]    # compare x part                           
        || $$a[1] <=> $$b[1] # compare y part, if x parts are identical
    }
    map { [/\S+/g] }         # convert input line to point as array reference
    <>                       # read input lines               

Circuit variants

In the first question version, there was a connection between the last and first point to make a circuit.

Center is not existing point, 253 bytes

This variant can fail, if the center is one of the points, see example 3.

Edits:

  • In his answer swish noticed, that the points should be centered around the origin to ensure a cross-free circuit:

    • Sorting needs transformed coordinates.
    • The original string representation of the numbers need to be kept for the output.
  • Bug fix: the special case for the negative x-axis had included the positive x-axis.

print"$$_[2] $$_[3]$/"for sort{($X,$Y)=@$a;($x,$y)=@$b;(!$X&&!$Y?-1:0)||!$x&&!$y||!$Y&&!$y&&$X<0&&$x<0&&$X<=>$x||atan2($Y,$X)<=>atan2($y,$x)||$X**2+$Y**2<=>$x**2+$y**2}map{[$$_[0]-$M/$n,$$_[1]-$N/$n,@$_]}map{$n++;$M+=$$_[0];$N+=$$_[1];$_}map{[/\S+/g]}<>

Example 1:

4 4
-2 0
2 0
1 1
4 0
-2 -2
-3 -1
1 -2
3 0
2 -4
0 0
-1 -2
3 3
-3 0
2 3
-5 1
-6 -1

Output 1:

0 0
-6 -1
-3 -1
-2 -2
-1 -2
1 -2
2 -4
2 0
3 0
4 0
1 1
3 3
4 4
2 3
-5 1
-3 0
-2 0

Result circuit 1

Example 2:

Testing number representation and coordinate transformation.

.9e1 9
7 7.0
8.5 06
7.77 9.45

Output 2:

7 7.0
8.5 06
.9e1 9
7.77 9.45

Result circuit 2

Ungolfed:

print "$$_[2] $$_[3]$/" for sort { # print sorted points
    ($X, $Y) = @$a;                # ($X, $Y) is first point $a
    ($x, $y) = @$b;                # ($x, $y) is second point $b
    (!$X && !$Y ? -1 : 0) ||       # origin comes first, test for $a
    !$x && !$y ||                  # origin comes first, test for $b
    !$Y && !$y && $X < 0 && $x < 0 && $X <=> $x ||
        # points on the negative x-axis are sorted in reverse order
    atan2($Y, $X) <=> atan2($y, $x) ||
        # sort by angles; the slope y/x would be an alternative,
        # then the x-axis needs special treatment
    $X**2 + $Y**2 <=> $x**2 + $y**2
        # the (quadratic) length is the final sort criteria
}
map { [ # make tuple with transformed and original coordinates
        # the center ($M/$n, $N/$n) is the new origin
        $$_[0] - $M/$n,  # transformed x value
        $$_[1] - $N/$n,  # transformed y value
        @$_              # original coordinates
] }
map {
    $n++;                # $n is number of points
    $M += $$_[0];        # $M is sum of x values
    $N += $$_[1];        # $N is sum of y values
    $_                   # pass orignal coordinates through
}
map {                    # make tuple with point coordinates
    [ /\S+/g ]           # from non-whitespace in input line
}
<>                       # read input lines

Without restriction, 325 bytes

print"$$_[2] $$_[3]$/"for sort{($X,$Y)=@$a;($x,$y)=@$b;atan2($Y,$X)<=>atan2($y,$x)||$X**2+$Y**2<=>$x**2+$y**2}map{[$$_[0]-$O/9,$$_[1]-$P/9,$$_[2],$$_[3]]}map{$O=$$_[0]if$$_[0]>0&&($O>$$_[0]||!$O);$P=$$_[1]if$$_[1]>0&&($P>$$_[1]||!$P);[@$_]}map{[$$_[0]-$M/$n,$$_[1]-$N/$n,@$_]}map{$n++;$M+=$$_[0];$N+=$$_[1];$_}map{[/\S+/g]}<>

In the previous version, the center is put at the begin and the last points on the negative axis are sorted in reverse order to get cross-free to the center again. However, this is not enough, because the last points could lie on a different line. Thus the following example 3 would fail.

This is fixed by moving the centered origin a little to the top and right. Because of centering, there must be at least one point with positive x value and a point with positive y value. Thus the minimums of the positive x and y values are taken and reduced to a ninth (a half or third could be enough). This point cannot be one of the existing points and is made the new origin.

The special treatments of the origin and the negative x-axis can be removed, because there is any point that lies on the new origin.

Example 3:

-2 -2
-1 -1
-2 2
-1 1
2 -2
1 -1
2 2
1 1
0 0

Output 3:

0 0
-1 -1
-2 -2
1 -1
2 -2
1 1
2 2
-2 2
-1 1

Result 3

Example 1 is now differently sorted:

Result 1

Ungolfed:

print "$$_[2] $$_[3]$/" for sort { # print sorted points        
    ($X, $Y) = @$a;                # ($X, $Y) is first point $a 
    ($x, $y) = @$b;                # ($x, $y) is second point $b
    atan2($Y, $X) <=> atan2($y, $x) ||
        # sort by angles; the slope y/x would be an alternative,
        # then the x-axis needs special treatment
    $X**2 + $Y**2 <=> $x**2 + $y**2
        # the (quadratic) length is the final sort criteria
}  
map { [ # make tuple with transformed coordinates
    $$_[0] - $O/9, $$_[1] - $P/9,  # new transformed coordinate
    $$_[2],  $$_[3]                # keep original coordinate
] }
map {
    # get the minimum positive x and y values 
    $O = $$_[0] if $$_[0] > 0 && ($O > $$_[0] || !$O);         
    $P = $$_[1] if $$_[1] > 0 && ($P > $$_[1] || !$P);
    [ @$_ ]               # pass tuple through
}
map { [ # make tuple with transformed and original coordinates
        # the center ($M/$n, $N/$n) is the new origin
        $$_[0] - $M/$n,  # transformed x value
        $$_[1] - $N/$n,  # transformed y value 
        @$_              # original coordinates
] }  
map {
    $n++;                # $n is number of points
    $M += $$_[0];        # $M is sum of x values 
    $N += $$_[1];        # $N is sum of y values
    $_                   # pass orignal coordinates through
}
map {                    # make tuple with point coordinates
    [ /\S+/g ]           # from non-whitespace in input line
} 
<>                       # read input lines
share|improve this answer
    
+1 for including a circuit variant (I suspect the requirement will eventually find its way into the question again, once Rusher responds) –  Martin Büttner Apr 18 at 0:34
add comment

GolfScript, 6 / 13 chars (open path; 49 chars for closed path)

Note: This solution is for the current version of the challenge as edited by Rusher. It is not a valid solution to the original challenge, which required that the line from last point back to the first also should not intersect the other lines. The 49-char solution below is valid for the original challenge too.

~]2/$`

The code above assumes that the output can be in any reasonable format. If the output format has to match the input, the following 13-character version will do:

~]2/${" "*n}/

Explanation:

  • ~ evaluates the input, turning it into a list of numbers; ] gathers these numbers into an array, and 2/ splits this array into two-number blocks, each representing one point.

  • $ sorts the points in lexicographic order, i.e. first by the x-coordinate and then, if there are ties, by the y-coordinate. It is easy to show that this will guarantee that the lines drawn between the points do not intersect, as long as the path does not need to loop back to the beginning.

  • In the 5-character version, ` stringifies the sorted array, producing the native string representation of it (e.g. [[0 0] [0 4] [4 0] [4 4]]). In the longer version, {" "*n}/ joins the coordinates of each point by a space, and appends a newline.

Online demo: short version / long version.


Ps. Here's a 49-char solution to the original problem, where the path is required to be closed:

~]2/$.0=~:y;:x;{~y-\x-.+.@9.?*@(/\.!@@]}${" "*n}/

It works in a similar manner as Heiko Oberdiek's Perl solution, except that, instead of using trig functions, this code sorts the points by the slope (yy0) / (xx0), where (x0, y0) is the point with the lowest x-coordinate (and lowest y-coordinate, if several points are tied for lowest x).

Since GolfScript doesn't support floating point, the slopes are multiplied by the fixed constant 99 = 387420489. (If that's not enough precision, you can replace the 9 with 99 to turn the multiplier into 9999 ≈ 3.7 × 10197.) There's also some extra code to break ties (by the x coordinate) and to ensure that, as in Heiko's solution, points with x = x0 are sorted last, in decreasing order by y coordinate.

Again, here's an online demo.

share|improve this answer
add comment

Mathematica, 35

This works for ANY list of unique points.

s=StringSplit;Grid@Sort@s@s[%,"\n"]

You say "read from stdin", so for Mathematica, I'm assuming "read from last output".

Input (last output):

"0 0
4 4
0 4
4 0"

Output:

0 0
0 4
4 0
4 4

If input and output needn't be in the "newlines" format, this can shrink to 6 characters:

Sort@%

taking the last output as input, assuming the last output is a 2-dimensional array.

Input (last output):

{{0,0},{4,4},{0,4},{4,0}}

Ouput:

{{0,0},{0,4},{4,0},{4,4}}
share|improve this answer
    
Wouldn't just Sort do the same thing? –  swish Apr 17 at 23:23
    
@swish I'm using SortBy so I can easily sort with respect to the "x" values and the "y" values. –  kukac67 Apr 17 at 23:27
    
But sort does the same thing, sorting by x and y. –  swish Apr 17 at 23:28
    
You can save seven characters by renaming StringSplit again and using infix syntax Sort@(s=StringSplit)@%~s~"\n". –  Martin Büttner Apr 18 at 0:33
    
@swish Well thanks for telling me about 'Sort'. That shortened the code a lot... –  kukac67 Apr 18 at 0:37
show 2 more comments

PHP (175 109 100 chars)

while(fscanf(STDIN,'%d%d',$a,$b))$r[]=sprintf('%1$04d %2$04d',$a,$b);sort($r);echo implode('
',$r);

OK, I admit, PHP isn't the best golfing language, but I gave it a try.

Here's some sample output:

0000 0000
0000 0004
0004 0000
0004 0004

What is does is it puts the information into a string formatted with previous zeroes.
Then it just sorts the points textually.
P.S. It fails on numbers above 9999.

share|improve this answer
add comment

Python 2.7, 42B

import sys
print''.join(sorted(sys.stdin))

Couldn't really be simpler; read STDIN, sort lines, print lines. NB I've respected the exact I/O requirements of the question, but if you're manually populating STDIN you need to press CTRL+d to end input.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.