Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Uncategorized category for The Shortest Knight's Path by Kurush
# migrated from python 2.7
from collections import deque
def checkio(cells):
search_queue = deque()
visited = [[False for j in range(8)] for i in range(8)]
move_shifts = [[-2, -1], [-2, 1], [-1, -2], [-1, 2], [1, -2], [1, 2], [2, -1], [2, 1]]
values = cells.split("-")
width_initial_index, height_initial_index = get_indices(values[0])
width_goal_index, height_goal_index = get_indices(values[1])
search_queue.append([0, height_initial_index, width_initial_index]);
while True:
if not search_queue: break
step, height_index, width_index = search_queue.popleft()
if height_index == height_goal_index and width_index == width_goal_index:
return step
visited[height_index][width_index] = True
for shift in move_shifts:
if is_correct_cell(height_index + shift[0], width_index + shift[1]) and visited[height_index + shift[0]][width_index + shift[1]] == False:
search_queue.append([step + 1, height_index + shift[0], width_index + shift[1]])
return -1
def is_correct_cell(i, j):
if i < 0 or i > 7: return False
if j < 0 or j > 7: return False
return True
def get_indices(cell):
height_marks = "hgfedcba"
return height_marks.find(cell[0]), int(cell[1]) - 1
if __name__ == "__main__":
#These "asserts" using only for self-checking and not necessary for auto-testing
assert checkio("b1-d5") == 2, "1st example"
assert checkio("a6-b8") == 1, "2nd example"
assert checkio("h1-g2") == 4, "3rd example"
assert checkio("h8-d7") == 3, "4th example"
assert checkio("a1-h8") == 6, "5th example"
June 13, 2014