Given two different positions on a chess board, 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

(Warning: many of the tests were generated randomly. If any do not work, the test cases will return the input, output, and expected output; please post them.)

Difficulty: interview

Starter code:

def knight(p1, p2):
	

Solutions:
from collections import deque
moves = ((1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1))

def knight(p1, p2):
    x, y = ord(p2[0])-97, int(p2[1])-1
    left, seen = deque([(ord(p1[0])-97, int(p1[1])-1, 0)]), set()
    while left:
        i, j, v = left.popleft()
        if i==x and j==y: return v
        if (i, j) in seen: continue
        seen.add((i, j))
        for a,b in moves:
            if 0 <= i+a < 8 and 0 <= j+b < 8:
                left.append((i+a, j+b, v+1))

def knight(p1, p2):
    a, b = [('abcdefgh'.index(p[0]), int(p[1])) for p in [p1, p2]]
    x, y = sorted((abs(a[0] - b[0]), abs(a[1] - b[1])))[::-1]

    if (x, y) == (1, 0): return 3
    if (x, y) == (2, 2) or ((x, y) == (1, 1) and any(p in ['a1','h1','a8','h8'] for p in [p1, p2])): return 4
    
    delta = x - y
    
    return delta - 2*((delta-y)//(3 if y > delta else 4))    

from copy import copy
move_map = ((-2, -1), (-1, -2), (1, -2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1))

def algebraic_to_eucledian(pos):
    return (int(pos[1]) - 1, 'abcdefgh'.index(pos[0]))

def knight(p1, p2):
    p1, p2 = algebraic_to_eucledian(p1), algebraic_to_eucledian(p2)
    num_moves = -1
    visited = []
    moves = [p1]
    while moves:
        next_moves = []
        num_moves += 1
        for move in moves:
            if move == p2:
                return num_moves
            visited.append(move)
            next_moves.extend([(move[0]+x, move[1]+y) for x, y in move_map if 0 <= move[0]+x < 8 and 0 <= move[1]+y < 8 and (move[0]+x, move[1]+y) not in visited])
        moves = copy(next_moves)


from collections import deque
MOVES = [[1, -2], [1, 2], [2, -1], [2, 1], [-1, -2], [-1, 2], [-2, 1], [-2, -1]]

def knight(p1, p2):    
    p1 = (8 - int(p1[1]), 'abcdefgh'.index(p1[0]))
    p2 = (8 - int(p2[1]), 'abcdefgh'.index(p2[0]))
    
    Q = deque([(p1, -1)])
    visited = set()
    
    while Q:
        k, l = Q.popleft()
        l += 1
        visited.add(k)
    
        if k == p2 : return l
    
        for i, j in MOVES:
            ni, nj = k[0] + i, k[1] + j
            if 0 <= ni < 8 and 0 <= nj < 8 and (ni, nj) not in visited:
                Q.append([(ni, nj),l])
    return None

# https://www.codewars.com/kata/shortest-knight-path/python

# Function to transform from "a1" to "[1,1]", for example
def transformChessPointToMatrixPoint(point):
    return [int(ord(point[0])-96),int(point[1])]

# From a point in a matrix, check all possible moves as a knight and then remove every move out of the board.
def availableMoves(point):
    moves = []
    final_moves = []
    moves.append([point[0]+2, point[1]+1])
    moves.append([point[0]+2, point[1]-1])
    moves.append([point[0]-2, point[1]+1])
    moves.append([point[0]-2, point[1]-1])
    moves.append([point[0]+1, point[1]+2])
    moves.append([point[0]+1, point[1]-2])
    moves.append([point[0]-1, point[1]+2])
    moves.append([point[0]-1, point[1]-2])

    # Return only the points IN the board
    for move in moves:
        if 1<=move[0]<=8 and 1<=move[1]<=8:
            final_moves.append(move)
    return final_moves

# Main Function - Implementing Breadth First Search (kinda)
def knight(p1, p2):
    #Transform Points from letters "ky" to "[x,y]" points
    p1 = transformChessPointToMatrixPoint(p1)
    p2 = transformChessPointToMatrixPoint(p2)
    # Initialize visited nodes
    already_visited = [p1]

    # Queue to check and to find the minimum solution. A list of arrays where first is the point (array [x,y]) and second is the amount of steps done, initialized at 0.
    to_check = [[p1,0]]

    # While we have nodes to check
    while len(to_check) > 0:

        # If we have found the answer
        if to_check[0][0] == p2:
            # Return the amount of steps done
            return to_check[0][1]

        # Check available moves from point to_check[0][0]
        moves_to_visit = availableMoves(to_check[0][0])
        for move in moves_to_visit:
            # If they have been visited once, we must not check them again
            if move in already_visited:
                pass
            # First time checking the point
            else:
                # Added to visited nodes
                already_visited.append(move)
                # Added to the check "queue" and added 1 to the amount of steps
                to_check.append([move,to_check[0][1]+1])
        # Remove first node after being checked
        to_check.pop(0)
    # Return impossibility to reach an answer (just in case they enter an invalid point out of an 8x8 board)
    return None    

def knight(p1, p2):
    pos={'a':1,'b':2,'c':3,'d':4,'e':5,'f':6,'g':7,'h':8}
    p1=[pos[p1[0]]-1,int(p1[1])-1]
    p2=[pos[p2[0]]-1,int(p2[1])-1]
    moves=[[2,1],[1,2],[-1,2],[-2,1],[-2,-1],[-1,-2],[1,-2],[2,-1]]
    board=[]
    for i in range(8): board.append([0,0,0,0,0,0,0,0])
    board[p1[1]][p1[0]]=1
    while True in [0 in ii for ii in board]:
        for j in range(8):
            for k in range(8):
                for i in moves:
                    new=[j+i[0],k+i[1]]
                    if new[0] in range(8) and new[1] in range(8) and new!=p1 and board[k][j]!=0:
                        if board[new[1]][new[0]]==0:
                            board[new[1]][new[0]]=board[k][j]+1
                        else:
                            board[new[1]][new[0]]=min(board[k][j]+1,board[new[1]][new[0]])
    return board[p2[1]][p2[0]]-1


from itertools import chain

def knight(p1, p2):
    p1,p2 = ('abcdefgh'.index(p1[0]),int(p1[1])-1), ('abcdefgh'.index(p2[0]),int(p2[1])-1)
    span = [p1]
    for i in range(8):
        if p2 in span: return i
        span = set(chain.from_iterable(map(lambda p: [(p[0]+i,p[1]+j) for (i,j) in [(1,2),(2,1),(-1,2),(-2,1),(1,-2),(2,-1),(-1,-2),(-2,-1)] if p[0]+i>=0 and p[1]+j>=0 and p[0]+i<8 and p[1]+j<8],span)))

def knight(p1, p2):
    from collections import deque

    mapper = {1: "a", 2: "b", 3: "c", 4: "d", 5: "e", 6: "f", 7: "g", 8: "h"}
    mapper_inv = {"a": 1, "b": 2, "c": 3, "d": 4, "e": 5, "f": 6, "g": 7, "h": 8}
    visited = set()
    que = deque()

    start_pos = tuple(p1)
    start_pos = (int(mapper_inv[start_pos[0]]), int(start_pos[1]))

    que.appendleft((start_pos, 1))

    def _gen_move(spos):
        """
        Generate next moves
        eg. spos = (a, 1) == (1, 1) == (x, y)
        """
        dx = [-2, -1, 1, 2, 2, 1, -1, -2]  # relative directions x
        dy = [1, 2, 2, 1, -1, -2, -2, -1]  # relative directions y
        for d in range(8):
            nx = spos[0] + dx[d]
            ny = spos[1] + dy[d]
            if not 0 < nx < 9 or not 0 < ny < 9 and (nx, ny) not in visited:
                continue
            npos = (nx, ny)
            visited.add(npos)
            yield npos

    while len(que) > 0:

        # generate next positions and put them in que
        sp, step = que.pop()
        for nm in _gen_move(sp):
            # check if next move is last
            nm_ = mapper[nm[0]]+str(nm[1])
            if nm_ == p2:
                return step
            que.appendleft((nm, step+1))

import heapq

def knight(p1, p2):
    heuristic = lambda f: max(abs(f[0] - p2[0]), abs(f[1] - p2[1])) // 2
    p1, p2 = ((ord(p[0]) - ord('a'), int(p[1]) - 1) for p in (p1, p2))
    pqueue = [(heuristic(p1), p1, 0)]
    while pqueue:
        _, (x, y), count = heapq.heappop(pqueue)
        if (x, y) == p2:
            return count
        for dx, dy in ((-2, -1), (-2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2), (2, -1), (2, 1)):
            x2, y2 = x + dx, y + dy
            if 0 <= x2 < 8 and 0 <= y2 < 8:
                heapq.heappush(pqueue, (count + heuristic((x2, y2)), (x2, y2), count + 1))

letter_to_number={"a":1, "b":2,"c":3,"d":4, "e":5, "f":6, "g":7, "h":8}

def possible_moves(p1):
  possible_moves = ([1,2],[-1,2],[1,-2],[-1,-2],[2,1],[-2,1],[2,-1],[-2,-1])
  new_positions=[]
  for move in possible_moves:
    if (0<(p1[0]+move[0])<=8) and (0<(p1[1]+move[1])<=8):
      new_positions.append([(p1[0]+move[0]),(p1[1]+move[1])])
  return new_positions
  
def knight(p1, p2):
  new_p1=[letter_to_number[p1[0]], int(p1[1])]
  new_p2=[letter_to_number[p2[0]], int(p2[1])]
  
  if new_p2 in possible_moves(new_p1):
    return 1

  for move1 in possible_moves(new_p1):
    if new_p2 in possible_moves(move1):
      return 2
      break
  
  for move1 in possible_moves(new_p1):
    for move2 in possible_moves(move1):
      if new_p2 in possible_moves(move2):
        return 3

  for move1 in possible_moves(new_p1):
    for move2 in possible_moves(move1):
      for move3 in possible_moves(move2):
        if new_p2 in possible_moves(move3):
          return 4
          
  for move1 in possible_moves(new_p1):
    for move2 in possible_moves(move1):
      for move3 in possible_moves(move2):
        for move4 in possible_moves(move3):
          if new_p2 in possible_moves(move4):
            return 5
  return 6