# Shortest code to sort walking points

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

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:

• @Rusher Why are closed circuits guaranteed to intersect? (the OP's example doesn't) – Martin Ender Apr 17 '14 at 22:48
• 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 '14 at 23:27
• @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 '14 at 0:26
• @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 '14 at 4:15
• 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 '14 at 9:02

## 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@%] &]


• 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 Ender Apr 18 '14 at 11:08
• @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 '14 at 11:18
• How convenient! :) – Martin Ender Apr 18 '14 at 11:33

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


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


# 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  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  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
}


## 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


Example 1 is now differently sorted:

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
}

• +1 for including a circuit variant (I suspect the requirement will eventually find its way into the question again, once Rusher responds) – Martin Ender Apr 18 '14 at 0:34

# 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. # 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}}  • Wouldn't just Sort do the same thing? – swish Apr 17 '14 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 '14 at 23:27 • But sort does the same thing, sorting by x and y. – swish Apr 17 '14 at 23:28 • You can save seven characters by renaming StringSplit again and using infix syntax Sort@(s=StringSplit)@%~s~"\n". – Martin Ender Apr 18 '14 at 0:33 • @swish Well thanks for telling me about 'Sort'. That shortened the code a lot... – kukac67 Apr 18 '14 at 0:37 # PHP (175109 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.

# 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.