0
\$\begingroup\$

Given a matrix, clockwise rotate elements in it. Examples:

Input
1    2    3
4    5    6
7    8    9

Output:
4    1    2
7    5    3
8    9    6


Input:
1    2    3    4    
5    6    7    8
9    10   11   12
13   14   15   16

Output:
5    1    2    3
9    10   6    4
13   11   7    8
14   15   16   12

Scala Implementation is below. I do feel that I do not need to have a rotatedMatrix predefined (which I am filling with -1) and I can build it up during my recursive calls, but I am not able to do it. Thanks in advance for helping me on this.

import scala.util.Random

object MatrixRotate extends App {

  def getCol(c: Int, m: Array[Array[Int]]): Seq[Int] = (0 to (m(0).length - 1)) map ( r => m(r)(c))
  def getRow(r: Int, m: Array[Array[Int]]): Seq[Int] = m(r).toSeq
  def innerMatrix(m: Array[Array[Int]]): Array[Array[Int]] = {
    if (m.length == 0) Array.empty
    else {
      val rows = m.length - 1
      val cols = m(0).length - 1

      (1 until rows).map { r =>
        (1 until cols).map { c =>
          m(r)(c)
        }.toArray
      }.toArray
    }
  }

  val rotatedMatrix = Array.fill(6)(Array.fill(6)(-1))
  def rotateByOne(m: Array[Array[Int]], startRow: Int, startCol: Int,
                  endRow: Int, endCol: Int): Unit = {
    m.size match {
      case 0 =>
      case _ =>
        getRow(0, m) match {
          case Nil =>
          case x => x.init.zipWithIndex foreach { case (e, index) => rotatedMatrix(startRow)(startCol+index+1) = e }
        }
        getCol(m(0).length - 1, m) match {
          case Nil =>
          case x => x.init.zipWithIndex foreach { case (e, index) =>  rotatedMatrix(startRow+index+1)(endCol) = e }
        }
        getRow(m.length - 1, m) match {
          case x :: Nil =>
          case x => x.tail.zipWithIndex foreach { case (e, index) => rotatedMatrix(endRow)(startCol+index) = e }
        }
        getCol(0, m) match {
          case x :: Nil =>
          case x => x.tail.zipWithIndex foreach { case (e, index) => rotatedMatrix(startRow+index)(startCol) = e }
        }
        rotateByOne(innerMatrix(m), startRow + 1, startCol + 1, endRow - 1, endCol - 1)
    }

  }


  val matrix = Array.fill(6)(Array.fill(6)(Random.nextInt(100)))
  matrix foreach(row => println(row.mkString(",")))

  println("----------")

  rotateByOne(matrix, 0, 0, 5, 5)
  rotatedMatrix foreach (row => println(row.mkString(",")))
}

Update

I realize that this code seems to be failing for rectangular matrix. I still need to solve it for that case.

\$\endgroup\$
2
\$\begingroup\$

Functional programming

Since you've tagged this post with functional-programming I guess that the goal of this exercise may have been to practice functional programming or to present you skills in functional programming. This way or another, I'll stick to the assumption that it was supposed to be written in the functional programming paradigm.

When working with functional code, a function returning a Unit is a huge warning sign. In functional programming we compose programs of functions which are (quoting John De Goes):

  1. Total: They return an output for every input.
  2. Deterministic: They return the same output for the same input.
  3. Pure: Their only effect is computing the output.

In FP, if a function returns a Unit, it basically means that the function does nothing, as the only thing a function can do is to return a result.

rotatedMatrix

In FP preallocating the rotatedMatrix doesn't make sens, because in order to stay Pure rotateByOne is disallowed to mutate the rotatedMatrix. And the solution is simple, the rotateByOne should allocate and return a rotated matrix.

rotateByOne

While moving the allocation of rotatedMatrix into the rotateByOne would make rotateByOne a pure function, the implementation of the function would still be clattered with state mutations, and generally much more complex than it needs to be.

So let's have a look at how it can be improved.

Edge-case/error handling aside, I would expect the problem to be solved with a def rotateByOne(in: Array[Array[Int]]): Array[Array[Int]]. That function would have to create a new matrix of the same dimensions, finding a new value of each cell in the matrix. It's implementation could look like

  def rotateByOne(in: Array[Array[Int]]): Array[Array[Int]] = {
    val size = in.length
    (0 until size).map { i =>
      (0 until size).map { j =>
        newValueAt(in, i, j)
      }.toArray
    }.toArray
  }

Now all that's left is to implement the def newValueAt(in: Array[Array[Int]], i: Int, j: Int): Int which is again - a pure function - doing nothing but returning an Int. There are 5 cases to be considered, in newValueAt. Using the value of the cell: below, above, on the right, on the left, and the same cell.

For 3 x 3 matrix it's:

b l l
b s a
r r a

For 4 x 4 matrix it's:

b l l l
b b l a
b r a a
r r r a

After a few minutes of trial and error, I've ended up with the following implementation:

  def newValueAt(in: Array[Array[Int]], i: Int, j: Int): Int = {
    val s = in.size - 1
    if      (i >= j && s - i >  j) in(i + 1)(j) // 'b'
    else if (i <  j && s - i >= j) in(i)(j - 1) // 'l'
    else if (i <= j && s - i <  j) in(i - 1)(j) // 'a'
    else if (i >  j && s - i <= j) in(i)(j + 1) // 'r'
    else                           in(i)(j)     // 's'
  }
\$\endgroup\$
  • \$\begingroup\$ Thanks for explaining it so well. rotateByOne not returning new matrix was troubling me as well (as I observed in my question), but I was not for the right reasons. Your guidelines will help me in thinking it right way. I do think that identifying new value for each position is a difficult approach for this problem and the current solution handles it in a different way (with recursion). Approach is inspired by this answer codereview.stackexchange.com/a/210390/37522 . \$\endgroup\$ – vikrant Dec 28 '18 at 20:03

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.