Program for finding longest run of zeros from a list of 100 random integers which are either 0 or 1

Question

I have written an answer to this question on Stack Overflow. To make it easier for you, I have copy-pasted the main question below.

Write a program that generates 100 random integers that are either 0 or 1.

Then find the:

• longest run of zeros, the largest number of zeros in a row. For instance, the longest run of zeros in [1,0,1,1,0,0,0,0,1,0,0] is 4.

Here is my answer to this:

import random

l = []

def my_list():
    for j in range(0,100):
        x = random.randint(0,1)
        l.append(x)
    print (l)
    return l

def largest_row_of_zeros(l):

    c = 0
    max_count = 0

    for j in l:
        if j == 0:
            c += 1
        else:
            if c > max_count:
                max_count = c
            c = 0
    return max_count

l = my_list()
print(largest_row_of_zeros(l))

NOTE: I have changed zero_count to max_count as it sounds more sensible. It keeps track of the max_count (or the largest number of zeros in a row) seen so far, and if a number is not 0, it resets the value of c (count) to 0 after updating the value of max_count with a new value.

So, I would like to know whether I could make this code shorter and more efficient.

Any help would be highly appreciated.

Answer 1

Generating a random list

Instead of defining a global variable that will be modified by your generation function, you should instead define that variable inside the function and return it. This way, you will be able to call my_list a second time without having l being 200 items long. It will make the code easier to test.

Also note that l as a variable name is a poor choice as certain fonts make it hard to distinguish from 1.

You also use the "empty list + for loop + append" pattern which can be converted to a more efficient list-comprehension:

def random_list(length=100):
    return [random.randint(0, 1) for _ in range(length)]

Note that, as suggested by @jpmc26 in the comments, and starting with Python 3.6, you can simplify further using random.choices:

def random_list(length=100):
    return random.choices((0, 1), k=length)

Finding the longest sequence

Your manual counting is not that bad, but usually counting a number of element can be done using either sum or len depending on the iterable at play. And finding the longest count can be delegated to max. So you just need to group zeroes together, count how much there is in each group and find the max of these counts.

itertools.groupby will happily do the grouping for you. But you won't be able to use len on the resulting groups, so you can add 1 for each element in said group.

Lastly, if there is no sequence of zeroes, you'll get no groups, and thus no lengths to take the maximum from, so you need to instruct max that the longest count is 0 in such cases:

def largest_row_of_zero(iterable):
    return max((sum(1 for _ in group) for value, group in itertools.groupby(iterable) if value == 0), default=0)

Testing code

Instead of putting the testing code at the top-level of the file, you should take the habit of using an if __name__ == '__main__': guard:

if __name__ == '__main__':
    l = random_list()
    print(l, largest_row_of_zero(l))

Answer 2

Bug in the posted code. If you try it with the input [1,0,1,0,0] you will get the answer 1. The first two lines in the else won't get executed if the sequence ends with the longest run of zeros. Correct code is

    for j in l:
        if j==0:
            c+=1
        else:
            c = 0
        if c > max_count:
            max_count = c

    return max_count

This can be considerably shortened and, I think, clarified:

    for j in l:
        c = c + 1 if j==0 else 0  # in other languages there is a ternary ?: op
        max_count = max( max_count, c) 

    return max_count

Two stylistic issues:

never use l as a variable name, it reads like 1. Lowercase l is best avoided altogether unless it's part of a word in a natural language. Similar arguments against O and Z which read like 0 and 2, but class-names starting with capital O or Z aren't so confusing.

The Pythonic form of initialization is c, max_count = 0, 0 (one line) provided the right-hand side, in particular, needs no real thought.

Answer 3

First the good: your code provides a testable function. So let's add some test code

def largest_row_of_zeros(l):
    '''
    >>> largest_row_of_zeros([])
    0
    >>> largest_row_of_zeros([0])
    1
    >>> largest_row_of_zeros([1])
    0
    >>> largest_row_of_zeros([0, 0])
    2
    >>> largest_row_of_zeros([0, 1])
    1
    >>> largest_row_of_zeros([1, 0])
    1
    >>> largest_row_of_zeros([1, 1])
    0
    '''

    c = 0
    max_count = 0
    for j in l:
        if j==0:
            c+=1
        else:
            if c > max_count:
                max_count = c
            c = 0
    return max_count


if __name__ == "__main__":
    import doctest
    doctest.testmod()

which gives

Python 3.6.1 (default, Dec 2015, 13:05:11)
[GCC 4.8.2] on linux
**********************************************************************
File "main.py", line 5, in __main__.largest_row_of_zeros
Failed example:
    largest_row_of_zeros([0])
Expected:
    1
Got:
    0
**********************************************************************
File "main.py", line 9, in __main__.largest_row_of_zeros
Failed example:
    largest_row_of_zeros([0, 0])
Expected:
    2
Got:
    0
**********************************************************************
File "main.py", line 13, in __main__.largest_row_of_zeros
Failed example:
    largest_row_of_zeros([1, 0])
Expected:
    1
Got:
    0
**********************************************************************
1 items had failures:
   3 of   7 in __main__.largest_row_of_zeros
***Test Failed*** 3 failures.

Here I use doctest. Another very common module is unittest. But you could also use simple assertions

if __name__ == "__main__":
    assert largest_row_of_zeros([0]) == 1

Have fun with testing.

Answer 4

To simplify the code you can:

1. You can use itertools.groupby to group the runs of 1s and 0s.
2. Filter if these groups to ones just containing zero.
3. Find the length of each group.
4. Return the maximum.

import itertools


def largest_row_of_zeros(l):
    return max(len(list(g)) for k, g in itertools.groupby(l) if k == 0)

---

In your code I would move the max aspect of the code out of the function and make the original a generator function. This allows you to use max to simplify the handling of the data.

def zero_groups(l):
    c = 0
    for j in l:
        if j == 0:
            c += 1
        else:
            yield c
            c = 0


def largest_row_of_zeros(l):
    return max(zero_groups(l))

Answer 5

Why check all the elements? You can jump ahead k+1 elements at a time once you find k in a row. After a while you're jumping huge amounts each iteration

def longest_run(arr, element):
   longest = 0
   start = 0
   non_match = -1
   while start < len(arr):
       if arr[start] == element:
           current_run = 1
           while current_run <= longest and arr[start - current_run] == element:
               current_run += 1
           if current_run > longest:
               while non_match + current_run + 1 < len(arr) and arr[non_match + current_run + 1] == element:
                   current_run += 1
               longest = current_run
               non_match = non_match + current_run
           else:
               non_match = start - current_run
       else:
           non_match = start
       start = non_match + longest + 1
   return longest

Answer 6

Another alternative: use RLE (run-length-encoding; with thanks to the comments for the correct naming), borrowed originally from a very simple data compressor of the same name.

Here's the code, albeit in the R language. (For non-users, 1L just forces integer-class, x[-k] means all of vector x except index 'k' )

Here's the base package code for the function rle(x) :
First line: generate logical vector of "is x[j] == x[j-1] ? "

  y <- x[-1L] != x[-n] ;

which returns index values when argument is TRUE, and c concatenates vectors (is.na just catches N/A values in case the input was skeevy)

 i <- c(which(y | is.na(y)), n) ; 

finally, create a structure. First element calculates run lengths by comparing sequential index values in i ; second element returns the value of the input vector every time that run terminates

  structure(list(lengths = diff(c(0L, i)), values = x[i]), class = "rle")

then add a line to find max(lengths[values==0]).

Answer 7

Just curious, but if the values list appears as a delimited collection, could you not just strip out the commas and split on the 1's to make an array and then reduce that? I haven't worked in python in 15 years (edit: updated to python) but this code seems to work:

# importing functools for reduce() 
import functools 

# initializing list 
inputString = "1,0,1,1,0,0,0,0,1,0,0"

#remove commas and split result into an array using 1 as the delimiter
inputString = inputString.replace(",", "")
resultArr = inputString.split("1");

# using reduce to compute maximum element from resulting array list 
longestString = (functools.reduce(lambda a,b : a if a >= b else b,resultArr)) 

#output the result
print ("The maximum element of the list is : ",end="") 
print (len(longestString)) 

Answer 8

Wanted to provide an alternate solution to the largest_row_of_zeros method. Easier to understand, but might not be as efficient.

def largest_row_of_zeros():
    asStr = reduce((lambda x, y: str(x) + str(y)), random_list())
    splitted = asStr.split("1")
    return len(max(splitted))

• Basically create a string "1010010101010"
• Split at 1s. "","0","00","0" ...
• Get length of longest string