In this post we will attempt to solve the Codility_ problem Fish (https://app.codility.com/programmers/lessons/7-stacks_and_queues/fish/) in which we are given 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. 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: o 0 represents a fish flowing upstream, o 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: o If A[P] > A[Q] then P eats Q, and P will still be flowing downstream, o 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. Given two non-empty arrays A and B consisting of N integers, returns the number of fish that will stay alive.
The problem statement is rather long. I had to read it several times to make sure I understood what was required from the function of interest. We need to determine what happens when fish swimming upstream or downstream meet or not meet. If they meet, given that all fish are of different sizes, one of them eats the other (I guess that is why the problem statement calls them voracious).
I will attempt to solve the problem using Java and the VSCode IDE on a Windows computer. When satisfied will copy and paste the contents of the function of interest to the IDE provided by Codility_ and will submit the code for evaluation. The simplest way to solve the problem is to directly write code in the online IDE provided by Codility_. Since I am not following such a step, we will have to generate a test scaffold which IS NOT PART OF THE SOLUTION.
Before we get into the code for the test scaffold, let’s spend a few moments to go over the ways fish will encounter other fish.
current alive fish dir 0 0 0 current upstream and alive upstream (do not meet) 0 1 -1 current upstream and alive downstream (meet) 1 0 1 current downstream and alive upstream (do not meet) 1 1 0 current and alive downstream (do dot meet)
The description of the problem indicates that fish are swimming upstream or downstream. There are four possible situations as indicated by the table. We will keep track of the fish that are alive and the interaction with the current fish as we traverse the arrays.
public int fish(int[] A, int[] B) {
}
Since we are using Java the signature for the function of interest requires two input arrays. One will hold the sizes of the fish and the other the direction in which each fish is swimming in the river. The function needs to return the number of fish that will remain alive.
For a fish to remain alive, they do not meet (swim in the same direction) or if they meet (swim in opposite directions) the largest remain alive because it will devour the smaller.
4,3,2,1,5 0,1,0,0,0 main <<< a: [4, 3, 2, 1, 5] main <<< b: up <- 0 [0, 1, 0, 0, 0] 1 -> down <<< i: 0 size: 4 dir: 0 <<< i: 0 alive: [0] <<< i: 1 size: 3 dir: 1 <<< i: 1 alive: [0, 1] <<< i: 2 size: 2 dir: 0 <<< i: 2 alive: [0, 1] <<< i: 3 size: 1 dir: 0 <<< i: 3 alive: [0, 1] <<< i: 4 size: 5 dir: 0 <<< i: 4 alive: [0, 4] <<<< alive: [0, 4] main <<< result: 2 6,4,3,2,1,5,7 0,1,0,0,0,1,0 main <<< a: [6, 4, 3, 2, 1, 5, 7] main <<< b: up <- 0 [0, 1, 0, 0, 0, 1, 0] 1 -> down <<< i: 0 size: 6 dir: 0 <<< i: 0 alive: [0] <<< i: 1 size: 4 dir: 1 <<< i: 1 alive: [0, 1] <<< i: 2 size: 3 dir: 0 <<< i: 2 alive: [0, 1] <<< i: 3 size: 2 dir: 0 <<< i: 3 alive: [0, 1] <<< i: 4 size: 1 dir: 0 <<< i: 4 alive: [0, 1] <<< i: 5 size: 5 dir: 1 <<< i: 5 alive: [0, 1, 5] <<< i: 6 size: 7 dir: 0 <<< i: 6 alive: [0, 6] <<<< alive: [0, 6] main <<< result: 2 6,4,3,2,1,5 0,1,0,0,0,1 main <<< a: [6, 4, 3, 2, 1, 5] main <<< b: up <- 0 [0, 1, 0, 0, 0, 1] 1 -> down <<< i: 0 size: 6 dir: 0 <<< i: 0 alive: [0] <<< i: 1 size: 4 dir: 1 <<< i: 1 alive: [0, 1] <<< i: 2 size: 3 dir: 0 <<< i: 2 alive: [0, 1] <<< i: 3 size: 2 dir: 0 <<< i: 3 alive: [0, 1] <<< i: 4 size: 1 dir: 0 <<< i: 4 alive: [0, 1] <<< i: 5 size: 5 dir: 1 <<< i: 5 alive: [0, 1, 5] <<<< alive: [0, 1, 5] main <<< result: 3 6,4,3,7,1,5 0,1,0,0,0,1 main <<< a: [6, 4, 3, 7, 1, 5] main <<< b: up <- 0 [0, 1, 0, 0, 0, 1] 1 -> down <<< i: 0 size: 6 dir: 0 <<< i: 0 alive: [0] <<< i: 1 size: 4 dir: 1 <<< i: 1 alive: [0, 1] <<< i: 2 size: 3 dir: 0 <<< i: 2 alive: [0, 1] <<< i: 3 size: 7 dir: 0 <<< i: 3 alive: [0, 3] <<< i: 4 size: 1 dir: 0 <<< i: 4 alive: [0, 3, 4] <<< i: 5 size: 5 dir: 1 <<< i: 5 alive: [0, 3, 4, 5] <<<< alive: [0, 3, 4, 5] main <<< result: 4 0,1 1,1 main <<< a: [0, 1] main <<< b: up <- 0 [1, 1] 1 -> down <<< i: 0 size: 0 dir: 1 <<< i: 0 alive: [0] <<< i: 1 size: 1 dir: 1 <<< i: 1 alive: [0, 1] <<<< alive: [0, 1] main <<< result: 2 1 1 main <<< a: [1] main <<< b: up <- 0 [1] 1 -> down main <<< result: 1 1 0 main <<< a: [1] main <<< b: up <- 0 [0] 1 -> down main <<< result: 1
I believe that the first test case is the example provided by Codility_. The others test some conditions or were generated as variations of the first.
Our test code will read the two input lines. The first holds the sizes for the fish and the second the direction the fish are swimming in the river. A 0 represents upstream and a 1 represents downstream.
Our test code reads the input lines, populates the two arrays and displays their values so we can check that all is well so far. When the array holding the directions in which the fish swim is displayed I added an arrow to help understand what is going on.
Our test code seems to call the function of interest which displays a few statements that can be used to follow the algorithm while we process all the fish in the river.
We will talk about them when we get to the actual code.
When all is said and done the function of interest returns the number or fish that remain alive in the river. In the first test case our result seems to match the result provided with the requirements in the Codility_ website.
/**
* Test scaffold
* !!! NOT PART OF SOLUTION !!!!
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read int[] array a ****
int[] a = Arrays.stream(br.readLine().trim().split(","))
.mapToInt(Integer::parseInt)
.toArray();
// **** read int[] b ****
int[] b = Arrays.stream(br.readLine().trim().split(","))
.mapToInt(Integer::parseInt)
.toArray();
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< a: " + Arrays.toString(a));
System.out.println("main <<< b: up <- 0 " + Arrays.toString(b) + " 1 -> down");
// **** call function of interest and display result ****
System.out.println("main <<< result: " + fish(a, b));
}
The test code which is NOT PART OF THE SOLUTION, uses a buffered reader to read the contents of the two input arrays. It then displays the contents of the arrays which allows us to determine if all is well so far.
The function of interest is then called and the result is displayed.
/**
* Return the number of fish that will stay alive.
*
* Execution: O(n) - Space: O(n)
*/
static public int fish(int[] a, int[] b) {
// **** sanity check(s) ****
if (a.length == 1) return 1;
// **** initialization ****
Stack<Integer> alive = new Stack<>();
// **** process each fish - O(n) ****
for (int i = 0; i < a.length; i++) {
// **** current fish size (for ease of use) ****
int size = a[i];
// **** current fish direction (for ease of use) ****
int dir = b[i];
// ???? ????
System.out.println("<<< i: " + i + " size: " + size + " dir: " + dir);
// **** this fish is alive (for now) ****
if (alive.empty()) alive.push(i);
// **** check these fish ****
else {
// **** check if this fish eats alive fish ****
while (!alive.empty() && dir - b[alive.peek()] == -1 && a[alive.peek()] < size)
alive.pop();
// **** ****
if (!alive.empty()) {
// **** these fish do not meet; this fish is alive (for now) ****
if (dir - b[alive.peek()] != -1)
alive.push(i);
} else {
// **** this fish is alive (for now) ****
alive.push(i);
}
}
// ???? ????
System.out.println("<<< i: " + i + " alive: " + alive.toString());
}
// ???? ????
System.out.println("<<<< alive: " + alive.toString());
// **** number of fish alive ****
return alive.size();
}
We start by performing a sanity check. You can find two test cases to verify it works.
We will use a stack to keep the current live fish in the river. The top of the stack represents the current fish which may be eaten by other fish if encountered in the river.
We enter a loop that will be used to determine which fish remain alive swimming up or down stream in the river.
For ease of use we put into the size variable the size of the current fish and into the dir variable the direction in which the current fish is swimming. The alive fish in the stack will have to deal with other fish as we check the remaining fish in the river.
If the stack is empty then the current fish is pushed into the alive stack.
If the stack is not empty we need to check if the current fish is able to eat the smaller fish on the top of the stack. It is possible it could eat all fish if the fish alive are swimming downstream and they are smaller than the current fish. If an alive fish is swimming upstream then it will be saved.
The current fish may end on the top of the alive stack if it does not meet a fish on the top of the stack or if it ate all the alive fish it found. To verify this logic take a look at any example and follow each fish as it swims in the river. Keep in mind that the printed statements ARE NOT PART OF THE SOLUTION.
When all is said and done, the alive stack will hold the indices for all the fish that were not eaten while swimming in the river. Our function of interest returns the number of elements in the alive stack.
The function of interest executes in O(n) time and in the worst case uses O(n) space. This happens when all fish are swimming in the same direction and they do not get to meet and eat others.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository named Fish.
Please note that the code here presented might not be the best possible solution. In most cases, after solving the problem, you can take a look at the best accepted solution provided by the different websites (i.e., Codility_, HackerRank, LeetCode).
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer / engineering toolset.
Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.
Enjoy;
John