Daily Challenge #116 - Shortest Knight Path

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),
    ]

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));
}