This problem is adapted from a problem in CodeForces, the premier Russian competitive coding problem collection and online judge. Even if you never participate in competitive coding contests, we can still partake in the most important contest of them all, trying to beat the yesterday's version of yourself. You never know when that extra coding strength and knowledge of little techniques will come handy in the future. Inside a version of the classic video game Frogger updated for the needs of our course, an army of frogs is standing at the edge of a canyon, aiming to escape to the other side to avoid the fate of being slowly boiled in their tanks. The distance between the canyon edges is far too long for even the mightiest frog to levitate its way across. The good news is that a row of boxes has been magically suspended to float in the mid-air between the edges of the canyon. The bad news is that each of these boxes can be used only once, since each box vanishes the moment that some frog propels itself off it. Given the x-coordinate positions of the boxes and the jumping strength of each frog, how many frogs are able to cross the canyon successfully? In your labs project, I need to make a new class named FrogCrossing, and there the method public static int maximumFrogs(int[] strength, int[] boxes) The first parameter strength is an array whose length equals the number of frogs in the army. The element strength[i] gives the maximum distance between two boxes that the frog i can clear with a single hop. The strength array is guaranteed to be sorted in descending order so that the strongest frogs take their turn first, the way Nature and Nature's God dictated it to be. The second parameter boxes gives the horizontal coordinates of the boxes floating in the canyon, listed in ascending order. The first and the last element of this array are the fixed positions of the edges of the canyon that do not vanish when used by some frog. For example, if strength equals {7, 5, 4} and boxes equals {0, 3, 4, 6, 8, 10, 11}, it is possible for the strongest two frogs to cross the canyon from the edge at x = 0 to the opposite edge at x = 11, with several different ways to achieve this. However, no matter how you try to finagle it, all three frogs will not be able to cross the canyon, as can be established with the following argument. The two weakest frogs will use up the boxes at x = 3 and x = 4, and then the boxes at x = 6 and x = 8. Since this uses up all the boxes between x = 0 and x = 10, the first frog can now only imitate Wiley E. Coyote. Having the strongest frog cross first changes nothing, since he will use up at least one box before the box at x = 10 that was necessary for the other two frogs to cross the canyon successfully. This problem is best solved recursively with the aid of the aid of the private utility method that determines whether it is possible for the k strongest frogs to cross the canyon. The public method maximumFrogs should consist of a single loop that counts the values of k from the size of the army down to zero, and return the largest value of k for which the recursive method given below returns true to indicate a successful crossing. If there is no solution using the k strongest frogs, abandon the weakest of those frogs as the Cold Equations of Nature dictate, and try to find the solution for the k - 1 strongest frogs. (This solution illustrates the general technique known as iterative deepening that often comes handy in recursive optimization problems of this nature.) private static boolean canCross(int[] strength, int[] boxes, int[] atBox, boolean[] used) The first two parameters strength and boxes are the same as in the previous method, and their contents do not change during this recursion. The k-element array atBox gives the index of the box that each frog is currently standing on. (You should use the indices of the boxes directly instead of their x-coordinate values, to make the lookup of boxes and their successors faster.) At the top-level call, the values of the atBox array are all zeros, since every frog starts at the edge of the canyon. The fourth parameter is a truth valued array to keep track of which boxes have already been used by some frog so that other frogs can't hop on them any more. The base case of this recursion is when every element of atBox equals boxes.length-1, for all k frogs having successfully crossed the canyon. Otherwise, find the frog currently on the box with the lowest x-coordinate. If it is possible for that frog to jump directly to the opposite edge, make it do so and update the atBox array accordingly, and try to solve the rest of the problem recursively. If the leftmost frog cannot reach the opposite edge directly, use a while-loop to iterate through the unused boxes that it can reach with a single jump. For each such box, see what happens when making the frog jump on that box and update the atBox and used arrays accordingly, and try to solve the problem recursively for the new situation of frogs and boxes. If that recursive call returns true, your loop can also stop and return true, since we are looking for any one working solution. Otherwise, continue looping over the rest of the reachable boxes to if the leftmost frog jumping there would produce a more favourable result. Once you have tried jumping on every reachable box but the recursive calls from those jumps led only to failure, your method can also stop and return false. Since the hop sequences of the crossing frogs never intersect each other in their visited the floating boxes and can therefore be arbitrarily interleaved and still remain successful, there is no point looping over the other frogs in search for a solution. If some solution existed starting with some frog other than the current leftmost one, that solution would have been found by starting with the leftmost frog. We shall leave it as an exercise for the reader to note other hard and thus useful constraints that can be used speed up this basic search. Your mind will answer most questions if you learn to relax and wait for the answer. In this kind of branching recursive searches it is hugely important to detect inevitable failures as soon as possible. In that frozen moment when everyone sees what is on the end of every fork, you should turn back and return to the previous level of recursion to try out some earlier alternative instead.

Answer rating: 100% (QA)

Code for FrogCrossing Problem in Java Heres the Java code for the FrogCrossing ... View the full answer