Matrix Rotation Study

January 2, 2017

Introduction
Julia learns the hard way. This past 2016, Julia worked on matrix rotation practice (No.1) again in April, 2016, she failed to deliver the ideal result in one hour setting. And then, she came back to work on matrix rotation so many times. Hackonacci Matrix rotation - algorithm on HackerRank week code 27, Julia spent more than 4 hours to review all submissions, she did learn the hard way - in the contest she spent more than 3 hours to write code, but scored less than 10% in Dec. 2016.

Now, she came cross this study about using transpose and flip code again, now she was smart and mature enough to take it and be the master of matrix rotation time saver.


Workout

Use transpose and flip operations


Another code of transpose and flip with a flag to separate clockwise from anti-clockwise.

Julia's C# practice.

Matrix Rotation - Code Review - Series 3 of 10+

Dec. 6, 2016
Problem statement:
https://www.hackerrank.com/challenges/matrix-rotation-algo

Study code:
https://gist.github.com/jianminchen/1c1c07b5454a43d493264c6db4444ea3

Because there are over hundred C# solution to review, Julia likes to go over them first, mark good solutions to study first.

1. jaygundy
https://www.hackerrank.com/rest/contests/master/challenges/matrix-rotation-algo/hackers/jaygundy/download_solution

2. pableFomenta - similar to code review #2
https://www.hackerrank.com/rest/contests/master/challenges/matrix-rotation-algo/hackers/PabloFomenta/download_solution

Ideas to study code submissions:
1. Study all submissions using JavaScript with full score.
  30+ solutions

2. Study submissions - using filters:

Carnegie Mellon University, Pittsburgh(30+)
MIT ()
Stanford University
University of California, Berkeley

Amazon (20+)
Google  (20+)
Facebook (5)
     Facebook - Player-1

Look for code with good style and design ideas:

Facebook:
1. Java
Define Set function, line 65 - 69.
https://gist.github.com/jianminchen/5e7796bce5a9420472bec31a2cc6e30b

Google

2. C++
line 25, int lt_corner - variable is very clear and meaningful
https://gist.github.com/jianminchen/d8843e292df6e9070e5f55c907ad0f69

3. C++
Matrix at most 300x300, so total size at most is 300*300*4bytes = 360MB, 360KB, HackerRank maximum space is 512MB.
line 8: int M[300][300]
Declare a global variable - jagged array, the code is very easy to read.
Use the condition:  n <= 300
https://gist.github.com/jianminchen/15ff14b51ab1c9f86084dbba4a036684

4. C

For any element in the array, use one for loop to rotate k steps. Very smart handling - code from
line 29 - 45, total 16 lines of code
https://gist.github.com/jianminchen/137807675ba27fd532ffaed4f98a68df

5. Java
Cannot believe!
https://gist.github.com/jianminchen/6e84dfcf2fb222d84900bda27687e6a1

Amazon

Java
6. Design a class: LinkedListLight, with an API  - RotateBy(int steps)
https://gist.github.com/jianminchen/b7cb950b70563b56cb37909e72e0b48c

Standford:

JavaScript
7. https://gist.github.com/jianminchen/ae14bc0d764240d03831e6429337199a

HackerRank - Matrix Rotation (Series 5 of 5)

Dec. 6, 2016

Introduction:
Julia has more talent now after she attended her new school - stackexchange.com code review for code review on stackexchange.com. She did post two questions, and the first one, she learned a few things. One most important one is "Do not use abstract variable name. Do not let user guess what the variable name does".

Julia spent 30 minutes to review the practice in April 2016, and then, she went through the code, found the bug.

Last practice scoring 8 of 80:
(more than 1 hour, still having bugs, score 8.89/ wrong answer)
https://gist.github.com/jianminchen/57572227dafe939060f7cc81b193cd9b

Code review done by Julia on Dec. 6, 2016
1. Do not use abstract variable names. Please use meaningful name
line 16, s1
line 17, sA
line 20, T
line 22, arr
line 27, aA

In the function rotateArrayOneStepAntiClockwise
line 53, cnt
int 53, arr
line 71, ci
line 73, startR
line 74, startC
line 75, endR
line 76, endC
line 78, tmpVal
line 81, i
line 85, i,
line 89, i,
line 94, i,

2. function name should use
rotateArrayOneStepAntiClockwise
Should use PascalCased
RotateArrayOneStepAntiClockwise

"In C#, method names should be PascalCased, not camelCased"

Workout:
c# solution: pass all test cases
https://gist.github.com/jianminchen/6fabef7436097552e35633a549b0268a

Discussion:

Use meaningful variable name - The code is much easy to understand, therefore, static analysis should be much more easy.

For example, Julia reviewed the code on Dec. 6, 2016, line 53 cnt, the variable name is not meaningful, so she decided to replace the name using "steps". Line 114, there is some calculation, so in order to avoid timeout, there is actual steps taken < strip size. So, she decided to add a new variable name on line 114, called actualSteps. Just those two changes, Julia fixed the bug she could not fix in April, 2016 over 1 hour.

HackerRank - matrix rotation (Series 4 of 5)

Nov. 8, 2016

Plan to work on unfinished HackerRank algorithm related to array, try to score full score this time to celebrate new year 2017.

http://juliachencoding.blogspot.ca/2016/04/hackerrank-matrix-rotation-ii.html

Rotate array - HackerRank

problem statement:
https://www.hackerrank.com/challenges/matrix-rotation-algo

Write C# solution:

Review April, 2016 practice: 

another practice: (more than 1 hour, still having bugs, score 8.89/ wrong answer)
https://gist.github.com/jianminchen/57572227dafe939060f7cc81b193cd9b

Will come back very soon with the solution, hopefully score a hard algorithm perfectly. 

Dec. 6, 2016
Fix the bug on line 114, declare a new variable on line 114 actualSteps
C# solution - pass all test cases:
https://gist.github.com/jianminchen/6fabef7436097552e35633a549b0268a

There are over 100 C# solutions, Julia, let us have some fun; code review as many solutions as possible. 
Post C# solution here:

HackerRank: Matrix Rotation (Series 3 of 5) - using extra space - an array

April 18, 2016 
Rotate array - HackerRank

problem statement:
https://www.hackerrank.com/challenges/matrix-rotation-algo

Study other's code:

https://gist.github.com/jianminchen/9005cbbbbbd60e307759747856e3a35a

Write a solution using the same idea. Try to practice 20 - 30 minutes.

Just be simple; Read other people's code, like it; and then, write exactly same idea, and see if you can make it work as well.

Write same algorithm again and again, use various ideas; same idea, write again and again, see if you can improve the performance, more concentration - write the program from hours to 30 minutes, less than 10 minutes. Practice makes perfect.

To be continued:
Action item:

Will write my own version of implementation.

HackerRank: Matrix Rotation (Series 2 of 5)

April 18, 2016 
Rotate array - HackerRank

problem statement:
https://www.hackerrank.com/challenges/matrix-rotation-algo

Study other's code:

https://gist.github.com/jianminchen/c234a238ea331ea9a037d603c37a6649

So, do not swap two nodes value, just save first node's value in a variable, and then, shift array kind operation.

Write C# solution:

another practice: (more than 1 hour, still having bugs, score 8.89/ wrong answer)
https://gist.github.com/jianminchen/57572227dafe939060f7cc81b193cd9b

Time spent:

More than 2 hours 

HackerRank: Matrix Rotation (Series 1 of 5)

April 14, 2016

Rotate array - HackerRank

problem statement:
https://www.hackerrank.com/challenges/matrix-rotation-algo

Spent hours to work on the solution, passed 4 basic test case, but still score 0 out of 80 points:

https://gist.github.com/jianminchen/4d719488e378aeb498d4cb363cbd1f7d

Just be patient. Study other's code:

https://gist.github.com/jianminchen/c234a238ea331ea9a037d603c37a6649

So, do not swap two nodes value, just save first node's value in a variable, and then, shift array kind operation.

Corner case is very simple. Julia wasted hours to work on poor design, try to avoid overwrite the value of arr[1][0]. Just use a variable to save it.

https://www.hackerrank.com/rest/contests/master/challenges/matrix-rotation-algo/hackers/Relentless/download_solution

So, changed my own code, with bugs to fix:  Int16 should be int, check Int16 max value 32767, whereas Int32 max value 2,147,484,647, less than 3 *10^9
https://gist.github.com/jianminchen/6e3ca88e8633ad8bace8387f154904df

only pass one case:
https://gist.github.com/jianminchen/12b58729c59e44a0d71d9f9c47bc937c

another practice: (more than 1 hour, still having bugs, score 8.89/ wrong answer)
https://gist.github.com/jianminchen/57572227dafe939060f7cc81b193cd9b

study the code here:
https://gist.github.com/jianminchen/6e2ca0ac395913646ed012c40c283e7f

https://gist.github.com/jianminchen/c0f91e5f5406c3dce35ce48c4c646c33

study forum:
https://www.hackerrank.com/challenges/matrix-rotation-algo/forum

Algorithm, Rotate matrix nxm clockwise 90 degree

April 5, 2016

  Write an algorithm to rotate matrix nxm clockwise 90 degree.

  Use no compiler, no Ctrl+C, and then, time complexity analysis:

Here is the code Julia wrote, she thought about the swapping strategies:
1. swap multiple times
2. leave four corners as is, swap four corners seperately.

https://gist.github.com/jianminchen/e489cf7a490ac426eb50b4300890387d

/*
April 5, 2016

NO ctrl+C copy

matrix nxm rotate clockwise 90 degree

do it in place
*/

 public static bool rotateInplace90ClockWise(int[][] arr)
        {
            if (arr == null || arr.Length == 0 || arr[0].Length == 0) return false;
            int n = arr.Length;      // row
            int m = arr[0].Length;   // column

            if (n != m) return false;

            // we need to start loops

            int start = 0;
            int end = n - 1;

            while (start < end && start < n / 2 && end < n / 2)
            {

                // top with right swap - left the terminal point untouched
                // left to right <- row
                // top to down   <- column
                for (int i = start + 1; i < end - 1; i++)
                {
                    int currx = start;
                    int curry = i;

                    int currx_col = i;
                    int curry_col = end;

                    swap(arr, currx, curry, currx_col, curry_col);
                }

                // now, top down, we need to cross swap

                for (int i = start + 1; i < end - 1; i++)
                {
                    int currx = start;
                    int curry = i;

                    int currx_down = end;
                    int curry_down = end - i;

                    swap(arr, currx, curry, currx_down, curry_down);
                }

                // left and top swap
                for (int i = start + 1; i < end - 1; i++)
                {
                    // left part
                    int currx = end - 1 - i;
                    int curry = start;

                    int currx_top = start;
                    int curry_top = i;

                    swap(arr, currx, curry, currx_top, curry_top);
                }

                // and then, rotate four corners
                // 1, 2
                // 4  3
                swap(arr, start, start, start, end);
                swap(arr, end, end, start, start);
                swap(arr, start, start, end, start);

                start++;
                end--;
            }
            return true;
        }
 
       private static void swap(int[][] arr, int x, int y, int x2, int y2)
       {
           int tmp     = arr[x][y];
           arr[x][y]   = arr[x2][y2];
           arr[x2][y2] = tmp;
       }

https://gist.github.com/jianminchen/e489cf7a490ac426eb50b4300890387d

time complexity: since every node in the matrix at most swaps twice, so the count of swap is O(n^2)