Solution to Fish by codility

38 Replies to “Solution to Fish by codility”

1. Hi Shen, what is the use of ‘downstream_count’ if you increase it everytime you push to ‘downstream’ stack and decrease it everytime you pop from ‘downstream’ stack, and you have len(downstream) at your disposal?
   Am I wrong or that variable has no use? you could substitute ‘downstream_count != 0’ condition with len(downstream) != 0, am I not right?
   thank you for this solutions, you are helping me a lot when I get stuck on something… T_T

   Reply

   • Yes, you are right. It is a redundant variable. It could be replaced with len(downstream).

     Reply

     • Eheh, it’s just your code is so neat and your logic is so good it seemed odd you used a redundant variable! 😀
       Since I am already writing, how come you have completed all codility tasks? Was it for a job application or for fun?
       I am having quite a hard time, because it’s been a while since I am not coding seriously and last time I handled logic problems like this, it was in first year at university. I would love to put myself to challenge and learn them myself, but I have been assigned a test for a job application and I only have four days to perform it…so I am just trying to learn as much as I can, as best as I can.
       I obviously do not know what test they have for me, what do you think, what is your experience?
       thanks a lot, congrats again for your logic skills

       Reply

       • I did these questions for both fun and internship hunting. For some hard questions, they cost me days or even weeks to solve one. But to be honest, I am a Muggle in interviews… So I cannot give you any valuable suggestion. Good luck and enjoy coding!

         Reply

         • Good to know I am not the only one who does not solve them in 120 mins!
           It is quite reassuring, although not very useful.
           I am curious now, what do you do in your life?

       • A long story short, a computer science student. In terms of the time, I wish I could finish the hard problem in even 1200 mins~ But I cannot in most cases. That is why I enjoy it. Coding and improving.

         Reply

2. My solution to this problem (looks a little bit stupid tho..):

   Solution to Fish by codility

   Python

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

   def solution(A, B):     N = len(A)     fish = []     for i in range(N):         if len(fish) == 0 or B[i] == 1:             fish.append((A[i], B[i]))         elif B[i] == fish[-1][1] == 0:             fish.append((A[i], B[i]))         else:             while len(fish) >= 1 and fish[-1][1] == 1:                 if A[i] > fish[-1][0]:                     fish.pop()                 else:                     break             else:                 fish.append((A[i], B[i]))     return len(fish)

   Reply

   • Thanks for sharing your code. Enjoying coding!

     Reply

3. I like your use of the pythonic while/else. It makes the code more simple.
   Just for completeness sake, here my 100/100 solution.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

   def solution(A, B):     survivals = 0     stack = []     for idx in xrange(len(A)):         if B[idx] == 0:             while len(stack) != 0:                 if stack[-1] > A[idx]:                     #print "downstream ate candidate"                     break                 else:                     #print "upstream ate stack"                     stack.pop()             else:                 survivals += 1                 #print "fish size", A[idx], "survived"         else:             stack.append(A[idx])             #print "stack push", A[idx]     survivals += len(stack)     #print len(stack), "downstreams survived"     return survivals

   Great job with the blog!

   Reply

   • Thanks! Looking forward your novel solutions to other challenges!
     Enjoy coding!

     Reply

4. This solution got 100% correctness but 75% performance, though O(N):
   EDITED BY SEHNG: you code is incomplete.

   Reply

   • Please read my post. I think it shows the idea clearly.

     Reply

5. I have quite simple one 🙂

   1 2 3 4 5 6 7 8 9 10

   def solution(A, B):     stack = []     for i in xrange(len(A)):             live_fish = i             while B[live_fish] == 0 and stack and B[stack[-1]] == 1:                 other_fish = stack.pop()                 if A[other_fish] > A[live_fish]:                     live_fish = other_fish             stack.append(live_fish)     return len(stack)

   Reply

   • Thanks!

     Reply

   • I like your solution. If I understand correctly, It works by taking fish, have them battle and then place the winner on the stack.

     Reply

6. 100% solution in c++

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

   #include int solution(vector &A, vector &B) {     int arrSize = A.size();     stack downStream;     int alive = A.size();     for(int i=0; i 0) // when one fish meets another         {             if(A[downStream.top()] < A[i]) // upstream eats downstream             {                 downStream.pop(); // remove "dead" fish from the stack                 i--; // i-- because we have to check the same fish again             }             alive--;         }     }     return alive; }

   Reply

7. Hello this is my solution

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

   public int solution(int[] A, int[] B) {     Stack<Integer> fishesToFight = new Stack<Integer>();     int passedUpstream = 0;     for (int i = 0; i < B.length; i++) {         if (B[i] == 0) {             if (fishesToFight.size() == 0)                 passedUpstream++;             else {                 while (!fishesToFight.empty() && A[i] > fishesToFight.peek())                     fishesToFight.pop();                 if (fishesToFight.size() == 0)                     passedUpstream++;             }         } else             fishesToFight.push(A[i]);     }     return fishesToFight.size() + passedUpstream; }

   Reply

   • Thank you very much for sharing!
     Personally, I strongly discourage your coding style: while/if/else without {}.

     Reply

     • You discourage this style and still you choose Python to present your solutions?! :p
       (Sorry, I just hate Python syntax 🙂 )

       Reply

       • I know. Programming language is extremely personal preference.
         C/C++ use bracelets { and } to solve the dangling else problem, while Python use indentation. As a result, to me, the bracelets is strongly recommended when I used any while/for/if.

         Reply

8. A Java Solution that uses the Stack size as a result.
   https://codility.com/demo/results/demo967MY4-J2X/

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

   import java.util.Stack; class Solution {     private static final int UPSTREAM = 0;     private static final int DOWNSTREAM = 1;     // Sample input     // ([2,3],[1,0]) = 1     // ([4, 3, 2, 1, 5], [0, 1, 0, 0, 0])  = 2     public int solution(int[] A, int[] B) {         Stack<Fish> stack = new Stack<>();         for(int f = 0; f < A.length; ++f) {             Fish currentFish = new Fish(A[f],B[f]);             if (stack.isEmpty()) {                 stack.push(currentFish);             } else {                 Fish previousFish = stack.peek();                 if(previousFish.direction == DOWNSTREAM && currentFish.direction == UPSTREAM) {                     boolean currentFishAlive = true;                     while (!stack.isEmpty() && stack.peek().direction != currentFish.direction) {                         if (stack.peek().size < currentFish.size) {                             stack.pop(); // previous fish eaten                         } else {                             currentFishAlive = false;                             break;                         }                     }                     if (currentFishAlive) { stack.push(currentFish); }                 } else { // same direction or don't meet P < Q, but no B[P] = 1, B[Q] = 0                     stack.push(currentFish);                 }             }         }         return stack.size();     }     public static class Fish {         public int direction;         public int size;         public Fish(int size, int direction) {             this.size = size;             this.direction = direction;         }     } }

   Reply

9. In java .. kind of similar

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

   Stack prevfishes = new Stack(); int nooffish = 0; for(int i=0;i<A.length;i++) {     int currentflow = B[i];     // considering going up as natural order     if(currentflow == 0) {         // no one in between increase count         if(prevfishes.isEmpty()) {             nooffish ++;         } else {             // if something already in between sort it out             while(!prevfishes.isEmpty() && prevfishes.peek() < A[i])                 prevfishes.pop();             // no one in between increase the count             if(prevfishes.isEmpty())                 nooffish ++;         }     } else {         // noting down whose are not with going up         prevfishes.push(A[i]);     } } return prevfishes.size() + nooffish;

   Reply

10. My 100% C# solution:

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

    private static int solution(int[] A, int[] B)   // this solution scored %100       {          var downstreamFish = new Stack<int>();          int eatenFish = 0;          for (int i = 0; i < A.Length; i++)          {             if (B[i] == 0)             {                // fish swims upstream                // this upstream swimming fish will continue to meet downstream swimming fish                // until the stack is empty or it gets eaten                while (true)                {                   if (downstreamFish.Count == 0)                   {                      // the fish can swim upstream with no problem                      break;                   }                   // else                   int sizeOfFirstDownstreamFish = downstreamFish.Pop();                   eatenFish++;   // one fish will be eaten                   if (sizeOfFirstDownstreamFish > A[i])                   {                      // downstream fish eats upstream fish                      // push it back in the stack                      downstreamFish.Push(sizeOfFirstDownstreamFish);                      break;                   }                   // else, the upstream fish eats the downstream fish and                   // I need to repeat the loop                }             }             else             {                // fish swims downstream                downstreamFish.Push(A[i]);             }          }          return A.Length - eatenFish;       }

    Reply

11. 100%, 100% java solution

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61

    public int solution(int[] A, int[] B) {         Stack<Integer> downStreamSize =  new Stack<Integer>();         int surview = 0 ; public int solution(int[] A, int[] B) {         Stack<Integer> downStreamSize =  new Stack<Integer>();         int surview = 0 ;         for(int i=0 ;  i<A.length ; i++){             if(B[i] == 1){                 downStreamSize.push(A[i]);             }             else if(B[i] == 0 && downStreamSize.isEmpty()){               surview++;             }             else{                 while(!downStreamSize.isEmpty()  && downStreamSize.peek() < A[i] ){                     downStreamSize.pop();                 }                 if(downStreamSize.size() ==0){                     surview ++ ;  public int solution(int[] A, int[] B) {         Stack<Integer> downStreamSize =  new Stack<Integer>();         int surview = 0 ;         for(int i=0 ;  i<A.length ; i++){             if(B[i] == 1){                 downStreamSize.push(A[i]);             }             else if(B[i] == 0 && downStreamSize.isEmpty()){               surview++;             }             else{                 while(!downStreamSize.isEmpty()  && downStreamSize.peek() < A[i] ){                     downStreamSize.pop();                 }                 if(downStreamSize.size() ==0){                     surview ++ ;                 }             }         }         return surview + downStreamSize.size();     }                 }             }         }         return surview + downStreamSize.size();     }         for(int i=0 ;  i<A.length ; i++){             if(B[i] == 1){                 downStreamSize.push(A[i]);             }             else if(B[i] == 0 && downStreamSize.isEmpty()){               surview++;             }             else{                 while(!downStreamSize.isEmpty()  && downStreamSize.peek() < A[i] ){                     downStreamSize.pop();                 }                 if(downStreamSize.size() ==0){                     surview ++ ;                 }             }         }         return surview + downStreamSize.size();     }

    Reply

12. Can you explain me in your answer why you’re taking into account this?
    # NEVER meet the previous fishs. But possibly it has to fight with the downstream fishs.
    downstream.append(A[index])
    downstream_count += 1
    Since, what I understand is that the first fish will never “see” the second one…”If P and Q are two fish and P If A[0] = 1 and B[0] = 0 and A[1] = 2 and B[1] = 0 they will not meet since are flowing the same direction and if B[1] = 1, they will not meet since P < Q (0 A[1] is ahead of A[0] so they will be separating more and more and never meet. What am I missing?
    From the example:
    -> A[0]
    A[2]
    ->A[3]
    ->A[4]

    Reply

    • Yes, you are right:
      1. If A[0] = 1 and B[0] = 0 and A[1] = 2 and B[1] = 0 they will not meet since are flowing the same direction;
      2. If A[0] = 1 and B[0] = 0 and A[1] = 2 and B[1] = 1, they will not meet since P < Q (0 A[1] is ahead of A[0] so they will be separating more and more and never meet.
      My fault. There is an implicit condition for the statement "# NEVER meet the previous fishs. But possibly it (P) has to fight with the downstream fishs (Q)": the mentioned downstream fishes Q are swimming toward the this fish P. Because:
      1. they are swimming in different directions; And
      2. P < Q.
      In other words, the P is on the left end and swimming toward the right side; and the Q is on the right end (we scan the fishes from left to right, or say, from index 0 to index N-1. We get Q later than P, so Q is on the righter sider than P.), and swimming toward the left side. So they might meet.

      Reply

13. Checkout my C++ solution for this problem.

    Reply

    • Please read the “Guideline for Comments” in the right column to post the complete code. Thanks!

      Reply

14. I am wondering, is in all this solutions complexity actually O(n2) because we have for loop and while loop in it?

    Reply

    • Short answer is: yes, it’s actually O(N).
      It’s a common trap to count the complexity by checking the number of nested for/while. However, that’s not always correct. Please note that during the whole function, the while loop is executed at most N times, independently with the for loop.

      Reply

    • It’s the reason why it took me 2 weeks to finish this task (in the context of adult life with non-dev job). I was trying to avoid a for-while combination, thinking back to the for-while combination in Insertion Sort, which does have O(n^2) time.

      Thank you, Sheng for pointing out that this is a common trap, to assume that any for-while is O(n^2). Actually wrote down your comment, hopefully to never repeat this mistake again.

      Indeed, like Sheng said, most times the while gets executed is n times. Worst case, when the while-loop has the largest number of fish to go through, is when you have n-1 downstreamers and one upstreamer at the end, bigger than all.

      The last fish, the upstreamer, eats them one by one in the while loop. This means your program goes through all the n fish once in the for-loop, then once more through all the downstreamers in the while-loop. So thats n + (n-1). Technically, Sheng is right to say that while gets executed n times, as any while or for-loop will have the test executed one more time compared to its loop body.

      At any rate, this is 2n (or 2n +1, to be more precise) number of times the for + while statements are evaluated in total. So worst case is 2n, therefore O(n).

      Reply

15. Here’s a solution that uses only stack i.e. the result is the length of the stack and scores 100%.

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

    def solution(A, B):     n = len(A)         stackFish = [A[0]]     stackDirection = [B[0]]          for i in range(1, n):         if A[i] == 0:             continue                  if stackDirection[-1] == B[i] or (stackDirection[-1] == 0 and B[i] == 1):             stackFish.append(A[i])             stackDirection.append(B[i])         else:             while (stackDirection[-1] != 0 and B[i] != 1):                 if (stackFish[-1] < A[i]):                     stackFish.pop()                     stackDirection.pop()                     boolean = True                 else:                     boolean = False                     break                                  if len(stackFish) == 0:                     break             if boolean:                 stackFish.append(A[i])                 stackDirection.append(B[i])                 boolean =False       return len(stackFish)

    Reply

16. Python 100% , took me a while tho

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

    def solution(A, B):     to_left = []     to_right = []     ziped = [[e[1],  e[0]] for  i, e in enumerate(zip(A,B))]          for i in range (len(A)):           if(ziped[i][0] == 0):             to_left.append(ziped[i])                          while(len(to_right) != 0):                 if (ziped[i][1]>to_right[-1][1]):                                       to_right.pop()                                     else:                                         to_left.remove(ziped[i])                                         break;         else:                         to_right.append(ziped[i])        return len(to_right) + len(to_left)

    Reply

    • I updated the code as your follow-on comment. Thanks for sharing your code!

      Reply

17. My 100% PHP -version

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

    function solution($A, $B) {     // write your code in PHP7.0     $stack = [];     $alive = 0;     foreach($A as $key => $val){         if($B[$key] == 1) {             array_push($stack, $key);         } elseif(count($stack) == 0){                 $alive++;         } else {             while(count($stack)>0) {                 $fish_id = array_pop($stack);                 if($val < $A[$fish_id]){                     array_push($stack, $fish_id);                     break;                 } else {                     if(count($stack) == 0){                         $alive++;                     }                 }             }         }     }     return $alive+count($stack); }

    Reply

18. Here is my solution in Python:

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

    def solution(A, B):     L = len(A)     stack = []     count = L          for k in range(L):         if B[k] == 1:             stack.append(A[k])         else:             for i in reversed(stack):                 count -=1                 if A[k] > i:                     stack.pop()                 else:                     break          return count

    Reply

19. Where do you handle the case where an upstream fish doesn’t eats all downstream ones but survive (they are of the same size).

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

    function solution(A, B) {     const down = []     let alive = 0     for(let i=0; i<A.length; i++) {         if(B[i]) {             down.push(A[i])         } else {             let stayAlive = 1             while(down.length !== 0) {                 if(down[down.length-1] < A[i]) {                     down.pop()                 } else if(down[down.length-1] > A[i]) {                     stayAlive = 0                     break                 }             }             if(stayAlive) alive++         }     }     return  down.length + alive }

    Reply

    • We do not need to care about that. Problem description says “the elements of A are all distinct.”

      Reply