Skip to content

Instantly share code, notes, and snippets.

@xalakox
Last active January 28, 2017 16:53
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save xalakox/b5eda23c33cd7a865681adecada21815 to your computer and use it in GitHub Desktop.
Save xalakox/b5eda23c33cd7a865681adecada21815 to your computer and use it in GitHub Desktop.
Kight Problem: ¿ How many moves to reach a destination using the knight on a infinite sized chessboard ?
#!/usr/bin/env node
function solution(A, B) {
moves = [[2,1],[2,-1],[-2,1],[-2,-1],[-1,+2],[+1,+2],[-1,-2],[+1,-2]]
maxmoves = ~~(A*B/4) || 3
finaldestinations = []
trymove = function(startx,starty,priormoves){
priormoves++;
possiblemoves = moves.filter(function(move){
return startx + move[0] > -1 && starty + move[1] > -1
});
possiblemoves.forEach(function(lemove){
destination_x = startx+lemove[0]
destination_y = starty+lemove[1]
combo = [destination_x,destination_y,priormoves]
// save the destinations if we reached the goal
if (destination_x == A && destination_y == B) finaldestinations.push(combo);
// next move
if (priormoves+1<maxmoves) trymove(destination_x,destination_y,priormoves);
});
}
trymove(0,0,0)
if (finaldestinations.length===0) return -1
return (Math.min.apply(null,finaldestinations.map(function(e){return e[2]})))
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment