An interview test about a chess knight?

Question

Algorithms

"You have an infinite chessboard, and a knight. The knight starts at [0, 0] and can move [like a knight moves, skipped for brevity]. Given two coordinates on the board, return the least amount of moves the knight has to make to get to that position"

As I understand it, this is a multidimensional array.
We have X and Y coordinates. It is
quite easy to calculate the options for moves; they are always only 8 where the shift is +2 and +1 along the axes. For example, the knight moves to the right, which is X + 2, if the direction is up Y-1, down Y + 1 if the starting point is the upper left corner, as in cocos2d.
Thus, based on the coordinates, for example, X=63 and Y=31, it can be estimated that the knight made at least 31 moves to the right. to move to the right, we will have X + 2, and it doesn’t really matter Y-1 or Y + 1 until the very end, where you need to put the knight on a point.

Therefore, these 2 moments are not clear to me, how to put the knight on a point when in such cases
1 - X = 99, Y = 100 - even and odd
2 - X = 100, Y = 99 -
3 - X = 99, Y = 99
4 - X = 100, Y = 100
And you need to calculate the total number of moves. I believe that there is a formula that does this simply by dividing and multiplying the coordinates somehow.

An example of a solution, please, in any language, it's hard to imagine in words.


I will say right away that I had 1/12 in matan at school.

Answer 1

Solution with a small enumeration of cases, for a constant. But with a lot of math.
First, a couple of simple observations. You can take X and Y modulo and swap them so that X <= Y. These are, as it were, rotations and reflections of the entire field. The moves themselves are also rotated, but in the problem you only need their number, and you can convert the moves when outputting back, if you remember what we did with the input data.
Further, the order of moves is unimportant. What matters is the number of each type of move. The field is endless. If the borders were always close, it would be different.
It is obvious that you never do reverse moves - i.e. there is no point in doing (+1, +2) and then (-1, -2).
Those. in fact, we have only 4 variables - how many moves of each of the 4 types you make. Perhaps a negative amount if we go in the opposite direction. Four types - (+2, +1), (+1, +2), (-1, +2), (-2, +1).
You can make equations:
2a+bc-2d = X
a+2b+2c+d = Y
|a|+|b|+|c|+|d| -> min
Hence
a = (2X-Y+4c+5d)/3
b = (2Y-X-5c-4d)/3
Not any values ​​of c and d are suitable, but only those that give a number divisible by 3 in the numerators .
The last important observation is that at least one of the variables does not exceed 3 in absolute value in the optimal answer. Let's say otherwise. First, it is obvious that sing(a) = sign(b), and sign(c) = sign(d) (otherwise 6 moves 3x(+1,+2)-3x(+2+1) can be replaced by 2 moves (-1,+2)+(-2,1) Similarly 3x(-1,+2)-3x(-2,+1)=(-1,+2)+(-2,+1 )).
In the first case, all variables are positive (otherwise we would not get Y>=0). But then we have 8 moves 2x(+2, +1)+2x(+1, +2)+2x(-1, +2)+2x(-2, +1) = (0, 12). But this can be done in just 6 moves 3x(-1,+2)+3x(+1,+2). In the second case, the first 2 variables are positive and the second 2 are negative and we have 8 moves 2x(+2, +1)+2x(+1, +2)-2x(-1, +2)-2x(-2, +1) = (12, 0). Again, these 8 moves can be replaced by 6 moves. So, we decrease the number of moves until we get that some variable is less than 3 modulo.
So, we know for sure that in the optimal answer at least one variable does not exceed 3 in absolute value. Let's go over what this variable is and its value. Let it be c=-3..3. Let's use the formulas above:
a = (2X-Y+4c+5d)/3
b = (2Y-X-5c-4d)/3
Here c is fixed and only d is unknown.
The remainder after dividing by 3 for d is known, it is r=(2Y-X-5c)%3, otherwise the second equation would not be divided entirely. We also need to check that this remainder fits into the first equation. Let us rewrite d = 3k+r. Substitute:
a = (2X-Y+4c+5r)/3 + 5k
b = (2Y-X-5c-4r)/3 - 4k
c = -3..3
d = 3k+r
|a|+|b |+3|k| -> min
You can stupidly enumerate k (after all, any integer k gives some answer).
And you can put on axis 3 the values ​​\u200b\u200bof 0, - (2X-Y + 4c + 5r) / 15, (2Y-X-5c-4r) / 12. Sort, get 4 intervals.
On each interval, see how |a|, |b| and |k|. As a result, you will get the coefficient before k + -5 + -4 + -1. Depending on the sign, you need to take either the left or right end of the interval (rounded to the nearest integer inside the interval - left up and right down). Don't forget to check that this interval contains integers at all. Substitute k in all equations and find a, b and d, compare with the current optimal answer, remember if necessary.
In theory, you need to go through 3 more options when a, b or d is fixed. But there is a simplification. We can also rotate the board as we want by swapping X and Y and their signs. One can always assume that the fixed variable is c. But you need to choose the minimum of the answers for (X,Y), (-X,Y), (Y,X), (-Y,X).
Solution in O(1).
Once again, we decide for 4 or 8 options (not to think) the location of X, Y.
There we sort through c from -3 to 3. Find r. We check that it fits into both equations (divided by an integer).
Find 3 sign change points |a|, |b|, |k|, sort, look at 4 segments. It is possible, in order not to analyze cases of infinity, to add any value less than the first one to the beginning and any value greater than the last one to the end in the sorted points[] array. Then we look at 4 intervals, consider the sign of the coefficient in front of k in the objective function and take the leftmost or rightmost integer point in the interval as a candidate for the answer. We consider |a|, |b|, |d|.

Answer 2

The first request to Yandex gives a video with a detailed solution.