Problem Statement :
Below given are two arrays indicating the size of the arrays and the direction in which they are moving. A bigger fish can eat a smaller fish if they are moving in opposite direction.
Two fishes moving in same direction cannot eat each other because all the fishes are moving at a constant speed. Print the output of the fishes which survives
Fishes with distinct sizes and with their direction of movement from their current index
| 10 |
11
|
8
|
5
|
3
|
4
|
6
|
9
| 2 |
1
|
7
|
| <-- | <-- | --> | --> | --> | <-- | <-- | <-- | <-- | <-- |
-->
|
Output :
| 10 |
11
|
9
|
3
|
1
|
7
|
| <-- | <-- | <-- | <-- | <-- | --> |
Explanation of output:
Fishes with size 10 and 11 won't collide hence escapes,
4 eats 3, 5 eats 4 , 6 eats 5 , 8 eats 6 , 9 eats 8, then 2 and 1 survives because their behind bigger fish 9. Fish 7 survives because from its current position it will not collide with any other fish , hence the output.
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 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 | import java.util.Stack; /** * Bigger fisehes eat smaller ones , in diff direction , * No Fish Eats any other fish of same direction. * Assume all fish sizes are different * @author prateek */ public class EatFishProblem { public static void main(String[] args) { int[] arr1 = {10, 11, 8, 5, 3, 4, 6, 9, 2, 1 , 8} ; int[] dir1 = {-1, -1, 1, 1, 1, -1, -1, -1, -1, -1 , 1} ; solve(arr1,dir1); } static boolean solve(int[] arr,int[] dir){ Stack<Integer> rightDir = new Stack<Integer>(); Stack<Integer> leftDir = new Stack<Integer>(); int i = 0; //Skip all fishes moving to left in the beggining while(dir[i]!=1){ printFish(arr[i],dir[i]); i++; } int len = arr.length ; while(i<len){ if(dir[i] ==1 ) rightDir.push(arr[i]); else leftDir.push(arr[i]); eatFish(leftDir,rightDir); //if Fishes are empty in right stack, print fishes of the left stack //because these fishes moving to the left wont ever collide with subsequent fishes moving the right if(rightDir.isEmpty()) printStackInReverse(leftDir,-1); i++; } //Print Fishes moving the right first printStackInReverse(rightDir,1); printStackInReverse(leftDir,-1); return false; } /** Print stack in reverse order */ static void printStackInReverse(Stack<Integer> stack, Integer direction) { if(stack.isEmpty()) return ; Stack<Integer> temp = new Stack<Integer>(); while (!stack.isEmpty()) temp.push(stack.pop()); while (!temp.isEmpty()) printFish(temp.pop(), direction); } /** Eats fish from the stacks , depending on size */ static void eatFish(Stack<Integer> left, Stack<Integer> right){ while(!(left.isEmpty() || right.isEmpty())){ if(left.isEmpty() || right.isEmpty()) return ; else if(left.peek() > right.peek()) right.pop(); else if(left.peek() < right.peek()) left.pop(); else return ; } } static void printFish(int size, int direction){ System.out.println(direction == 1 ? size + "--> " : "<--"+size + " "); } } |
Post your comments and suggestions if any.
Happy Coding :)
Happy Coding :)
In the example above, in output it should be 2 and not 3.
ReplyDelete