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.

• Sᴀᴍ Onᴇᴌᴀ: Welcome to Code Review! I rolled back your last edit. After getting an answer you are not allowed to change your code anymore. This is to ensure that answers do not get invalidated and have to hit a moving target. If you have changed your code you can either post it as an answer (if it would constitute a code review) or ask a new question with your changed code (linking back to this one as reference). Refer to this post for more information
• Eric Lippert: What's your metric for efficiency? Shortest program, fastest execution, least memory? I mean, you're using Python and you have a tiny string; you're not going to see any user-visible efficiency wins in that scenario.
• jpmc26: What version of Python are you using?
• Justin: @jpmc26 - Python 3.7
• Carl Witthoft: what's wrong with the various rle codes? It's 2 or 3 lines, at least in R; then add a line to find max(runlength(val==0)) Here's the base package code: y <- x[-1L] != x[-n] ; i <- c(which(y | is.na(y)), n) ; structure(list(lengths = diff(c(0L, i)), values = x[i]), class = "rle")

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

• jpmc26: Looping over random.randint is 5 times slower (on my machine) than random.choices(POPULATION, k=100), with a global list POPULATION = [0, 1].
• Right leg: Pretty sure numpy.random.randint(0, 1, size=100) would make a good job here
• 301_Moved_Permanently: @jpmc26 right, but choices is only available in latest versions and not yet an automatism
• jpmc26: OP is using 3.7.
• 301_Moved_Permanently: @Rightleg And then using np.max on a variation of this answer. But I fear that, for such a small problem, you spend more time importing numpy than you'd be able to get as speedup from it.

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.

• Simon Forsberg: For discussions about whether or not this answer is a good answer for Code Review Stack Exchange, see this question on meta
• Justin: @stefan - Upvoted! I tried unit-testing and I am starting to get a hang of it. Thank you!

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]).

• Justin: Is the R language related to Python?
• AlexV: Welcome to Code Review! If you are not able to provide example code in the OP's requested language, it might be worth to write an informal/pseudo-code description of the algorithm if the algorithm itself is the core of your answer.
• Carl Witthoft: @AlexV Done -- I hope :-)
• Graipher: RLE stands for Run Length Encoding, AFAIK. There is no estimation involved.

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

• pacmaninbw: Is there someway you can change the wording of your answer so that it doesn't appear to be a question. Also can you add something about why the alternate solution you provided in another language would be an improvement. Please see this help page codereview.stackexchange.com/help/how-to-answer.
• Justin: @user200345 - You could try getting some help on converting this javascript code to python. This answer seems interesting to me.
• user200345: Updated my example. I was just looking to minimize the looping and lines of code that the other ideas had. This seems to work... Thanks for the comments guys.

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

• Justin: Yes, this also a very good solution to my question. Thanks for the answer!
• 301_Moved_Permanently: Instead of using reduce, ''.join(map(str, random_list())) is more idiomatic and understandable at a glance.
• Viktor Mellgren: @MathiasEttinger much nicer