Scala Style: Matrix Rotation and Spirals .Post -5

This post is 4th in the series I am writing to make on boarding to scala a little easier. Target reader of this post is someone who has experience in some other language (like java) and finding it hard to appreciate/understand scala. I was one of them few years back.

If you are someone who is just starting to learn programming and picked up scala as her/his first language.. you can still read this article, but you may be writing better code then one you find in this page.

Continuing on our discussion on matrix, lets try to solve some more confusing problems. Rotations & Spiral. Problems like Clockwise rotate by 90 or anti-clock wise rotate by 90 etc.

Like with any other problem, first we need to findout a solution without bringing language in mind. How would we rotate a matrix. First thing comes to mind it compute the actual rotation. Rotate each layer etc. Thats one way. But there are easier way of doing it. (we will visit layered approach when we discuss spiral). Let see how matrix looks before and after rotation.

Lets try to find a pattern. Do you see it somehow related with matrix transpose ? Transpose is the matrix you get when you flip it over diagonal. For matrix above transpose will be.

Look hard on transpose now. If we reverse the rows we get the 90 degree rotated matrix.

Thats it. Thats the 90 degree clockwise rotation for you. Take transpose and reverse row. Lets see the code

taking transpose

def transpose(m: List[List[Int]]): List[List[Int]] = {
  (0 until m.head.size toList) map { c =>
    (0 until m.size toList) map { r =>
      m(r)(c)
    }
  }
}

reversing rows

def reverseRows(m: List[List[Int]]): List[List[Int]] = m.map(_.reverse)

With those two defined rotateBy90Clockwise is

def rotateBy90ClockWise(m: List[List[Int]]): List[List[Int]] = reverseRows(transpose(m))

Cant be simpler!!!

How to do it anti clockwise. Well it is reversing columns instead of rows

But wait a minute.. how to reverse a column?? We are using immutable design. Remember we dont need to replace members, we need to identify the correct element and just populate the new matrix.

def reverseCols(m: List[List[Int]]): List[List[Int]] = {
  val rows = m.size -1
  val cols = m.head.size - 1
  (0 to rows toList).map { r =>
    (0 to cols toList).map { c =>
      m(rows-r)(c)
    }
  }
}

With transpose already defined, final function is

def rotateBy90AntiClockwise(m: List[List[Int]]): List[List[Int]] = reverseCols(transpose(m))

Take a break and compare it with a java and c++ solution. I am sure you will find it less error prone and more readable.

For rotation by 180, I am not explaining the solution. I will let code talk. If you are following what is discussed till this point, I am sure you will understand it. There are 4 possible solutions.

def rotateBy180_1(m: List[List[Int]]): List[List[Int]] =swapRows(swapCols(m))
def rotateBy180_2(m: List[List[Int]]): List[List[Int]] =swapCols(swapRows(m))
def rotateBy180_3(m: List[List[Int]]): List[List[Int]] =rotateBy90ClockWise(rotateBy90ClockWise(m))
def rotateBy180_4(m: List[List[Int]]): List[List[Int]] =rotateBy90AntiClockwise(rotateBy90AntiClockwise(m))

Lets talk about Spirals now. How to print spiral? naturally going by layers. first print outer layer, then inner and so on.

Something like this

topRow ++ lastCol ++ lastRow ++ firstCol ++ 
"spiral for innerMatrix(m)"

Looks like a possibility of recursive call. But how to find inner matrix. We did it last post. So just putting code here

def innerMatrix(m: List[List[Int]]): List[List[Int]] =
  (1 until m.size-1 toList) map { r =>
    (1 until m.head.size-1 toList) map { c =>
      m(r)(c)
    }
  }

if spiral is the name of method, it will look something like this

def spiral(m: List[List[Int]]): List[Int] = {
//some code
topRow ++ lastCol ++ lastRow ++ firstCol ++ spiral(innerMatrix(m))
}

Now this Some code is nothing but.. indexes of outer matrix. have a look

def spiral(m: List[List[Int]]): List[Int] = {
  if (m.isEmpty) List.empty else {
    val rows = m.size
    val cols = m.head.size
    val topRow = m.head
    val lastCol = (1 until rows toList).map(r => m(r)(cols - 1))
    val lastRow = m.last.reverse.tail
    val firstCol = (rows - 2 to 1 by -1 toList).map(r => m(r)(0))

    topRow ++ lastCol ++ lastRow ++ firstCol ++ spiral(innerMatrix(m))
  }
}

Isn’t Recursion beautiful here?

But is it tricky to build a matrix back if you have a spiral? Not really specially if you are able to follow till this point. But code may look tricky. So lets talk. From a given spiral , its very easy to findout what is top row & what is bottom row.

topRow ++  (?????) ++ bottom row

what is missing is inner matrix and element of columns. So if we find inner matrix and add column to sides that can fill our missing piece.

Finding inner matrix can be a recursive call, just take all element from outer shell away.

val restOfSpiral = spiral drop ((2 * N) + (2 * M) - 4)val innerMatrix = matrixFromSpiral(restOfSpiral, M - 2, N - 2)

so Overall method looks like this

def matrixFromSpiral( spiral: List[Int], M: Int, N: Int): List[List[Int]] =
  if (M <= 2 || N <= 2) {
    spiral.grouped(N).toList
  } else {
    val topRowEnd = N
    val (rightColStart, rightColEnd) = (topRowEnd, topRowEnd + M - 2)
    val (bottomRowStat, bottomRowEnd) = (rightColEnd, rightColEnd + N)
    val (leftColStart, leftColEnd) = (bottomRowEnd, bottomRowEnd + M - 2)
    val restOfSpiral = spiral drop ((2 * N) + (2 * M) - 4)

    val topRow = spiral.take(topRowEnd)
    val lastColWithoutCorners = spiral.slice(rightColStart, rightColEnd)
    val lastRow = spiral.slice(bottomRowStat, bottomRowEnd).reverse
    val firstColWithoutCorners = spiral.slice(leftColStart, leftColEnd).reverse
    val innerMatrix = matrixFromSpiral(restOfSpiral, M - 2, N - 2)

    topRow :: (firstColWithoutCorners,innerMatrix,lastColWithoutCorners).zipped.map { (left, mid, right) =>
      List(left) ++ mid ++ List(right) } ::: List(lastRow)
  }

Above was a difficult problem.. and scala provides a reasonably easy solution.

I am happy to discuss it more. Leave comments.

Cheers!!