Magic Squares (#124)


#1

The three rules of Ruby Q.:

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

  2. Support Ruby Q. by submitting ideas as often as you can:

http://www.rubyquiz.com/

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

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

A magic square of size N is a square with the numbers from 1 to N ** 2
arranged
so that each row, column, and the two long diagonals have the same sum.
For
example, a magic square for N = 5 could be:

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

In this case the magic sum is 65. All rows, columns, and both diagonals
add up
to that.

This week’s Ruby Q. is to write a program that builds magic squares.
To keep
the problem easy, I will say that your program only needs to work for
odd values
of N. Try to keep your runtimes pretty reasonable even for the bigger
values of
N:

$ time ruby magic_square.rb 9
±-------------------------------------------+
| 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 |
±-------------------------------------------+

real 0m0.012s
user 0m0.006s
sys 0m0.006s

For extra credit, support even values of N. You don’t need to worry
about N = 2
though as it is impossible.


#2

Here’s my solution. It only works for odd-sized squares at the moment,
maybe I’ll get ambitious later and go for the extra credit.

file: magic_square.rb

author: Drew O.

class MagicSquare

access to the raw square (not used here, maybe used by others?)

attr_reader :square

check that size is odd, then store size and build our square

def initialize size
raise “Size must be odd” unless size%2 == 1
@size = size
build_square size
self
end

scary looking method for pretty printing

def to_s
# find the largest number of digits in the numbers we
# are printing
digits = max_digits @size**2

# create the row divider. flexible based on size of numbers
# and the square.
divider = "+"+("-"*(@size*(3+digits)-1))+"+\n"

# build each row by formatting the numbers to the max
# digits needed and adding pipe dividers
(0...@size).inject(divider) do |output,i|
  output + "| " +
    @square[i].map{|x| "%#{digits}d" % x}.join(" | ") +
    " |\n" + divider
end

end

private

get the highest digit count up to size

def max_digits size
(1…size).map{|x| x.to_s.size}.max
end

initialize our 2d array (probably slicker ways to do this)

def init_array size
(0…size).inject(Array.new) do |arr,i|
arr[i] = []
arr
end
end

build square based on the algorithm from wikipedia.

start in the middle of the first row, move up and right.

if new space is occupied, move down one space and continue.

def build_square size
#starting positions
x,y = size/2,0

# build square
@square = (1..size**2).inject(init_array(size)) do |arr,i|

  # store current number in square
  arr[y][x] = i

  # move up and left
  x = (x+1)%size
  y = (y-1)%size

  # undo move and move down if space is taken
  if arr[y][x]
    y = (y+2)%size
    x = (x-1)%size
  end
  arr
end

end
end

build and print out square

if FILE == $0
puts MagicSquare.new(ARGV[0].to_i)
end


#3

On May 18, 2007, at 10:22 AM, Drew O. wrote:

Here’s my solution. It only works for odd-sized squares at the moment,
maybe I’ll get ambitious later and go for the extra credit.

Drew:

Ruby Q. has a “no spoiler period” rule. We request that users do
not share and spoiler material for the first 48 hours after a quiz is
released. This rule is at the top of every quiz. No big deal, but
please keep that in mind for the future.

James Edward G. II


#4

James G. wrote:

On May 18, 2007, at 10:22 AM, Drew O. wrote:

Here’s my solution. It only works for odd-sized squares at the moment,
maybe I’ll get ambitious later and go for the extra credit.

Drew:

Ruby Q. has a “no spoiler period” rule. We request that users do
not share and spoiler material for the first 48 hours after a quiz is
released. This rule is at the top of every quiz. No big deal, but
please keep that in mind for the future.

James Edward G. II

Doh! So sorry, totally spaced out on this one. My fault, won’t happen
again.


#5

On 5/18/07, Ruby Q. removed_email_address@domain.invalid wrote:

This week’s Ruby Q. is to write a program that builds magic squares. To keep
the problem easy, I will say that your program only needs to work for odd values
of N. Try to keep your runtimes pretty reasonable even for the bigger values of
N:

Here is my solution.

It is based on the steps at Wikipedia.

http://en.wikipedia.org/wiki/Magic_square#A_method_for_constructing_a_magic_square_of_odd_order

I input the 1 in the middle of the first array (tot[0][mid]).

Then I moved the arrays into position so I could always input using

the same index (tot[0][mid]).

Code Start

num = ARGV[0].to_i
if num % 2 != 0 and num > 0
mid = ((num + 1) / 2) - 1
tot = []
num.times {tot.push(Array.new(num))}
tot[0][mid] = 1.to_s.rjust((num**2).to_s.length)

(2…num**2).each do |x|
tot.unshift(tot.pop)
tot.each {|g| g.push(g.shift)}

if tot[0][mid] != nil # Square is already filled ?
2.times {tot.push(tot.shift)}
tot.each {|g| g.unshift(g.pop)}
tot[0][mid] = x.to_s.rjust((num**2).to_s.length)
end

tot[0][mid] = x.to_s.rjust((num**2).to_s.length) if tot[0][mid] == 

nil
end

tot.push(tot.shift)
tot.each {|x| p x.join(" ")}
end

Harry

A Look into Japanese Ruby List in English
http://www.kakueki.com/


#6

|Robert D.|

RD> BTW is there a book to be published one day about Ruby Q.?
It is
http://pragmaticprogrammer.com/titles/fr_quiz/index.html

Or you meant second book?


#7

Hi

here goes my solution for Ruby Q. #124.
This was quite tough, firstly to find the algorithms and secondly to
write concise code that still runs not too slowly.
I have therefore adapted my original solution (which runs 30% faster
and still is attached to this mail) to something more “readable”, well
it is up to you to judge that :).

I know this is not DRY, but politeness cannot be ;). Ty again for the
great effort Ruby Q. is.
BTW is there a book to be published one day about Ruby Q.?

Cheers
Robert

Usage = <<-EOS
usage:
ruby #{$0} [-t|–test] [-h|–html]

  Prints Magic Squares for all indicated orders.
  Indicating -t also tests the results.

EOS
loop do
case ARGV.first
when “-t”, “–test”
require ‘test-squares’
ARGV.shift
when “-h”, “–html”
require ‘html-output’
ARGV.shift
when “-?”, “–help”, nil
puts Usage
exit
when “–”
ARGV.shift && break
else
break
end
end

class Array
def lpos; first end
def cpos; self[1] end
end

This is a default output module, another output

module called HTMLOutput is provided as an example

how to pull in an appropriate Output module

as plugin.

module Output
def to_s decoration = false
l = (@order*@order).to_s.size
return @data.map{ |line|
line.map{ |cell|
“%#{l}d” % cell
}.join(" “)
}.join(”\n") unless decoration

sep_line = "+" << ( "-" * l.succ.succ << "+" ) * @order
sep_line.dup << "\n" <<
@data.map{ | line | "| " << line.map{ |cell| "%#{l}d" % cell

}.join(" | “) << " |” }.
zip( [sep_line] * @order ).flatten.join("\n")
end
end

The usage of cursors is slowing down the program a little

bit but I feel it is still fast enough.

class Cursor
attr_reader :cpos, :lpos
def initialize order, lpos, cpos
@order = order
@lpos = lpos
@cpos = cpos
end

def move ldelta, cdelta
l = @lpos + ldelta
c = @cpos + cdelta
l %= @order
c %= @order
self.class.new @order, l, c
end
def next!
s = dup
@cpos += 1
return s if @cpos < @order
@cpos = 0
@lpos += 1
@lpos %= @order
s
end
end

This is where the work is done, like

testing and outputting and what was it?

Ah yes storing the data.

class SquareData
include Output
include HTMLOutput rescue nil
include TestSquare rescue nil
def initialize order
@order = order
@data = Array.new( @order ){ Array.new( @order ) { nil } }
end

def ; @data[c.lpos][c.cpos] end
def []=(c, v); @data[c.lpos][c.cpos] = v end

def each_subdiagonal
(@order/4).times do
| line |
(@order/4).times do
| col |
4.times do
| l |
4.times do
| c |
yield [ 4line + l, 4col + c ] if
l==c || l+c == 3
end
end # 4.times do
end # (@order/4).times do
end # (@order/4).times do
end

def siamese_order
model = self.class.new @order
last = @order*@order
@pos = Cursor.new @order, 0, @order/2
yield @pos.lpos, @pos.cpos, self[@pos]
model[ @pos ] = true
2.upto last do
npos = @pos.move -1, +1
npos = @pos.move +1, 0 if model[ npos ]
model[ @pos = npos ] = true
yield @pos.lpos, @pos.cpos, self[@pos]
end # @last.times do
end
end # class SquareData

The base class for Magic Squares it basically

is the result of factorizing the three classes

representing the three differnt cases, odd, even and

double even.

It’s singleton class is used as a class Factory for

the three implementing classes.

class Square

def to_s decoration = false
@data.to_s decoration
end
private
def initialize order
@order = order.to_i
@last = @order*@order
@data = SquareData.new @order
compute
@data.test rescue nil
end

end

The simplest case, the Siamese Order algorithm

is applied.

class OddSquare < Square

private
def compute
count = 1
@data.siamese_order do
| lpos, cpos, _ |
@data[[ lpos, cpos]] = count
count += 1
end # @data.siamese_order do
end

end # class OddSquare

The Double Cross Algorithm is applied

to double even Squares.

class DoubleCross < Square
def compute
pos = Cursor.new @order, 0, 0
1.upto( @last ) do
| n |
@data[ pos.next! ] = n
end # 1.upto( @last ) do
@data.each_subdiagonal do
| lidx, cidx |
@data[[ lidx, cidx ]] = @last.succ - @data[[lidx, cidx]]
end

end
end

And eventually we use the LUX algorithm of Conway for even

squares.

class FiatLux < Square
L = [ [0, 1], [1, 0], [1, 1], [0, 0] ]
U = [ [0, 0], [1, 0], [1, 1], [0, 1] ]
X = [ [0, 0], [1, 1], [1, 0], [0, 1] ]
def compute
half = @order / 2
lux_data = SquareData.new half
n = half/2
pos = Cursor.new half, 0, 0
n.succ.times do
half.times do
lux_data[ pos.next! ] = L
end # half.times do
end # n.succ.times do
half.times do
lux_data[ pos.next! ] = U
end # half.times do
lux_data[[ n, n ]] = U
lux_data[[ n+1, n]] = L
2.upto(n) do
half.times do
lux_data[ pos.next! ] = X
end
end # 2.upto(half) do

count = 1
lux_data.siamese_order do
  | siam_row, siam_col, elem |
  elem.each do
    | r, c |
    @data[[ 2*siam_row + r, 2*siam_col + c ]] = count
    count += 1
  end # elem.each do
end # lux_data.siamese_order do

end
end # class FiatLux

class << Square

trying to call the ctors with consistent values only

protected :new
def Factory arg
arg = arg.to_i
case arg % 4
when 1, 3
OddSquare.new arg
when 0
DoubleCross.new arg
else
FiatLux.new arg
end
end
end
ARGV.each do
|arg|
puts Square::Factory( arg ).to_s( true )
puts
end


#8

On May 18, 6:57 pm, Ruby Q. removed_email_address@domain.invalid wrote:

    +------------------------+

    | 45 | 34 | 23 | 12 |  1 | 80 | 69 | 58 | 47 |
    +--------------------------------------------+

For extra credit, support even values of N. You don’t need to worry about N = 2
though as it is impossible.

Here it is:

magic_square.rb

Magic Square with Odd Number

class OddMagicSquare
attr_reader :square

def initialize(n)
@square = Array.new(n)
@square.each_index {|i| @square[i] = Array.new(n)}
middle = n/2
@square[0][middle] = 1
@pos = [0,middle]
@len = n
end

def printing_magic_square
v_border = ‘+’ + ‘-’ * (6 * @len - 1) + ‘+’
@square.each do |row|
puts v_border
row.each do |r|
if r then
print format(’|’ + “%4d” + ’ ', r)
else
print '| nil ’
end
end
print “|\n”
end
puts v_border
end

def iterate_square
value = 2
last_value = @len ** 2
while true do
move
fill value
break if value == last_value
value = value + 1
end
end

private

def fill(value)
@square[@pos[0]][@pos[1]] = value
end

def move
move_down if not move_diagonal_up
end

def move_diagonal_up
# get future position
future_pos = Array.new(2)
@pos[0] == 0 ? future_pos[0] = @len - 1 : future_pos[0] = @pos[0]

  • 1
    @pos[1] == @len - 1 ? future_pos[1] = 0 : future_pos[1] = @pos[1]
  • 1

    check if it is empty or not

    if @square[future_pos[0]][future_pos[1]] then
    return false
    else
    @pos = future_pos
    end
    return true
    end

    def move_down
    @pos[0] == @len - 1 ? @pos[0] = 0 : @pos[0] = @pos[0] + 1
    end

end

The test case:
#tc_magic_square.rb
require ‘test/unit’

require ‘magic_square’

class TestOddMagicSquare < Test::Unit::TestCase

def setup
@n = 5
@odd_magic_square = OddMagicSquare.new(@n)
@odd_magic_square.iterate_square
@square = @odd_magic_square.square
@sum = (@n ** 2 / 2 + 1) * @n
end

def test_sum_row_and_col
@n.times do |t|
assert_equal @sum, get_sum_column(t)
assert_equal @sum, get_sum_row(t)
end
assert_equal @sum, get_sum_diagonal(‘left’)
assert_equal @sum, get_sum_diagonal(‘right’)
end

private

def get_sum_column(i)
sum = 0
@n.times do |t|
sum += @square[t][i]
end
sum
end

def get_sum_row(i)
sum = 0
@n.times do |t|
sum += @square[i][t]
end
sum
end

def get_sum_diagonal(alignment)
if alignment == ‘left’ then
sum = i = 0
@n.times do |t|
sum += @square[i][i]
i = i + 1
end
return sum
elsif alignment == ‘right’ then
sum = 0
i = @n - 1
@n.times do |t|
sum += @square[i][i]
i = i - 1
end
return sum
else
raise ‘Alignment must be left or right.’
end
end

end

Here how it is run:

use_magic_square.rb

require ‘magic_square’

getting input

n = ARGV[0].to_i

input must be odd and bigger than 2

raise ‘Argument must be odd and bigger than 2’ if n % 2 == 0 or n < 3

odd_magic_square = OddMagicSquare.new(n)
odd_magic_square.iterate_square
odd_magic_square.printing_magic_square

$ ruby use_magic_square.rb 5
±----------------------------+
| 17 | 24 | 1 | 8 | 15 |
±----------------------------+
| 23 | 5 | 7 | 14 | 16 |
±----------------------------+
| 4 | 6 | 13 | 20 | 22 |
±----------------------------+
| 10 | 12 | 19 | 21 | 3 |
±----------------------------+
| 11 | 18 | 25 | 2 | 9 |
±----------------------------+


#9

I heard that this approach only works with every other odd sided square.
Did you test it with larger squares and does it still work? If not, is
there a further quiz for that? What about even sided squares?

Just wondering.


#10

On 5/20/07, I. P. removed_email_address@domain.invalid wrote:

|Robert D.|

RD> BTW is there a book to be published one day about Ruby Q.?
It is
http://pragmaticprogrammer.com/titles/fr_quiz/index.html

Or you meant second book?

Why did nobody tell me??? :wink:
Yeah a second and a third and so on…

At least the idea was not a bad one :wink:

Cheers
Robert


#11

On 5/18/07, Ruby Q. removed_email_address@domain.invalid wrote:

The three rules of Ruby Q.:

  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
@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 + yorder + 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/


#12

On 5/20/07, Lloyd L. removed_email_address@domain.invalid wrote:

I heard that this approach only works with every other odd sided square.
Did you test it with larger squares and does it still work? If not, is
there a further quiz for that? What about even sided squares?

Just wondering.


Posted via http://www.ruby-forum.com/.

It is not clear to me to which solution you are referring, yes I have
tested with various larges sides ;).
Can I post the links to the algorithms for the interested or would
this be a spolier?

Cheers
Robert


#13

Here is my solution. I also used the steps from Wikipedia:

magic_squares.rb

Ruby Q. (#124)

class MagicSquare

def initialize(n)
raise ArgumentError, “N must be an odd number.” if n%2 == 0
@n = n
@square = fill
end

def fill
square = Array.new(@n)
square.each_index { |row| square[row] = Array.new(@n) }
current = 1
row = 0
col = (@n/2+1)-1
square[row][col] = current
until current == @n**2
current+=1
row = move_down(row)
col = move_down(col)
unless square[row][col].nil?
2.times { |i| row = move_up(row) }
col = move_up(col)
end
square[row][col] = current
end
square
end

def move_down(val)
if (val-1) > -1
val -= 1
else
val = (@n-1)
end
val
end

def move_up(val)
if (val+1) > (@n-1)
val = 0
else
val += 1
end
val
end

def display
header = “+” + “-” * (@n*5-1) + “+”
puts header
@square.each do |row|
current = "| "
row.each do |col|
current << " " * ((@n**2).to_s.length - col.to_s.length)
current << col.to_s + " | "
end
puts current
puts header
end
end

end

if FILE == $0
square = MagicSquare.new(ARGV[0].to_i)
square.display
end


~/desktop $ ruby magic_squares.rb 9
±-------------------------------------------+
| 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 |
±-------------------------------------------+


#14

On May 20, 2007, at 8:38 AM, Lloyd L. wrote:

I heard that this approach only works with every other odd sided
square.
Did you test it with larger squares and does it still work? If
not, is
there a further quiz for that? What about even sided squares?

Just wondering.

There’s a very easy algorithm for odd size squares, which is why the
quiz focused on this. Finding the even sizes is trickier, but not
impossible, thus the extra credit.

James Edward G. II


#15

On May 20, 2007, at 9:57 AM, Robert D. wrote:

Can I post the links to the algorithms for the interested or would
this be a spolier?

The no spoiler period has passed. Post whatever you like.

James Edward G. II


#16

This is the solution I made to generate the quiz examples:

#!/usr/bin/env ruby -w

parsing command-line arguments

begin
N = Integer(ARGV.shift)
MAX = N ** 2
raise “Bad number” if N < 0 or N % 2 == 0
rescue
abort “Usage: #{File.basename($PROGRAM_NAME)} ODD_INTEGER_SIZE”
end

build the square

square = Array.new(N) { Array.new(N) }
x, y = N / 2, 0
1.upto(MAX) do |i|
square[y][x] = i
x = x.zero? ? square.first.size - 1 : x - 1
y = y.zero? ? square.size - 1 : y - 1
unless square[y][x].nil?
x = (x + 1) % square.first.size
2.times { y = (y + 1) % square.size }
end
end

validate magic square

rows

tests = square.dup

columns

(0…N).each { |i| tests << square.map { |row| row[i] } }

diagonals

tests << (0…N).map { |i| square[i][i] } <<
(0…N).map { |i| square[N - (i + 1)][i] }

test all sums

unless tests.map { |group| group.inject { |sum, n| sum +
n } }.uniq.size == 1
raise “Not a magic square”
end

square output

width = MAX.to_s.size
border = “+#{’-’ * (width * N + 3 * (N - 1) + 2)}+”
puts border
square.each do |row|
puts “| #{row.map { |f| “%#{width}d” % f }.join(’ | ')} |”,
border
end

END

James Edward G. II


#17

On 5/20/07, James Edward G. II removed_email_address@domain.invalid wrote:

On May 20, 2007, at 9:57 AM, Robert D. wrote:

Can I post the links to the algorithms for the interested or would
this be a spolier?

The no spoiler period has passed. Post whatever you like.
:))
For those who did not search or find
http://www.answers.com/topic/conway-s-lux-method-for-magic-squares
http://mathworld.wolfram.com/MagicSquare.html

Robert


#18

My second version. Just did a little code cleanup mostly regarding
initializing the array. Again, I apologize for the early quiz submission
this week, hope I didn’t ruin anyone’s quiz.

file: magic_square.rb

author: Drew O.

class MagicSquare

access to the raw square (not used here, maybe used by others?)

attr_reader :square

check that size is odd, then store size and build our square

def initialize size
raise “Size must be odd” unless size%2 == 1
@size = size
@square = build_square size
self
end

scary looking method for pretty printing

def to_s
# find the largest number of digits in the numbers we
# are printing
digits = max_digits @size**2

# create the row divider. flexible based on size of numbers
# and the square.
divider = "+"+("-"*(@size*(3+digits)-1))+"+\n"

# build each row by formatting the numbers to the max
# digits needed and adding pipe dividers
(0...@size).inject(divider) do |output,i|
  output + "| " +
    @square[i].map{|x| "%#{digits}d" % x}.join(" | ") +
    " |\n" + divider
end

end

private

get the highest digit count up to size

def max_digits size
(1…size).map{|x| x.to_s.size}.max
end

build square based on the algorithm from wikipedia.

start in the middle of the first row, move up and right.

if new space is occupied, move down one space and continue.

def build_square size
#starting positions
x,y = size/2,0

# build square
(1..size**2).inject(Array.new(size){[]}) do |arr,i|

  # store current number in square
  arr[y][x] = i

  # move up and left
  x = (x+1)%size
  y = (y-1)%size

  # undo move and move down if space is taken
  if arr[y][x]
    y = (y+2)%size
    x = (x-1)%size
  end
  arr
end

end
end

build and print out square

if FILE == $0
puts MagicSquare.new(ARGV[0].to_i)
end


#19

This is my solution. It only does odd magic squares, but it can generate
all eight versions (assuming there are only eight. It seemed that way to
me.)

http://pastie.caboo.se/63130

  • donald

Ruby Q. 124

Donald B.

version 1.0

class MagicSquare
SLANTS = [-1, 1]
STARTS = [:top, :bottom, :left, :right]

def initialize(n, slant=SLANTS[rand(SLANTS.length)],
start=STARTS[rand(STARTS.length)])
raise ArgumentError unless n > 0 && (n % 2) == 1
raise ArgumentError unless SLANTS.include?(slant)
raise ArgumentError unless STARTS.include?(start)
@n = n
@sum = (@n3 + @n) / 2
@values = Array.new(@n
2)
if start == :top || start == :bottom
c = @n / 2
dc = slant
ddc = 0
if start == :top
r = 0
dr = -1
ddr = 1
else
r = -1
dr = 1
ddr = -1
end
else
r = @n / 2
dr = slant
ddr = 0
if start == :left
c = 0
dc = -1
ddc = 1
else
c = -1
dc = 1
ddc = -1
end
end
(1…@n).each do |i|
(1…@n).each do |j|
self[r, c] = @n*(i-1) + j
unless j==@n
r += dr
c += dc
else
r += ddr
c += ddc
end
end
end
end

def offset(r, c)
(r % @n) * @n + (c % @n)
end

def [](r, c)
@values[offset(r, c)]
end

def []=(r, c, v)
@values[offset(r, c)] = v
end

def range
(0…@n-1)
end

def col©
range.map {|r| @values[c + r*@n]}
end

def cols
range.map {|c| col©}
end

def row®
@values[r*@n, @n]
end

def rows
range.map {|r| row®}
end

def diagonals
[range.map {|i| @values[i*(@n+1)]}, range.map {|i|
@values[(@n-1)*(i+1)]}]
end

def valid?
(rows + cols + diagonals).each do |chunk|
return false unless chunk.inject {|sum, v| sum += v} == @sum
end
true
end

def to_s
def ojoin(a, sep)
sep + a.join(sep) + sep
end
l = (@n**2).to_s.length
sep = “+#{’-’(@n(l+2) + (@n-1))}+\n”
ojoin(rows.map {|row| ojoin(row.map {|v| sprintf(" %#{l}d ", v)},
‘|’) + “\n”}, sep)
end
end

if $0 == FILE
puts MagicSquare.new(ARGV[0].to_i) if ARGV.length == 1
end


#20

Hmm does not seem that the attachments are too readable on the Ruby Q.
site.
So please forgive me for posting them here again, inline. I do not
include the HTML plugin as it is not closely connected to the topic of
the Quiz.

Cheers
Robert

cat 124-magic-square.rb

vim: sts=2 sw=2 ft=ruby expandtab nu tw=0:

Usage = <<-EOS
usage:
ruby #{$0} [-t|–test] [-h|–html]

  Prints Magic Squares for all indicated orders.
  Indicating -t also tests the results.

EOS
loop do
case ARGV.first
when “-t”, “–test”
require ‘test-squares’
ARGV.shift
when “-h”, “–html”
require ‘html-output’
ARGV.shift
when “-?”, “–help”, nil
puts Usage
exit
when “–”
ARGV.shift && break
else
break
end
end

This is a default output module, another output

module called HTMLOutput is provided as an example

how to pull in an appropriate Output module

as plugin.

module Output
def to_s decoration = false
l = (@order*@order).to_s.size
return @data.map{ |line|
line.map{ |cell|
“%#{l}d” % cell
}.join(" “)
}.join(”\n") unless decoration

sep_line = "+" << ( "-" * l.succ.succ << "+" ) * @order
sep_line.dup << "\n" <<
@data.map{ | line | "| " << line.map{ |cell| "%#{l}d" % cell

}.join(" | “) << " |” }.
zip( [sep_line] * @order ).flatten.join("\n")
end
end

The usage of cursors is slowing down the program a little

bit but I feel it is still fast enough.

class Cursor
attr_reader :cpos, :lpos
def initialize order, lpos, cpos
@order = order
@lpos = lpos
@cpos = cpos
end

def move ldelta, cdelta
l = @lpos + ldelta
c = @cpos + cdelta
l %= @order
c %= @order
self.class.new @order, l, c
end
def next!
@cpos += 1
return if @cpos < @order
@cpos = 0
@lpos += 1
@lpos %= @order
end
end

This is where the work is done, like

testing and outputting and what was it?

Ah yes storing the data.

class SquareData
include Output
include HTMLOutput rescue nil
include TestSquare rescue nil
def initialize order
@order = order
@data = Array.new( @order ){ Array.new( @order ) { nil } }
end

def peek(i, j); @data[i][j] end
def poke(i, j, v); @data[i][j] = v end
def ; @data[c.lpos][c.cpos] end
def []=(c, v); @data[c.lpos][c.cpos] = v end

def each_subdiagonal
(@order/4).times do
| line |
(@order/4).times do
| col |
4.times do
| l |
4.times do
| c |
yield [ 4line + l, 4col + c ] if
l==c || l+c == 3
end
end # 4.times do
end # (@order/4).times do
end # (@order/4).times do
end

def siamese_order
model = self.class.new @order
last = @order*@order
@pos = Cursor.new @order, 0, @order/2
yield @pos.lpos, @pos.cpos, peek( @pos.lpos, @pos.cpos )
model[ @pos ] = true
2.upto last do
npos = @pos.move -1, +1
npos = @pos.move +1, 0 if model[ npos ]
model[ @pos = npos ] = true
yield @pos.lpos, @pos.cpos, peek( @pos.lpos, @pos.cpos )
end # @last.times do
end
end # class SquareData

The base class for Magic Squares it basically

is the result of factorizing the three classes

representing the three differnt cases, odd, even and

double even.

It’s singleton class is used as a class Factory for

the three implementing classes.

class Square

def to_s decoration = false
@data.to_s decoration
end
private
def initialize order
@order = order.to_i
@last = @order*@order
@data = SquareData.new @order
compute
@data.test rescue nil
end

end

The simplest case, the Siamese Order algorithm

is applied.

class OddSquare < Square

private
def compute
@pos = Cursor.new @order, 0, @order/2
@data[ @pos ] = 1
2.upto @last do
| n |
npos = @pos.move -1, +1
npos = @pos.move +1, 0 if @data[ npos ]
@data[ @pos = npos ] = n
end # @last.times do
end

end # class OddSquare

The Double Cross Algorithm is applied

to double even Squares.

class DoubleCross < Square
def compute
pos = Cursor.new @order, 0, 0
1.upto( @last ) do
| n |
@data[ pos ] = n
pos.next!
end # 1.upto( @last ) do
@data.each_subdiagonal do
| lidx, cidx |
@data.poke lidx, cidx, @last.succ - @data.peek( lidx, cidx )
end

end
end

And eventually we use the LUX algorithm of Conway for even

squares.

class FiatLux < Square
L = [ [0, 1], [1, 0], [1, 1], [0, 0] ]
U = [ [0, 0], [1, 0], [1, 1], [0, 1] ]
X = [ [0, 0], [1, 1], [1, 0], [0, 1] ]
def compute
half = @order / 2
lux_data = SquareData.new half
n = half/2
pos = Cursor.new half, 0, 0
n.succ.times do
half.times do
lux_data[ pos ] = L
pos.next!
end # half.times do
end # n.succ.times do
half.times do
lux_data[ pos ] = U
pos.next!
end # half.times do
lux_data.poke n, n, U
lux_data.poke n+1, n, L
2.upto(n) do
half.times do
lux_data[ pos ] = X
pos.next!
end
end # 2.upto(half) do

count = 1
lux_data.siamese_order do
  | siam_row, siam_col, elem |
  elem.each do
    | r, c |
    @data.poke 2*siam_row + r, 2*siam_col + c, count
    count += 1
  end # elem.each do
end # lux_data.siamese_order do

end
end # class FiatLux

class << Square

trying to call the ctors with consistent values only

protected :new
def Factory arg
arg = arg.to_i
case arg % 4
when 1, 3
OddSquare.new arg
when 0
DoubleCross.new arg
else
FiatLux.new arg
end
end
end
ARGV.each do
|arg|
puts Square::Factory( arg ).to_s( true )
puts
end
END
#########################################
#########################################
#207/15 > cat test-squares.rb

vim: sts=2 sw=2 ft=ruby expandtab nu tw=0:

module TestSquare
def assert cdt, msg
return $stderr.puts( “#{msg} . . . . . ok” ) if cdt
raise Exception, msg << “\n” << to_s
end
def test
dia1 = dia2 = 0
@order.times do
| idx |
dia1 += peek( idx, idx )
dia2 += peek( idx, -idx.succ )
end # @lines.each_with_index do
assert dia1==dia2, “Both diagonals”
@order.times do
| idx1 |
col_n = row_n = 0
@order.times do
| idx2 |
col_n += peek idx2, idx1
row_n += peek idx1, idx2
end
assert dia1 == col_n, “Col #{idx1}”
assert dia1 == row_n, “Row #{idx1}”
end # @lines.each_with_index do
end # def test

def is_ok?
dia1 = dia2 = 0
@order.times do
| idx |
dia1 += peek( idx, idx )
dia2 += peek( idx, -idx.succ )
end # @lines.each_with_index do
return false unless dia1==dia2
@order.times do
| idx1 |
col_n = row_n = 0
@order.times do
| idx2 |
col_n += peek idx2, idx1
row_n += peek idx1, idx2
end
return false unless dia1 == col_n
return false unless dia1 == row_n
end # @lines.each_with_index do
true

end

end
END