Last active
October 27, 2019 14:33
-
-
Save esperancaJS/16f1509394cd257ffde2474040f8a4c8 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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