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 fdudu
def str2pos(s):
l = int(s[1]) - 1
c = ord(s[0]) - ord("a")
return [l, c]
def checkio(move_string):
'''
Find a length of the shortest path of knight
'''
start_pos = str2pos(move_string[0:2])
end_pos = str2pos(move_string[3:5])
pos = [start_pos]
all_pos = [start_pos] # Keep a memory of where we've been
i = 1
while len(pos) > 0:
npos = []
for p in pos:
# Test every move
for diff in [[2, 1], [2, -1], [-2, 1], [-2, -1],
[1, 2], [1, -2], [-1, 2], [-1, -2]]:
np = [p[0] + diff[0], p[1] + diff[1]]
# We found the destination
if np == end_pos:
return i
# If it is still on the board and we've not been here, add it
# to the list for the next move
if 0 <= np[0] < 8 and 0 <= np[1] < 8 and np not in all_pos:
npos.append(np)
pos = npos
all_pos += pos
i += 1
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. 18, 2012
