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 [e-mail] with your suggestions!

Comments

[Jon Bristow]

inelegant python brute force solution

def parse(s):
    return (ord(s[0]) - ord('a'), int(s[1]))

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] >= 0
                and position[1] >= 0
                and position[0] < 8
                and position[1] < 8
            ):
                moves.add(position)
    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[0] + move[0];
                let file = position[1] + move[1];

                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 aDistance = calculateDistance(a.position, positionToArray(target));
            let bDistance = calculateDistance(b.position, positionToArray(target));

            return bDistance - aDistance;
        });
    }

    // 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[0] + move[0];
        let file = position[1] + move[1];

        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[0]),
        files.indexOf(chars[1])
    ];
}

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

/**
 * 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[0] - pos2[0];
    let fileDistance = pos1[1] - pos2[1];

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