Straight Developer

In this post I am going to talk about a 100% score javascript solution to the second exercise of the Stacks & Queues lesson named Fish

Now here’s the exercise’s description on Codility:

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.

Fish number P is represented by A[P] and B[P]. 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, number 0 and 4, never meet and therefore stay alive.

Write a function:

function solution(A, B);

that, given two non-empty 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.

Write an efficient algorithm for the following assumptions:

• 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.

Before we elaborate, here’s the full javascript solution in case you’re just coming for the code:

function solution(A, B) {
    function processFish(fish){
        for(var i=survivors.length-1;i>=0;i--){
         var lastFish=survivors[i]
             if(lastFish>0 && fish<0) {//last fish is going down
                if(Math.abs(lastFish)<Math.abs(fish)) {// fish is bigger
                    survivors.pop()
                    if(i<=0){
                        survivors.push(fish)
                        break;
                    }
                }
                else
                    break; //do nothing
            }
            else{
                survivors.push(fish)
                break
            }
        }
    }
    function addFish(i){
        if(B[i]>0)
            var fish=A[i]
        else
            var fish=-A[i]
        if(survivors.length==0)
            survivors.push(fish)
        else
            processFish(fish)
    }
    var survivors=[]
    addFish(0)
    for(var i=1;i<A.length;i++){
       addFish(i)
    }
   return survivors.length
}

this solution gives a score of 100% in matter of correctness and performance and has a time complexity of O(N)

Using a stack to determine the number of surviving fish

In order to calculate how much fish are left in the end, we need to create a stack and fill it with all the surviving fish, one at a time

survivors.push(fish)

each time a fish is added to the stack it may devour one or more of the survivors in case the conditions are met, so in case the upcoming fish is meant to eat the last fish of the stack, we’re simply going to remove the prey (the last fish of the stack):

survivors.pop()

in the opposite case (the last fish of the stack is eating the upcoming fish) we’re simply going to do nothing.
Once we’re done with collecting the surviving fish in a stack, we just need to return its length which will gives us the exact number of fish that will stay alive

return survivors.length

Now we need to build the logic around this base, that is to say making sure to properly interact with the survivors array according to the description of the exercise

Combining arrays A & B (sizes and directions of the fish) into one

Since we need two criterias to determine which one of a two given crossing fish is going to survive we are given two arrays, one contains the size of each fish while the other is containing the direction but we don’t really need to rely on two arrays !
In fact, a single array would be easier to manage then two so that why combining the two arrays is a good idea.
We can keep note of the direction plus the size of a fish using a simple method:
we make sure to use the size of the fish as the value and we make it a negative number if the fish in question is going upstream, on the other hand, if the fish is floating downstream we just keep the number positive. Example: -5 would represent a fish floating upstream that has a size of 5
so first step is to loop on the fish list:

for(var i=1;i<A.length;i++){
   addFish(i)
}

Second, we combine each fish’s size and direction into one value:

if(B[i]>0) // if current fish is floating downstream
  var fish=A[i]
else //upstream
  var fish=-A[i]

Combining happens at the same time as filling the survivors array so that performances are kept minimal.
By combining the size and the direction the one dimension survivors array becomes enough to keep note of each fish in case we have to return to it later.

Filling the stack

Now we just need to write the logic that will determine how to deal with each fish passed by the previous loop.
Testing the outcome of two fish crossing each other becomes simple now that we have the direction and size into a single variable so to test if a fish is going upstream or downstream we just compare it to zero:

if(fish<0)
//fish is floating upstream
else
//downstream

and to test which fish is bigger we just need to compare their absolute values

Math.abs(fish1)<Math.abs(fish2)

To start, we need to loop on the stack. Remember: once we introduce a new fish to the stack we need to make sure to check if it’s going to eat one or more of the survivors we collected before !
of course the first fish that’s going to be attacked if the conditions are met is the last element of the stack, once eaten we keep moving to the previous one until we find another fish that floats in the opposite direction and then either:
-our fish is bigger: in this case we remove the last fish from the stack or..
-the last fish is bigger: we stop the loop and bring up a new fish from the remaining ones.
if when looping on the stack we reach one of these cases:
-the beginning of the stack
-a fish going in the same direction (upstream)
We insert the new fish in the stack and it becomes the last fish

for(var i=survivors.length-1;i>=0;i--){
         var lastFish=survivors[i]
             if(lastFish>0 && fish<0) {//last fish is going down
                if(Math.abs(lastFish)<Math.abs(fish)) {// fish is bigger
                    survivors.pop()
                    if(i<=0){
                        survivors.push(fish)
                        break;
                    }
                }
                else
                    break;
            }
            else{
                survivors.push(fish)
                break
            }
        }

Once the loop on the fish is done, we gets an array containing all the fish that survived, again all you have to do here is to return its length

This solution may bring a 100% score but I am sure there’s an alternative with less lines of code, if you think you have this alternative and it has 100% score then don’t hesitate to share it with me as I am curious to see which approach you have followed.