Thursday 25 February 2016

Algorithm to rotate a matrix using transpose

This is a horrible question but there is a neat trick.

To rotate 90 degrees just take transpose then reverse the rows. To rotate -90 (270) degrees take the transpose then reverse the columns.

val matrix = Array(Array(1,2), Array(3,4), Array(5,6))
print(matrix)

1 2
3 4
5 6

Transpose

def transpose(matrix: Array[Array[Int]]): Array[Array[Int]] = {
  matrix.head.indices.map(i => matrix.map(_(i))).toArray
}

print(transpose(matrix))

1 3 5
2 4 6

Rotate 90 degrees clockwise 


Transpose and reverse rows:

def rotate90(matrix: Array[Array[Int]]): Array[Array[Int]] = {
  transpose(matrix).map(_.reverse)
}
print(rotate90(matrix))

5 3 1
6 4 2

Voila.

Rotate 90 degrees anticlockwise


Transpose and reverse columns:

def rotateMinus90(matrix: Array[Array[Int]]): Array[Array[Int]] = {
  val t = transpose(matrix)
  t.head.indices.foreach { i =>
    (0 until (t.length/2)).foreach { j =>
      val temp = t(j)(i)
      t(j)(i) = t(t.length - j - 1)(i)
      t(t.length - j - 1)(i) = temp
    }
  }
  t
}
print(rotateMinus90(matrix))

2 4 6
1 3 5

Full code:


No comments:

Post a Comment

Scala with Cats: Answers to revision questions

I'm studying the 'Scala with Cats' book. I want the information to stick so I am applying a technique from 'Ultralearning&#...