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: MEDIUM

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


def transformChessPointToMatrixPoint(point):
	return [int(ord(point[0]) - 96), int(point[1])]

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])
	for move in moves:
		if 1 <= move[0] <= 8 and 1 <= move[1] <= 8:
			final_moves.append(move)
	return final_moves

def knight(p1, p2):
	p1 = transformChessPointToMatrixPoint(p1)
	p2 = transformChessPointToMatrixPoint(p2)
	already_visited = [p1]
	to_check = [[p1, 0]]
	while len(to_check) > 0:
		if to_check[0][0] == p2:
			return to_check[0][1]
		moves_to_visit = availableMoves(to_check[0][0])
		for move in moves_to_visit:
			if move in already_visited:
				pass
			else:
				already_visited.append(move)
				to_check.append([move, to_check[0][1] + 1])
		to_check.pop(0)
	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):
		dx = [-2, -1, 1, 2, 2, 1, -1, -2]
		dy = [1, 2, 2, 1, -1, -2, -2, -1]
		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:
		(sp, step) = que.pop()
		for nm in _gen_move(sp):
			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