Matrix Rotator (#209)

Ruby
1

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

The three rules of Ruby Q.:

  1. Please do not post any solutions or spoiler discussion for this
    quiz until 48 hours have elapsed from the time this message was
    sent.

  2. Support Ruby Q. by submitting ideas and responses
    as often as you can!
    Visit: http://rubyquiz.strd6.com/suggestions

  3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem
helps everyone on Ruby T. follow the discussion. Please reply to
the original quiz message, if you can.

RSS Feed: http://rubyquiz.strd6.com/quizzes.rss

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

Matrix Rotator (#209)

Здравствуйте 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 Matrix.rotate(square), square_rotated
  end

  def test_rectangular_rotation
    rectangle = [
      [0, 1, 0],
      [1, 1, 1]
    ]

    rectangle_rotated = [
      [0, 1],
      [1, 1],
      [0, 1]
    ]

    assert_equal Matrix.rotate(rectangle), rectangle_rotated
  end
end

Have Fun!

–
-Daniel
http://rubyquiz.strd6.com

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

2

2009/6/12 Daniel M. [email protected]:

I have attached the following test suite for your convenience:
assert_equal Matrix.rotate(square), square_rotated
assert_equal Matrix.rotate(rectangle), rectangle_rotated

Shouldn’t that be?:

assert_equal square_rotated, Matrix.rotate(square)
assert_equal rectangle_rotated, Matrix.rotate(rectangle)

:slight_smile:

3

On Fri, Jun 12, 2009 at 11:06 AM, [email protected] wrote:

:slight_smile:

That’s what I thought at first, and how I originally had it, but the
docs on TestUnit specify:

assert_equal(expected, actual, message=nil)

In this situation square_rotated is the expected result and
Matrix.rotate(square) is the actual result that the quiz solution
generates.

Thanks for bringing this up, each testing framework has its own order
conventions as well, I know QUnit has actual first and expected
second.

Have fun on the quiz!

4

On Fri, Jun 12, 2009 at 4:03 PM, Robert D.[email protected]
wrote:

assert_equal rectangle_rotated, Matrix.rotate(rectangle)
But as all my tests pass it does not matter ;).

This somehow coincides with the specs I have attached, with Daniel’s
kind permission. It is interesting to
notice how each of the three test tools avoids that kind of confusion
in three different ways.

Cheers
Robert

Brahbur and Robert are right on the order of the test arguments, my
mistake.

5

On Fri, Jun 12, 2009 at 8:34 PM, Daniel M.[email protected] wrote:

generates.
Wait a second, maybe I am completely confused, but that is exactly
what brabuhr said no?,…
But as all my tests pass it does not matter ;).

This somehow coincides with the specs I have attached, with Daniel’s
kind permission. It is interesting to
notice how each of the three test tools avoids that kind of confusion
in three different ways.

Cheers
Robert

–
Toutes les grandes personnes ont d’abord été des enfants, mais peu
d’entre elles s’en souviennent.

All adults have been children first, but not many remember.

[Antoine de Saint-Exupéry]

6

Hope this isn’t too early, but I may be offline for a couple of days,
so I’m posting my method now:

Matrix Rotator (#209)

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 0 0 0
0 X 0 0 0 0 X 0
X X X 0 0 X X 0
0 0 0 0 0 0 X 0

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

3 tests, 5 assertions, 0 failures, 0 errors:
assert_equal square_rotated, Matrix.rotate(square)
assert_equal rectangle_rotated, Matrix.rotate(rectangle)
assert_equal( [[5], [4], [3], [2], [1]],
Matrix.rotate([(1…5).to_a]) )
assert_equal( [[1, 2, 3, 4, 5]], Matrix.rotate((1…5).to_a.map{|n|
[n]}) )
assert_equal(
[ [1, 2, 3, 4, 5],
[6, 7, 8, 9, 0] ],
Matrix.rotate([ [6, 1], [7, 2], [8, 3], [9, 4], [0, 5] ])
)

7

Spoiler
My solution does not mean that I am clever, it only means that Ruby
has such an incredible API
Maybe you should try yourself before looking at my solution :wink:

http://pastie.org/511643

Toutes les grandes personnes ont d’abord été des enfants, mais peu
d’entre elles s’en souviennent.

All adults have been children first, but not many remember.

[Antoine de Saint-Exupéry]

8

Daniel X Moore wrote:

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

Matrix Rotator (#209)

Здравствуйте 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

–
-Daniel
http://rubyquiz.strd6.com

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

Here’s my solution; not too savvy but I guess kinda OK given that I’ve
recently started with Ruby. :slight_smile:

http://pastie.org/511668

9 
0 X 0 0

-Daniel
http://rubyquiz.strd6.com

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

Here’s my (different) solution, rather manual this way.
http://pastie.org/511889

  • Lee
10

On Sun, Jun 14, 2009 at 12:04 PM, Robert D.[email protected]
wrote:

Spoiler
My solution does not mean that I am clever, it only means that Ruby
has such an incredible API
Maybe you should try yourself before looking at my solution :wink:

Robert, shame on you. You just allowed us all to write a program for
efficiently solving Rubik’s Revenge (4x4).

Todd

11

On Mon, Jun 15, 2009 at 2:52 AM, Todd B.[email protected] wrote:

On Sun, Jun 14, 2009 at 12:04 PM, Robert D.[email protected] wrote:

Spoiler
My solution does not mean that I am clever, it only means that Ruby
has such an incredible API
Maybe you should try yourself before looking at my solution :wink:

Robert, shame on you. You just allowed us all to write a program for
efficiently solving Rubik’s Revenge (4x4).
I should not have posted my bad, yet Todd you forget it is Ruby you
should put the blame on :wink:
But I guess it is not that simple anyway, puuuh.
R.

–
Toutes les grandes personnes ont d’abord été des enfants, mais peu
d’entre elles s’en souviennent.

All adults have been children first, but not many remember.

[Antoine de Saint-Exupéry]

12

Well, I just think the easier way while not using Matrix Class is:
http://pastie.org/512561
It just transpose by the definition(i,j->j,i) and reverse :smiley:

I don’t know why I searched also to do with inject, but it seems to be
non-sense.

2009/6/15, Robert D. [email protected]:

13

On Mon, Jun 15, 2009 at 4:22 AM, Robert D.[email protected]
wrote:

I should not have posted my bad, yet Todd you forget it is Ruby you
should put the blame on :wink:
But I guess it is not that simple anyway, puuuh.
R.

I don’t want to hijack the thread, but since my venting is off topic,
it will probably get lost in the noise anyhow. Solving a cube (of any
number of pieces) is mostly working backwards from a solved state. A
good transformation algorithm is handy. Maybe that should be another
quiz :slight_smile:

I tried a mathematical transformation for this quiz so that it could
be useful for something other than a quarter turn. Didn’t work. For
those more inclined to “make it so”, it’s an inverse matrix in front
of a position matrix. What’s funny about the extra dimension required
fascinates me. I get the math, but why do we need singularity (a
bunch of 1’s) on that final dimension?

14

My solution:

def self.rotate(rect)
rotated = []
rect.each_with_index do |row, irow|
row.reverse.each_with_index do |col, icol|
rotated[icol] ||= []
rotated[icol][irow] = col
end
end
rotated
end

It works by reversing the elements in the row and then swapping elements
in the x & y axis.

Luke

15

Here’s my solution:

class Matrix
def self.rotate( mat )
mat = mat.map{|r| r.reverse}
mat.first.zip(*mat[1…-1])
end
end

Again, it works by reversing the elements in each row and transposing
the
matrix.

16

I just happened to have done this in a side project I was working on…
Here’s my rotate method. It accepts negative and positive numbers…

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

Which supports grid.rotate(-2) for left twice, or 1 for right… or
whatever really…

Here’s the Grid class:

#!/usr/bin/env ruby -W0
SAMPLE_DATA = %w[
0 0 7 0 5 0 0 0 0
0 0 0 0 6 4 0 0 1
4 0 0 0 0 0 2 0 9
0 8 9 0 0 0 4 0 3
6 0 3 0 0 4 0 9 0
0 0 2 4 0 0 8 0 6
0 0 0 9 1 0 6 0 0
0 0 0 0 0 0 0 0 0
2 0 4 0 0 0 0 0 0
].collect {|i| i.to_i}

class Array
def /len
a = []
self.each_with_index do |x,i|
a << [] if i % len == 0
a.last << x
end
a
end
end

class Grid < Array
attr_accessor :set
def initialize(set=SAMPLE_DATA)
@set = set
self.replace(set/Math.sqrt(set.size))
end

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

def flip(direction=:right)
case direction
when :right then self.replace(self.transpose.rotate(1))
when :left then self.replace(self.transpose.rotate(-1))
end
end

def children ## returns array of new Grids(3x3), ordered from left to
right
return self.collect {|i| i/3}.transpose.collect {|i|
i/3}.transpose.collect {|i| i.collect {|j| Grid.new(j.flatten.compact)}}
end

def sum
Array.new(self.flatten.compact).sum
end

def columns
self.transpose
end

def rows
self
end

def inspect
self.to_s
end

def to_s
“\n” + self.collect {|i| i.inspect}.join("\n")
end

end

grid = Grid.new
grid.rotate(1) #right cw 90deg
p grid
grid.rotate(-2) #left ccw 180deg
p grid

17

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 D. and brabuhr straightened out my mix-up about the
order of arguments for assert_equal. For the record, it’s
, then .

Robert also shared three alternative test suites using RSpec1,
testy2, and Verify3. They are included in the quiz attachment.
Check them out if you are interested in alternatives to Test::Unit.
Another alternative is shoulda4.

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!