Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
BFS solution in Clear category for The Shortest Knight's Path by tom-tom
def checkio(cells: str) -> int:
"""Number of moves in the shortest path of knight"""
def moves(cell):
x, y = map(ord, cell)
for move in ((x + 1, y + 2), (x + 2, y + 1), (x - 1, y + 2), (x - 2, y + 1),
(x + 1, y - 2), (x + 2, y - 1), (x - 1, y - 2), (x - 2, y - 1)):
ca, cb = map(chr, move)
if ca in 'abcdefgh' and cb in '12345678':
yield ca + cb
start, end = cells.split('-')
visited, current = set(), {start}
for step in range(1, 100):
visited |= current
new = {new_cell for cell in current for new_cell in moves(cell)} - visited
if end in new:
return step
current = new
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"
Sept. 7, 2019
Comments:
