In this article I will provide a solution to the Fish sample Codility problem. The problem description is copyrighted, so have a look at the link for the description since it is lengthy.
Having read the description, our goal is to calculate how many fish stay alive.
My approach is as follows: I keep a stack \(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\)
- If there no fish on the stack, push \(f\) to \(s\)
- Otherwise
- If \(f\) is going upstream, pop off fish from \(s\) as long as \(f\) eats the fish from top of \(s\). This fish is eaten.
- If the stack got empty, push \(f\) to the top of \(s\)
- Otherwise, if the configuration of the fish is different from \(f\) upstream, top of \(s\) downstream, push \(f\) to the top of the stack. This signals that \(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.
The following implementation in Java scores 100/100 on Codility.
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();
}