Hackerrank: KnightL on a Chessboard

Question

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 (x₁, y₁) to some (x₂, y₂) satisfying either of the following:

• x₂ = x₁ ± a and y₂ = y₁ ± b or

• x₂ = x₁ ± b and y₂ = y₁ ± 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 played the contest and then I spent 1 hours 41 minutes to write the algorithm in C# programming language after I spent at least 20 minutes to understand the problem. The best performer only needs to take less than 20 minutes. I spent extra time in the contest to change the code from 4 directions to 8 directions after I failed some test cases, I should have worked on 8 possible directions to next move in the design before I start to write the code.

The C# code passes all test cases on hackerrank.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace KnightLOnAChessboard
{
    /*
     * problem statement:
     * https://www.hackerrank.com/contests/rookierank-2/challenges/knightl-on-chessboard
     * start time: 9:30am, 2/11/2017
     * end time: 12:11pm, 2/11/2017 
     */
    class Node
    {
        public Tuple<int, int> element { get; set; }
        public int steps { get; set; }

        public Node(Tuple<int, int> node, int value)
        {
            element = new Tuple<int, int>(node.Item1, node.Item2);
            steps = value;
        }
    }

    class KnightL
    {
        private int nSquaresHorizontal { get; set; }
        private int mSquaresVertically { get; set; }
        private int chessBoardSize { get; set; }

        /*
         * row from 1 to size - 1
         * col from 1 to size - 1
         * where size is from 5 to 25
         */
        public KnightL(int row, int col, int size)
        {
            nSquaresHorizontal = row;
            mSquaresVertically = col;
            chessBoardSize = size;
        }

        /*
         * @knightL - knightL is defined, from (0,0) to (n-1, n-1) minimum steps
         * if there is one, return true; 
         * else return false
         * 
         * BoundaryCheck
         * BFS using queque
         * HashSet check visitedNodes
         * 
         * 8 directions - need to define those 8 directions
         */
        public static bool CalculateStepsFromLeftTopToBottomRight(KnightL knightL, ref int minimumFoundSteps)
        {
            var visitedNodes = new HashSet<Tuple<int, int>>();
            bool foundOne = false;

            var queue = new Queue<Node>();

            queue.Enqueue(new Node(new Tuple<int, int>(0, 0), 0));

            while (queue.Count > 0)
            {
                var visiting = queue.Dequeue();

                if (IsDestination(visiting.element, knightL.chessBoardSize))
                {
                    int currentSteps = visiting.steps;
                    minimumFoundSteps = (currentSteps < minimumFoundSteps) ? currentSteps : minimumFoundSteps;
                    foundOne = true;
                    continue;
                }

                // do not continue, prune to save time. 
                if (visiting.steps + 1 > minimumFoundSteps)
                {
                    continue;
                }

                // there are 8 possible next moves in next knightL game, implementing in two steps.
                // 1. column and row in orginal order, or switch column and row
                // 2. four directions for each time
                int[] directionRow = new int[] { 1, 1, -1, -1 };
                int[] directionCol = new int[] { 1, -1, 1, -1 };

                int visitingRow = visiting.element.Item1;
                int visitingCol = visiting.element.Item2;

                for (int switchRowAndCol = 0; switchRowAndCol < 2; switchRowAndCol++)
                {
                    for (int direction = 0; direction < directionRow.Length; direction++)
                    {
                        int incrementRow = knightL.nSquaresHorizontal;
                        int incrementCol = knightL.mSquaresVertically;

                        if (switchRowAndCol == 1)
                        {
                            incrementRow = knightL.mSquaresVertically;
                            incrementCol = knightL.nSquaresHorizontal;
                        }
                        var nextRow = visitingRow + directionRow[direction] * incrementRow;
                        var nextCol = visitingCol + directionCol[direction] * incrementCol;

                        var nextVisit = new Tuple<int, int>(nextRow, nextCol);

                        if (IsInBoundary(nextRow, nextCol, knightL.chessBoardSize) &&
                            !visitedNodes.Contains(nextVisit))
                        {
                            visitedNodes.Add(nextVisit);

                            queue.Enqueue(new Node(nextVisit, visiting.steps + 1));
                        }
                    }
                }
            }

            return foundOne;
        }

        public static bool IsDestination(Tuple<int, int> visiting, int size)
        {
            return visiting.Item1 == (size - 1) &&
                   visiting.Item2 == (size - 1);
        }

        public static bool IsInBoundary(int row, int col, int size)
        {
            return row >= 0 && row < size && col >= 0 && col < size;
        }
    }

    public class ChessBoardWithMinimumSteps
    {
        private int Size { get; set; } // code review: public -> private
        public int[][] Step { get; set; }

        public ChessBoardWithMinimumSteps(int value)
        {
            Size = value;
            Step = new int[Size][];
            for (int i = 0; i < Size; i++)
            {
                Step[i] = new int[Size];
            }
        }

        /*
         * Go over each row from 0 to n - 1, 
         * for each row, go over column from 0 to n - 1
         *
         */
        public void CalculateChessBoardMinimumSteps()
        {
            for (int row = 1; row < Size; row++)
            {
                for (int col = 1; col < Size; col++)
                {
                    KnightL knightL = new KnightL(row, col, Size);
                    int minimumSteps = Int32.MaxValue;
                    bool found = KnightL.CalculateStepsFromLeftTopToBottomRight(knightL, ref minimumSteps);

                    Step[row - 1][col - 1] = found ? minimumSteps : (-1);
                }
            }
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            ProcessInput();
            //RunSampleTestcase(); 
        }

        public static void RunSampleTestcase()
        {
            ChessBoardWithMinimumSteps myChessBoard = new ChessBoardWithMinimumSteps(5);

            myChessBoard.CalculateChessBoardMinimumSteps();

            int[][] steps = myChessBoard.Step;

            for (int i = 0; i < steps.Length - 1; i++)
            {
                StringBuilder concatented = new StringBuilder();
                for (int j = 0; j < steps[0].Length - 1; j++)
                {
                    concatented.Append(steps[i][j] + " ");
                }

                Console.WriteLine(concatented.ToString());
            }
        }

        public static void ProcessInput()
        {
            int size = Convert.ToInt32(Console.ReadLine());

            ChessBoardWithMinimumSteps myChessBoard = new ChessBoardWithMinimumSteps(size);

            myChessBoard.CalculateChessBoardMinimumSteps();

            int[][] steps = myChessBoard.Step;

            for (int i = 0; i < steps.Length - 1; i++)
            {
                StringBuilder concatented = new StringBuilder();
                for (int j = 0; j < steps[0].Length - 1; j++)
                {
                    concatented.Append(steps[i][j] + " ");
                }

                Console.WriteLine(concatented.ToString());
            }
        }
    }
}

Answer 1

Main routine can be simplified

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

1. No need to use HashSet to mark visited nodes when a simple array of bool will do.
2. 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.
3. 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.
4. Instead of using a Tuple<int, int> for coordinates, you can use a single int encoded as row * SIZE + col.
5. 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<int> queue,
            bool[] visited)
    {
        if (row < 0 || col < 0 || 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<int>();

        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.