Pages

HackerRank Sorting: Comparator

Write a comparator for a class Player that has, as data member, name (a string) and score (integer) so that sorting a list of players would put higher score on top. In case of a tie, names should be ordered in natural order.
I don't think this HackerRank problem was conceived with Python in mind, however there is some interest in implementing a solution in this language too.

As usual, I converted the proposed sample in a python test.
def test_provided_1(self):
    data = {'amy': 100, 'david': 100, 'heraldo': 50, 'aakansha': 75, 'aleksa': 150}
    players = []
    for k, v in data.items():
        players.append(Player(k, v))

    players.sort(key=cmp_to_key(Player.comparator))

    self.assertEqual(5, len(players))
    self.assertEqual('aleksa', players[0].name)
    self.assertEqual('amy', players[1].name)
    self.assertEqual('david', players[2].name)
    self.assertEqual('aakansha', players[3].name)
    self.assertEqual('heraldo', players[4].name)
The tie case, where amy and david have the same score, is already sorted. So I added a second test.
def test_ex_aequo(self):
    players = []
    for i in range(3):
        players.append(Player('Tom' + chr(ord('k') - i), 100))

    players.sort(key=cmp_to_key(Player.comparator))

    self.assertEqual(3, len(players))
    self.assertEqual('Tomi', players[0].name)
    self.assertEqual('Tomj', players[1].name)
    self.assertEqual('Tomk', players[2].name)
Here I have Tomk, Tomj, Tomi, same score but in reversed order.
Writing a comparator for the class Player shouldn't be difficult.
class Player:
    def __init__(self, name, score):
        self.name = name
        self.score = score

# ...

    def comparator(self, rhs):
        if self.score == rhs.score:
            return 1 if self.name > rhs.name else -1
        return 1 if self.score < rhs.score else -1
The interesting point is, do we really need it? If the comparator is commonly used by the client code for the class Player, yes, definetely. However, if this is not a standard requirement we should leave the user free to define his own comparator on the fly. Instead of using the functools cmp_to_key() function to convert a comparator in a suitable key function for sorting, we could use the operator attrgetter() function to specify on which attribute of the class the sort should act. Something like:
players.sort(key=attrgetter('name'))
players.sort(key=attrgetter('score'), reverse=True)
I am using the fact that python sort() is stable, so I firstly sort the collection by the second key of interest, in this case 'name', in natural order, and then I sort again the players by their score, this time in reversed order. The advantage of this approach is that it is much more flexible. Any user could decide how to sort its players, and the Player does not have to create a comparator each time a new way of sorting is required. I pushed to GitHub both the python script that I submitted to HackerRank and the unit test that includes also the attrgetter() variation.

No comments:

Post a Comment