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

# generate an odd order magic square using siamese method
def generate_odd
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