26
\$\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)\$ or \$(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

This is so the shortest code in bytes wins

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

10 Answers 10

12
\$\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\$
8
  • 14
    \$\begingroup\$ Mathematica builtins strike again \$\endgroup\$
    – qwr
    Apr 27, 2018 at 14:59
  • 1
    \$\begingroup\$ Slightly shorter: GraphDistance[KnightTourGraph@@({x,y}=Abs@{##}+5),2y+3,(x-2)y-2]& \$\endgroup\$
    – Lukas Lang
    Apr 27, 2018 at 20:51
  • 1
    \$\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, 2018 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\$
    – DELETE_ME
    Apr 29, 2018 at 9:46
  • 1
    \$\begingroup\$ Wow, it just like a semi-transparent image! \$\endgroup\$
    – tsh
    May 7, 2018 at 1:44
9
\$\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\$
6
\$\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\$
5
  • 1
    \$\begingroup\$ @tsh But that is true for x==y==0 too. \$\endgroup\$
    – DELETE_ME
    Apr 28, 2018 at 4:03
  • \$\begingroup\$ Why max(x+y,x-y,y-x)? \$\endgroup\$
    – tsh
    Apr 28, 2018 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, 2018 at 9:38
  • \$\begingroup\$ @Nova "Assume x ≥ 0 and y ≥ 0". \$\endgroup\$
    – DELETE_ME
    Apr 29, 2018 at 9:43
  • \$\begingroup\$ the link code doesnt print anything \$\endgroup\$
    – DialFrost
    Jan 27 at 8:08
5
\$\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\$
0
5
\$\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\$
0
3
\$\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\$
3
\$\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\$
1
  • \$\begingroup\$ 72 bytes \$\endgroup\$
    – Lynn
    Apr 29, 2018 at 18:51
3
\$\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\$
2
\$\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\$
2
  • \$\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, 2018 at 22:33
  • \$\begingroup\$ @supercat Indeed, as Python would say, x>=y>=0... \$\endgroup\$
    – Neil
    Apr 27, 2018 at 23:42
2
\$\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\$
3
  • \$\begingroup\$ Pretty sure you don't need the :Int to specify return type. \$\endgroup\$
    – 2xsaiko
    Apr 28, 2018 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, 2018 at 12:45
  • 1
    \$\begingroup\$ Oh, I missed the recursive calls. Whoops \$\endgroup\$
    – 2xsaiko
    May 6, 2018 at 16:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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