# pythonic longest repetition

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
``````
-

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.

-
I realize this has been up for a while, but I wanted to point out that there's a further small optimization that could be made in the "easy to understand" version. You can move the `if` block that checks `current_repeats > longest_repeats` into the preceding `else` block (before the code that's already there), and avoid it running every time the longest repeated sequence gets longer. You will also need to do the test at the end of the loop, though, just before returning (in case the longest consecutive repetition is at the end). –  Blckknght Sep 10 '12 at 12:52
Yes, you could do that, but you'd have to balance the optimization against the duplication of the test. I came down on the side of simplicity here, but I can understand someone else deciding the other way. –  Gareth Rees Sep 10 '12 at 13:09

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
``````
-
The use of `key` is a definite improvement—good spot! But the use of `len(list(items))` is not an improvement on `sum(1 for _ in items)` as it builds an unnecessary temporary list in memory that is then immediately thrown away. This makes the memory usage O(n) instead of O(1). –  Gareth Rees Aug 28 '12 at 14:40
@GarethRees you're right. I feel like using sum isn't the most clear, and I really wish python had a builtin function for it. I made myself feel a bit better by putting it into a function. –  Winston Ewert Aug 28 '12 at 16:12
Yes, it's a frustrating omission from `itertools`. Such a function gets proposed from time to time (e.g. here) but the opinion of the Python developers seems to be that such a function would be a bad idea because it would lead to an infinite loop if passed an infinite generator (e.g. here). –  Gareth Rees Aug 28 '12 at 16:21

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
``````

The OP wanted consecutive repetitions, but `Counter('abbbacada').most_common(1)` returns `[('a', 4)]`. –  Gareth Rees Aug 27 '12 at 9:30
According to the OP, `longest_repetition([1, 2, 2, 3, 3, 3, 2, 2, 1])` should return `3`, but your updated function returns `2`. –  Gareth Rees Aug 27 '12 at 13:23