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 Marigold
def checkio(move_string):
'''
Find a length of the shortest path of knight
'''
def letters_to_coordinates(s):
return ord(s[0]) - 97, int(s[1]) - 1
def available_moves(v):
ret = set()
x,y = v
ret = ret.union((x + i, y + j) for i in (-2,2) for j in (-1,1))
ret = ret.union((x + i, y + j) for i in (-1,1) for j in (-2,2))
return {(x, y) for x,y in ret if 0 <= x < 8 and 0 <= y < 8}
start, finish = move_string.split('-')
start = letters_to_coordinates(start)
finish = letters_to_coordinates(finish)
visited = set([start])
turns = 0
while finish not in visited:
visited = set.union(*[available_moves(v) for v in visited])
turns += 1
return turns
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. 6, 2012
Comments:
