[QUIZ] Magic Squares (#124)

R

Ruby Quiz

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.rubyquiz.com/

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

Drew Olson

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.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 = []
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
 
J

James Edward Gray II

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.
Click to expand...

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
 
D

Drew Olson

James said:
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
Click to expand...

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

Harry Kakueki

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:
Click to expand...
# 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

akbarhome

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.rubyquiz.com/

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.
Click to expand...

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 = 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]
end
sum
end

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

def get_sum_diagonal(alignment)
if alignment == 'left' then
sum = i = 0
@n.times do |t|
sum += @square
i = i + 1
end
return sum
elsif alignment == 'right' then
sum = 0
i = @n - 1
@n.times do |t|
sum += @square
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 |
+-----------------------------+
 
L

Lloyd Linklater

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

Rick DeNatale

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.
Click to expand...

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 :eek:rder

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

Robert Dober

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.
Click to expand...
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
 
J

James Edward Gray II

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

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

James Edward Gray II
 
J

James Edward Gray II

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.
Click to expand...

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
 
J

James Edward Gray II

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 } }
# diagonals
tests << (0...N).map { |i| square } <<
(0...N).map { |i| square[N - (i + 1)] }
# 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 Gray II
 
D

Drew Olson

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

Ball, Donald A Jr (Library)

------_=_NextPart_001_01C79B0C.A7182637
Content-Type: text/plain;
charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable

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 Quiz 124
# Donald Ball
# version 1.0

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

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

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

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

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

def range
(0..@n-1)
end

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

def cols
range.map {|c| col(c)}
end

def row(r)
@values[r*@n, @n]
end

def rows
range.map {|r| row(r)}
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 +=3D v} =3D=3D @sum
end
true
end

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

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

------_=_NextPart_001_01C79B0C.A7182637--
 
R

Robert Dober

Hmm does not seem that the attachments are too readable on the Ruby Quiz 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] <Square Order List>

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[j] end
def poke(i, j, v); @data[j] = v end
def [](c); @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 [ 4*line + l, 4*col + 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__
 
D

Dan Manges

#!/usr/bin/env ruby
#
# Dan Manges - http://www.dcmanges.com
# Ruby Quiz #124 - http://rubyquiz.com/quiz124.html

module ArrayExtension
def sum
inject { |x,y| x + y } || 0
end
end
Array.send :include, ArrayExtension

class MagicSquare
def initialize(size)
@size = size
end

def row
result
end

def column
row[0].zip(*row[1..-1])
end

def diagonal
first_diagonal = (0...@size).map { |index| row[index][index] }
second_diagonal = (0...@size).map { |index|
row[index][@size-index-1] }
[first_diagonal, second_diagonal]
end

protected

def result
@result ||= MagicSquareGenerator.new(@size).generate
end

def method_missing(method, *args, &block)
result.send(method, *args, &block)
end
end

class MagicSquareGenerator
def initialize(size)
@size = size
end

def generate
square = (0...@size).map { [nil] * @size }
x, y = 0, @size / 2
1.upto(@size**2) do |current|
x, y = add(x,2), add(y,1) if square[x][y]
square[x][y] = current
x, y = add(x, -1), add(y, -1)
end
square
end

private

def add(x,y)
value = x + y
value = @size + value if value < 0
value = value % @size if value >= @size
value
end

end

class MagicSquareFormatter
def initialize(magic_square)
@magic_square = magic_square
end

def formatted_square
formatting = "|" + " %#{number_width}s |" * size
rows = @magic_square.map { |row| formatting % row }
body = rows.join("\n#{row_break}\n")
"#{row_break}\n#{body}\n#{row_break}"
end

private

def row_break
dashes = '-' * (row_width-2)
'+' + dashes + '+'
end

def number_width
(@magic_square.size**2).to_s.length
end

def row_width
(number_width+3) * size + 1
end

def size
@magic_square.size
end
end

if ARGV.first =~ /^\d+$/
size = ARGV.first.to_i
puts "Generating #{size}x#{size} magic square..."
magic_square = MagicSquare.new(size)
puts MagicSquareFormatter.new(magic_square).formatted_square
elsif __FILE__ == $0
require 'test/unit'
class MagicSquare3x3Test < Test::Unit::TestCase

def setup
@magic_square = MagicSquare.new(3)
end

def test_sum_of_rows_columns_and_diagonals
(0...3).each do |index|
assert_equal 15, @magic_square.row[index].sum
assert_equal 15, @magic_square.column[index].sum
end
assert_equal 15, @magic_square.diagonal[0].sum
assert_equal 15, @magic_square.diagonal[1].sum
end

def test_expected_values
assert_equal [1,2,3,4,5,6,7,8,9], @magic_square.flatten.sort
end

end

class MagicSquare9x9Test < Test::Unit::TestCase
def setup
@magic_square = MagicSquare.new(9)
end

def test_sum_of_rows_columns_and_diagonals
(0...9).each do |index|
assert_equal 369, @magic_square.row[index].sum
assert_equal 369, @magic_square.column[index].sum
end
assert_equal 369, @magic_square.diagonal[0].sum
assert_equal 369, @magic_square.diagonal[1].sum
end

def test_expected_values
assert_equal (1..81).to_a, @magic_square.flatten.sort
end
end
end
__END__
$ ruby rubyquiz124.rb 9
Generating 9x9 magic square...
+--------------------------------------------+
| 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 |
+--------------------------------------------+
 
H

Harry Kakueki

# Slight improvement to my first solution.
# I moved the 1 into the range (1..num**2) and deleted the old line
that input the 1.
# I didn't see a reason to keep it out of the range. So I saved a step.
# Also, I initialized the arrays with the value "empty".

### 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,"empty"))}

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

if tot[0][mid] != "empty"
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] == "empty"
end

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

# Harry
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

[SUMMARY] Magic Squares (#124) 0
Minimum Total Difficulty 0
[QUIZ] Pen and Paper (#90) 44
[QUIZ SOLUTION] Happy Numbers (#93) 3
Taskcproblem calendar 4
[QUIZ] Probable Iterations (#141) 14
Machine Learning.. Endless Struggle 3
[QUIZ] Number Spiral (#109) 27

Members online

Total: 72 (members: 1, guests: 71)
Robots: 384

Forum statistics

Threads
473,982
Messages
2,570,189
Members
46,735
Latest member
HikmatRamazanov

Latest Threads

Top