209 Matrix Rotator

Description

Здравствуйте Rubyists,

This week’s quiz is write ruby method that will rotate a matrix 90 degrees counter-clockwise (or π/2 radians).

Ex:

0 0 0 0
0 X 0 0
X X X 0
0 0 0 0

0 0 0 0
0 0 X 0
0 X X 0
0 0 X 0

I have attached the following test suite for your convenience:

require 'test/unit'
require 'solution'

class RotationTest < Test::Unit::TestCase
  def test_square_rotation
    square = [
      [0, 1, 0, 0],
      [0, 1, 1, 0],
      [0, 0, 1, 0],
      [0, 0, 0, 0]
    ]
    
    square_rotated = [
      [0, 0, 0, 0],
      [0, 1, 1, 0],
      [1, 1, 0, 0],
      [0, 0, 0, 0]
    ]
    
    assert_equal square_rotated, Matrix.rotate(square)
  end
  
  def test_rectangular_rotation
    rectangle = [
      [0, 1, 0],
      [1, 1, 1]
    ]
    
    rectangle_rotated = [
      [0, 1],
      [1, 1],
      [0, 1]
    ]
    
    assert_equal rectangle_rotated, Matrix.rotate(rectangle)
  end
end

Have Fun!

P. S. This may come in handy on a future quiz.

Summary

The goal for this week’s quiz was to rotate a two dimensional matrix counter-clockwise. I provided a simple test suite to make the process easier. Robert Dober and brabuhr straightened out my mix-up about the order of arguments for assert_equal. For the record, it’s <expected>, then <actual>.

Robert also shared three alternative test suites using RSpec, testy, and Verify. They are included in the quiz attachment. Check them out if you are interested in alternatives to Test::Unit. Another alternative is shoulda.

I find the primary advantage of testing, aside from knowing when your code is correct, is that it frees you up to refactor your code, knowing that at each step of the way you haven’t broken anything.

Now, on to the solutions submitted for this week’s quiz.

brabuhr’s solution creates and returns a new matrix by transposing the row and column index, and populating the elements in reversed order.

module Matrix
  def self.rotate(o)
    rows, cols = o.size, o[0].size
    Array.new(cols){|i| Array.new(rows){|j| o[j][cols - i - 1]}}
  end
end

The secret is knowing that a counterclockwise rotation is equivalent to transposing, then reversing the matrix.

Robert showed a simple way to accomplish this using the standard Ruby API.

matrix.transpose.reverse

list had an interesting solution: it can rotate a matrix any number of times, even a negative number. This is accomplished by using the mod operator, since four rotations would leave you back where you started.

def rotate(n=1)
  (n%4).times {self.replace(self.reverse.transpose)}
end

One note about list’s solution is that it rotates clockwise. It is interesting that changing the order in which the operations are called changes the direction that the rotation occurs in, but it makes sense because most matrix operations are non-commutative. The ‘direction’ in which the operations are performed determines the direction of the rotation.

Thank you everyone for your solutions!

Matrix Rotator (#209) - Solutions


Friday, June 12, 2009