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:

enter image description here

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

enter image description here

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.

• Jianmin Chen: Excellent reviews. All advice are making good sense. I could not believe that you put all the great ideas in one algorithm.
• Jianmin Chen: I like your idea to count each breadth level ( denoted as n, actually it is variable: steps), I will put together code and test it against hackerrank test cases. You teach me the breadth first search very well on this algorithm. Excellent!
• Jianmin Chen: do you think that it is also good idea to declare var queue = new queue<int[]>? row and col can put into the array new int[2]. Therefore, we do not need to encode a key and then decode the key to row and col two variables. I am learning data structure and try to speed up coding.
• JS1: It's a matter of preference. I tend to use primitive types whenever possible, but if using int[] seems easier to understand than using a single int, then you should do that. Note that using a single encoded int leads to a simpler visited array as well.
• paparazzo: Slick. Like how you did steps.