## DEV Community is a community of 851,150 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Daily Challenge #116 - Shortest Knight Path

Given two different positions on a chessboard, find the least number of moves it would take a knight to get from one to the other. The positions will be passed as two arguments in algebraic notation. For example, `knight("a3", "b5")` should return 1.

The knight is not allowed to move off the board. The board is 8x8.

For information on knight moves, see https://en.wikipedia.org/wiki/Knight_%28chess%29

For information on algebraic notation, see https://en.wikipedia.org/wiki/Algebraic_notation_%28chess%29

This challenge comes from ElDynamite on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions!

## Discussion (2) Jon Bristow

inelegant python brute force solution

``````def parse(s):
return (ord(s) - ord('a'), int(s))

def move(start, end):
return move_inner({parse(start)}, parse(end))

def next_moves(positions):
moves = set()
for move in positions:
for position in get_moves(move):
if (
position >= 0
and position >= 0
and position < 8
and position < 8
):
return moves

def move_inner(from_start, end, n=1):
print(from_start)
nstart = from_start | next_moves(from_start)

if end in nstart:
return n
else:
return move_inner(nstart, end, n + 1)

def get_moves(point):
(x, y) = point
return [
(x + 2, y + 1),
(x + 2, y - 1),
(x - 2, y + 1),
(x - 2, y - 1),
(x + 1, y + 2),
(x + 1, y - 2),
(x - 1, y + 2),
(x - 1, y - 2),
]
`````` Carl Anderson

Messy, inefficient JavaScript solution

``````let ranks = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'];
let files = ['1', '2', '3', '4', '5', '6', '7', '8'];
let allMoves = [
[1, 2],
[1, -2],
[-1, 2],
[-1, -2],
[2, 1],
[2, -1],
[-2, 1],
[-2, -1]
];

/**
* Search for the required moves to move a knight between two squares
*
* @param position
* @param target
* @returns {*}
*/
function moveSearch(position, target) {
let stack = []; // maintain an ordered stack so that we choose the 'best first'

stack.push({position: positionToArray(position), moves: []});
while (stack.length !== 0) {
let move = stack.pop();
let position = move.position;

// If the current position is the target, then we're done and we can send back the moves we've
// taken
if (arrayToPosition(move.position) === target) {
return [...move.moves, position].map(arrayToPosition);
}

// Otherwise, we need to get the candidate moves from this list, and place them on the stack
pruneMoves(position)
.map(move => {
// Apply the move
let rank = position + move;
let file = position + move;

return [rank, file];
})
.forEach(item => {
// Don't allow doubling back
if (move.moves.map(arrayToPosition).includes(arrayToPosition(item))) {
return;
}

// Push the move to the stack
stack.push({position: item, moves: [...move.moves, position]});
});

// Check the candidate with the fewest moves so far, otherwise choose the one
// that's closest
stack.sort((a, b) => {
if (a.moves.length !== b.moves.length) {
return  b.moves.length - a.moves.length;
}

let bDistance = calculateDistance(b.position, positionToArray(target));

});
}

// we shouldn't really reach here -- this signifies that it's impossible
return [];
}

/**
* Takes all the available knight moves, and return the ones that keep it on the board
*
* @param position
* @returns {*[]}
*/
function pruneMoves(position) {
return allMoves.filter((move) => {
let rank = position + move;
let file = position + move;

return rank >= 0 && rank < ranks.length && file >= 0 && file < files.length;
});
}

/**
* Converts a chess position to an array
*
* @param move
* @returns {*[]}
*/
function positionToArray(move) {
let chars = move.split('');
return [
ranks.indexOf(chars),
files.indexOf(chars)
];
}

/**
* Converts an array to a chess position
*
* @param arr
* @returns {string}
*/
function arrayToPosition(arr) {
return ranks[arr] + files[arr];
}

/**
* Calculates the distance between two positions
* @param pos1 array the first position
* @param pos2 array the second position
* @returns {number} the distance between the two positions
*/
function calculateDistance(pos1, pos2) {
// Take the euclidean distance using a2 + b2 = c2
let rankDistance = pos1 - pos2;
let fileDistance = pos1 - pos2;

return Math.sqrt(Math.pow(rankDistance, 2) + Math.pow(fileDistance, 2));
}
``````