Python codility lesson : stacks and queues fish bug

codility test
codility data structures
codility challenges

My code seems to be returning the wrong answer for one test case on codility.(rest of the test cases are correct)

for a test case: large_random

large random test, N = ~100,000 i'm getting a

got 868 expected 840

question link: https://app.codility.com/programmers/lessons/7-stacks_and_queues/fish/

def solution(A, B): #declare stacks for fish traveling downstrea, upstream dstrm = [] ustrm = [] #set counter to zero for fish traveling upstream UNHINDERED #by fish traveling downstream, needed because iteration starts upstream counter = 0 n = len(A) #iterate over input, starting from upstream for i in range(n): if B[i] == 0: ustrm.append(A[i]) elif B[i] == 1: dstrm.append(A[i])

# clear upstream stack of fish known to be UNHINDERED, increase counter if len(ustrm) > 0 and len(dstrm) == 0: counter += len(ustrm) ustrm.clear() #compare what's bigger and decrease stack of fish that is eaten while len(dstrm) > 0 and len(ustrm) > 0: if dstrm[-1] > ustrm[-1]: ustrm.pop() elif ustrm[-1] > dstrm[-1]: dstrm.pop() return len(dstrm) + len(ustrm) + counter

Here is my approach - may be some one can get idea - how i solved it Codility 100 % in Codility Python

Code

def solution(A, B):
"""
Codility 100%
https://app.codility.com/demo/results/trainingF5HTCA-YFV/

Idea is to use stack concept
For each iteration if current fish is of type 1 add it to stack 1 fish
Create stack 1 fish - it always holds the downstream ie 1 kind of fish
 and keep killing the smaller fish from the list if it is greater
  else killed by current fish.
Now if stack 1 fish has no fish it means current fish can be counted as remaining fish.


0 represents a fish flowing upstream - 0 fish
1 represents a fish flowing downstream - 1 fish

A[0] = 4    B[0] = 0 alive fish
A[1] = 3    B[1] = 1 downstream
A[2] = 2    B[2] = 0 eaten by A[1]
A[3] = 1    B[3] = 0 eaten by A[1]
A[4] = 5    B[4] = 0 eat to A[1] and remain alive

"""

count = 0
# stores the 1 fish in stack
stack_1_fish = []
print(A)
print(B)
for index in range(len(A)):
    if B[index] == 0:
        # until stack has some 1 fish
        while stack_1_fish:
            # get last fish from stack and check if it can die or not
            # the larger fish eats the smaller one.
            # two fish P and Q meet each other when P < Q, B[P] = 1 and B[Q] = 0, and there are no living fish between them
            if stack_1_fish[-1] > A[index]:
                # stack 1 fish kill to current fish
                # exit from while loop and else block also execute next top for loop
                # check for other fish fight
                print("Killed by " + str(stack_1_fish[-1]) + " Die " + str(A[index]))
                break
            else:
                # stack 1 fish is killed by current fish
                p = stack_1_fish.pop()
                print("Killed by " + str(A[index]) + " Die " + str(p))

        # this is the case when stack becomes empty ie. no fish of kind 1
        # it would never meet previous fish but can fight with downstream fish
        else:
            print("Count fish as remaining......." + str(A[index]))
            count += 1
    else:
        # fish 1 found add to stack
        stack_1_fish.append(A[index])
        print("1 fish found, add to stack, it can kill or killed by someone..." + str(A[index]))
        print(stack_1_fish)

print("Count: " + str(count))
print("Stack 1 fish: " + str(len(stack_1_fish)))
return count + len(stack_1_fish)

Execution Output -

if __name__ == '__main__':
result = solution([4, 3, 2, 1, 5], [0, 1, 0, 0, 0])
# result = solution([4, 3, 2, 1, 5], [0, 0, 0, 0, 0])
# result = solution([4, 3, 2, 1, 5], [1, 1, 1, 1, 1])
print("")
print("Solution " + str(result))

[4, 3, 2, 1, 5]
[0, 1, 0, 0, 0]
Count fish as remaining.......4
1 fish found, add to stack, it can kill or killed by someone...3
[3]
Killed by 3 Die 2
Killed by 3 Die 1
Killed by 5 Die 3
Count fish as remaining.......5
Count: 2
Stack 1 fish: 0

Solution 2

[4, 3, 2, 1, 5]
[0, 0, 0, 0, 0]
Count fish as remaining.......4
Count fish as remaining.......3
Count fish as remaining.......2
Count fish as remaining.......1
Count fish as remaining.......5
Count: 5
Stack 1 fish: 0

Solution 5

[4, 3, 2, 1, 5]
[1, 1, 1, 1, 1]
1 fish found, add to stack, it can kill or killed by someone...4
[4]
1 fish found, add to stack, it can kill or killed by someone...3
[4, 3]
1 fish found, add to stack, it can kill or killed by someone...2
[4, 3, 2]
1 fish found, add to stack, it can kill or killed by someone...1
[4, 3, 2, 1]
1 fish found, add to stack, it can kill or killed by someone...5
[4, 3, 2, 1, 5]
Count: 0
Stack 1 fish: 5

Solution 5

Best solutions for Codility Lessons. Lesson 7 Stacks and Queues, Best solutions for Codility Lessons. Lesson 7 Stacks and Queues In this case we should return error. The best container for collecting of downstream fish is stack because when we will take The same solution in Python: Lesson 7 Stacks and Queues PDF. StoneWall; Brackets; Nesting; Fish; Lesson 8 Leader PDF. EquiLeader; Dominator; Lesson 9 Maximum slice problem PDF. MaxDoubleSliceSum; MaxProfit; MaxSliceSum; Lesson 10 Prime and composite numbers PDF. MinPerimeterRectangle; CountFactors; Peaks (respectable) Flags (respectable) Lesson 11 Sieve of Eratosthenes PDF

Your overall strategy doesn't make sense to me, and I'm actually surprised that most test cases pass. Here is a very simple case that your code gets wrong:

A:[1,2] B:[0,1]

If I've understood the notation correctly, fish 0 is the most upstream fish, and it is swimming upstream, and fish 1 is the most downstream fish, and it is swimming downstream. Thus, the fish won't meet, and the answer is two.

However, your code outputs 1, because it doesn't actually check their relative positions at all. It just compares the most upstream downstream-headed fish to the most upstream upstream-headed fish, and declares that one will eat the other, regardless of whether they meet at all.

(If I got the notation backwards, just invert array B - your code outputs 1 in both cases, which is definitely not correct.)

A correct solution needs to compare the positions of the fish, not just their sizes.

Fish coding task - Learn to Code, Stacks and Queues � Lesson 8. Leader � Lesson 9. Maximum slice problem N voracious fish are moving along a river. Calculate how many fish are alive. You are given two non-empty arrays A and B consisting of N integers. Arrays A and B represent N voracious fish in a river, ordered downstream along the flow of the river. The fish are numbered from 0 to N − 1. If P and Q are two fish and P < Q, then fish P is initially upstream of fish Q. Initially, each fish has a unique position.

Here's my Python approach using tuples if somebody is still interested in the solution to this problem. I got a 100%.

def solution(A, B):

    fishes, stack = [], []

    for i in range(len(A)):
        fishes.append((B[i], A[i]))

    while fishes:
        if stack and not stack[-1][0] and fishes[-1][0]:
            if stack[-1][1] > fishes[-1][1]:
                fishes.pop()
            else:
                stack.pop()
        else:
            stack.append(fishes.pop())

    return len(stack)

Codility Solutions, On this page I am sharing my solutions to the codility.com problem sets. [ ambitious]✗ 5) Stacks and Queues Brackets [painless]✓ Nesting [painless]✓ StoneWall throw new Error("out of range"); This is a really good resource for Codility's lessons. explaining most of these puzzles from codlity in java, python and ruby: Lesson 7 Stacks and Queues June 11, 2020 June 24, 2020 Jonathan 0 Comments Codility , Lesson 7 , Programming , Programming platforms , Python Brackets

I found the most elegant Codility fish solution may be found in here. It is using the stack:

def solution(a, b):
    l = 0 # left
    s = [] # stack
    for i in range(len(a)):
        if b[i]==1: # fish moving upwards
            s.append(a[i]) # to the stack
        else: # eat fish mowing downwards.
            while len(s)>0:
                if s[-1]<a[i]:
                    s.pop() # eat from the stack
                else:
                    break
            else:
                l+=1
    l+=len(s)
    return l

Python codility課程:堆棧和隊列魚bug, Python codility課程:堆棧和隊列魚bug. [英]Python codility lesson : stacks and queues fish bug. 本文翻译自 PCI-DJ 查看原文 2018-02-05 129 python/ stack� Browse other questions tagged javascript algorithm stack codility or ask your own question. The Overflow Blog Podcast 241: New tools for new times

Unofficial Solutions to the Training by Codility – Code Says, codility.com is another great place to improve our programming skills. Binary- Gap ☆: Python solution Lesson 7: Stacks and Queues Nesting ☆: Python solution; sigma2012 (Stone-Wall) : Python solution; Fish : Python solution. While the stack is not empty, if the direction of the fish is 1 and the direction of the last fish in the stack is 0 (aliveFishes.Peek()) and the size of the fish is bigger that the last fish in the stack, the we pop (delete) the last fish in the stack (as it has been eaten).

【Python】Codility in Python : Lesson 7, Stacks and Queues 第三題:【Fish】 N voracious fish are moving along a river. Calculate how many fish are alive. This is a master index of the Codility practice problems I solved in Java. All solutions were unit tested with TestNG and I have included the test code for each solution. All code has been committed to Github. Lesson 1 – Iterations BinaryGap Lesson 2 – Arrays CyclicRotation OddOccurrencesInArray (Odd Occurrences In Array) Lesson 3 …

stacks and queues--codility, stacks and queues--codility lesson 7: stacks and queues 1. def solution(H):; # write your code in Python 2.7; cnt = 0; stack = [] Arrays A and B represent N voracious fish in a river, ordered downstream along the flow of the river. 测试报告出现乱码的问题Test Group/Test case Count Pass Fail Error Vie . On this page I am sharing my solutions to the codility.com problem sets. They can be found here. Enjoy and share your comments! 1) Time Complexity TapeEquilibrium [painless] FrogJmp [painless] PermMissingElem [painless] 2) Counting Elements PermCheck [painless] FrogRiverOne [painless] MaxCounters [respectable] MissingInteger [respectable] 3) Prefix Sums PassingCars [painless] GenomicRangeQuery

Comments
  • just to clarify my strategy, i will start "upstream" and iterate going "downstream", adding to stacks ustrm and dstrm respective fish. fish that are known to go upstream unhindered and therefore not eaten will be added to variable "counter" by the if statement in the middle and the ustrm stack cleared, the while loop will loop as long as there are fish in the stacks (fish facing each other) and after comparions, will be 'eaten' (popped away) leaving the next fish in line to be compared. variable counter, and length of dstrm would be added and returned
  • I copied your code verbatim and called it exactly as you describe, and it returns 1. Is the code you're running identical to the code in the question? As written, the if statement you mention definitely will not run, since len(dstrm) != 0 at that point. I wonder though, is this an indentation issue? Is that if supposed to be inside the for loop?
  • sorry that's my bad, i must have screwed it up while copying and pasting my code, i've just noticed that the return statement was outside of the def solution as well.... i've put the if statement and the while inside the for loop (edited the code above)but still getting the same error as described in the original question... is this a problem with my strategy