Skip to content

Instantly share code, notes, and snippets.

@chumaumenze
Created January 18, 2019 08:38
Show Gist options
  • Save chumaumenze/8778cc9a73815537c69ac8a528e7d546 to your computer and use it in GitHub Desktop.
Save chumaumenze/8778cc9a73815537c69ac8a528e7d546 to your computer and use it in GitHub Desktop.
Toptal Codility Problem: Can Knight reach square?
'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