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 bryukh
def convert_move(move_str):
first, second = move_str.split('-')
start = 'abcdefgh'.index(first[0]), int(first[1]) - 1
end = 'abcdefgh'.index(second[0]), int(second[1]) - 1
return start, end
def checkio(move_str):
start, end = convert_move(move_str)
steps = [(-2 , 1), (-1, 2), (1, 2), (2, 1),
(2, -1), (1, -2), (-1, -2), (-2, -1)]
checked = []
queue = [start]
queue_dst = [0]
while queue:
x, y = queue.pop(0)
dst = queue_dst.pop(0)
if (x, y) == end:
return dst
checked.append((x, y))
for xp, yp in steps:
xc, yc = x + xp, y + yp
if 0 <= xc < 8 and 0 <= yc < 8 \
and (xc, yc) not in queue and (xc, yc) not in checked:
queue.append((xc, yc))
queue_dst.append(dst+1)
return 0
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
