Forum: Ruby Matrix Rotator (#209)

33117162fff8a9cf50544a604f60c045?d=identicon&s=25 Daniel X Moore (yahivin)
on 2009-06-12 18:56
(Received via mailing list)
Attachment: 209-test.tar.gz (461 Bytes)
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

The three rules of Ruby Quiz:

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 Quiz 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 Talk 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.
E0c987f680cd640c14912ebfbf0f0f07?d=identicon&s=25 unknown (Guest)
on 2009-06-12 20:07
(Received via mailing list)
2009/6/12 Daniel Moore <yahivin@gmail.com>:
> 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)

:-)
33117162fff8a9cf50544a604f60c045?d=identicon&s=25 Daniel X Moore (yahivin)
on 2009-06-12 20:35
(Received via mailing list)
On Fri, Jun 12, 2009 at 11:06 AM, <brabuhr@gmail.com> wrote:
> :-)
>

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!
703fbc991fd63e0e1db54dca9ea31b53?d=identicon&s=25 Robert Dober (Guest)
on 2009-06-13 01:05
(Received via mailing list)
Attachment: more-tests.tgz (513 Bytes)
On Fri, Jun 12, 2009 at 8:34 PM, Daniel Moore<yahivin@gmail.com> 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]
33117162fff8a9cf50544a604f60c045?d=identicon&s=25 Daniel X Moore (yahivin)
on 2009-06-13 01:29
(Received via mailing list)
On Fri, Jun 12, 2009 at 4:03 PM, Robert Dober<robert.dober@gmail.com>
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.
E0c987f680cd640c14912ebfbf0f0f07?d=identicon&s=25 unknown (Guest)
on 2009-06-14 18:56
(Received via mailing list)
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] ])
    )
703fbc991fd63e0e1db54dca9ea31b53?d=identicon&s=25 Robert Dober (Guest)
on 2009-06-14 19:04
(Received via mailing list)
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 ;)


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]
02f2d5a5d0610a28a9a3634640385b36?d=identicon&s=25 Sanjay Sharma (sos)
on 2009-06-14 19:35
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. :-)

http://pastie.org/511668
4536ba4e184002807cd1de1ce5ccd574?d=identicon&s=25 Lee Hinman (Guest)
on 2009-06-14 23:53
(Received via mailing list)
>>     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
289cf19aa581c445915c072bf45c5e25?d=identicon&s=25 Todd Benson (Guest)
on 2009-06-15 02:53
(Received via mailing list)
On Sun, Jun 14, 2009 at 12:04 PM, Robert Dober<robert.dober@gmail.com>
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 ;)

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

Todd
703fbc991fd63e0e1db54dca9ea31b53?d=identicon&s=25 Robert Dober (Guest)
on 2009-06-15 11:23
(Received via mailing list)
On Mon, Jun 15, 2009 at 2:52 AM, Todd Benson<caduceass@gmail.com> wrote:
> On Sun, Jun 14, 2009 at 12:04 PM, Robert Dober<robert.dober@gmail.com> 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 ;)
>
> 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 ;)
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]
0ea7f61aec8fee539be0cf39b7bab77c?d=identicon&s=25 Benoit Daloze (Guest)
on 2009-06-15 16:51
(Received via mailing list)
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 :D

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

2009/6/15, Robert Dober <robert.dober@gmail.com>:
289cf19aa581c445915c072bf45c5e25?d=identicon&s=25 Todd Benson (Guest)
on 2009-06-15 21:42
(Received via mailing list)
On Mon, Jun 15, 2009 at 4:22 AM, Robert Dober<robert.dober@gmail.com>
wrote:
> I should not have posted my bad, yet Todd you forget it is Ruby you
> should put the blame on ;)
> 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 :)

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?
990bf71a4e84e1145a3131f35656dc18?d=identicon&s=25 List Rb (listx300108u79872)
on 2009-06-16 00:31
(Received via mailing list)
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
1566d4066e11205ec3e3aaeeaf89348b?d=identicon&s=25 Luke Cowell (lcowell)
on 2009-06-16 06: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
B802d4cd5258fd7600fba49472ae3072?d=identicon&s=25 Frank Fischer (Guest)
on 2009-06-16 09:20
(Received via mailing list)
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.
33117162fff8a9cf50544a604f60c045?d=identicon&s=25 Daniel X Moore (yahivin)
on 2009-06-21 20:18
(Received via mailing list)
Attachment: 209.tar.gz (3 KB)
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[1],
testy[2], and Verify[3]. They are included in the quiz attachment.
Check them out if you are interested in alternatives to Test::Unit.
Another alternative is shoulda[4].

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!

[1]: http://rspec.info/
[2]: http://github.com/ahoward/testy/tree/master
[3]: http://www.ruby-forum.com/topic/183354
[4]: http://thoughtbot.com/projects/shoulda
Please log in before posting. Registration is free and takes only a minute.
Existing account

NEW: Do you have a Google/GoogleMail, Yahoo or Facebook account? No registration required!
Log in with Google account | Log in with Yahoo account | Log in with Facebook account
No account? Register here.