zipfsong.py

#!/usr/bin/env python
# encoding: utf-8
# GistID: 4676361
import re
from operator import itemgetter


def get_tracks_by_popularity(no_tracks, track_provider, no_matches):
    '''
    Retrieves the most popular tracks.

    no_tracks: An integer specifying the number of tracks
    track_provider: A function returning a string on the form 'number_of_listens trackname'
                    each time it is executed. Expects tracks from an album in ascending order.
    no_matches: An integer specifying the expected number of (top popularity) results.
    '''
    '''
    Implementation notes:
    If we had optimized for efficiency rather than readability, we'd instead
    insert into a sorted datastructure and prune the lowest rated item from
    it if we already have as many items as we need.

    track_provider is used to increase testability (see Dependency Injection).
    In the real world we'd take an iterator, but adjusting my test cases (to
    return iterator.next rather than iterator) is more straight forward than
    wrapping input in an iterator.
    '''
    track_pattern = re.compile(r'^(?P<no_listens>\d+)\s(?P<track_name>\w+)$')
    tracks = []
    for i in reversed(xrange(1, no_tracks + 1)):
        m = track_pattern.match(track_provider())
        tracks.append((
            int(m.group('no_listens')) / i,  # Zipf adjusted popularity
            m.group('track_name')))

    # Built in sort is stable (preserves inherent order)
    sorted_tracks = sorted(tracks, key=itemgetter(0), reverse=True)
    return sorted_tracks[:no_matches]

if __name__ == '__main__':
    problem_specification = re.match(r'^(\d+)\s(\d+)$', input())
    no_tracks = problem_specification.group(0)
    no_matches = problem_specification.group(1)

    tracks = get_tracks_by_popularity(no_tracks, input, no_matches)
    for track in tracks:
        print track[1]