Python Implementation: Summer of 69

Question

SUMMER OF '69: Return the sum of the numbers in the array, except ignore sections of numbers starting with a 6 and extending to the next 9 (every 6 will be followed by at least one 9). Return 0 for no numbers.

My solution:

def summer_sum(a_list):
    """
    Use a stack to solve the problem.

    1. If current num is '6', push '0' on the stack.
    2. If current num is not '6' and the stack is empty, add it.
    3. If current num is '9' and the stack is not empty, pop the stack.
    """

    exclude_stack = []
    total = 0

    for num in a_list:
        if num == 6:
            exclude_stack.append(0)

        elif not len(exclude_stack):
            total += num

        elif num == 9 and len(exclude_stack):
            exclude_stack.pop()

    return total

Questions:

1. Is this implementation correct?
2. Is the time complexity of the this implementation O(n)?
3. Is there a better/faster way to solve the problem?

Answer 1

Your code looks good. It's always nice to see people following PEP 8. There is a small issue though with how you check if a list is empty or not. Currently you write elif not len(exclude_stack): or elif num == 9 and len(exclude_stack): but PEP 8 actually has the following recommendation for this kind of tests:

For sequences, (strings, lists, tuples), use the fact that empty sequences are false.

Yes: if not seq:  
     if seq:

No:  if len(seq):  
     if not len(seq):

So, in your case, it should be elif not exclude_stack: and elif num == 9 and exclude_stack:.

Additionally, the details on implementation in the docstring look redundant, I would remove them and leave only the task description.

The main question I have regarding your implementation is: Do you really need to have the stack to keep track if you are inside the 6-9 section? If I print exclude_stack for this input summer_sum([6] * 10 + [9] * 10), it will look like this:

[0]
[0, 0]
[0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0]
[0, 0]
[0]
[]

This doesn't really look like the most optimal solution memory-wise. How about keeping a track of the 6-9 sections by simply incrementing/decrementing some integer variable instead? Something like this:

def summer_sum(a_list):
    """Solution for Summer 69 challenge"""
    section_depth = 0
    total = 0
    for num in a_list:
        if num == 6:
            section_depth += 1
        elif section_depth == 0:
            total += num
        elif num == 9 and section_depth > 0:
            section_depth -= 1
    return total

I assume this will be also a bit faster as you won't have to pop or append to a list.

My hands are also itching to remove the total variable and make a generator function, but this may be a bit overboard:

def summer_sum(a_list):
    """Solution for Summer 69 challenge"""

    def free_numbers(numbers):
        section_depth = 0
        for num in numbers:
            if num == 6:
                section_depth += 1
            elif section_depth == 0:
                yield num
            elif num == 9 and section_depth > 0:
                section_depth -= 1

    return sum(free_numbers(a_list))