1
\$\begingroup\$

Problem statement

Given a matrix (up to 300 × 300), rotate each element R steps anti-clockwise along concentric rectangular paths (R up to 109).

The algorithm is rated as hard on HackerRank.

On April, 2016, I wrote the algorithm with a bug, scored 8 out of maximum 80 points. I could not find the bug after hours work.

On Dec. 6, 2016, I reviewed the code again, and then decided to use meaningful variable names, removed all abstract variables names, and found the bug because of reusing the function RotateAntiClockwiseByLayer input argument steps,

steps = steps % circleLength;

Bug fix is to declare a new variable: actualSteps, so the statement is

int actualSteps = steps % circleLength;

and scored 80. Lesson learned: Meaningful variable names are helpful to do static analysis, code review, and bug fixes.

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

namespace RotateArray
{
class Program
{
    /*
     * Int16 maximum value is 32676, less than 4 * 10^9
     */
    static void Main(string[] args)
    {
        MatrixRotation();             
    }       

    private static void MatrixRotation()
    {
        string input = Console.ReadLine();
        string[] arr = input.Split(' ');
        int row = Convert.ToInt32(arr[0].Trim());
        int col = Convert.ToInt32(arr[1].Trim());
        int rotations = Convert.ToInt32(arr[2].Trim());

        int[,] matrix = new int[row, col];
        int[][] mx = new int[row][];

        for (int i = 0; i < row; i++)
        {
            mx[i] = GetInts(Console.ReadLine(), col);

            for (int j = 0; j < col; j++)
                matrix[i, j] = mx[i][j];
        }

        RotateAntiClockwiseByLayer(matrix, rotations);

        for (int i = 0; i < row; i++)
        {
            string s = "";
            for (int j = 0; j < col; j++)
                s += matrix[i, j] + " ";
            Console.WriteLine(s.Trim());
        }
    }

    static int[] GetInts(string inp, int cnt)
    {
        string[] vals = inp.Split(new char[] { ' ' });
        int[] res = new int[cnt];
        for (int i = 0; i < cnt; i++)
        {
            res[i] = Convert.ToInt32(vals[i]);
        }
        return res;
    }

    /*
     * Dec. 6, 2016
     * Review the code, 
     * follow the code style - 
     * 1. Do not use abstract variable name 
     * 
     * 
     */
    public static bool RotateAntiClockwiseByLayer(int[,] matrix, int steps)
    {
        if (matrix == null) return false;

        int rows = matrix.GetLength(0);  // row
        int cols = matrix.GetLength(1);  // column 

        int startRow = 0;
        int startCol = 0;           

        while (rows > 1 && cols > 1)
        {
            int circleLength = 2 * rows + 2 * cols - 4;
            int actualSteps = steps % circleLength;

            for (int step = 0; step < actualSteps; step++) //  move one step anti-clockwise a time
            {
                int lt_corner = matrix[startRow, startCol]; // left-top corner element

                for (int colIndex = startCol; colIndex < startCol + cols - 1; colIndex++)
                    matrix[startRow, colIndex] = matrix[startRow, colIndex + 1];

                int lastCol = startCol + cols - 1;
                for (int rowIndex = startRow; rowIndex < startRow + rows - 1; rowIndex++)
                    matrix[rowIndex, lastCol] = matrix[rowIndex + 1, lastCol];


                int lastRow = startRow + rows - 1;
                for (int colIndex = startCol + cols - 1; colIndex >= startCol + 1; colIndex--)
                    matrix[lastRow, colIndex] = matrix[lastRow, colIndex - 1];

                for (int rowIndex = startRow + rows - 1; rowIndex >= 1 + startRow; rowIndex--)
                    matrix[rowIndex, startCol] = matrix[rowIndex - 1, startCol];

                matrix[startRow + 1, startCol] = lt_corner;
            }

            startRow++;
            startCol++;

            rows -= 2;
            cols -= 2;
        }

        return true;
    }
}
}

Also, I read a lot of submissions, in C/C++/ Java/ JavaScript. For example, one solution is to declare a global jagged array with size 300, using 300 MB of space.

There are several concerns about the code I wrote. Inside the function RotateAntiClockwiseByLayer, there are four for loop inside a while loop, inside the first for loop:

for (int step = 0; step < actualSteps; step++)

+1 four times, -1 four times. It's easy to make a mistake in 8 places. And I saw an idea to replace 4 for loops, using one for loop instead with 4 if statements. The code looks simple, no -1, +1 compared to my solution:

int parameter = (maxRow + maxCol) * 2 - min * 4;

int row = r;
int col = c;
for (int a = 0; a < rot%parameter; a++) {
    if (col == min && row < maxRow) {
        row++;
    }
    else if (row == maxRow && col < maxCol) {
        col++;
    }
    else if (row > min && col == maxCol) {
        row--;
    }
    else if (row == min && col > min) {
        col--;
    }
}
result[row][col] = arr[r][c];

I talked about my practice, concerns, seek better ideas to solve the problem.

\$\endgroup\$
  • 1
    \$\begingroup\$ A 300x300 array of 4 byte values is 360000 bytes, which is 360 KB not 360 MB. So you can use a temp matrix without worrying about exceeding the 512 MB limit. \$\endgroup\$ – JS1 Dec 8 '16 at 10:55
  • \$\begingroup\$ @JS1, you are correct on the calculation - 360KB, not 360MB. \$\endgroup\$ – Jianmin Chen Dec 8 '16 at 18:11
  • 1
    \$\begingroup\$ Good work! Now the version with new variable names is much much easier to understand so I guess I can take a look at it. The first one was like WTF is this? ;-D As there aren't any reviews yet, you can replace the orginal code with the new one. Two versions just confuse. \$\endgroup\$ – t3chb0t Dec 24 '16 at 10:15
  • \$\begingroup\$ @t3chb0t, I am removing the first version of code to follow your advice. \$\endgroup\$ – Jianmin Chen Dec 24 '16 at 18:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.