Created
March 9, 2017 05:09
-
-
Save seyfer/8900dc3ffa311eee14458c6f2333ff01 to your computer and use it in GitHub Desktop.
Toptal Codility Problem: Can Knight reach square?
This file contains 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
'use strict'; | |
function getNextPositions(start) { | |
var moves = [ | |
{ x: -2, y: -1 }, | |
{ x: -2, y: +1 }, | |
{ x: -1, y: -2 }, | |
{ x: -1, y: +2 }, | |
{ x: +1, y: -2 }, | |
{ x: +1, y: +2 }, | |
{ x: +2, y: -1 }, | |
{ x: +2, y: +1 } | |
]; | |
var positions = []; | |
for (var i = 0; i < moves.length; i++) { | |
var move = moves[i]; | |
var position = {}; | |
position.x = start.x + move.x; | |
position.y = start.y + move.y; | |
positions.push(position); | |
} | |
return positions; | |
} | |
function countMovesTo(destination, depth, cache) { | |
depth = depth || 0; | |
cache = cache || {}; | |
var result = (cache[destination.x]||{})[destination.y]; | |
if (result) { | |
return result; | |
} | |
if (destination.x === 0 && destination.y === 0) { | |
result = 0; | |
} else if (depth > 100) { | |
result = -2; | |
} else { | |
var minMoves = Infinity; | |
var nextPositions = getNextPositions(destination); | |
for (var i = 0; i < nextPositions.length; i++) { | |
var nextPosition = nextPositions[i]; | |
var result = countMovesTo(nextPosition, depth + 1, cache); | |
if (result < 0) { | |
continue; | |
} | |
// console.log('found at moves', result); | |
minMoves = Math.min(minMoves, 1 + result); | |
} | |
if (minMoves === Infinity) { | |
result = -2 | |
} else { | |
result = minMoves | |
} | |
} | |
cache[destination.x] = cache[destination.x] || {}; | |
cache[destination.x][destination.y] = result; | |
return result; | |
} | |
function solution(A, B) { | |
return countMovesTo({x: A, y: B }) | |
} | |
console.log(solution(4, 5)); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment