CareerCup

EDITED July 7th '17:
- changed the assumption about start condition
- added the decrease jump into the recursion
- specified more clearly assumption what "jump of 1" means
- corrected some typos


Assumption:
- the first field must be 1, because that's where it starts, then one can decide to
jump to the 2nd field (keep jump of 1) or the 3rd (increase)
- jump of 1 means jumping from e.g. index 0 to 1, increase that jump by 1, it jumps
from 1 to 3 etc.

Solution:

First start by writing down the recursion of the problem:

recursion = dp(i, j) = max[
                            dp(i + j, j),               // if i < n and arr[i]
                            dp(i + j + 1, j + 1),       // if i < n and arr[i] 
                            dp(i + j - 1, j - 1)        // if i < n and arr[i] and j > 1
                        ] // max just acts as or, since dp(...) will return True / False                        
                       False, if i < n and not arr[i]
                       True, if i >= n

i = position, j = jump, n = array length, arr = input-array
passable = dp(0, 1)

this has O(3^n) time complexity, because at most recursion step, it spans three
execution, so it doubles at every step and there are n steps. space is O(n),
used by call stack. There is a tighter bound although.

improvement is memorization which brings it down to O(n^2) time complexity.

alternatively an iterative solution can be created with O(n^2) time and
space complexity.

in python 3

# the recursive solution
def is_passable(arr):    
    def dp(i, j):
        if i >= n:
            return True #  it
        if not arr[i]:
            return False # landed on 0
        key = i * (n + 1) + j
        val = memo.get(key)
        if val is not None: 
            return val            
        val = dp(i + j, j) # try with same distance jump
        if not val: # if not successful, try increasing jump 
            val = dp(i + j + 1, j + 1)
        if not val and j > 1: # if not successful and jump can be decreased
            val = dp(i + j - 1, j - 1)        

        memo[key] = val
        return val

    n = len(arr)
    memo = {}
    return dp(0, 1)

# the more elegant iterative solution
def is_passable_itr(arr):
    n = len(arr)
    dp = [[False for i in range(n + 2)] for j in range(n)]
    dp[0][1] = True # start condition
    for i in range(1, n):
        if not arr[i]:
            continue
        for j in range(1, i + 1): # this i + 1 is bad, because at i = 27, max jump is 8 ... etc...
            if dp[i - j][j] or dp[i - j][j - 1] or dp[i - j][j + 1]:
                dp[i][j] = True
                if i + j + 1 >= n: 
                    return True
    return False

print(is_passable([1,1,0,1,0,0,1,0,0,1])) # sample with increasing steps
print(is_passable_itr([1,1,0,1,0,0,1,0,0,1]))
print(is_passable([1,1,1,1,1,1,0,0,0,0])) # sample given by missing, that shouldn't work according to my understanding of the problem
print(is_passable_itr([1,1,1,1,1,1,0,0,0,0]))
print(is_passable([1,0,1,0,0,1,0,1,0,0,1])) # sample with increasing steps, decreasing and increasing step
print(is_passable_itr([1,0,1,0,0,1,0,1,0,0,1])) # sample with increasing steps, decreasing and increasing step

#output:
#True
#True
#False
#False
#True
#True

DP solution. Time : O(n^2) Space: O(N^2)

boolean find(int[] a){
		int n = a.length;
		boolean[][] mat = new boolean[n][n];
		
		if(a[0] != 1 || a[1] != 1) return false;
		
		mat[1][0] = mat[1][1] = true; 
		for(int i = 1; i < n; i++){
			if(a[i] == 0) continue;
			for(int j = 1; j < n; j++){
				if(mat[j][i]){
					if(j > 1){
						if(i + j -1 < n) mat[j-1][i+j-1] = (a[i+j-1] == 1);
						else return true;
					}
					if(i + j < n) mat[j][i+j] = (a[i+j] == 1);
					else return true;
					if(i + j + 1 < n) mat[j+1][i+j+1] = (a[i+j+1] == 1);
					else return true;
				}
			}
		}
		return false;
	}

static boolean find(int[] a){
		int n = a.length;
		boolean[][] mat = new boolean[n][n];
		
		if(a[0] != 1 || a[1] != 1) return false;
		
		mat[1][0] = mat[1][1] = true; 
		for(int i = 1; i < n; i++){
			if(a[i] == 0) continue;
			for(int j = 1; j < n; j++){
				if(mat[j][i]){
					if(j > 1){
						if(i + j -1 < n) mat[j-1][i+j-1] = (a[i+j-1] == 1);
						else return true;
					}
					if(i + j < n) mat[j][i+j] = (a[i+j] == 1);
					else return true;
					if(i + j + 1 < n) mat[j+1][i+j+1] = (a[i+j+1] == 1);
					else return true;
				}
			}
		}
		return false;
	}

#include <iostream>
#include <string.h>
using namespace std;
 
int count = 0;
int cache[10];
 
bool canPass(int arr[], int n, int pos, int v) {
	count++;
	if (pos >= n)
		return true;
	if ((v <= 0) || arr[pos] == 0)
		return false;
	if (cache[v] != -1)
		return cache[pos];
 
	return cache[v] = canPass(arr, n, (pos + v), v) || canPass(arr, n, (pos + (v - 1)), (v - 1)) ||
	canPass(arr, n, (pos + (v + 1)), (v + 1));
}
 
int main() {
	int pass[] = {1,1,0,1,0,1,1,1,0,1};
	int N = sizeof(pass) / sizeof(pass[0]);
	memset(cache, -1, sizeof(cache));
	cout << canPass(pass, (N - 1), 0, 1);
	cout << endl << count;
	return 0;
}

@missing, how can you pass 1,1,1,1,1,1,0,0,0,0? please provide the jumps
best I see from your description is 0-->2, 2--> 5, 5 --> 9, but 9 is 0, so can't
other interpretations of your question may be: 0-->3, 3-->7, but 7 is 0, so can't pass
I don't see how you can pass that array with the problem statement given, please clearify

The code should pass the following test {1,1,1,1,1,1,0,0,0,0};
but does not.