On 5/18/07, Ruby Quiz <james / grayproductions.net> wrote:
> The three rules of Ruby Quiz:
>
> 1.  Please do not post any solutions or spoiler discussion for this quiz until
> 48 hours have passed from the time on this message.

Okay, the time has come to reveal my solution publicly.  I'd already
submitted this privately to JEGII.  I solved this in a couple of
hours, then
had an idea in the shower yesterday morning which led to a simplification of
the generate_singly_even method.

The motherlode of information on the approaches I've used is to be
found on the mathworld site, the URL is in the code.

My solution solves all orders of magic squares, odd, singly-even, and
doubly even.  Here's a small command line program which takes a number
as input and pretty prints a magic square of that order:

=== ms.rb

#! /usr/local/bin/ruby
require 'magic_square'

if ARGV.size == 1

  size = ARGV.first.to_i
end
if size && size > 0 && size != 2
  puts MagicSquare.new(size)
else
  print ["ms.rb prints a magic square of order n", "",
         "Usage:", "  ms n", "", "  where n is an integer > 0 and not = 2", ""
  ].join("\n")
end

=====

And here's my test/unit testcase which tests orders from -1 to 10

=== ms_test.rb
require 'magic_square'
require 'test/unit'

class TestMagicSquare < Test::Unit::TestCase

  def test_negative_n
    assert_raise(ArgumentError) { MagicSquare.new(-1)}
  end

  def test_2
    assert_raise(ArgumentError) { MagicSquare.new(2)}
  end

  def test_to_ten
    try(1)
    for i in (3..10)
      try(i)
    end
  end

  private
  def try(n)
    m = nil
    assert_nothing_raised { m = MagicSquare.new(n)}
    assert(m.is_magic?)
  end

end

===
Here's a run of the test case
rick@frodo:/public/rubyscripts/rubyquiz/trunk/magic_square$ ruby ms_test.rb
Loaded suite ms_test
Started
...
Finished in 0.067171 seconds.

3 tests, 20 assertions, 0 failures, 0 errors

And here's the crux of the biscuit.  I used NArray to hold the 2d
array for it's speed.

=== magic_square.rb
require 'narray'
# Based on
# http://mathworld.wolfram.com/MagicSquare.html
#
# and
#
# http://en.wikipedia.org/wiki/Magic_square
#
class MagicSquare
  def initialize(n)
    raise ArgumentError.new("Invalid order #{n}") if n < 1 || n == 2
    @order = n
    @contents = NArray.int(n,n)
    case
    when n % 4 == 0
      generate_doubly_even
    when n % 2 == 0
      generate_singly_even
    else
      generate_odd
    end
  end

  def [](row,col)
    @contents[row,col]
  end

  def []=(row,col,val)
    @contents[row,col] = val
  end

  def is_magic?
    magic_constant = (order**3 + order) / 2
    each_row do |r|
      return false unless magic_constant == r.inject {|sum, e| sum + e}
    end
    each_col do |r|
      return false unless magic_constant == r.inject {|sum, e| sum + e}
    end
    each_diag do |r|
      return false unless magic_constant == r.inject {|sum, e| sum + e}
    end
    true
  end

  def each_row
    for row in (0...order)
      yield @contents[0..-1,row].to_a
    end
  end

  def each_col
    for col in (0...order)
      yield @contents[col, 0..-1].to_a
    end
  end

  def each_diag
    diag1 = []
    diag2 = []
    for i in (0...order)
      diag1 << self[i,i]
      diag2 << self[i, order-(i+1)]
    end
    yield diag1
    yield diag2
  end

  def to_s
    iw = (1 + Math.log10(order*order)).to_i
    h = "#{"+-#{'-'*iw}-"*order}+"
    fmt = " %#{iw}d |" * order
    r = [h]
    each_row do |row|
      r << "|#{fmt % row}"
    end
    r << h
    r.join("\n")
  end

  attr_reader :order

  # generate an odd order magic square using siamese method
  def generate_odd
    # start with first row, middle column
    x = order / 2
    y = 0
    total_squares = order*order
    for i in (1..total_squares)
      self[x,y]=i
      new_x = (x+1) % order
      new_y = (y-1) % order
      self[x,y]=i
      x, y = *((self[new_x, new_y] == 0) ? [new_x, new_y] : [x, (y+1) % order] )
    end
  end

  # generate magic square whose order is a multiple of 4
  def generate_doubly_even
    # First fill square sequentially
    for y in (0...order)
      for x in (0...order)
	self[x,y] = 1 + y*order + x
      end
    end
    # now replace elements on the diagonals of 4x4 subsquares
    # with the value of subtracting the intial value from n^2 + 1
    # where n is the order
    pivot = order*order + 1
    (0...order).step(4) do |x|
      (0...order).step(4) do |y|
	for i in (0..3) do
	  self[x+i, y+i] = pivot - self[x+i,y+i]
	  self[x+i, y+3-i] = pivot - self[x+i,y+3-i]
	end
      end
    end
  end

  # Generate magic square whose order is a multiple of 2 but not 4
  # using Conway's method
  def generate_singly_even
    m = (order - 2)/4
    l = [[1,0], [0,1], [1,1], [0,0]]
    u = [[0,0], [0,1], [1,1], [1, 0]]
    x = [[0,0], [1,1], [0,1], [1, 0]]
    # the mathworld article uses the expression
    # 2m + 1 for the generator magic square
    # but it can be easily shown that this is equal
    # to order/2 which makes the code more understandable
    pat_order = order/2
    prototype = self.class.new(pat_order)
    for p_row in (0...pat_order)
      for p_col in (0...pat_order)
	deltas =
	  case
	  when p_row < m
	    l
	  when p_row == m
	    p_col == m ? u : l
	  when p_row == m + 1
	    p_col == m ? l : u
	  else
	    x
	  end
	base = 1 + (prototype[p_col,p_row] - 1) * 4
	deltas.each_with_index do |dxdy, i|
	  dx, dy = *dxdy
	  self[p_col*2 + dx, p_row*2 + dy] = base + i
	end
      end
    end
  end
end



---
Rick DeNatale

My blog on Ruby
http://talklikeaduck.denhaven2.com/