Forum: Ruby Magic Squares (#124)

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
James G. (Guest)
on 2007-05-18 15:58
(Received via mailing list)
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/

3.  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.
Drew O. (Guest)
on 2007-05-18 19:22
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
James G. (Guest)
on 2007-05-18 19:39
(Received via mailing list)
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
Drew O. (Guest)
on 2007-05-18 19:40
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.
Harry K. (Guest)
on 2007-05-20 16:02
(Received via mailing list)
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...
# 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/
Robert D. (Guest)
on 2007-05-20 16:06
(Received via mailing list)
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] <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

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 [](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, 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
I. P. (Guest)
on 2007-05-20 16:37
(Received via mailing list)
|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?
Akbar H. (Guest)
on 2007-05-20 16:55
(Received via mailing list)
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 |
+-----------------------------+
Robert D. (Guest)
on 2007-05-20 17:05
(Received via mailing list)
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??? ;)
Yeah a second and a third and so on...

At least the idea was not a bad one ;)

Cheers
Robert
Lloyd L. (Guest)
on 2007-05-20 17:38
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.
Rick D. (Guest)
on 2007-05-20 18:37
(Received via mailing list)
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 [](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.denhaven2.com/
Bryan W. (Guest)
on 2007-05-20 18:38
(Received via mailing list)
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 |
+--------------------------------------------+
Robert D. (Guest)
on 2007-05-20 18:58
(Received via mailing list)
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
James G. (Guest)
on 2007-05-20 19:09
(Received via mailing list)
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
James G. (Guest)
on 2007-05-20 19:11
(Received via mailing list)
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
James G. (Guest)
on 2007-05-20 19:30
(Received via mailing list)
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
Robert D. (Guest)
on 2007-05-20 19:45
(Received via mailing list)
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-f...
http://mathworld.wolfram.com/MagicSquare.html

Robert
Drew O. (Guest)
on 2007-05-20 21:17
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
Ball, Donald A Jr (Library) (Guest)
on 2007-05-20 22:29
(Received via mailing list)
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 = (@n**3 + @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(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 += 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
Robert D. (Guest)
on 2007-05-20 23:53
(Received via mailing list)
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] <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[i][j] end
  def poke(i, j, v); @data[i][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__
Dan M. (Guest)
on 2007-05-21 00:44
#!/usr/bin/env ruby
#
#  Dan M. - http://www.dcmanges.com
#  Ruby Q. #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 |
+--------------------------------------------+
James G. (Guest)
on 2007-05-21 02:24
(Received via mailing list)
On May 20, 2007, at 2:53 PM, Robert D. wrote:

> Hmm does not seem that the attachments are too readable on the Ruby
> Quiz site.

http://www.rubyquiz.com/quiz115.html

;)

James Edward G. II
Harry K. (Guest)
on 2007-05-21 09:52
(Received via mailing list)
On 5/20/07, Harry K. <removed_email_address@domain.invalid> wrote:
> 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:
> >
>

# 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


--

A Look into Japanese Ruby List in English
http://www.kakueki.com/
Yossef M. (Guest)
on 2007-05-21 18:11
(Received via mailing list)
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.new(:x, :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 D. (Guest)
on 2007-05-21 21:35
(Received via mailing list)
On 5/21/07, Yossef M. <removed_email_address@domain.invalid> wrote:
> 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.

--
Rick DeNatale

My blog on Ruby
http://talklikeaduck.denhaven2.com/
Ivo D. (Guest)
on 2007-05-22 01:51
(Received via mailing list)
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 P. (Guest)
on 2007-05-22 19:21
(Received via mailing list)
$ 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
Ruben M. (Guest)
on 2007-05-22 21:56
(Received via mailing list)
On May 18, 6:57 am, Ruby Q. <removed_email_address@domain.invalid> wrote:
> The three rules of Ruby Q.:

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

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[i].sum != magic_number
      return false if @grid.map{|e| e[i]}.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 K. (Guest)
on 2007-05-26 05:13
(Received via mailing list)
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:
>
# I know that people are already working on the next Ruby Q.,
# 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

--

A Look into Japanese Ruby List in English
http://www.kakueki.com/
Glenn W. (Guest)
on 2015-10-22 15:36
Some interesting background history on Magic Squares in art, science and
culture on this blog: www.glennwestmore.com.au
This topic is locked and can not be replied to.