Introduction

Matrix rotation is the transformation based on replacing the value of a cell with the value of an adjacent one, where the notion of “adjacent” is expressed with reference to the decomposition of a matrix in “rings”. It’s a bit like peeling an onion. Let us consider the matrix depicted above. We can easily identify its outer ring. { a₀₀, a₀₁, a₀₂, a₀₃, a₀₄, a₁₄, a₂₄, a₃₄, a₃₃, a₃₂, a₃₁, a₃₀, a₂₀, a₁₀ }. The next ring is also easily identified: { a₁₁, a₁₂, a₁₃, a₂₃, a₂₂, a₂₁ }.

Assumptions

In this article I will assume that matrix rotation is applied counterclockwise. Similar arguments apply if the rotation is done clockwise. For simplicity’s sake, I will use a matrix of integers.

Representing a matrix

The typical representation of a matrix is based on two-dimensional arrays. Since we will use Scala and we want to learn to write clean algorithms without side effects, we will use immutable type Vector instead.

So, our matrix of integers will be defined as matrix: Vector[Vector[Int]]

The algorithm

I will illustrate the algorithm in steps. First will I explain how the decomposition of a matrix in rings simplifies the logic of rotation. Second, I will explain how to implement this logic without duplicating the content of the matrix for the creation of its constituent rings: we will create an abstraction which will allow us to navigate the matrix as if it were structured in rings. This trick will reduce the space complexity of the algorithm.

Using the rings to implement rotation

Given the matrix in our example above, we can represent the rings using vectors:

val ring0 = Vector( a₀₀, a₀₁, a₀₂, a₀₃, a₀₄, a₁₄, a₂₄, a₃₄, a₃₃, a₃₂, a₃₁, a₃₀, a₂₀, a₁₀ )

val ring1 = Vector( a₁₁, a₁₂, a₁₃, a₂₃, a₂₂, a₂₁ )

As you can see, we have ring0.size = 14 and ring1.size = 6

The logic of rotation can now be expressed using plain modulo arithmetic. If we define “r” the number of (anticlockwise) rotations, and “i” the position of a cell in vector ring0, the new value of ring0(i) is the value of cell ring0((i+r) % ring0.size)

Let us now set r=1

ring0(0) = ring0((0+1) % 14) = ring0(1) = a₀₁

ring0(1) = ring0((1+1) % 14) = ring0(1) = a₀₂

…

ring0(13) = ring0((13+1) % 14) = ring0(0) = a₀₀

The logic above can be written like this:

(0 until ring0.size).map(i -> ring0((i+r) % ring0.size))

where the “map” method applies the function passed to it as an argument to each element of the collection.

If we apply the logic above to each ring of the matrix, we obtain the rotated matrix.

Implementation

Given a matrix, we have seen above that we can conceptualise it as a set of concentric rings (remember the onion metaphor). We will now write our first method, which will generate a Vector allowing to navigate the matrix as a ring of depth “r”, where depth is 0 for the outer ring.

def m2ring(matrix: Vector[Vector[Int]])(offset:Int): Vector[(Int, Int)] = {
    val m = matrix.size
    val n = matrix(0).size
    val north = (0 + offset to n - 1 - offset).map(j => (offset, j)).toVector
    val east = (1 + offset to m - 2 - offset).map(j => (j, n - 1 - offset)).toVector
    val south = (n - 1 - offset to 0 + offset by -1).map(j => (m - 1 - offset, j)).toVector
    val west = (m - 2 - offset to 1 + offset by -1).map(j => (j, offset)).toVector
    north ++ east ++ south ++ west
  }

If we invoke method m2ring passing our example matrix above, with offset = 0 (this is how the ring depth is called in the method signature), we get this output:

Vector( (0,0), (0,1), (0,2), (0,3), (0,4), (1,4), (2,4), (3,4), (3,3), (3,2), (3,1), (3,0), (2,0), (1,0) )

If we invoke m2ring(matrix)(1) we get:

Vector( (1,1), (1,2), (1,3), (2,3), (2,2), (2,1) )

Our next method will invoke m2ring for each ring depth until the entire matrix is processed (the entire onion is peeled). This method will return two data structures:

• A Vector of vectors. This vectors will have as many elements as there are rings in the matrix. For each ring, say “i”, rings(i) is the vector having as many elements as there are cells in ring “i”, each element being the (row, col) coordinates of the cell in the matrix.
• A map having key (row, col) and value (index1, index2) where:
  • (row, col) are the coordinate of a cell in the matrix
  • index1 is the index of the rings vector corresponding to the ring where cell (row, cell) belongs
  • index2 is the index of vector rings(index1) corresponding to the position of cell (row, cell)

def m2rings(matrix: Vector[Vector[Int]]) = {
    val m = matrix.size
    val n = matrix(0).size
    val g = m2ring(matrix)(_)
    val rings = (0 to Math.min(m,n)/2-1).map(i => g(i))
    val coords = (0 until rings.size).flatMap ( i => (0 until rings(i).size).map ( j => rings(i)(j) -> (i, j))).toMap
    (rings, coords)
  }

If we invoke m2rings passing our example matrix above we obtain:

rings = Vector(Vector( (0,0), (0,1), (0,2), (0,3), (0,4), (1,4), (2,4), (3,4), (3,3), (3,2), (3,1), (3,0), (2,0), (1,0) ), Vector( (1,1), (1,2), (1,3), (2,3), (2,2), (2,1) ) )

coords = Map ( (0,0) -> (0,0), (0,1) -> (0,1), (0,2) -> (0,2), (0,3) -> (0,3), (0,4) -> (0,4), (1,0) -> (0,13), (1,1) -> (1,0), (1,2) -> (1,1), (1,3) -> (1,2), (1,4) -> (0,5), (2,0) -> (0,12), (2,1) -> (1,5), (2,2) -> (1,4), (2,3) -> (1,3), (2,4) -> (0,6), (3,0) -> (0,11), (3,1) -> (0,10), (3,2) -> (0,9), (3,3) -> (0,8), (3,4) -> (0,7) )

We have now all the elements to implement the matrix rotation method:

  def perform(matrix: Vector[Vector[Int]], times: Int) = {
    val (rings, coords) = m2rings(matrix)
    def rotateMatrix(lmat: List[Vector[Int]], acc: Vector[Vector[Int]], row: Int = 0): Vector[Vector[Int]] = lmat match {
      case Nil => acc
      case r::rr =>
        val rotatedRow = (0 until r.size ).map { case col =>
                      val (rix, vix) = coords.getOrElse((row, col), (0,0))
                      val (_r, _c) = rings(rix)((vix+times) % rings(rix).size)
                      matrix(_r)(_c)
                    }.toVector

        rotateMatrix(rr, acc :+ rotatedRow, row + 1)
    }
    rotateMatrix(matrix.toList, Vector.empty, 0)
  }

The complete source code for this algorithm is available on my github space.

I hope you enjoyed this article and, up Scala!!!