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 Moff
from collections import defaultdict
def moves(x, y):
delta = [(1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2)]
return [(i, j) for i, j in ((x + dx, y + dy) for dx, dy in delta)
if 0 <= i < 8 and 0 <= j < 8]
def bfs(x, t):
seen = set()
entry = defaultdict(list)
q = list()
q.append(x)
while q:
x = q.pop()
seen.add(x)
for v in moves(*x):
if v not in entry:
entry[v] = entry[x] + [x]
q.insert(0, v)
seen.add(v)
if v == t:
break
return entry[t]
def checkio(s):
return len(bfs(*map(lambda a: (ord(a[0]) - ord('a'), int(a[1]) - 1), s.split('-'))))
Aug. 10, 2015
