[Tutor] Consecutive_zeros

[Martin A. Brown]

Hello there,

> For example, given the string:
> Its failing on below test case
> 
> print(consecutive_zeros("0"))
> It should return 1. Returns 0
> I get the max(length) as 1, if I print it separately

There are many ways to this sort of thing, and I think Mats has 
already responded that your function (below) looks good aside from 
your boundary case.  Of course, boundary cases are one of the things 
that software quality assurance and test tooling are there to help 
you discover.

If your code never hits the boundary condition, then you'll always 
sleep soundly.  But, as an excellent systems programmer I worked 
with used to say:  "I like to think that my software inhabits a 
hostile universe."  It's a defensive programming mindset that I have 
also tried to adopt.

> def consecutive_zeros(string):
>     zeros = []
>     length = []
>     result = 0
>     for i in string:
>         if i == "0":
>             zeros.append(i)        else:
>             length.append(len(zeros))
>             zeros.clear()
>             result = max(length)
>     return result

> Goal: analyze a binary string consisting of only zeros and ones. Your code
> should find the biggest number of consecutive zeros in the string.

I took a look at the problem statement and I thought immediately of 
the itertools.groupby function [0].  While this is not generally one 
of the Python modules that you'd encounter at your first exposure to 
Python, I thought I'd mention it to illustrate that many languages 
provide advanced tooling that allow you to solve these sorts of 
computer science problems. There's no substitute for knowing how to 
write or apply this yourself. There's also value in knowing what 
other options are available to you in the standard library.  (Like 
learning when to use a rasp, chisel, smoothing plane or sandpaper 
when working with wood:  All work.  Some work better in certain 
situations.)

The itertools module is fantastic for dealing with streams and 
infinite sequences.

This function (and others in this module) useful for stuff like your 
specific question, which appears to be a string that probably fits 
neatly into memory.

  def consecutive_zeros(s):
      zcount = 0
      for char, seq in itertools.groupby(s):
          if char != '0':
              continue
          t = len(list(seq))
          zcount = max((t, zcount))
      return zcount, s

I am mentioning this particular function not because I have any 
specific deep experience with the itertools module, but to share 
another way to think about approaching any specific problem.  I have 
never regretted reading in the standard libraries of any language 
nor the documentation pages of any system I've ever worked on.

In this case, your question sounded to me closer to a "pure" 
computer science question and in the vein of functional programming 
and itertools jumped directly into my memory.

One exercise I attempt frequently is to move a specific question, 
e.g. "count the number of zeroes in this string sequence" to a more 
general case of "give me the size of the longest repeated 
subsequence of items".  This often requires keeping extra data (e.g.
the collections.defaultdict) but means you sometimes have other 
answers at the ready.  In this case, you could also easily answer 
the question of 'what is the longest subsequence of "1"s' as well.

And, in keeping with the notion of testing* (as Mats has suggested) 
and worrying about boundaries, I include a toy program (below) that 
demonstrates the above function as well as an alternate, generalized 
example, as well as testing the cases in which the result is known 
ahead of time.

Best of luck,

-Martin

   * Note, what I did is not quite proper testing, but is a simple 
     illustration of how one could do it.  Using assert is a 
     convenient way to work with test tooling like py.test.

 [0] https://docs.python.org/3/library/itertools.html#itertools.groupby


#! /usr/bin/python
#
# -- response to Consecutive_zeros question

import os
import sys
import random
import itertools
import collections


def consecutive_items(s):
    counts = collections.defaultdict(int)
    for item, seq in itertools.groupby(s):
        counts[item] = max(sum(1 for _ in seq), counts[item])
    return counts, s


def consecutive_char_of_interest(s, item):
     counts, _ = consecutive_items(s)
     return counts[item], s


def consecutive_zeros(s):
    return(consecutive_char_of_interest(s, '0'))


# def consecutive_zeros(s):
#      zcount = 0
#      for char, seq in itertools.groupby(s):
#          if char != '0':
#              continue
#          t = len(list(seq))
#          zcount = max((t, zcount))
#      return zcount, s


def report(count, sample):
    sample = (sample[:50] + '...') if len(sample) > 75 else sample
    print('{:>9d} {}'.format(count, sample))


def fail_if_wrong(sample, correct):
    count, _ = consecutive_zeros(sample)
    assert count == correct
    report(count, sample)
    return count, sample


def cli(fin, fout, argv):
    fail_if_wrong('a', 0)          # - feed it "garbage"
    fail_if_wrong('Q', 0)          # - of several kinds
    fail_if_wrong('^', 0)          # - punctuation! What kind of planet?!
    fail_if_wrong('1', 0)          # - check boundary
    fail_if_wrong('0', 1)          # - check boundary
    fail_if_wrong('01', 1)         # - oh, let's be predictable
    fail_if_wrong('001', 2)
    fail_if_wrong('0001', 3)
    fail_if_wrong('00001', 4)
    fail_if_wrong('000001', 5)
    fail_if_wrong('0000001', 6)
    fail_if_wrong('00000001', 7)
    fail_if_wrong('000000001', 8)
    n = 37
    fail_if_wrong('0' * n, n)      # - favorite number?
    n = 1024 * 1024                # - some big number
    fail_if_wrong('0' * n, n)
    n = random.randint(9, 80)
    fail_if_wrong('0' * n, n)      # - let the computer pick

    report(*consecutive_zeros(''.join(random.choices('01', k=60))))
    report(*consecutive_zeros(''.join(random.choices('01', k=60))))
    report(*consecutive_zeros(''.join(random.choices('01', k=1024))))
    report(*consecutive_zeros(''.join(random.choices('01', k=1024*1024))))

    return os.EX_OK


if __name__ == '__main__':
    sys.exit(cli(sys.stdin, sys.stdout, sys.argv[1:]))

# -- end of file



-- 
Martin A. Brown
http://linux-ip.net/