Created
October 5, 2016 15:10
-
-
Save hartliddell/938ae04d79fcf50f55e421450e237142 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