[QUIZ] Magic Squares (#124)

[Yossef Mendelssohn]

Ahh, this reminds me of college. Some other people may have had to
look up the algorithm or figure it out by the supplied magic squares,
but a decade later, I still remember. Of course, back then we started
at the bottom middle, not the top middle. Doesn't make much of a
difference in the end, though, and that's why it's for odd side
lengths.



#!/usr/bin/env ruby

class MagicSquare
Coords = Struct.newx, :y)

def initialize(size)
@size = size.to_i
@final_num = @size**2
@coords = Coords.new(@size/2, 0)

create_square
end

def init_square
@square = []
1.upto(@size) do
@square << [0] * @size
end
end

def create_square
init_square

n = 1
while n <= @final_num
@square[@coords.y][@coords.x] = n
n += 1
next_coords
end
end

def to_s
output = []
num_length = @final_num.to_s.length
num_length+2 * @size
hline = '+' + Array.new(@size, '-' * (num_length + 2)).join('+') +
'+'

output.push(hline)
(0...@size).each do |x|
output.push('| ' + @square[x].collect { |n|
sprintf("%#{num_length}d", n) }.join(' | ') + ' |')
output.push(hline)
end
output.join("\n")
end

private
def next_coords
new_coords = Coords.new((@coords.x-1 + @size) % @size,
(@coords.y-1 + @size) % @size)
if @square[new_coords.y][new_coords.x] != 0
new_coords = Coords.new(@coords.x, (@coords.y+1) % @size)
end
@coords = new_coords
end
end


square = MagicSquare.new(ARGV[0])

puts square

 

[Rick DeNatale]

Ahh, this reminds me of college. Some other people may have had to
look up the algorithm or figure it out by the supplied magic squares,
but a decade later, I still remember. Of course, back then we started
at the bottom middle, not the top middle. Doesn't make much of a
difference in the end, though, and that's why it's for odd side
lengths.

You're right that it doesn't mattter if you just want to generate an
odd-order magic square.

On the other hand, Conway's LUX algorithm for generating a magic
square of an order which has a single 2 in its prime factorization,
makes use of an odd order magic square which starts in the center cell
of the top row to seed the values for generating the larger square.

 

[Ivo Dancet]

My solution, without extra credits.

#! /usr/bin/ruby

class MagicSquare
def initialize( ord )
@ord = ord

checkOrd
initSquare
makeSquare
printNiceSquare
end

def checkOrd
if @ord%2 != 1 || @ord < 0
puts "Not implemented or not possible..."
exit
end
end

def setCoord( row, col, number )
loop do
if @square[row][col].nil?
@square[row][col] = number
@oldCoord = [row, col]
return
else
row = @oldCoord[0] + 1
col = @oldCoord[1]
row -= @ord if row >= @ord
end
end
end

def initSquare
@square = Array.new(@ord)
@square.each_index do |row|
@square[row] = Array.new(@ord)
end
end

def makeSquare
(@ord**2).times do |i|
setNewCoord( i + 1 )
end
end

def setNewCoord( i )
if @oldCoord.nil?
setCoord(0, (@ord + 1)/2-1, i)
else
row = @oldCoord[0] + 2
col = @oldCoord[1] + 1

row -= @ord if row >= @ord
col -= @ord if col >= @ord

setCoord(row, col, i)
end
end

def printNiceSquare
width = (@ord**2).to_s.length

@square.each do |row|
row.each do |nr|
nr = nr.nil? ? "." : nr
spaces = width - nr.to_s.length
print " "*spaces + "#{nr}" + " "
end
puts
end
end
end

ord = ARGV[0].to_i
MagicSquare.new( ord )

 

[G.Durga Prasad]

------=_Part_54135_32723785.1179847290951
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

$ cat magic_square.rb

#!/usr/bin/env ruby
# G.D.Prasad
class Array
def / len # Thanks to _why
a=[]
each_with_index do |x,i|
a <<[] if i%len == 0
a.last << x
end
a
end
def rotate_left
self.push(self.shift)
end
def rotate_right
self.unshift(self.pop)
end
end

def rotate_array_right_index_times(arrays)
arrays.each_with_index{|array,i| i.times{array = array.rotate_right}}
end

def show(rows,n)
string = rows.map{|r| r.inject(""){|s,e| s + e.to_s.center(5," ")
+"|"}}.join("\n"+"-"*6*n+"\n")
puts string
end

n=ARGV[0].to_i
raise "Usage: magic_square (ODD_NUMBER>3) " if n%2==0 or n<3
nsq=n*n
arrays = ((1..nsq).to_a/n).each{|a| a.reverse!}
sum = nsq*(nsq+1)/(2*n)
(n/2).times{arrays = arrays.rotate_left}
rotate_array_right_index_times(arrays)
cols=arrays.transpose
rotate_array_right_index_times(cols)
rows=cols.transpose

puts;puts
show(rows,n)
puts
puts " sum of each row,column or diagonal = #{sum}"
puts;puts

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.

------=_Part_54135_32723785.1179847290951
Content-Type: application/x-ruby; name="magic_square.rb"
Content-Transfer-Encoding: base64
Content-Disposition: attachment; filename="magic_square.rb"
X-Attachment-Id: f_f20ill32

IyEvdXNyL2Jpbi9lbnYgcnVieSAKI0cuRC5QcmFzYWQKY2xhc3MgQXJyYXkKICBkZWYgLyBsZW4g
ICAgICAgICAgICMgVGhhbmtzIHRvIF93aHkKICBhPVtdCiAgZWFjaF93aXRoX2luZGV4IGRvIHx4
LGl8CiAgYSA8PFtdIGlmIGklbGVuID09IDAKICBhLmxhc3QgPDwgeAogIGVuZAogIGEKICBlbmQK
ICBkZWYgcm90YXRlX2xlZnQKICAgIHNlbGYucHVzaChzZWxmLnNoaWZ0KQogIGVuZCAgCiAgZGVm
IHJvdGF0ZV9yaWdodAogICAgc2VsZi51bnNoaWZ0KHNlbGYucG9wKQogIGVuZCAgCmVuZAoKZGVm
IHJvdGF0ZV9hcnJheV9yaWdodF9pbmRleF90aW1lcyhhcnJheXMpCiAgYXJyYXlzLmVhY2hfd2l0
aF9pbmRleHt8YXJyYXksaXwgaS50aW1lc3thcnJheSA9IGFycmF5LnJvdGF0ZV9yaWdodH19CmVu
ZAoKZGVmIHNob3cocm93cyxuKQogIHN0cmluZyAgPSByb3dzLm1hcHt8cnwgci5pbmplY3QoIiIp
e3xzLGV8IHMgKyBlLnRvX3MuY2VudGVyKDUsIiAiKSArInwifX0uam9pbigiXG4iKyItIio2Km4r
IlxuIikKICBwdXRzIHN0cmluZwplbmQKCm49QVJHVlswXS50b19pCnJhaXNlICJVc2FnZTogbWFn
aWNfc3F1YXJlIChPRERfTlVNQkVSPjMpICIgaWYgbiUyPT0wIG9yIG48Mwpuc3E9bipuCmFycmF5
cyA9ICgoMS4ubnNxKS50b19hL24pLmVhY2h7fGF8IGEucmV2ZXJzZSF9CnN1bSA9IG5zcSoobnNx
KzEpLygyKm4pCihuLzIpLnRpbWVze2FycmF5cyA9IGFycmF5cy5yb3RhdGVfbGVmdH0Kcm90YXRl
X2FycmF5X3JpZ2h0X2luZGV4X3RpbWVzKGFycmF5cykKY29scz1hcnJheXMudHJhbnNwb3NlCnJv
dGF0ZV9hcnJheV9yaWdodF9pbmRleF90aW1lcyhjb2xzKQpyb3dzPWNvbHMudHJhbnNwb3NlCgpw
dXRzO3B1dHMKc2hvdyhyb3dzLG4pCnB1dHMKcHV0cyAiCXN1bSBvZiBlYWNoIHJvdyxjb2x1bW4g
b3IgZGlhZ29uYWwgPSAgI3tzdW19IgpwdXRzO3B1dHMK
------=_Part_54135_32723785.1179847290951--

 

[CHubas]

The three rules of Ruby Quiz:

A little late, but did it.
As always, enjoyed it vey much. Here is my solution

===============================
===============================

#! /usr/bin/ruby

# Ruby quiz 124 - Magic Squares
# Author: Ruben Medellin

class Array
def sum
inject(0){|a,v|a+=v}
end
end

class MagicSquare

attr_accessor :grid
SHAPES = {:L => [3, 0, 1, 2], :U => [0, 3, 1, 2], :X => [0, 3, 2, 1]}

# Validates the size, and then fills the grid
# according to its size.
# For reference, see
# Weisstein, Eric W. "Magic Square." From MathWorld--A Wolfram Web
Resource.
# http://mathworld.wolfram.com/ MagicSquare.html
def initialize(n)
raise ArgumentError if n < 3
@grid = Array.new(n){ Array.new(n) }
if n % 2 != 0
initialize_odd(n)
else
if n % 4 == 0
initialize_double_even(n)
else
initialize_single_even(n)
end
end
end

def [](x, y)
@grid[x][y]
end

def display
n = @grid.size
space = (n**2).to_s.length
sep = '+' + ("-" * (space+2) + "+") * n
@grid.each do |row|
print sep, "\n|"
row.each{|number| print " " + ("%#{space}d" % number) + " |"}
print "\n"
end
print sep, "\n"
end

def is_magic?
n = @grid.size
magic_number = (n * (n**2 + 1)) / 2
for i in 0...n
return false if @grid.sum != magic_number
return false if @grid.map{|e| e}.sum != magic_number
end
return true
end

private

# Fill by crossing method
def initialize_double_even(n)
current = 1
max = n**2
for x in 0...n
for y in 0...n
if is_diag(x) == is_diag(y)
@grid[x][y] = current
else
@grid[x][y] = max - current + 1
end
current += 1
end
end
end

def is_diag(n)
n % 4 == 0 || n % 4 == 3
end

# Fill by LUX method
def initialize_single_even(n)
# Build an odd magic square and fill the new one based on it
# according to the LUX method
square = MagicSquare.new(n/2)
m = (n+2)/4
for x in 0...(n/2)
for y in 0...(n/2)
if(x < m)
shape = (x == m-1 and x == y) ? :U : :L
fill(x, y, square[x,y], shape)
elsif ( x == m )
shape = (x == y+1) ? :L : :U
fill(x, y, square[x,y], shape)
else
fill(x, y, square[x,y], :X)
end
end
end
end

def fill(x, y, number, shape)
number = ((number-1) * 4) + 1
numbers = [* number...(number + 4)]
@grid[x*2][y*2] = numbers[ SHAPES[shape][0] ]
@grid[x*2][y*2+1] = numbers[ SHAPES[shape][1] ]
@grid[x*2+1][y*2] = numbers[ SHAPES[shape][2] ]
@grid[x*2+1][y*2+1] = numbers[ SHAPES[shape][3] ]
end

# Fill by Kraitchik method
def initialize_odd(n)
x, y = 0, n/2
for i in 1..(n**2)
@grid[x][y] = i
x = (x-1)%n
y = (y+1)%n
# If the new square is not empty, return to the inmediate empty
# square below the former.
unless @grid[x][y].nil?
x = (x+2)%n
y = (y-1)%n
end
end
end

end

$stdout = File.new('magic_square', 'w') if ARGV.delete("-f")

$m = MagicSquare.new(ARGV[0] && ARGV[0].to_i || 5)
$m.display

if $DEBUG
require 'test/unit'
class SquareTest < Test::Unit::TestCase
def test_magic
assert($m.is_magic?)
end
end
end

$stdout.close

==============================
==============================

Thanks for the quizes.
Ruben.

 

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

# I know that people are already working on the next Ruby Quiz,
# but this idea just hit me and I made this improvement to my solution.
# If I make more improvements, I won't bother everyone with more posts.
# I just thought this quiz was interesting.

### Code Start
num = ARGV[0].to_i
if num % 2 != 0 and num > 0
tot = (0...num).map {Array.new(num)}

(1..num**2).each do |x|
tot.unshift(tot.pop).each {|g| g.push(g.shift)} if x % num != 1
tot.push(tot.shift) if x % num == 1
tot[0][((num + 1) / 2) - 1] = x.to_s.rjust((num**2).to_s.length)
end

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

# Harry