On Wed, Oct 28, 2009 at 1:34 PM, Robert Berman <berma...@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 _______________________________________________ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
