pythonic longest repetition

Question

I put together this code to for the Udacity cs101 exam. It passes the test, but I feel their must be a more elegant way to manage this problem. Some help from a module (like itertools).

Question 8: Longest Repetition

Define a procedure, longest_repetition, that takes as input a list, and returns the element in the list that has the most consecutive repetitions. If there are multiple elements that have the same number of longest repetitions, the result should be the one that appears first. If the input list is empty, it should return None.

def longest_repetition(alist):
    alist.reverse()
    largest = []
    contender = []
    if not alist:
        return None
    for element in alist:
        if element in contender:
            contender.append(element)
            if len(contender) >= len(largest):
                largest = contender
        else:
            contender = []
            contender.append(element)

    if not largest:
        return contender[0]
    else:
        return largest[0]

#For example,

print longest_repetition([1, 2, 2, 3, 3, 3, 2, 2, 1])
# 3

print longest_repetition(['a', 'b', 'b', 'b', 'c', 'd', 'd', 'd'])
# b

print longest_repetition([1,2,3,4,5])
# 1

print longest_repetition([])
# None

Answer 1

First, I'll comment on your code, and then I'll discuss a more "Pythonic" way to do it using features in the Python standard library.

1. There's no docstring. What does the function do?

2. You start out by reversing the list. This is a destructive operation that changes the list. The caller might be surprised to find that their list has changed after they called longest_repetition! You could write alist = reversed(alist) instead, but it would be even better if you didn't reverse the list at all. By changing the >= test to > you can ensure that the earliest longest repetition is returned, while still iterating forwards over the input.

3. You build up a list contender that contains the most recent series of repetitions in the input. This is wasteful: as contender gets longer, the operation element in contender takes longer. Since you know that this list consists only of repetitions of an element, why not just keep one instance of the element and a count of how many repetitions there have been?

4. You only update largest when you found a repetition. That means that if there are no consecutive repetitions in the input, largest will never be updated. You work around this using an if statement at the end to decide what to return. But if you always updated largest (whether you found a repetition or not) then you wouldn't need the if statement.

5. By suitable choice of initial values for your variables, you can avoid the if not alist special case. And that would allow your function to work for any Python iterable, not just for lists.

So let's apply all those improvements:

def longest_repetition(iterable):
    """
    Return the item with the most consecutive repetitions in `iterable`.
    If there are multiple such items, return the first one.
    If `iterable` is empty, return `None`.
    """
    longest_element = current_element = None
    longest_repeats = current_repeats = 0
    for element in iterable:
        if current_element == element:
            current_repeats += 1
        else:
            current_element = element
            current_repeats = 1
        if current_repeats > longest_repeats:
            longest_repeats = current_repeats
            longest_element = current_element
    return longest_element

---

So is there a more "Pythonic" way to implement this? Well, you could use itertools.groupby from the Python standard library. Perhaps like this:

from itertools import groupby

def longest_repetition(iterable):
    """
    Return the item with the most consecutive repetitions in `iterable`.
    If there are multiple such items, return the first one.
    If `iterable` is empty, return `None`.
    """
    try:
        return max((sum(1 for _ in group), -i, item)
                   for i, (item, group) in enumerate(groupby(iterable)))[2]
    except ValueError:
        return None

However, this code is not exactly clear and easy to understand, so I don't think it's actually an improvement over the plain and simple implementation I gave above.

Answer 2

Gareth's itertools method can be written a bit better:

def iterator_len(iterator):
    return sum(1 for _ in iterator)

def longest_repetition(iterable):
    """
    Return the item with the most consecutive repetitions in `iterable`.
    If there are multiple such items, return the first one.
    If `iterable` is empty, return `None`.
    """
    try:
        return max(groupby(iterable), 
            key = lambda (key, items): iterator_len(items))[0]
    except ValueError:
        return None

Answer 3

Take a look at collections.Counter. It will do your work for you.

>>> Counter(['a', 'b', 'b', 'b', 'c', 'd', 'd', 'd']).most_common(1)
[('b', 3)]

UPD. Full example:

from collections import Counter

def longest_repetition(alist):
    try:
        return Counter(alist).most_common(1)[0][0]
    except IndexError:
        return None

If you ask more question, please ask.