Finding the shortest path as for knight in the game of chess on an infinite board (WARNING: solution for "can't move backward" scenario that isn't actually implied by the original problem).

The knight is the piece in the game of chess that, in one turn, can move two squares horizontally and one square vertically or two squares vertically and one square horizontally.

An infinite chessboard is given. All of its squares are empty except for the square with coordinates (0,0), where a knight stands.

Write a function:

def solution(A, B)

that, given two numbers A and B, returns the minimum number of turns required for the knight to move from square (0,0) to square (A,B). The function should return -1 if the knight cannot reach the given square. The function should return -2 if the required number of turns exceeds 100,000,000.

For example, given A=4 and B=5 the function should return 3, because the knight requires three turns to move from square (0,0) to square (4,5):

• in the first turn the knight moves from square (0,0) to square (2,1);
• in the second turn the knight moves from square (2,1) to square (3,3);
• in the thirs turn the knight moves from square (3,3) to square (4,5)

Assume that:

• A and B are integers within the range [-100,000,000...100,000,000]

Complexity:

• expected worst-case time complexity is O(1);
• expected worst-case space complexity is O(1).

---

Ok, here we are... people with no math background but with a need to pass another test :) Fortunately such kind of tests may be visualized on paper and then all the obvious patterns could be extracted and converted to the code by guess... literally.

First of all, don't get trapped by the condition. The task is not as much about calculating the minimal number of steps to a destination point, but more about figuring out whether that specific square could be reached out at all. And this is where I'll begin.

Imagine two ultimate cases when you take same moves all way long, i.e. either you're moving two squares horizontally and one square vertically over and over again into infinity, or you're moving two squares vertically and one square horizontally also into infinity. For better visualization let's do some sketch:

As you may have guessed black boxes represent abovementioned two ultimate pathes with dark dots representing reachable squares on them. These two pathes are showing us a sort of boundaries. There're obviously no squares that could be reached out with given moving rules outside of in between those pathes in that quadrant (until otherwise specified whatever is described below and so far is relevant to the quadrant I where X and Y are both positive). In other words you can't move vertically without taking at least half of that move horizontally, as well as you can't move horizontally without taking at least half of that move vertically. Hence, here's how one may describe every square inside of those boundaries (inclusively) in terms of ratios of X to Y:

( x/y >= 0.5 && x/y <= 2 )

where 0.5 and 2 are ratios of X to Y describing our boundaries (potentially reachable squares may be met between them). Yeap! That's a nasty word - 'potentially', because not every square that's inside may be reached as well, what's above is just a kind of a rough 1st-level filter.

Let's improve our drawing:

You may either check what those orange dots stay for if you do have time and some skills of visualization, or you may just take my word for it: those represent reachable squares between the boundaries. You may see sequences of those orange dots are forming a sort of diagonals between 'opposite' reachable squares located on the boundaries themselves (those marked with dark dots). By 'opposite' in this case I mean squares with swapped X and Y, e.g. (8,16) is an opposite of the (16,8) So, how could we describe those 'diagonals' formed by orange dots? Easily enough: +1 on X-axis and -1 on Y-axis... until opposite reachable square located on the the boundary is met. Just think of it as:

• 8;16
• 9;15
• 10;14
• 11;13
• 12;12
• 13;11
• 14;10
• 15;9
• 16;8

Have you guessed pattern yet? As for this specific 'diagonal', the sum of X and Y of every reachable point on it will be the same, but our interest not in the sum as such, but in the fact that the sum is divisible by 3. Which is logical enough considering the fact that 'opposite' points located on the boundaries represent extreme cases with either 1:2 or 2:1 ratio of X to Y, and the diagonal as I've mentioned is built by just substracting 1 from Y and adding 1 to X. Hence we may extend out reachability checking expression with the following:

( (x+y) % 3 == 0 )

As for the number of moves: because by one move you'd pass not more, not less but 3 squares, the total number of moves obviously can't be less than a sum of X and Y of the destination point divided by 3.

Furthermore and finally, since

A and B are integers within the range [-100,000,000...100,000,000]

we should consider calculations for all quadrants, not only the I. Luckily it's just about adding another modification of our preliminary check with changed sign:

( A/B <= -0.5 && A/B >= -2 )

---

Yeap! Believe it or not, here's the eventual solution in the flesh code :)

JavaScript

// A for X-axis, B for Y-axis coordinates
// just for a sake of initial naming requirement
function solution(A, B) {
    return ( ( ( A/B >= 0.5 && A/B <= 2 ) || ( A/B <= -0.5 && A/B >= -2 ) ) && ( (A+B) % 3 == 0 ) )
        // given assumption about A and B ranges makes it hardly possible to get -2 as a return value
        // however let this checking just be here to not show ourselves as inattentive persons
        ? ( ( (A+B)/3 <= 100000000 ) ? (A+B)/3 : -2
        : -1;
}