1
\$\begingroup\$

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?
\$\endgroup\$
  • 7
    \$\begingroup\$ If you're not sure the implementation is correct, why not write some tests? \$\endgroup\$ – ben rudgers Jul 31 '19 at 14:14
  • 2
    \$\begingroup\$ What does [6,9,9] return? What does [9] return? \$\endgroup\$ – ben rudgers Jul 31 '19 at 14:18
  • 1
    \$\begingroup\$ @pacmaninbw Yeah, I saw that. And that's something I don't understand. The guy in the comment section used the index method which is O(n) and then says it's O((k+j)logn). What? Also, I don't think that implementation considers nested cases. \$\endgroup\$ – sg7610 Jul 31 '19 at 18:50
  • 1
    \$\begingroup\$ @spyr03 [6, 6, 9, 5] returns 0. The question says, "every 6 will be followed by at least one 9." \$\endgroup\$ – sg7610 Jul 31 '19 at 23:04
  • 2
    \$\begingroup\$ I don't understand why this question is downvoted. Looks like a valid code review request. I've seen much worse posts with lots of upvotes. \$\endgroup\$ – Georgy Aug 1 '19 at 22:19
3
\$\begingroup\$

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

| improve this answer | |
\$\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.