Hackerrank: KnightL on a Chessboard

Problem statement


KnightL is a chess piece that moves in an L shape. We define the possible moves of KnightL(a,b) as any movement from some position (x1, y1) to some (x2, y2) satisfying either of the following:


• x2 = x1 ± a and y2 = y1 ± b or


• x2 = x1 ± b and y2 = y1 ± a or


Note that (a, b) and (b, a) allow for the same exact set of movements. For example, the diagram below depicts the possible locations that KnightL(1,2) or KnightL(2,1) can move to from its current location at the center of a 5 × 5 chessboard:





Observe that for each possible movement, the Knight moves 2 units in one direction (i.e., horizontal or vertical) and 1 unit in the perpendicular direction.


Given the value of n for an n×n chessboard, answer the following question for each (a,b) pair where 1 ≤a, b <n:


• What is the minimum number of moves it takes for KnightL(a,b) to get from position (0,0) to position (n-1, n-1)? If it's not possible for the Knight to reach that destination, the answer is -1 instead.


Then print the answer for each KnightL(a,b) according to the Output Format specified below.


Input Format


A single integer denoting n.


Constraints


•5 ≤ n ≤ 25


Output Format


Print exactly n - 1 lines of output in which each line i (where 1 ≤ i < n) contains n - 1 space-separated integers describing the minimum number of moves KnightL(i, j) must make for each respective j (where 1 ≤ j < n). If some KnightL(i, j) cannot reach position (n-1, n-1), print -1 instead.


For example, if n = 3, we organize the answers for all the (i,j) pairs in our output like this:


(1, 1) (1, 2)


(2, 1) (2, 2)


Sample Input 0


5


Sample Output 0


4 4 2 8


4 2 4 4


2 4 -1 -1


8 4 -1 1



My Introduction of algorithm

This is the first medium algorithm on Hackerrank RookieRank2 contest in Feb. 11, 2017, I pla

Main routine can be simplified

There are a few things about your CalculateStepsFromLeftTopToBottomRight() function that I feel could be simplified:

• No need to use HashSet to mark visited nodes when a simple array of bool will do.

• When you find a solution, you keep going to find all solutions. However, since you are using a breadth first search, the first solution you find will be the shortest one, and you can return it immediately.

• You have a double loop to generate the 8 possible moves. It would be simpler to have a single loop of 8, or even to just use 8 hardcoded lines.

• Instead of using a Tuple for coordinates, you can use a single int encoded as row * SIZE + col.

• Instead of returning a bool and also modifying a reference to an int, just return an int. If you don't find a solution, just return -1.

Simplified version

Here is how I would have rewritten your function:

public static void Visit(int row, int col, int n, Queue queue,
            bool[] visited)
    {
        if (row = n || col >= n)
            return;
        int position = row * n + col;
        if (visited[position])
            return;
        visited[position] = true;
        queue.Enqueue(position);
    }

    public static int CalculateStepsFromLeftTopToBottomRight(
            KnightL knightL)
    {
        int      n        = knightL.chessBoardSize;
        int      dx       = knightL.nSquaresHorizontal;
        int      dy       = knightL.mSquaresVertically;
        bool []  visited  = new bool[n*n];
        int      steps    = 0;

        var queue = new Queue();

        visited[0] = true;
        queue.Enqueue(0);

        while (queue.Count > 0)
        {
            int count = queue.Count;

            for (int i = 0; i < count; i++)
            {
                int position = queue.Dequeue();
                int row      = (position / n);
                int col      = (position % n);

                if (row == n-1 && col == n-1)
                {
                    // Found solution.
                    return steps;
                }

                Visit(row + dx, col + dy, n, queue, visited);
                Visit(row + dx, col - dy, n, queue, visited);
                Visit(row + dy, col + dx, n, queue, visited);
                Visit(row + dy, col - dx, n, queue, visited);
                Visit(row - dx, col + dy, n, queue, visited);
                Visit(row - dx, col - dy, n, queue, visited);
                Visit(row - dy, col + dx, n, queue, visited);
                Visit(row - dy, col - dx, n, queue, visited);
            }
            steps++;
        }

        return -1;
    }
}

You may notice that I did the breadth first search in a slightly different way. The search happens in "rounds", where each "round" handles all the possible positions at the current depth, while enqueuing the positions for the next depth. That way, the depth level doesn't have to be encoded into each item in the queue.

StackExchange Code Review Q#156882, answer score: 4