From: James Edward Gray II <james@...>
Date: 2007-05-21T00:11:48+09:00
Subject: Fwd: Please Forward: Ruby Quiz Submission

--Apple-Mail-1--496755143
Content-Transfer-Encoding: 7bit
Content-Type: text/plain;
	charset=US-ASCII;
	format=flowed

Begin forwarded message:

> From: Hirotsugu Asari <asari@mac.com>
> Date: May 19, 2007 6:57:27 PM CDT
> To: submission@rubyquiz.com
> Subject: Please Forward: Ruby Quiz Submission
>
> Here's my solution and the tests.
>

--Apple-Mail-1--496755143
Content-Transfer-Encoding: 7bit
Content-Type: text/x-ruby-script;
	x-unix-mode=0644;
	x-mac-creator=54784D74;
	name=magic_square.rb
Content-Disposition: attachment;
	filename=magic_square.rb

#!/usr/bin/env ruby -wKU

# Ruby Quiz #124
# Magic Square -- build an NxN magic square

require 'matrix'

class Matrix
  def magic?
    return false if ! self.square?
    
    size = self.row_size
    
    # compute the sum of each row, each column and the diagonals
    magic_sum = (1..size**2).inject{ |s,i| s += i } / size

    begin
      # checks rows and columns
      self.row_vectors.each { |v|
        if v.to_a.inject { |s,i| s += i } != magic_sum
          raise RuntimeError, "row #{v} doesn't add up to #{magic_sum}"
        end
      }
      self.column_vectors.each { |v|
        if v.to_a.inject { |s,i| s += i } != magic_sum
          raise RuntimeError, "column #{v} doesn't add up to #{magic_sum}"
        end
      }

      # check diagonals
      if (0..size-1).inject(0) {|s,i| s += self[i,i] } != magic_sum
        raise RuntimeError, "the main diagonal doesn't add up to #{magic_sum}"
      end

      # finally.... check the other main diagonal
      if (0..size-1).inject(0) {|s,i| s += self[i, -1-i] } != magic_sum
        raise RuntimeError, "the other diagonal doesn't add up to #{magic_sum}"
      end
      
    rescue
      return false
    end
    
    # it passed all checks
    return true

  end
  
  def to_s_pretty
    if ! self.square?
      return self.to_s
    end
    array      = self.to_a
    max_length = array.flatten.sort.last.to_s.length # the length of the largest number to fit in
    s          = ""
    
    until array.empty? do
      row = array.shift
      s  += "+" + "-" * ((max_length+2)*row.length + row.length-1) + "+\n"
      s  += "| " + row.map{ |i| i.to_s.rjust(max_length) }.join(" | ") + " |\n"
    end
    s += "+" + "-" * ((max_length+2)*row.length + row.length-1) + "+"
    
  end
  
  # See <http://mathworld.wolfram.com/MagicSquare.html>
  def Matrix.new_magic_square(n=3)
    n = n.to_i
    if n == 2
      raise ArgumentError, "2x2 magic square does not exist"
    elsif n < 1
      raise ArgumentError, "Cannot create a magic square of size #{n}"
    end
    
    if n % 2 != 0
      return Matrix.new_odd_magic_square(n)
    elsif n % 4 == 0
      return Matrix.new_doubly_even_magic_square(n)
    else
      return Matrix.new_singly_even_magic_square(n)
    end
  end
  
  private
  def Matrix.new_odd_magic_square(n)
    if ! n.integer? || n%2 != 1
      raise RuntimeError, "Internal error on line #{__LINE__}"
    end    
    # generate the NxN magic square by the Siamese method
    a = []
    0.upto(n-1) { |i|
      a[i]=[]
    }

    m = (n-1)/2
    # put 1 in a[0][m], then 2 goes to a[-1][m+1], 3 to a[-2][m+2], ...
    x=0
    y=m
    1.upto(n**2) { |i|
      if (a[x][y]).nil?
        a[x][y] = i
      else
        # this cell is already filled, so we move to the cell below; we had
        # already moved to the upper right cell, so we must offset that move, too
        x += 2
        y -= 1
        a[x%n][y%n] = i
      end
      x = (x-1)%n # move up
      y = (y+1)%n # then right
    }
    
    Matrix.rows(a)
    
  end
  
  def Matrix.new_doubly_even_magic_square(n)
    if ! n.integer? || n%4 != 0
      raise RuntimeError, "Internal error on line #{__LINE__}"
    end    
    
    # first fill the cells in order
    a=[]
    1.upto(n) do |i|
      first = (i-1)*n+1 # first element
      a << (first..(first+n-1)).to_a
    end
    # then replace the entries
    0.upto(n-1) do |i|
      0.upto(n-1) do |j|
        if (i-j)%4 == 0 || (i+j)%4 == 3
          a[i][j] = n**2+1-a[i][j]
        end
      end
    end
    Matrix.rows(a)
  end
  
  def Matrix.new_singly_even_magic_square(n)
    if ! n.integer? || n%4 != 2
      raise RuntimeError, "Internal error on line #{__LINE__}"
    end    
    
    # first generate the magic square of size n/2
    m = (n-2)/4
    matrix = Matrix.new_odd_magic_square(2*m+1).to_a
    
    lux=[] # identifier for "L,U,X" for each 4x4 squares
    # m+1 rows of L's
    1.upto(m+1) do |i|
      lux << (1..(2*m+1)).to_a.map{"L"}
    end
    # 1 row of U's
    lux << (1..(2*m+1)).to_a.map{"U"}
    # m-1 rows of X's
    1.upto(m-1) do |i|
      lux << (1..(2*m+1)).to_a.map{"X"}
    end
    # swap an L and a U as required by the method
    lux[m][m]="U"
    lux[m+1][m]="L"
    
    # finally, fill up the cells
    a = []
    0.upto(n-1) do |i|
      a[i]=[]
      0.upto(n-1) do |j|
        k = i/2
        l = j/2
        case
        when lux[k][l] == "L"
          # 4 1
          # 2 3
          if i%2 == 0
            if j%2 == 0
              a[i][j]=(matrix[k][l]-1)*4+4
            else
              a[i][j]=(matrix[k][l]-1)*4+1
            end
          else
            if j%2 == 0
              a[i][j]=(matrix[k][l]-1)*4+2
            else
              a[i][j]=(matrix[k][l]-1)*4+3
            end
          end # end of case "L"
        when lux[k][l] == "U"
          # 1 4
          # 2 3
          if i%2 == 0
            if j%2 == 0
              a[i][j]=(matrix[k][l]-1)*4+1
            else
              a[i][j]=(matrix[k][l]-1)*4+4
            end
          else
            if j%2 == 0
              a[i][j]=(matrix[k][l]-1)*4+2
            else
              a[i][j]=(matrix[k][l]-1)*4+3
            end
          end # end of case "U"
        when lux[k][l] == "X"
          # 1 4
          # 3 2
          if i%2 == 0
            if j%2 == 0
              a[i][j]=(matrix[k][l]-1)*4+1
            else
              a[i][j]=(matrix[k][l]-1)*4+4
            end
          else
            if j%2 == 0
              a[i][j]=(matrix[k][l]-1)*4+3
            else
              a[i][j]=(matrix[k][l]-1)*4+2
            end
          end # end of case "X"
        else
          raise RuntimeError, "Internal error on line #{__LINE__}"
        end
      end
    end
    
    return Matrix.rows(a)
  end
  
end
--Apple-Mail-1--496755143
Content-Transfer-Encoding: 7bit
Content-Type: text/x-ruby-script;
	x-unix-mode=0644;
	x-mac-creator=54784D74;
	name=124_test.rb
Content-Disposition: attachment;
	filename=124_test.rb

#!/usr/bin/env ruby -wKU

require "test/unit"
require "magic_square.rb"

class MagicSquareTest < Test::Unit::TestCase
  def test_magicness
    
    # here's a magic square of size 5
    m = Matrix[
      [15, 8, 1,24,17],
      [16,14, 7, 5,23],
      [22,20,13, 6, 4],
      [ 3,21,19,12,10],
      [ 9, 2,25,18,11]
    ]
    assert m.magic?

    # here's another
    m = Matrix[
      [19,21, 3,10,12],
      [25, 2, 9,11,18],
      [ 1, 8,15,17,24],
      [ 7,14,16,23, 5],
      [13,20,22, 4, 6]
    ]
    assert m.magic?
    
    # one of size 9
    m = Matrix[
      [45,34,23,12, 1,80,69,58,47],
      [46,44,33,22,11, 9,79,68,57],
      [56,54,43,32,21,10, 8,78,67],
      [66,55,53,42,31,20,18, 7,77],
      [76,65,63,52,41,30,19,17, 6],
      [ 5,75,64,62,51,40,29,27,16],
      [15, 4,74,72,61,50,39,28,26],
      [25,14, 3,73,71,60,49,38,36],
      [35,24,13, 2,81,70,59,48,37]
    ]
    assert m.magic?
    
  end
  
  def test_exceptions
    assert_raise ArgumentError do 
      m = Matrix.new_magic_square(2)
    end
    
    assert_raise ArgumentError do
      m = Matrix.new_magic_square(-1)
    end
  end
  
  def test_generator
    assert_equal Matrix.new_magic_square(1), Matrix[[1]]
    
    3.upto(100) do |n|
      s = Process.times
      m = Matrix.new_magic_square(n)
      t = Process.times
      # puts sprintf("size: %10d generated in utime: %8.2f\tstime: %8.2f", n, t.utime-s.utime, t.stime-s.stime)
      assert m.magic?
      u = Process.times
      # puts sprintf("size: %10d tested in utime: %8.2f\tstime: %8.2f", n, u.utime-t.utime, u.stime-t.stime)
    end
  end
end
--Apple-Mail-1--496755143
Content-Transfer-Encoding: 7bit
Content-Type: text/plain;
	charset=US-ASCII;
	delsp=yes;
	format=flowed

>
> I consulted http://mathworld.wolfram.com/MagicSquare.html for the  
> methods to generate the magic squares.
>
> Timing on my C2D MacBook Pro seems good.
>
> $ cat run_magic_square.rb
> require 'magic_square'
>
> puts Matrix.new_magic_square(ARGV[0]).to_s_pretty
>
> $ time ruby run_magic_square.rb 9
> +--------------------------------------------+
> | 47 | 58 | 69 | 80 |  1 | 12 | 23 | 34 | 45 |
> +--------------------------------------------+
> | 57 | 68 | 79 |  9 | 11 | 22 | 33 | 44 | 46 |
> +--------------------------------------------+
> | 67 | 78 |  8 | 10 | 21 | 32 | 43 | 54 | 56 |
> +--------------------------------------------+
> | 77 |  7 | 18 | 20 | 31 | 42 | 53 | 55 | 66 |
> +--------------------------------------------+
> |  6 | 17 | 19 | 30 | 41 | 52 | 63 | 65 | 76 |
> +--------------------------------------------+
> | 16 | 27 | 29 | 40 | 51 | 62 | 64 | 75 |  5 |
> +--------------------------------------------+
> | 26 | 28 | 39 | 50 | 61 | 72 | 74 |  4 | 15 |
> +--------------------------------------------+
> | 36 | 38 | 49 | 60 | 71 | 73 |  3 | 14 | 25 |
> +--------------------------------------------+
> | 37 | 48 | 59 | 70 | 81 |  2 | 13 | 24 | 35 |
> +--------------------------------------------+
>
> real    0m0.017s
> user    0m0.010s
> sys     0m0.007s
>
> $ for i in 298 300; do
> > time ruby run_magic_square.rb $i > /dev/null
> > done
>
> real    0m1.513s
> user    0m1.006s
> sys     0m0.505s
>
> real    0m1.344s
> user    0m0.836s
> sys     0m0.506s


--Apple-Mail-1--496755143--