DushDushDush DushDushDush -4 years ago 213
Java Question

Brute Force the Frog Jumping Game




The last variation of the Frog Jumping is shown at the end of the video.


In short, you have n number of lily pads in a line and one frog on
each one.

In the last variation (the one I want to brute force), the second
first and second last lily pads do not have a frog. Your goal is to
get all frogs to the same lily pad. Each frog can jump right or left
based on the number of frogs on its lily pad, but can't jump on a
empty lily pad.

(pad with 1 frog moves 1 spot, pad with n frogs moves only n spots)

Example of a solution for n=12: (there are no solutions below 12)

[1,0,1,1,1,1,1,1,1,1,0,1] - Starting formation of frogs. (counting
frogs from 0. to 11.)
[1,0,1,0,2,1,1,1,1,1,0,1] - Frog 3. jumped
right
[1,0,1,0,2,1,2,0,1,1,0,1] - Frog 7. jumped left

[1,0,1,0,4,1,0,0,1,1,0,1] - Frogs 6. jumped left

[5,0,1,0,0,1,0,0,1,1,0,1] - Frogs 4. jumped left

[0,0,1,0,0,6,0,0,1,1,0,1] - Frogs 0. jumped right

[0,0,1,0,0,0,0,0,1,1,0,7] - Frogs 5. jumped right

[0,0,1,0,0,0,0,0,0,2,0,7] - Frogs 8. jumped right

[0,0,1,0,0,0,0,0,0,0,0,9] - Frogs 9. jumped right

[0,0,10,0,0,0,0,0,0,0,0,0] - Frogs 11. jumped left- solved



I want to find solutions for n frogs, if the solution exists. I know by hand that 12,14,15,16,17,18,19,20 have at least one solution and that 1-11 and 13 do not have a solution.

I tried writing a piece of code that would run through all combinations to find a solution for n lily pads.

EDIT: The code works now, thanks to OleV.V., also added logging.

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

// # Brute Force # Brute Force # Brute Force # Brute Force # Brute Force # //
public class Frogger {

/**
* PUBLIC STATIC GLOBAL VARIABLES - Modify these as you wish.
*
* Time Data: Levels < 20 ~ around couple seconds
* Level = 20 ~ around a minute
* Level = 21 ~ around a quarter of an hour
* Level = 22 ~ around a sixth of a minute
* Level = 23 ~ around half an hour
* Level = 24 ~ around a minute
*
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
public static int Level = 12;
public static boolean LogSolution = true;
public static boolean LogAll = false;
/** * * * * * * * * * * * * * * * * * * * * * * * * * * * */

// used for logging
private static Deque<Jump> solution = new ArrayDeque<>(Level);
private static double time;

public static void main(String[] args) {

// log the time
time = System.currentTimeMillis();

// build the world & start jumping
run(Level);
}

public static void run(int n) {

// create the world
int[] world = new int[n];
for (int i = 0; i < n; i++) {
world[i] = 1;
}
world[1] = 0;
world[n-2] = 0;

// start jumping
if (Level > 11 || Level == 13) jump(world);
else System.out.println("Unsolvable");
}


//////////////////////////////////////////////////////

public static void jump(int[] world) {

for (int i = 0; i < world.length; i++) {

if (world[i] != 0) { // pad has a frog

// check if it is solved at current pad
if (world[i] == Level - 2) {
System.out.println("SOLUTION: " + Arrays.toString(world));
System.out.println(solution);
System.out.println("\n" + (System.currentTimeMillis() - time) / 1000 + " seconds");
System.exit(0);
}

// roll-back var
int temp = 0;

// attempts to make a RIGHT jump

if (world[i] + i < world.length) { // right jump is in bound
if (world[i + world[i]] != 0) { // can't jump on empty pad

temp = world[i];

// jump RIGHT
world[i + world[i]] += world[i];
world[i] = 0;

solution.push(new Jump(temp, i, i + temp)); // log the solution step 1/2
if (LogSolution) if (LogAll) System.out.println( "J: " + Arrays.toString(world)); // log the jump

// continue jumping
jump(world);

// roll-back right jump
world[i] = temp;
world[i + world[i]] -= world[i];

if (LogAll) System.out.println("R: " + Arrays.toString(world)); // log the rollback
if (LogSolution) solution.pop(); // log the solution step 2/2
}
}

// attempts to make a LEFT jump

if (i - world[i] >= 0) { // left jump is in bound
if (world[i - world[i]] != 0) { // can't jump on empty pad

temp = world[i];

// jump LEFT
world[i - world[i]] += world[i];
world[i] = 0;

if (LogSolution) solution.push(new Jump(temp, i, i - temp)); // log the solution step 1/2
if (LogAll) System.out.println("J:" + Arrays.toString(world)); // log the jump

// continue jumping
jump(world);

// roll-back left jump
world[i] = temp;
world[i - world[i]] -= world[i];

if (LogAll) System.out.println("R: " + Arrays.toString(world)); // log the rollback
if (LogSolution) solution.pop(); // log the solution step 2/2
}
}
}
}
}

}





Side note: This problem was mathematically solved for all solvable n (all n > 11, other than 13, have a solution, reachable by a generalized method). This piece of code is just me attempting to do some recursion in java.

Answer Source

Glad you got it to work. I don’t think you need my code now, but I will give at the bottom of this answer in case.

First, how does one log a solution? I guess you’re thinking that knowing that the end result was [0, 0, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0] is not that interesting; we’d like to know how it was obtained. I will present two ways.

The easier way is store each step as it is tried and then delete it when backtracking. Then when you get to the solution, you have also stored the steps that lead to it. Use a stack or similar:

private static Deque<Jump> solution = new ArrayDeque<>(Level);

(java.util.ArrayDeque is the recommended class for both stacks and queues; for a stack ArrayList is another option.) Now in your code, where it says log the jump do

                    solution.push(new Jump(temp, i, i + temp));

At log the rollback do

                    solution.pop();

Use a simple auxiliary class Jump that could for instance look like this:

public class Jump {
    int count;
    int from;
    int to;

    public Jump(int count, int from, int to) {
        this.count = count;
        this.from = from;
        this.to = to;
    }

    @Override
    public String toString() {
        return "" + count + " frog/s jump from " + from + " to " + to;
    }
}

When I tried it in my solution, one search took 20 % longer. I’d say it’s acceptable. If you are very concerned about performance, only log on your way out from having found the solution. This will require you to return a boolean to indicate success rather than using System.exit() for stopping the search. Now your recursive call becomes:

                    if (jump(world)) {
                        solution.push(new Jump(temp, i, i + temp));
                        return true;
                    }

You get the elements in your solution stack in the opposite order than before, I expect you to figure that out. Also instead of System.exit(0); do return true;. At the bottom of the method, return false. I have not measured performance impact, but I expect it to be minute compared to logging nothing. Now you can get output like:

1 frog/s jump from 3 to 4
1 frog/s jump from 7 to 6
2 frog/s jump from 6 to 4
4 frog/s jump from 4 to 0
5 frog/s jump from 0 to 5
6 frog/s jump from 5 to 11
1 frog/s jump from 8 to 9
2 frog/s jump from 9 to 11
9 frog/s jump from 11 to 2

Finally here’s how I did, just for the sake of completeness. I haven’t spotted any interesting differences from your code.

public static void jump(int[] world) {
    for (int fromIndex = 0; fromIndex < world.length; fromIndex++) { // index of pad to jump from
        // any frog/s here?
        int frogsJumping = world[fromIndex];
        if (frogsJumping > 0) {
            // try to jump left; frogsJumping frogs jump frogsJumping places
            int targetIndex = fromIndex - frogsJumping;
            if (targetIndex >= 0 && world[targetIndex] > 0) { // must not jump to empty pad
                performJump(fromIndex, targetIndex, world, frogsJumping);
            }
            // try a right jump
            targetIndex = fromIndex + frogsJumping;
            if (targetIndex < world.length && world[targetIndex] > 0) {
                performJump(fromIndex, targetIndex, world, frogsJumping);
            }
        }
    }
}

private static void performJump(int fromIndex, int toIndex, int[] world, int frogsJumping) {
    solution.push(new Jump(frogsJumping, fromIndex, toIndex));
    world[fromIndex] = 0;
    world[toIndex] += frogsJumping;
    if (world[toIndex] == noOfFrogs) {
        System.out.println("Solved: " + Arrays.toString(world));
        System.exit(0);
    }
    jump(world);
    // backtrack
    world[toIndex] -= frogsJumping;
    world[fromIndex] = frogsJumping;
    solution.pop();
}
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download