4
\$\begingroup\$

I am attempting the matched brackets problem. I have written a Python program which seems to do the job but is very slow and thus exceeds the time limit. Please help me making this code more efficient. I have explained my code in the comments.

length = int(input())
inp = input().split(' ')
inp = [ int(x) for x in inp ]
position = 0 ##where our cursor is.
highest_depth =0
buffer = 0
stretch = 0 ##max distance b/w two matched brackets.
bar = 0 ## jst a buffer for calculating max distance between two brackets.
stretch_pos = 0
for l in inp:
    position += 1
    bar += 1
    '''if the cursor is currently at open bracket(1) add 1 to buffer'''
    if l == 1:
        buffer += 1
    else:
        '''if the cursor is at a closed bracket(2) we need to stop calculating
        higest depth and assign it to highest_depth only if the current value
        is smaller'''
        if highest_depth < buffer:
             highest_depth = buffer
             hpos = position -1 ##position of highest depth.
        buffer -= 1
        '''if buffer is now 0  due to the above line it must mean that all the
           brackets opened have been closed.'''
        if buffer == 0:
            ''' bar which calculates the max distance between two matched brackets
                must be assigned now and reset to zero'''
            if bar > stretch:
                stretch = bar
                stretch_pos = position - stretch + 1
            bar = 0
print(highest_depth , hpos,stretch, stretch_pos)
\$\endgroup\$
4
\$\begingroup\$

I think your algorithm is fast enough to get accepted. Contest times are sometimes not well calibrated for python speed.

One part that could be optimized is splitting the string and converting it to integers, which is now creating a new string for every number, possibly up to \$10^5\$ strings. Since the string is always gonna be 1-digit numbers separated by spaces, you could instead iterate on the string without parsing it or converting it to integers.

Something like:

str = "1 2 3 4"
for index in range(0, len(str), 2):
  num = str[index]
  # use num here
\$\endgroup\$
  • \$\begingroup\$ I see... I really didn't need to convert them to int. This should give me some speed. I will try it out when I get time after college. \$\endgroup\$ – sudo_dudo Jan 30 '17 at 4:49
4
\$\begingroup\$

I would extend @HeshamAttia's advice and suggest to use enumerate rather than maintaining your own position counter.

You should also give meaninful names to your data, so that it is easier to reason about the logic. Using the enum module, you can define:

class Symbol(enum.Enum):
    OPEN_PARENTHESIS = '1'
    CLOSE_PARENTHESIS = '2'

And use Symbol.OPEN_PARENTHESIS and Symbol.CLOSE_PARENTHESIS in the rest of the code so it is clearer what you are comparing and why.

Lastly, use functions, it help make the code more reusable, testable and readable. Something like:

import enum


class Symbol(enum.Enum):
    OPEN_PARENTHESIS = '1'
    CLOSE_PARENTHESIS = '2'


def parse_data(stream):
    for character in stream:
        try:
            kind = Symbol(character)
        except ValueError:
            pass
        else:
            yield kind


def challenge(stream):
    depth_pos = depth_max = depth = 0
    span_pos = span = stretch = 0

    for index, symbol in enumerate(stream):
        stretch += 1
        if symbol == Symbol.OPEN_PARENTHESIS:
            depth += 1
        elif symbol == Symbol.CLOSE_PARENTHESIS:
            if depth_max < depth:
                depth_max = depth
                depth_pos = index - 1
            depth -= 1

            if not depth and span < stretch:
                span = stretch
                span_pos = index - stretch + 1
            stretch = 0

    return depth_max, depth_pos, span, span_pos


def main():
    input()  # discard chain length
    symbols = parse_data(input())
    print(challenge(symbols))


if __name__ == '__main__':
    main()
\$\endgroup\$

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.