Monday, September 10, 2012
A frog jumping
A frog can jump a river of n meters and at each step she can jump either x-1 or x or x+1 meter if she jumped x meter at the previous step. She can jump just if the starting place and the ending place has a stone. The available stones are maintained in an array S[i] given as input. The first just is just 1 meter. Can you compute whether or not the frog will arrive at the destination?
Subscribe to:
Post Comments (Atom)
Here my solution and my assumptions. Essentially is a path discovery algorithm where I explore all the possible paths from the current position given the possible moves I can do.
ReplyDeleteAssumptions: the array S is a binary array with the following meaning:
S[i]=0 there is no stone at position i
S[i]=1 there is a stone at position i
I assume that the stones could be placed exact N meters (N>=0) away from each other. In other words S[i] tells you if you have a stone on the i-th meter from the coast, since the frog seems to move with "discrete" jumps that are multiple of 1 meter.
By the description of the problem it seems that the frog can move both forward and backward by x-1, x or x+1 meters having jumped by x meters on the last jump.
Here the algorithm:
public static void main(String[] args) {
int[] S = new int[] {0, 1, 0, 1, 1, 0, 1};
List jumps = new ArrayList();
jumps.add(1); // the frog jumps 1 meter at the beginning
System.out.println(jump(S, 1, 1, jumps) + ": " + jumps);
}
public static boolean jump(int[] S, int x, int i, List jumps) {
if (i < 0) return false;
if (i >= S.length) return true;
if (S[i] <= 0) return false;
S[i] = -1;
int[] next = new int[] {1-x, -x, -(x+1), x-1, x, x+1};
for (int j = 0; j < next.length; j++) {
int jump = next[j];
jumps.add(i + jump);
if (jump(S, jump, i + jump, jumps)) {
return true;
}
jumps.remove(jumps.size() - 1);
}
S[i] = 1;
return false;
}
One key aspect of this exploration logic is that the frog must avoid infinite loops (jumping back and forth on the same stones, or jumping in place). This is addressed by marking the explored stones as already visited. the algo do that by changing the sign in S of the current position. If the next jump brings the frog on an already visited stone then the algo rollbacks, discards that possible path and moves forward in evaluating the next one.
The alog explores all the possible paths and stops as soon as one successful strategi is found (if any).
I've not time to do more research on this problem, but it seems that this solution is just an implicit BFS on the graph of all the possible paths. Interesting....