Matrix Rotation Exercise

Inside the directory you created for this course on PHP, create a new folder called Exercise-22-Matrix-Rotation and put the .php solution files for this exercise within it.

The function rotate_by_90() is only meant to rotate the given matrix by ::90^{\circ}::, and is likewise quite straightforward to implement.

Well, even if we were asked to rotate the matrix by an arbitrary angle, some multiple of ::90^{\circ}::, it would still be easy to implement the function in that case. How?

Well, if you think about it any arbitrary rotation angle, such as ::-90^{\circ}:: or ::540^{\circ}::, is the exact same as one of the following: ::0^{\circ}::, ::90^{\circ}::, ::180^{\circ}:: and ::270^{\circ}::. For ::0^{\circ}::, we need to do nothing; for ::90^{\circ}::, we need to call rotate_by_90() once; for ::180^{\circ}::, we need to call it twice, consecutively; and for ::270^{\circ}::, we need to call it thrice, consecutively.

Anyways, let's talk about the simple implementation of rotation by ::90^{\circ}:: as performed by our rotate_by_90() function.

The solution is merely about figuring out a pattern in the final rotated matrix based on the initial configuration of the matrix and then translating that pattern into actual code.

Let's think about that pattern...

Where is the ::(i, j)^{th}:: element of the rotated matrix located on the original matrix?

Well, it can easily be observed that anything that is in the ::i^{th}:: row of the rotated matrix lies somewhere in the ::i^{th}:: column of the original matrix.

Similarly, anything that's in the ::j^{th}:: column of the rotated matrix lies somewhere in the ::(n - j - 1)^{th}:: row of the original matrix (assuming that ::i:: begins at ::0::, and not at ::1::).

And voila! There we have the pattern.

With this awesome discovery, it's now finally time to code it out.

The function definition below of rotate_by_90() goes over the given $matrix array, iterates over each of its items and performs the assignment as described above:

<?php

function &rotate_by_90(&$matrix) {
   $n = count($matrix);

   for ($i = 0; $i < $n; $i++) {
      for ($j = 0; $j < $n; $j++) {
         $matrix[$i][$j] = $matrix[$n - $j - 1][$i];
      }
   }
   return matrix;
}

Note the & in the &$matrix parameter (remember pass by-reference?) — it's used because we need to mutate the original matrix passed into rotate_by_90().

In addition to this, also take note of the & in &rotate_by_90() (remember return by-reference?) — it's used because we need to return the original array passed into the function.

Now, let's test this code on one of the two arrays given in the exercise description above:

<?php

/* print_matrix() defined here */

function &rotate_by_90(&$matrix) {
   $n = count($matrix);

   for ($i = 0; $i < $n; $i++) {
      for ($j = 0; $j < $n; $j++) {
         $matrix[$i][$j] = $matrix[$n - $j - 1][$i];
      }
   }
   return $matrix;
}

$a = [ [1, 4], [10, 2] ];
print_matrix(rotate_by_90($a));

Oops! The output is NOT what we expected. There is definitely some problem in the code.

Can you spot the problem?

Well, the problem lies in line 10.

Let's identify the problem by going through the loop manually on the following matrix,

and witness each iteration closely.

$matrix is [[1, 4], [10, 2]]. Its length is 2. Likewise, $n = 2.

In the very first iteration of the inner loop (in line 9), $i = 0 and $j = 0. $matrix[$i][$j] thus becomes $matrix[0][0]. This position is assigned the value of $matrix[$n - $j - 1][$i], i.e. $matrix[1][0] which is simply the number 10.

At the end of this first iteration, $matrix is [[10, 4], [10, 2]].

And here's our problem.

As we assign values from $matrix directly to $matrix[$i][$j], we lose information from it. In the example above, we lost the number 1 from the matrix.

The solution to this is simply to make a copy of $matrix and then perform the assignments on it using its copy. Thanks to the copying, the original information of $matrix is always with us during the rotation.

Amazing!

In the code below, we assign $matrix to $matrix_copy, which effectively copies $matrix and then stores the copy in $matrix_copy, and use this in retrieving the element to be assigned to $matrix[$i][$j]:

<?php

/* print_matrix() defined here */

function &rotate_by_90(&$matrix) {
   $n = count($matrix);
   $matrix_copy = $matrix;

   for ($i = 0; $i < $n; $i++) {
      for ($j = 0; $j < $n; $j++) {
         $matrix[$i][$j] = $matrix_copy[$n - $j - 1][$i];
      }
   }
   return $matrix;
}

$a = [ [1, 4], [10, 2] ];
print_matrix(rotate_by_90($a));

As before, let's test this code to confirm its correctness:

Great!

Let's even check $a after subsequent double rotation, just as demonstrated in the exercise's description above:

<?php

/* print_matrix() defined here */

function &rotate_by_90(&$matrix) { /* ... */ }

$a = [ [1, 4], [10, 2] ];
rotate_by_90($a);
print_matrix(rotate_by_90(rotate_by_90($a)));
echo "\n";
print_matrix($a);

Perfect! It's working flawlessly.

You could even try to test this function on a ::3 \times 3::, ::4 \times 4::, ::5 \times 5::, or any ::n \times n:: matrix — the output would always be correct.