CareerCup

It's a Dynamic Programming problem with recursive function as

CanReach(i,j) = { true if stone[i] is true && (CanReach[i-j][j-1] || CanReach[i-j][j] ||CanReach[i-j][j+1])
where,
i is the stone
j is the velocity when the frog reached i

bool CanCross(vector<bool> vecStones)
{
	vecStones.push_back(true); // last true for the land, it makes things simpler
	int size = vecStones.size();
	vector<vector<bool>> vecCanReach(size, vector<bool>(size, false));

	vecCanReach[0][1] = true;
	for (int i = 1; i < size; i++)
	{
		if (vecStones[i] == false)
			continue;
		for (int j = i - 1; j >= 0; j--)
		{
			if (vecStones[j] == false)
				continue;
			if (vecCanReach[j][i - j] || ((i - j - 1 >= 0) && vecCanReach[j][i - j - 1]) || ((i - j + 1 < size) && vecCanReach[j][i - j + 1]))
				vecCanReach[i][i - j] = true;
		}
	}

	for (int i = 0; i < size; i++)
	{
		if (vecCanReach[size - 1][i])
			return true;
	}
	return false;
}

Search all options but do not revisit states (position, speed).

unordered_set<pair<int, int>> visited;
bool CanCross(vector<bool> field, int i, int speed) {
    if (i >= field.size())
        return true;
    pair<int, int> state(i, speed);
    if (!field[i] || speed <= 0 || visited.count(state))
        return false;
    visited.insert(state);
    return CanCross(field, i+speed, speed) 
	|| CanCross(field, i+speed+1, speed+1) 
        || CanCross(field, i+speed-1, speed-1);
}

Here's a solution is python. Pretty easy to understand

def canCrossHelper(path, v, index):
    if index >= len(path):
        return True
    if v <= 0:
        return False
    if path[index] == False:
        return False
    if canCrossHelper(path, v+1, index + v + 1) or canCrossHelper(path, v-1, index + v - 1) or canCrossHelper(path, v, index + v):
        return True
    return False

def canCross(path):
    return canCrossHelper(path, 1, 0)

I just use recursion plus memoization, by using a HashSet to store all the (index, velocity) pairs I have seen.

import java.util.*;

class CrossArray {
	private static HashSet<String> visited = new HashSet<String>();

	public static boolean canCross(boolean arr[]) {
		return canCrossHelper(arr, 0, 1);
	}

	public static boolean canCrossHelper(boolean arr[], int index, int velocity) {
		String key = "" + index + "-" + velocity;
		if(visited.contains(key))
			return false;
		for(int v=velocity-1; v<=velocity+1; v++) {
			if(v == 0)
				continue;
			int newIndex = v+index;
			if(newIndex >= arr.length)
				return true;
			if(arr[newIndex] && canCrossHelper(arr, newIndex, v))
				return true;
		}
		visited.add(key);
		return false;
	}

	public static void main(String[] args) {
		boolean arr[] = new boolean[] 
			{true, true, false, true, false, true, false, false, false, true};
		boolean arr2[] = new boolean[]
			{true, true, false, true, false, true, true, false, false, true, false};
		System.out.println(canCross(arr));
		System.out.println(canCross(arr2));
	}
}

{true, true, false, true, false, true, false, false, false, true}: how this doesn't get a route? Can somebody explain the problem statement still clear?

Here is C# Code

public static void VelocityJump()
        {
            bool[] just = { true, true, false, true, false, true, true, false, false, true, false };
            int velocity = 1;
            for (int i = 0; i < just.Length; i += velocity)
            {
                if (i == just.Length - 1 || i + velocity == just.Length - 1 || i + velocity + 1 == just.Length - 1)
                {
                    Console.WriteLine("Rabbit can cross");
                    break;
                }
                if (!just[i] || i + (velocity - 1) >= just.Length || i + velocity >= just.Length)
                {
                    Console.WriteLine("Rabbit can not jump");
                    break;
                }
                if ((i+velocity+1 < just.Length) && (just[i + velocity + 1]))
                    velocity++;
                else if ((i+velocity<just.Length) && !just[i+velocity])                
                {
                    if (i != 0) velocity--;
                }
            } 
        }