24
\$\begingroup\$

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 (tx, ty)?

Inputs

Two integers: tx, ty;

-100 < tx < 100, -100 < ty < 100

Output

Minimal steps needed to move a Knight from (0, 0) to (tx, ty).

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.
\$\endgroup\$
  • \$\begingroup\$ You may take a reference of the formula given in oeis.org/A065775 \$\endgroup\$ – tsh Apr 27 '18 at 12:18
  • 2
    \$\begingroup\$ Can I take input as a complex number x+yi? \$\endgroup\$ – Lynn Apr 27 '18 at 14:43
  • 1
    \$\begingroup\$ @lynn i think it is acceptable. \$\endgroup\$ – tsh Apr 27 '18 at 14:52
  • \$\begingroup\$ @user202729 updated the code snippet to show the result. \$\endgroup\$ – tsh Apr 28 '18 at 1:50
  • \$\begingroup\$ A very fine map. \$\endgroup\$ – Willtech Apr 29 '18 at 3:48

10 Answers 10

11
\$\begingroup\$

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!

ArrayPlot@Array[GraphDistance[KnightTourGraph@@({x,y}=Abs@{##}+5),2y+3,(x-2)y-2]&,{65,65},-32]

\$\endgroup\$
  • 14
    \$\begingroup\$ Mathematica builtins strike again \$\endgroup\$ – qwr Apr 27 '18 at 14:59
  • 1
    \$\begingroup\$ Slightly shorter: GraphDistance[KnightTourGraph@@({x,y}=Abs@{##}+5),2y+3,(x-2)y-2]& \$\endgroup\$ – Lukas Lang Apr 27 '18 at 20:51
  • \$\begingroup\$ What's with this language? How come all these built-ins are preloaded? Does trying to complete a phrase with tab takes ages? \$\endgroup\$ – OganM Apr 29 '18 at 3:18
  • \$\begingroup\$ @OganM Mathematica doesn't support auto completion in its command line interface. The auto completion in the notebook interface looks like this. \$\endgroup\$ – alephalpha Apr 29 '18 at 3:50
  • 1
    \$\begingroup\$ @OganM Maybe the developers use a Trie (data structure), or just binary search on the list of sorted built-ins. Yes, why linear search? | Note that Mathematica is a non-free closed-source language, so no one know how the predictor actually works. | Real programmers don't need auto-complete. :P \$\endgroup\$ – user202729 Apr 29 '18 at 9:46
7
\$\begingroup\$

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):

    2 moves

  • 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):

    3 moves

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

Graphics borrowed from chess.com

\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ @tsh But that is true for x==y==0 too. \$\endgroup\$ – user202729 Apr 28 '18 at 4:03
  • \$\begingroup\$ Why max(x+y,x-y,y-x)? \$\endgroup\$ – tsh Apr 28 '18 at 4:11
  • \$\begingroup\$ @tsh: No, see: x = -5, y = 5. x+y = 0, abs(x-y) = 10 and therefore x+y < abs(x-y) \$\endgroup\$ – Nova Apr 29 '18 at 9:38
  • \$\begingroup\$ @Nova "Assume x ≥ 0 and y ≥ 0". \$\endgroup\$ – user202729 Apr 29 '18 at 9:43
4
\$\begingroup\$

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).

\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 72 bytes \$\endgroup\$ – Lynn Apr 29 '18 at 18:51
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Do you need the x<0 test? Given e.g. -3,6, the x<y test would turn that into 6,-3, which the y<0 test would turn into 6,3, which the x<y test would turn into 3,6. \$\endgroup\$ – supercat Apr 27 '18 at 22:33
  • \$\begingroup\$ @supercat Indeed, as Python would say, x>=y>=0... \$\endgroup\$ – Neil Apr 27 '18 at 23:42
1
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ Pretty sure you don't need the :Int to specify return type. \$\endgroup\$ – therealfarfetchd Apr 28 '18 at 15:30
  • \$\begingroup\$ Recursive functions do require return type as the compiler isn't smart enough to figure out the type. \$\endgroup\$ – JohnWells May 5 '18 at 12:45
  • 1
    \$\begingroup\$ Oh, I missed the recursive calls. Whoops \$\endgroup\$ – therealfarfetchd May 6 '18 at 16:45
1
\$\begingroup\$

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.
\$\endgroup\$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.