Skip to content

Instantly share code, notes, and snippets.

@esperancaJS
Last active October 27, 2019 14:33
Show Gist options
  • Save esperancaJS/16f1509394cd257ffde2474040f8a4c8 to your computer and use it in GitHub Desktop.
Save esperancaJS/16f1509394cd257ffde2474040f8a4c8 to your computer and use it in GitHub Desktop.
function solution(A) {
//other shore bank
A.push(1);
//array with shortest paths for each leaf/bank
var reachable = [];
for(var i = 0; i<A.length; i++){
reachable.push(-1);
}
var possibleJumps = fibArray(A.length);
//get leafs/bank that can be reached from the starting shore
for(var i = 0; i<possibleJumps.length; i++){
if(A[possibleJumps[i]-1]===1){
reachable[possibleJumps[i]-1] = 1;
}
}
//for every position not reachable by the first bank find the shortest path
for(var i = 0; i<A.length; i++){
if(A[i]===1){
var minPrevPosition = -1;
var minDist = A.length+100;
for(var j = 0; j<possibleJumps.length; j++){
var prevPosition = i-possibleJumps[j];
if(prevPosition<0 || reachable[i]>-1){
break;
}
if(reachable[prevPosition]>0 && minDist>reachable[prevPosition]){
minPrevPosition = prevPosition;
minDist = reachable[prevPosition];
}
}
if(minPrevPosition > -1){
reachable[i] = minDist + 1;
}
}
}
return reachable[reachable.length-1];
}
function fibArray(num){
var current = 2;
var arr = [0,1,1];
while(current<=num){
current++;
var next = arr[current-1]+arr[current-2];
arr.push(next);
}
return arr;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment