Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
BFS with path solution in Uncategorized category for The Shortest Knight's Path by Gamblore
# migrated from python 2.7
moves = [
[2, -1],
[2, 1], # right
[-1, 2],
[1, 2], # up
[-2, -1],
[-2, 1], # left
[-1, -2],
[1, -2] # down
]
def checkio(move_string):
'''
Find a length of the shortest path of knight
'''
def valid_move(x, y):
return x < 8 and x >= 0 and y < 8 and y >= 0
def get_moves(posx, posy):
return [x for x in [[posx+x[0], posy+x[1]] if (valid_move(posx+x[0], posy+x[1])) else None for x in moves] if not x is None]
def bfs(start, end):
queue = [[start]]
visited = [start]
while(len(queue)):
path = queue.pop(0)
t = path[-1]
if (t == end):
return len(path)-1
for i in get_moves(*t):
if (not i in visited):
new_path = list(path)
new_path.append(i)
visited.append(i)
queue.append(new_path)
return -1
start, end = [[ord(x[0])-ord('a'), int(x[1]) - 1] for x in move_string.split("-")]
return bfs(start, end)
if __name__ == "__main__":
assert checkio("b1-d5") == 2, "First"
assert checkio("a6-b8") == 1, "Second"
assert checkio("h1-g2") == 4, "Third"
assert checkio("h8-d7") == 3, "Fourth"
assert checkio("a1-h8") == 6, "Fifth"
Nov. 10, 2012
