Asp Forum - [QUIZ] Magic Squares (#124

James Gray

5/18/2007 11:58:00 AM

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.

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

http://www.rub...

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.

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

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

24 Answers

Drew Olson

5/18/2007 3:22:00 PM

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 Olson

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

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

James Gray

5/18/2007 3:39:00 PM

On May 18, 2007, at 10:22 AM, Drew Olson 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 Quiz 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 Gray II

Drew Olson

5/18/2007 3:41:00 PM

James Gray wrote:
> On May 18, 2007, at 10:22 AM, Drew Olson 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 Quiz 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 Gray II

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

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

Harry Kakueki

5/20/2007 12:02:00 PM

On 5/18/07, Ruby Quiz <james@grayproductions.net> wrote:
>
> This week's Ruby Quiz 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...
# 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.ka...

akbarhome

5/20/2007 12:52:00 PM

On May 18, 6:57 pm, Ruby Quiz <j...@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.
>
> 2. Support Ruby Quiz by submitting ideas as often as you can:
>
> http://www.rub...
>
> 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.
>
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
>
> 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 Quiz 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.

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

Lloyd Linklater

5/20/2007 1:38:00 PM

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

Rick DeNatale

5/20/2007 2:36:00 PM

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/MagicS...
#
# and
#
# http://en.wikipedia.org/wiki/Ma...
#
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.denh...

Robert Dober

5/20/2007 2:58:00 PM

On 5/20/07, Lloyd Linklater <lloyd@2live4.com> 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-....
>
>
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

--
You see things; and you say Why?
But I dream things that never were; and I say Why not?
-- George Bernard Shaw

James Gray

5/20/2007 3:09:00 PM

On May 20, 2007, at 9:57 AM, Robert Dober 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 Gray II

James Gray

5/20/2007 3:11:00 PM

On May 20, 2007, at 8:38 AM, Lloyd Linklater 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 Gray II

comp.lang.ruby

[QUIZ] Magic Squares (#124

James Gray

Drew Olson

James Gray

Drew Olson

Harry Kakueki

akbarhome

Lloyd Linklater

Rick DeNatale

Robert Dober

James Gray

James Gray

x Login to ForumsZone