Fish 100% Solution in Python
Notice
Recently I got some codility challenges from companies and they don't allow me to use javascript. As a results, I learn the basic coding style in python from the very beginning on YouTube Python Programming Tutorial - 1 - Installing Python - YouTube and start to write codility in python.
Question
My Solution
def solution(A, B): downStack = [0] * len(A) downSize = 0 upAlive = 0 for i in range(-1, -1*(len(A)+1), -1): # push to downstream stack if B[i] is 0: downStack[downSize] = A[i] downSize += 1 else: # there's no downstream fish ahead of a upstream fish if downSize is 0: upAlive += 1 else: # eats all the smaller downstream fish ahead while A[i] > downStack[downSize-1]: downSize -= 1 if downSize is 0: break # it is alive if it eat them all if downSize is 0: upAlive += 1 return downSize+upAlive
Note
It took me a while to come up with this solution. Here's my concept behind the code:
I start trace the array from top to bottom, pushing all the downstream fishes to the stack. Whenever I meet an upstream fish. I popped up all the downstream fish ahead and smaller than this fish. If this stack is totally empty, it also means that this upstream fish survive, if not, this upstream fish is dead and all the remaining downstream survives.