2
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ 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). \$\endgroup\$
    – Blckknght
    Sep 10 '12 at 12:52
  • \$\begingroup\$ 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. \$\endgroup\$ Sep 10 '12 at 13:09
2
\$\begingroup\$

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
\$\endgroup\$
3
  • \$\begingroup\$ 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). \$\endgroup\$ Aug 28 '12 at 14:40
  • \$\begingroup\$ @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. \$\endgroup\$ Aug 28 '12 at 16:12
  • \$\begingroup\$ 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). \$\endgroup\$ Aug 28 '12 at 16:21
0
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\begingroup\$ The OP wanted consecutive repetitions, but Counter('abbbacada').most_common(1) returns [('a', 4)]. \$\endgroup\$ Aug 27 '12 at 9:30
  • \$\begingroup\$ I've updated my answer for you, @Gareth Rees. \$\endgroup\$
    – San4ez
    Aug 27 '12 at 13:12
  • \$\begingroup\$ According to the OP, longest_repetition([1, 2, 2, 3, 3, 3, 2, 2, 1]) should return 3, but your updated function returns 2. \$\endgroup\$ Aug 27 '12 at 13:23
  • \$\begingroup\$ Ok, I didn't notice consecutive word. So my solution doesn't work \$\endgroup\$
    – San4ez
    Aug 27 '12 at 13:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.