"Balls in a row": Someone on reddit mentioned stacks.

 

This post is an extension to my last post :The "Balls in a row" challenge.

 

jacobb11 on reddit mentioned:

I believe a significantly simpler solution creates a stack (array) of color/number pairs by scanning the initial array, pushing color/number pairs on the stack, and removing groups only on the top of the stack. Constant time deletion with only a single extra object. 3

Thats intriguing ... I'll write some code.

from collections import deque

def discard_S(balls):
    "using ball stack"
    balls = balls.copy() + [-1]         # Add terminator
    stack  = deque()
    push, pop = stack.append, stack.pop
    discards = 0
    for ball in balls:
        while stack:
            top, count = pop()
            if ball == top:
                push((top, count + 1))  # increment last run of balls
                break
            else:
                if count >= 3:          # last run discarded
                    discards += count
                    continue            # go deeper in stack
                else:
                    push((top, count))  # last run pushed back
                    push((ball, 1))     # start new run
                    break               # next ball
        else:
            push((ball, 1))             # start new run
    return discards

test(discard_S, exercises)

START Testing discard_S: 'using ball stack'
  discard_S([0, 0, 3, 3, 3, 0, 0]) == 7
  discard_S([0, 0, 3, 3, 3, 0, 9]) == 6
  discard_S([5, 5, 5, 5, 5, 5, 5]) == 7
  discard_S([2, 4, 5, 7, 8, 8]) == 0
STOP  Testing discard_S

My code works, (and I lengthened some of the names after reddit comments).
Debugging was similar to what was needed on my earlier algorithms, I needed that spur of "stack" to go investigate.

Timings

I'll drop the slowest discard_simple and discard_RLE and do time comparisons with just two algorithms.

t_gen = time_a_generator(range(33_333, 999_999, 33_333), gen=gen_all_downto_zero, 
                         solvers=[discard_LL, discard_S]);

discard_S, the stack based implementation is definitely fastest

discard_LL is similar, but with a time wasting initial run-length encoding using groupby and using LL pointer manipulations similar to the stack, but not having deque. discard_S feeds the stack from the bottom of the balls; discard_LL might be seen as having pt as top of stack fed from pt.next-in-list.

Nice.

END.