2
\$\begingroup\$

Problem:

Find the longest sequence consisting only of 0's, and the longest sequence consisting only of 1's?

Solution:

import sys

longestSequenceForOne = None
startIndexForOne = None
longestSequenceForZero = None
startIndexForZero = None

def setLongestSequence(array, longestSequence, startIndex):
    global longestSequenceForOne
    global startIndexForOne
    global longestSequenceForZero
    global startIndexForZero

    if array[startIndex] == 1:
        if longestSequenceForOne == None or longestSequenceForOne < longestSequence:
            longestSequenceForOne = longestSequence
            startIndexForOne = startIndex
    elif array[startIndex] == 0:
        if longestSequenceForZero == None or longestSequenceForZero < longestSequence:        
            longestSequenceForZero = longestSequence
            startIndexForZero = startIndex

def findLongestSequence(array, size):
    """
    Find the longest sequence of 0's and 1's
    """
    longestSequence = 1
    beginIndex = None
    index = 1
    startIndex = 0
    sameElementCount = 1

    while (index < size):
        if array[index] == array[index-1]:
            sameElementCount += 1
        elif sameElementCount > longestSequence:
            longestSequence = sameElementCount
            startIndex = index - sameElementCount
            sameElementCount = 1
            setLongestSequence(array, longestSequence, startIndex)
        else:
            sameElementCount = 1
        index += 1
    if sameElementCount > longestSequence:
        longestSequence = sameElementCount
        startIndex = index - sameElementCount
        setLongestSequence(array, longestSequence, startIndex)

if __name__ == '__main__':
    size = int(input())
    if size < 2 or size > 100:
        sys.exit()
    array = [int(x) for x in input().split() if x == '1' or '0']
    if len(array) != size:
        sys.exit()
    findLongestSequence(array, size)
    print(startIndexForZero, longestSequenceForZero)
    print(startIndexForOne, longestSequenceForOne)

Correctness

Input

12
0 1 0 1 1 1 0 1 0 0 0 0

Output

8 4
3 3

Input
17
1 1 0 1 0 1 0 0 1 0 0 0 0 1 0 1 0

Output

9 4
0 2

Questions:

  1. Does the code require better error handling?

  2. Can this code get more pythonic?

\$\endgroup\$
  • 1
    \$\begingroup\$ If you want to just increment by 1 each time, then for index in range(size) is both more pythonic and faster than while (index<size). Also, if your array is large, you can significantly improve the run time by incrementing by the current longest sequence instead of by 1. Check out this question of mine - it's not exactly the same, but the general idea of the algorithm still applies. \$\endgroup\$ – ZyTelevan Jun 29 '17 at 18:08
  • \$\begingroup\$ @ZyTelevan Yup for index in range(1, len(array)) works \$\endgroup\$ – overexchange Jun 29 '17 at 18:30
  • \$\begingroup\$ you could use regex and shorten the code too \$\endgroup\$ – depperm Jun 29 '17 at 19:38
4
\$\begingroup\$
  • Correctness

    Input
    1 1 1 1 0 0 0
    
    Output
    None, None
    0, 4
    

    The reason is obvious: the longestSequence does not distinguish between longest sequence of zeroes and longest sequence of ones, so 0 0 0 is not considered long enough.

  • General

    • Avoid globals; prefer returning values.

    • There is no need to pass size; a list already knows its size. For the same reason, size = int(input()) is redundant and reduces usability.

\$\endgroup\$
  • \$\begingroup\$ longestSequence = 1 after setLongestSequence() worked \$\endgroup\$ – overexchange Jun 29 '17 at 18:17

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.