fork download 
  1. from itertools import product, permutations
  2.  
  3. class vector(complex):
  4.     def __repr__(self):
  5.         return '({}, {})'.format(int(self.real), int(self.imag))
  6.  
  7. def knights_metric(target_x, target_y, start_x=0, start_y=0):
  8.     target = vector(target_x, target_y)
  9.     possible = [vector(sign_x * delta_x, sign_y * delta_y)
  10.                 for sign_x, sign_y in product((1, -1), repeat=2)
  11.                 for delta_x, delta_y in permutations((1, 2))]
  12.     visited = {vector(start_x, start_y): []}
  13.     while True:
  14.         for move, start in product(possible, visited):
  15.             if target in visited:
  16.                 return len(visited[target]), visited[target]
  17.             end = move + start
  18.             if end not in visited:
  19.                 visited[end] = visited[start] + [move]
  20.  
  21. # Testing
  22. cases = [((0, 0), 0), ((0, 1), 3), ((3, 7), 4), ((8, 7), 5), ((13, 12), 9)]
  23. for args, expected in cases:
  24.     n, path = knights_metric(*args)
  25.     print '{}: {} {}'.format(args, n, path)
  26.     assert n == expected
Success #stdin #stdout 0s 23352KB
comments ()
stdin 
Standard input is empty
stdout 
(0, 0): 0 []
(0, 1): 3 [(-2, 1), (1, -2), (1, 2)]
(3, 7): 4 [(-1, 2), (2, 1), (1, 2), (1, 2)]
(8, 7): 5 [(2, 1), (2, 1), (2, 1), (1, 2), (1, 2)]
(13, 12): 9 [(2, -1), (2, 1), (2, 1), (2, 1), (1, 2), (1, 2), (1, 2), (1, 2), (1, 2)]
https://ideone.com/SzxB5D
language:
Python (cpython 2.7.16)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!