[Tutor] Sorting points on a 2D plane

[Kent Johnson]

On Wed, Oct 28, 2009 at 1:34 PM, Robert Berman <bermanrl at cfl.rr.com> wrote:
> Hi,
>
> I am working on a practice problem called 'POINTS' on the CodeChef
> site:http://www.codechef.com/problems/POINTS/. This simply wants the sum
> of the distances between a number of points on a 2 dimensional plane.
> Looking at the problem, the algorithm to define the sum of the distances
> between all the points is not really difficult.The challenge is in
> ordering the points given the following rules:
> 1)  You cannot move to a point with a lesser X value as compared to
> the  X value of the point you are on.
> 2)  For points having the same X value you need to visit the point with
> the greatest Y value before visiting the new point with the same X
> value. The least X takes precedence over the greatest Y.
>
> In any given test case there can be from 2 to 100000 points. The X and Y
> coordinates of each point will be between 0 and 10000 both inclusive.
>
> OK. The rules are established. A properly constructed algorithm will
> work for 10 points as well as 10000 points given it is properly
> constructed. My point of confusion is in ordering the points. Given a
> very simple example set of points:
>
> 0 5
> 0 1
> 0 2
> 2 1
> 2 3
> 5 2
> 5 1
>
>
> The arrangement should be,
>
> 0 5
> 0 2
> 0 1
> 2 3
> 2 1
> 5 2
> 5 1
>
> My solution is to first sort all the X values which would give me
> 0,0,0,2,2,5,5. I then will look at the Y values associated with the X
> value so I know that I am going to sort 3 Y values in reverse order for
> X = 0 and then append the Y value to each X point.

There are two easy ways to do this. One is similar to what you
describe, but you sort first by Y value (descending) then sort by X
value ascending. Python sort will preserve the order of equal items so
the X sort preserves the descending Y sort and you get what you want.

operator.itemgetter() is a convenience function for generating a key
extraction function.

In [3]: data
Out[3]: [[0, 5], [0, 1], [0, 2], [2, 1], [2, 3], [5, 2], [5, 1]]

In [4]: from operator import itemgetter

In [5]: data.sort(key=itemgetter(1), reverse=True)

In [6]: data
Out[6]: [[0, 5], [2, 3], [0, 2], [5, 2], [0, 1], [2, 1], [5, 1]]

In [7]: data.sort(key=itemgetter(0))

In [8]: data
Out[8]: [[0, 5], [0, 2], [0, 1], [2, 3], [2, 1], [5, 2], [5, 1]]


The other way to do this is to make a key that negates Y:

In [10]: data.sort(key=lambda (x,y): (x, -y))

In [11]: data
Out[11]: [[0, 5], [0, 2], [0, 1], [2, 3], [2, 1], [5, 2], [5, 1]]

Kent