Knight Distance

Question

In Chess, a Knight on grid (x, y) may move to (x-2, y-1), (x-2, y+1), (x-1, y-2), (x-1, y+2), (x+1, y-2), (x+1, y+2), (x+2, y-1), (x+2, y+1) in one step. Imagine an infinite chessboard with only a Knight on (0, 0):

How many steps is required for moving a Knight from (0, 0) to (t_x, t_y)?

Inputs

Two integers: t_x, t_y;

-100 < t_x < 100, -100 < t_y < 100

Output

Minimal steps needed to move a Knight from (0, 0) to (t_x, t_y).

Rules

• code golf

Testcases

  x    y -> out
  0,   0 ->  0
  0,   1 ->  3
  0,   2 ->  2
  1,   1 ->  2
  1,   2 ->  1
  3,   3 ->  2
  4,   0 ->  2
 42,  22 -> 22
 84,  73 -> 53
 45,  66 -> 37
 99,  99 -> 66
-45, -91 -> 46
-81,   1 -> 42
 11,  -2 ->  7

document.write('<div>');[..."EFEDEDCDCBCBCBCBCBCBCBCBCBCBCBCBCBCDCDEDEFE;FEDEDCDCBCBABABABABABABABABABABABCBCDCDEDEF;EDEDCDCBCBABABABABABABABABABABABABCBCDCDEDE;DEDCDCBCBABA9A9A9A9A9A9A9A9A9A9ABABCBCDCDED;EDCDCBCBABA9A9A9A9A9A9A9A9A9A9A9ABABCBCDCDE;DCDCBCBABA9A9898989898989898989A9ABABCBCDCD;CDCBCBABA9A989898989898989898989A9ABABCBCDC;DCBCBABA9A98987878787878787878989A9ABABCBCD;CBCBABA9A9898787878787878787878989A9ABABCBC;BCBABA9A989878767676767676767878989A9ABABCB;CBABA9A98987876767676767676767878989A9ABABC;BABA9A9898787676565656565656767878989A9ABAB;CBA9A989878767656565656565656767878989A9ABC;BABA98987876765654545454545656767878989ABAB;CBA9A987876765654545454545456567678789A9ABC;BABA98987676565454343434345456567678989ABAB;CBA9A987876565454343434343454565678789A9ABC;BABA98987676545434323232343454567678989ABAB;CBA9A987876565434323232323434565678789A9ABC;BABA98987676545432341214323454567678989ABAB;CBA9A987876565434321232123434565678789A9ABC;BABA98987676545432323032323454567678989ABAB;CBA9A987876565434321232123434565678789A9ABC;BABA98987676545432341214323454567678989ABAB;CBA9A987876565434323232323434565678789A9ABC;BABA98987676545434323232343454567678989ABAB;CBA9A987876565454343434343454565678789A9ABC;BABA98987676565454343434345456567678989ABAB;CBA9A987876765654545454545456567678789A9ABC;BABA98987876765654545454545656767878989ABAB;CBA9A989878767656565656565656767878989A9ABC;BABA9A9898787676565656565656767878989A9ABAB;CBABA9A98987876767676767676767878989A9ABABC;BCBABA9A989878767676767676767878989A9ABABCB;CBCBABA9A9898787878787878787878989A9ABABCBC;DCBCBABA9A98987878787878787878989A9ABABCBCD;CDCBCBABA9A989898989898989898989A9ABABCBCDC;DCDCBCBABA9A9898989898989898989A9ABABCBCDCD;EDCDCBCBABA9A9A9A9A9A9A9A9A9A9A9ABABCBCDCDE;DEDCDCBCBABA9A9A9A9A9A9A9A9A9A9ABABCBCDCDED;EDEDCDCBCBABABABABABABABABABABABABCBCDCDEDE;FEDEDCDCBCBABABABABABABABABABABABCBCDCDEDEF;EFEDEDCDCBCBCBCBCBCBCBCBCBCBCBCBCBCDCDEDEFE"].forEach(c=>document.write(c==';'?'<br>':`<span class="d-${c}">${c}</span>`));
document.write('<style>body{line-height:16px;color:rgba(255,255,255,0.2);}span{display:inline-block;width:16px;font-size:16px;text-align:center;}div{white-space:pre;}');[...'0123456789ABCDEF'].map((c,i)=>document.write(`.d-${c}{background:hsl(${60-4*i},80%,${65-2*i}%)}`));

Related OEIS

Here are some OEIS for further reading

• A018837: Number of steps for knight to reach (n,0) on infinite chessboard.
• A018838: Number of steps for knight to reach (n,n) on infinite chessboard.
• A065775: Array T read by diagonals: T(i,j)=least number of knight's moves on a chessboard (infinite in all directions) needed to move from (0,0) to (i,j).
• A183041: Least number of knight's moves from (0,0) to (n,1) on infinite chessboard.

Answer 1

Wolfram Language (Mathematica), 64 bytes

Using the built-in KnightTourGraph.

Saved 2 bytes thanks to Mathe172.

GraphDistance[KnightTourGraph@@({x,y}=Abs@{##}+4),y+2,(x-2)y-2]&

Try it online!

Answer 2

JavaScript (ES6), 90 75 72 bytes

Inspired by the formula given for A065775. Slow as hell for (not so) long distances.

f=(x,y,z=x|y)=>z<0?f(-y,x):z>1?1+Math.min(f(x-1,y-2),f(x-2,y-1)):z*3^x&y

Try it online!

How?

We define z as the bitwise OR between x and y.

Step #1

We first ensure that we are located in a specific quadrant by forcing both x and y to be non-negative. As long as z < 0 (which means that either x or y is negative), we process the recursive call f(-y, x):

(+1, -2) --> (+2, +1)
(-1, +2) --> (-2, -1) --> (+1, -2) --> (+2, +1)
(-1, -2) --> (+2, -1) --> (+1, +2)

Step #2

While we have z > 1 (which means that either x or y is greater than 1), we recursively try the two moves that bring us closer to (0, 0): f(x-1, y-2) and f(x-2, y-1). We eventually keep the shortest path.

Step #3

When z is less than or equal to 1, we're left with 3 possibilities which are processed with z*3^x&y (we could use z*3-x*y instead):

• x & y == 1 implies x | y == 1 and means that x = y = 1. We need two more moves to reach (0, 0):

  

• x & y == 0 and x | y == 1 means that we have either x = 1 / y = 0 or x = 0 / y = 1. We need three more moves to reach (0, 0):

  

• x & y == 0 and x | y == 0 means that we already have x = y = 0.

_{Graphics borrowed from chess.com}

Answer 3

Python 3, 90 bytes

Thanks tsh for -11 bytes!

def f(x,y):x=abs(x);y=abs(y);s=x+y;return(.9+max(x/4,y/4,s/6)-s/2+(s==1or x==y==2))//1*2+s

Try it online!

(inline code formatting to avoid readers having to scroll. Sorry, but I have to golf my program)

Very very efficient.

---

How could I come up with this!?

1. Parity

Assumes that the whole board is colored in the checkerboard pattern (that is, cells with x+y odd and x+y even are colored with different colors).

Note that each step must jump between two differently-colored cell. Therefore:

• The parity of the number of steps must be equal to the parity of x+y.

2. Approximation

Assumes the knight starts from coordinate (0,0), and have moved n steps, and is currently at (x,y).
For simplicity, assumes x ≥ 0, y ≥ 0.
We can conclude:

• Since each step x increases by at most 2, x ≤ 2×n. Similarly, y ≤ 2×n.
• Since each step x+y increases by at most 3, x+y ≤ 3×n.

Therefore, n ≥ l(x,y) where l(x,y) = max(max(x,y)/2, (x+y)/3. (note that we don't need to include -x or x-y in the formula because by assumption, x ≥ 0 and y ≥ 0, so x+y ≥ max(x-y,y-x,-x-y) and x ≥ -x, y ≥ -y)

It turns out that a(x,y) = round(0.4 + l(x,y)) is a good approximation to n.

• Assume a(x,y) is an approximation with error less than 1, the correct value is given by

  f(x,y) = round((a(x,y) - (x+y)) / 2) * 2 + (x+y)
  

  (round under subtracting x+y and dividing by 2)

3. Special cases that fails the formula

Assume x ≥ 0 and y ≥ 0. There are 2 special cases where the algorithm fails:

• x == 1 and y == 0 or x == 0 and y == 1: The algorithm incorrectly returns 1 while the correct answer is 3.
• x == y == 2: The algorithm incorrectly returns 2 while the correct answer is 4.

So, just special-case those. Add the result by 2 if the value of x and y are one of those.

Answer 4

Python 2, 87 bytes

f=lambda z,a={0}:1-({z}<=a)and-~f(z,{k+1j**i*(2-i/4*4+1j)for k in a for i in range(8)})

Try it online!

Takes input as a complex number z = complex(tx, ty).

Answer 5

TI-Basic, 86 54 bytes

Based on @user202729's older solution

Input :abs(X->C:abs(Y->D:C+Ans
Ans+2int(.9+(S=1 or C=2 and D=2)-.5Ans+max({C/4,D/4,Ans/6

Answer 6

MATL, 29 bytes

`JEQ2J-htZjht_h@Z^2&sG=~}@Gg*

Input is a complex number with integer real and imaginary parts.

The code is very inefficient. Its memory requirements increase exponentially with the output. It times out in TIO for the test cases with output exceeding 7.

Try it online!

Answer 7

Haskell, 79 72 bytes

p l|elem(0,0)l=0|r<-[-2..2]=1+p[(x+i,y+j)|(x,y)<-l,i<-r,j<-r,(i*j)^2==4]

Try it online!

Takes the input as a singleton list of pairs of numbers.

A simple brute force. Needs a lot of time and memory for results > 8. Starting with a single element list of coordinates (the input), repeatedly add all positions that can be reached for every element until (0,0) is in this list. Keep track of the recursion level and return it as the result.

Edit: -7 bytes thanks to @Lynn.

Answer 8

JavaScript (ES6), 90 78 bytes

f=(x,y)=>y<0?f(x,-y):x<y?f(y,x):x+y<3?4-x-y&3:x-3|y-1?x-4|y-3?f(x-2,y-1)+1:3:2

Edit: Saved 12 bytes thanks to @supercat pointing out that x<0 implies either y<0 or x<y. Explanation: This is a recursive solution. The first two conditions just ensure the right quadrant for the other conditions. The third condition generates the answer for coordinates near the origin, while the last two conditions deal with the other two special cases (1 byte shorter than testing both moves):

0
32
2++
+2++
+++3+
++++++
(etc.)

All squares marked + can be determined by moving directly towards the origin and then recursing.

Answer 9

Jelly, 27 26 25 23 bytes

1,-pḤµ;UÆị
¢ṗS€;0i
0ç1#

Try it online!

Very slow; times out on TIO for outputs over 6. Takes a complex number as input.

Explanation

The code uses complex numbers because it was shorter in an intermediate step and it also seems a lot faster; you could also use pairs by removing Æi and replacing 0 with 0,0 on the second line.

1,-pḤµ;UÆị    Helper link. No arguments.
1,-             Get the pair [1,-1].
    Ḥ           Double each to get [2,-2].
   p            Cartesian product: get [[1,2],[1,-2],[-1,2],[-1,-2]].
     µ          Start a new chain with the list of pairs as argument.
       U        Reverse each pair.
      ;         Append the reversed pairs to the list.
        Æi      Convert each pair [real,imag] to a complex number.

¢ṗS€;0i    Helper link. Arguments: iterations, target
¢            Call the previous link to get knight moves as complex numbers.
 ṗ           Get the iterations-th Cartesian power of the list. This will
             yield 8^n tuples containing move sequences.
  S€         Sum each move sequence to get the resulting square.
    ;0       Add the starting square, since the zeroth iteration results
             in no move sequences.
      i      Find the target squares (1-based) index in the results, or 0.

0ç1#    Main link. Argument: target
0         Starting from 0,
   #      find the
  1       first number of iterations where
 ç        calling the previous link results in a nonzero result.

Answer 10

Kotlin, 148 146 140 bytes

fun s(x:Int,y:Int):Int=if(y<0)s(x,-y)else
if(x<y)s(y,x)else if(x+y<3)4-x-y and 3
else if(x!=3||y!=1)if(x!=4||y!=3)s(x-2,y-1)+1
else 3 else 2

Try it online!