Fish - Codility

Codility 'Fish' Solution | MartinKysel.com
https://app.codility.com/programmers/lessons/7-stacks_and_queues/fish/
https://www.cnblogs.com/wei-li/p/Fish.html

N voracious fish are moving along a river. Calculate how many fish are alive. 

You are given two non-empty zero-indexed 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, fish number P is represented by A[P] and B[P], and if P < Q then fish P is initially upstream of fish Q. Initially, each fish has a unique position.

Array A contains the sizes of the fish. All its elements are unique. Array B contains the directions of the fish. It contains only 0s and/or 1s, where:

• 0 represents a fish flowing upstream,
• 1 represents a fish flowing downstream.

If two fish move in opposite directions and there are no other (living) fish between them, they will eventually meet each other. Then only one fish can stay alive − the larger fish eats the smaller one. More precisely, we say that 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. After they meet:

• If A[P] > A[Q] then P eats Q, and P will still be flowing downstream,
• If A[Q] > A[P] then Q eats P, and Q will still be flowing upstream.

We assume that all the fish are flowing at the same speed. That is, fish moving in the same direction never meet. The goal is to calculate the number of fish that will stay alive.

For example, consider arrays A and B such that:

 A[0] = 4 B[0] = 0 A[1] = 3 B[1] = 1 A[2] = 2 B[2] = 0 A[3] = 1 B[3] = 0 A[4] = 5 B[4] = 0

Initially all the fish are alive and all except fish number 1 are moving upstream. Fish number 1 meets fish number 2 and eats it, then it meets fish number 3 and eats it too. Finally, it meets fish number 4 and is eaten by it. The remaining two fish, numbers 0 and 4, never meet and therefore stay alive.

Write a function:

int solution(vector<int> &A, vector<int> &B);

that, given two non-empty zero-indexed arrays A and B consisting of N integers, returns the number of fish that will stay alive.

For example, given the arrays shown above, the function should return 2, as explained above.

Assume that:

• N is an integer within the range [1..100,000];
• each element of array A is an integer within the range [0..1,000,000,000];
• each element of array B is an integer that can have one of the following values: 0, 1;
• the elements of A are all distinct.

Complexity:

• expected worst-case time complexity is O(N);
• expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

https://rafal.io/posts/codility-fish.html

My approach is as follows: I keep a stack s$s$ that represents the fish I’ve processed so far (note that these fish can still be eaten by a later larger fish flowing upstream). It also helps to see that the end of the process, there are only three possibilities: either all fish are flowing downstream, all fish are flowing upstream, or some fish are flowing upstream which are followed by fish flowing downstream. Fish flowing downstream followed by fish flowing upstream is not possible since when the two meet, the larger one will eat the smaller one. This leads us the following algorithm:

• For every fish f$f$
  • If there no fish on the stack, push f$f$ to s$s$
  • Otherwise
    • If f$f$ is going upstream, pop off fish from s$s$ as long as f$f$ eats the fish from top of s$s$. This fish is eaten.
    • If the stack got empty, push f$f$ to the top of s$s$
    • Otherwise, if the configuration of the fish is different from f$f$ upstream, top of s$s$downstream, push f$f$ to the top of the stack. This signals that f$f$ is safe for now.

By the end of the this process, we are left with a stack of fish that survived, so the size of this stack is the answer to the question.

public static int fish(int[] A, int[] B) {
  Stack<Integer> s = new Stack<Integer>();
  
  for(int i = 0; i < A.length; i++){
    int size  = A[i];
    int dir  = B[i];
    if(s.empty()){
      s.push(i);
    }
    else{
      while(!s.empty() && dir - B[s.peek()] == -1 && A[s.peek()] < size){
        s.pop();
      }
      if(!s.empty()){
        if(dir - B[s.peek()] != -1) s.push(i);
      }
      else{
        s.push(i);    
      }
    }
  }
  return s.size();
}

N voracious fish are moving along a river. Calculate how many fish are alive.
Link: Fish

Put all downstream swimming fishes on a stack. Any upstream swimming fish has to fight(eat) all fishes on the stack. If there is no fish on the stack, the fish survives. If the stack has some downstream fishes at the end, they also survive.

http://www.cnblogs.com/wei-li/p/Fish.html

1用一个stack来存flowing downstream的鱼，新来的鱼：
（1） 如果是flowing downstream，直接压栈
（2） 如果是flowing upsteam，跟栈顶元素相遇，要么使得栈顶pop几次，要么它被吃掉over
2 如果此时stack为空的话，放走flowing upstream的鱼并计数（注意这里越过大循环私自进行i++，需要再加i < B.size()控制），压入第一个flowing downstream的鱼。

3 最后别忘了写返回值，放走flowing upstream鱼的数量nalive，加上stack里flowing downstream的数量

 2 int solution(vector<int> &A, vector<int> &B) {
 3     if(A.size() < 2) return A.size();
 4 
 5     int nalive = 0;//upstream存活的鱼
 6     int i = 0;
 7     stack<int> safe;//downstream暂时存活的鱼
 8     while(i < B.size()){
 9         if(B[i] == 0){
10             while(!safe.empty() && A[i] > safe.top()){//栈不为空的条件很重要
11                 safe.pop();
12             }
13         }else{
14             safe.push(A[i]);//压入downstream的鱼
15         }
16         if(safe.empty()){//pop操作也可能导致栈空，因此这一步放在后面
17             while(B[i] == 0 && i < B.size()){//数组不越界的条件很重要
18                 nalive++;
19                 i++;
20             }
21             if(i == B.size())
22                 return nalive;
23             safe.push(A[i]);//压入downstream的鱼
24         }
25         i++;//处理下一条鱼
26     }
27     return nalive + safe.size();
28 }

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]:

                    break

                else:

                    stack.pop()

                         

            else:

                survivals += 1

        else:

            stack.append(A[idx])

             

    survivals += len(stack)

     

    return survivals

http://codilitysolutions.blogspot.com/2015/05/stacks-and-queues-fish.html

public int solution(int[] A, int[] B) {

09

10	int count = 0;

11	Stack < Integer > previousFishes = new Stack < Integer > ();

12

13	for (int i = 0; i < A.length; i++) {

14	int currentFish = A[i];

15	int currentFlow = B[i];

16	if (currentFlow == 1) {

17	previousFishes.push(currentFish);

18

}

19	if (!previousFishes.empty() && currentFlow == 0) {

20	while (!previousFishes.empty() && currentFish > previousFishes.peek()) {

21	int fish = previousFishes.pop();

22

}

23

}

24	if (previousFishes.empty() && currentFlow == 0) {

25

count++;

26

}

27

28

}

29	return count + previousFishes.size();

30

}

https://github.com/yiqin/Codility-Practice/blob/master/Fish.java
    public int solution(int[] A, int[] B) {      
        Stack<Integer> stackForOne = new Stack<Integer>();
        int numFish = 0;
     
        boolean isFirstOneAppreared = false;
     
        for(int i=0; i<A.length; i++) {
         
            if(B[i] == 1) {
                if(!isFirstOneAppreared) {
                    isFirstOneAppreared = true;
                }
                else {
                 
                }
                stackForOne.push(A[i]);
            }
            else {
                if(!isFirstOneAppreared) {
                    // System.out.println(i+": No One");
                    numFish++;
                }
                else {
                    while(!stackForOne.isEmpty() && A[i] > stackForOne.peek()) {
                        stackForOne.pop();
                        System.out.println("pop");
                    }
                    if (stackForOne.isEmpty()) {
                        isFirstOneAppreared = false;
                        numFish++;
                    }
                }
            }
         
        }
        return numFish+stackForOne.size();
    }

http://codility-lessons.blogspot.com/2015/02/lesson-5-fish.html
Different solution:
http://rafal.io/posts/codility-fish.html

public static int fish(int[] A, int[] B) {
  Stack<Integer> s = new Stack<Integer>();
  
  for(int i = 0; i < A.length; i++){
    int size  = A[i];
    int dir  = B[i];
    if(s.empty()){
      s.push(i);
    }
    else{
      while(!s.empty() && dir - B[s.peek()] == -1 && A[s.peek()] < size){
        s.pop();
      }
      if(!s.empty()){
        if(dir - B[s.peek()] != -1) s.push(i);
      }
      else{
        s.push(i);    
      }
    }
  }
  return s.size();
}

Read full article from Codility 'Fish' Solution | MartinKysel.com