Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

It's possible to work out the number of moves required to move from (0, 0) to (A, B) for a knight on an infinite chess board in O(1) time.

This is an attempt at a solution to do it in O(n) time, where n is the number of moves required. Disregarding inefficiency, are there any mistakes?

#define ABS(a) ({ typeof (a) _a = (a); _a > 0 ? _a : -_a; })

int movesRequired(int A, int B) {
    int X = 0, Y = 0;
    int count = 0;
    if (!(((A-X) % 2) ^ ((Y-B) % 2)))
        return -1;
    while (X != A && Y != B) {
        int distX = A-X;
        int distY = B-Y;
        if (ABS(distX) > ABS(distY)) {
            X += distX>0?2:-2;
            Y += distY>0?1:-1;
        } else {
            X += distX>0?1:-1;
            Y += distY>0?2:-2;
        }
        count++;
    }
    return count;
}

It returns the minimum moves required, or -1 if it's not possible.

share|improve this question

closed as off-topic by 200_success, rolfl, Malachi, ChrisW, Simon André Forsberg Jan 30 at 14:45

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question must contain working code for us to review it here. For questions regarding specific problems encountered while coding, try Stack Overflow. After getting your code to work, you may edit this question seeking a review of your working code." – 200_success, rolfl, Malachi, ChrisW, Simon André Forsberg
If this question can be reworded to fit the rules in the help center, please edit the question.

    
We are only considering one knight on this infinite chessboard, right? That's what I'm assuming since collisions with other chess pieces wouldn't be legal. –  syb0rg Jan 29 at 22:05
    
@syb0rg Yes, just the knight. –  Alec Jan 29 at 22:11
4  
Under what conditions is it not possible for a Knight to access a square? –  rolfl Jan 30 at 5:56
    
"It's possible to work out the number of moves required to move from (0, 0) to (A, B) for a knight on an infinite chess board in O(1) time." This statement is false. The proof is very simple: the output is not constant in size. If you choose bigger and bigger A and B in the infinite chessboard the number of moves increases and thus the size of the output. The time to compute such number of moves n is at least O(log(n)) otherwise the algorithm wouldn't even have the time to produce output. –  Bakuriu Jan 30 at 10:23
1  
A knight can always move to any square, it's never impossible because no square is unreachable to a knight: see for example Knight's tour. –  ChrisW Jan 30 at 14:42
add comment

3 Answers 3

A few notes (with efficiency aside, as you said):

  • Your defined ABS surrounded by parenthesis is not the usual way that C programmers declare macros so that they aren't problematic.

    #define ABS(a) do { typeof (a) _a = (a); _a > 0 ? _a : -_a; } while(0)
    

    Also, there is no point of using typeof in this instance. Just use the abs() function from <math.h>, or define a more simple ABS macro.

    #define ABS(x) ((x) > 0 ? x : -x)
    

    Note that you will have to use the fabs() for finding the absolute value of floating point numbers using the <math.h> library.

  • Why are all of your single letter variable names capitalized?

  • You need to let some of your code breathe a bit to make it easier to read (in my opinion).

    X += distX > 0 ? 2 : -2;
    
  • Use more comments to say what your code does and why. Don't overdo this though.

    if (!(((A-X) % 2) ^ ((Y-B) % 2)))  //<insert description here>
    
share|improve this answer
1  
On that last point, the operands and operators should be separated for readability. –  Jamal Jan 29 at 22:15
1  
Thanks for your answer syb0rg. I agree with the first and last suggestions. Using capitalised names was solely because the specification had A and B capitalised. –  Alec Jan 29 at 22:25
1  
@Alec That's fine. It's just more common for variable names to start with a lowercase letter, so I was wondering why it was uppercase. –  syb0rg Jan 29 at 22:26
    
I prefer comments on the previous line, not inline. –  ChrisW Jan 29 at 23:19
    
@ChrisW Depending on how long the comments are, yes. If it is a short description that can easily fit on the same line, then I usually put them on the same line. –  syb0rg Jan 29 at 23:20
add comment

\$O(1)\$ Discussion

Is it possible to calculate the distance in \$O(1)\$ time complexity?

Yes, it is.

This problem is called the "Knight's distance" problem, and googling it find a number of references.

This problem was posed as part of the South African "Computer Olympiad" in 2007 for high-school students to solve.... (I know, kids these days.... :) ). The specification was such that some input values for the programs were large enough that \$O(n)\$ solutions would fail to compute in the required time limits, so to get full marks you needed to (devise, and) compute the \$O(1)\$ system.

The problem description, and enough of the description of the \$O(1)\$ solution are available. In case the .za net goes dead, here's the description of the solution:

4 The Knights Who Say Ni

The (x, y)-coordinates in the 50% constraints are small enough to generate a full grid of the minimum number of moves required to get from any point to (0,0). The grid can be generated by a breadth-first search (BFS).

We know that getting to (0,0) requires 0 moves. We therefore know that the points (1,2), (2,1) and the other six movements each require 1 move. From each of those points with a shortest distance of 1, we can take another step in each direction for a shortest path of 2. However, some moves will bring us back to a point we have already found a shorter distance for and we therefore discard such moves. We continue this until the grid is full and then use the grid to find the distances for each knight.

To get 100%, a lot of scribbling on paper is required to make some key observations and work out some formulae. The first thing to note is that the grid is symetrical along the x, y axis and the lines y = ±x. You can therefore convert all points (x, y) into an equivalent point such that the new 0 ≤ y ≤ x.

The magic formula is:

$$ f(x, y) = \left\{ \begin{array}{ll} 2 \left\lfloor \frac{y - \delta}{3} \right\rfloor + \delta & \mbox{if } y > \delta \\ \delta - 2 \left\lfloor \frac{\delta - y}{4} \right\rfloor & \mbox{otherwise} \end{array} \right. $$

where \$δ = x − y\$.

Are there mistakes

Yes.... All squares are accessible to the knight. Why do you have a restriction?

I put your code in to an Ideone that loops through the 100 targets in positions (0,0) through (9,9).... and its results are disappointing... Does your code work?

NO. it does not. It produces wildly wrong values.....

Now, the algorithm I referenced above does not seem to be producing good values either (at least a short range....), but seriously? Your code hardly works at all :(

Lots, and lots of -1 distances, and lots and lots of 0.....

share|improve this answer
2  
Found a solution with O(1) time. chessprogramming.wikispaces.com/Knight-Distance –  Andris Jan 30 at 7:01
add comment

I have a bit of a bone to pick with this:

#define ABS(a) ({ typeof (a) _a = (a); _a > 0 ? _a : -_a; })

Firstly, typeof is a gcc extension, so by using this, you're making your code less portable. To be fair, for something small like this, it's not a big problem, but it's a bit of a bad habit to get into. In this case, it's also not even needed.

#define ABS(x) ((x) > 0 ? x : -x)

works just as well.

However, all of this isn't really necessary. <math.h> defines abs (for integers) and fabs (for floating point values) for you. Use the standard library unless you have very good reason not to.

share|improve this answer
    
Hmm, I was just making an edit on this when you posted it as an answer. Also, some good points on portability. +1 –  syb0rg Jan 30 at 1:09
1  
On the other hand, if you are using a compiler that supports typeof, such as GCC or Clang, this ABS(x) macro avoid evaluating its argument twice. –  200_success Jan 30 at 6:52
add comment

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