I am moving along with a project at work. I have completed the first pass. I am now optimizing the code and testing the system as a whole. As soon as I am done will move to replacing a component with a machine learning (ML) model. I am planning on developing the model using Azure. I would like to see if it is better that using OCR (Optical Character Recognition). Will let you know the results later this month.
I decided to give a try to the HackerRank Matrix Layer Rotation challenge. The challenge is rated HARD and worth 80 points. If interested take a look at the requirements. If interested you can read about how I addressed the problem in this post.
The idea is to rotate the elements in a matrix in an anti-clockwise direction. The dimensions and the number of rotations are specified.
By no means is this rotation a standard matrix operation!
4 4 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 2 3 4 8 1 7 11 12 5 6 10 16 9 13 14 15
In this case we have a 4 x 4 matrix and we need to perform a single rotation. I thought of viewing the rotations as independent rings (more about this later). In this case we have two rings. We rotate each once and the results follow. They seem to work.
4 4 2 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 3 4 8 12 2 11 10 16 1 7 6 15 5 9 13 14
In this case we also have a 4 x 4 matrix but we are asked to rotate each ring twice. A close look at the solution shows that the results match the requirements. By the way, this example is also illustrated in the HackerRank web page.
5 4 7 1 2 3 4 7 8 9 10 13 14 15 16 19 20 21 22 25 26 27 28 28 27 26 25 22 9 15 19 16 8 21 13 10 14 20 7 4 3 2 1
In this example things get a little more exciting. We are given a 5 x 4 matrix. The number of rows is different than the number of columns. In addition we rotate each ring 7 times. It takes a little more time to verify it, but the result seems to be fine. So far so good!
2 2 3 1 1 1 1 1 1 1 1
This example is interesting; not for the complexity, but for the possible message it sends. In this case, we are rotating a minimum size ring (2 x 2) a number of times (3). No matter how many times we rotate a ring with the same values, the result will be as if we do not rotate it in the first place. My thoughts were to come up with a solution first (of course not a brute force one) and if a test case timed out, then optimize it by checking if all numbers in all rings were the same, skip rotations. It turns out that I did not have to check for such condition.
6 4 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 2 3 4 8 1 7 11 12 5 6 15 16 9 10 19 20 13 14 18 24 17 21 22 23
I have to tell you that this example was due to an issue that I ran into. In my first submission, after passing the first set of tests, I encounter a division by zero exception. I bought an offending test case for 5 hackos but the complete set did not download. There seems to be an issue with the HackerRank site. That said I was able to figure out the issue by generating this test. More on this will follow. As you can see the results seem to match requirements.
/*
* Test scaffolding.
*/
public static void main(String[] args) {
// **** open scanner ****
Scanner sc = new Scanner(System.in);
// **** read m ****
int m = sc.nextInt();
// **** read n ****
int n = sc.nextInt();
// **** read r ****
int r = sc.nextInt();
sc.nextLine();
// **** declare the matrix ****
List<List<Integer>> matrix = new ArrayList<>();
// **** populate matrix (a row at a time) ****
for (int i = 0; i < m; i++) {
// **** read the next row of values ****
String[] matrixRowTempItems = sc.nextLine().split(" ");
// **** ****
List<Integer> matrixRowItems = new ArrayList<Integer>();
// **** ****
for (int j = 0; j < matrixRowTempItems.length; j++) {
int matrixItem = Integer.parseInt(matrixRowTempItems[j]);
matrixRowItems.add(matrixItem);
}
// **** ****
matrix.add(matrixRowItems);
}
// **** close scanner ****
sc.close();
// **** call function ****
matrixRotation(matrix, r);
}
As you may already know, most site that present challenges tend to include the test scaffolding since they need to test your solution against their results. I always follow the essence of TDD (Test Driven Development), not the hyped procedures. I start by looking at the input and developing the test scaffolding. I take a look at the actual function to make sure my approach matches the input for the function / method.
In this case the input could have been presented by a single array. The actual function expects a list of lists of integers. Not sure how well my main() function matches the one provided by HackerRank. What is important is that both present the same data to the function to be implemented as the solution.
/*
* Complete the matrixRotation function below.
*/
static void matrixRotation(List<List<Integer>> matrix, int r) {
// **** ****
int m = matrix.size();
int n = matrix.get(0).size();
// **** make rings ****
List<List<Integer>> rings = makeRings(matrix, m, n);
// **** rotate rings ****
List<List<Integer>> rotatedRings = rotateRings(rings, m, n, r);
// **** rings to matrix ****
int[][] rotMatrix = ringsToMatrix(rotatedRings, m, n);
// **** print matrix ****
printMatrix(rotMatrix, m, n);
}
For simplicity I decided to extract the matrix dimensions and make it available to the rest of the functions.
The solution is based on generating a set of rings; one per square / rectangle that needs to be rotated. Once we have the rings we can rotate them. We rotate the rings. Once they are rotated we need to get to a format that would be simple to print. I guess I could have just attempt to print the results from the rotated rings, but decided to convert them to a matrix. Once the matrix is available we can easily print results with 3 or 4 lines of code.
/*
* Make rings.
*/
static List<List<Integer>> makeRings(List<List<Integer>> matrix, int m, int n) {
// **** list of rings ****
List<List<Integer>> rings = new ArrayList<>();
// **** make rings (outer ring == 0) ****
for (int ringNum = 0; ringNum < Math.min(m / 2, n / 2); ringNum++) {
// **** ****
List<Integer> ring = makeRing(matrix, ringNum, m, n);
// **** add ring to rings ****
rings.add(ring);
}
// **** return rings ****
return rings;
}
This function declares a list of lists of integer to hold the rings. We then loop once per ring generating a single ring. The ring is then added to the list. I call your attention to the end condition for the loop. Initially I used m/2 but that creates a problem when we have matrices higher that wider. The examples in the web site do not cover such condition. I solved it using the Math.min() method.
/*
* Make a single ring.
*/
static List<Integer> makeRing(List<List<Integer>> matrix, int ringNum, int m, int n) {
// **** ****
List<Integer> ring = new ArrayList<Integer>();
// **** go right ****
for (int i = ringNum; i < (n - ringNum); i++) {
ring.add(matrix.get(ringNum).get(i));
}
// **** go down (skip first and last) ****
for (int i = ringNum + 1; i < m - ringNum - 1; i++) { ring.add(matrix.get(i).get(n - ringNum - 1)); } // **** go left **** for (int i = (n - ringNum - 1); i >= ringNum; i--) {
ring.add(matrix.get(m - ringNum - 1).get(i));
}
// **** go up (skip first and last) ****
for (int i = m - ringNum - 2; i > ringNum; i--) {
ring.add(matrix.get(i).get(ringNum));
}
// **** ****
return ring;
}
This method is in charge to make a single ring. We start by declaring an array list. We need to go in four directions in order to collect all the integers for the ring. We first go from left to right on the top. I labeled this “go right”. We then need to go down, followed by going left on the bottom, and finally going up to complete filling the contents of the ring.
I do not like to generate functions / methods when it is not needed. By having all the logic in a single function we can debug the code keeping an eye on the pieces that need to be integrated. For example, if the “go right” section start with the first element and ends taking the last element of the top row, then the “go down” section must start with the element in the second row (not the element in the first one) since it has already been picked up. You need to make sure that if you pick up the last element in a segment, you do not repeat it in the next segment. As you can see we could use the top and bottom segments to collect the entire rows, and have the up and down segments skip the first and last elements. Do as you please.
/*
* Rotate rings.
*/
static List<List<Integer>> rotateRings(List<List<Integer>> rings, int m, int n, int r) {
// **** loop rotating rings ****
for (int ringNum = 0; ringNum < rings.size(); ringNum++) {
// **** rotate this ring ****
rotateRing(rings, r, ringNum);
}
// **** return rotated rings ****
return rings;
}
Now we have to rotate the rings. The simplest way is to loop through the set of rings rotating each one.
/*
* Rotate the specified ring.
*/
static void rotateRing(List<List<Integer>> rings, int r, int ringNum) {
// **** initialization ****
List<Integer> tempRing = new ArrayList<>();
List<Integer> ring = rings.get(ringNum);
int len = ring.size();
// **** copy values to temp ring ****
int i = r % len;
while (true) {
// **** copy this element ****
tempRing.add(ring.get(i));
// **** update index ****
i++;
if (i >= len)
i = 0;
// **** check if done with copy ****
if (i == (r % len))
break;
}
// **** replace ring with temp ring ****
rings.set(ringNum, tempRing);
}
This function rotates a specified ring. We start by initializing some variables. We could loop for r passes which could be considered the brute force approach. What we do instead is to traverse the ring from a specified position and copy the value to a temporary list. We then update the index. We finally check if we are done looping and replace the specified ring with the temporary ring.
/*
* Convert rings to rotated matrix.
*/
static int[][] ringsToMatrix(List<List<Integer>> rotatedRings, int m, int n) {
// **** declare rotated matrix ****
int[][] matrix = new int[m][n];
// **** traverse each ring populating the matrix ****
for (int ringNum = 0; ringNum < Math.min(m / 2, n / 2); ringNum++) {
// **** select ring ****
List<Integer> ring = rotatedRings.get(ringNum);
// **** populate matrix with the ring contents ****
for (int i = 0; i < ring.size();) {
// **** go right ****
for (int col = ringNum; col < (n - ringNum); col++) {
matrix[ringNum][col] = ring.get(i++);
}
// **** go down ****
for (int row = ringNum + 1; row < (m - ringNum); row++) { matrix[row][n - ringNum - 1] = ring.get(i++); } // **** go left **** for (int col = (n - ringNum - 2); col >= ringNum; col--) {
matrix[m - ringNum - 1][col] = ring.get(i++);
}
// **** go up ****
for (int row = m - ringNum - 2; row > ringNum; row--) {
matrix[row][ringNum] = ring.get(i++);
}
}
}
// **** return rotated matrix ****
return matrix;
}
As I mentioned, I wanted to convert the rotated rings into a matrix of int[][] for ease of printing.
We start by declaring the matrix. We then enter a loop and in order select a ring by number. We need to traverse the ring and copy the integers to the proper places in the matrix. As you can see we take a similar approach to the one used in the makeRing() function. We move right, down, left and up copying the values in the ring to the proper locations in the matrix. When done we return the matrix.
/*
* Print the specified matrix.
*/
static void printMatrix(int[][] matrix, int m, int n) {
// **** ****
for (int row = 0; row < m; row++) {
for (int col = 0; col < n; col++) {
System.out.print(matrix[row][col] + " ");
}
System.out.println();
}
}
The challenge requires us to print the results to the screen. This method traverses the matrix printing the values to the output (in our case to the Terminal windows of the Visual Studio Code IDE).
There you have it. The solution was accepted by HackerRank.
The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to serve of assistance with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a message using the following address: john.canessa@gmail.com. All messages will remain private.
Keep on reading and experimenting. It is the best way to learn, refresh your knowledge and enhance your developer toolset!
John
Follow me on Twitter: @john_canessa