[QUIZ] Magic Squares (#124)

Discussion in 'Ruby' started by Ruby Quiz, May 18, 2007.

  1. Ruby Quiz

    Ruby Quiz Guest

    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.
     
    Ruby Quiz, May 18, 2007
    #1
    1. Advertising

  2. Ruby Quiz

    Drew Olson Guest

    Re: Magic Squares (#124)

    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

    --
    Posted via http://www.ruby-forum.com/.
     
    Drew Olson, May 18, 2007
    #2
    1. Advertising

  3. Re: Magic Squares (#124)

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

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


    Drew:

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

    James Edward Gray II
     
    James Edward Gray II, May 18, 2007
    #3
  4. Ruby Quiz

    Drew Olson Guest

    Re: Magic Squares (#124)

    James Gray wrote:
    > On May 18, 2007, at 10:22 AM, Drew Olson wrote:
    >
    >> Here's my solution. It only works for odd-sized squares at the moment,
    >> maybe I'll get ambitious later and go for the extra credit.

    >
    > Drew:
    >
    > Ruby Quiz has a "no spoiler period" rule. We request that users do
    > not share and spoiler material for the first 48 hours after a quiz is
    > released. This rule is at the top of every quiz. No big deal, but
    > please keep that in mind for the future.
    >
    > James Edward Gray II


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

    --
    Posted via http://www.ruby-forum.com/.
     
    Drew Olson, May 18, 2007
    #4
  5. On 5/18/07, Ruby Quiz <> wrote:
    >
    > This week's Ruby Quiz is to write a program that builds magic squares. To keep
    > the problem easy, I will say that your program only needs to work for odd values
    > of N. Try to keep your runtimes pretty reasonable even for the bigger values of
    > N:
    >

    # Here is my solution.
    # It is based on the steps at Wikipedia.
    # http://en.wikipedia.org/wiki/Magic_square#A_method_for_constructing_a_magic_square_of_odd_order
    # I input the 1 in the middle of the first array (tot[0][mid]).
    # Then I moved the arrays into position so I could always input using
    the same index (tot[0][mid]).

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

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

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

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

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

    # Harry

    --

    A Look into Japanese Ruby List in English
    http://www.kakueki.com/
     
    Harry Kakueki, May 20, 2007
    #5
  6. Ruby Quiz

    akbarhome Guest

    [QUIZ][SOLUTION]Re: Magic Squares (#124)

    On May 18, 6:57 pm, Ruby Quiz <> wrote:
    > The three rules of Ruby Quiz:
    >
    > 1. Please do not post any solutions or spoiler discussion for this quiz until
    > 48 hours have passed from the time on this message.
    >
    > 2. Support Ruby Quiz by submitting ideas as often as you can:
    >
    > http://www.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.


    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 |
    +-----------------------------+
     
    akbarhome, May 20, 2007
    #6
  7. Ruby Quiz

    Robert Dober Guest

    On 5/20/07, I. P. <> wrote:
    > |Robert Dober|
    >
    > RD> BTW is there a book to be published one day about Ruby Quiz?
    > 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
    >
    > --
    > I. P. 2007-05-20T16:36
    >
    >
    >



    --
    You see things; and you say Why?
    But I dream things that never were; and I say Why not?
    -- George Bernard Shaw
     
    Robert Dober, May 20, 2007
    #7
  8. [SOLUTION]Re: Magic Squares (#124)

    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/.
     
    Lloyd Linklater, May 20, 2007
    #8
  9. On 5/18/07, Ruby Quiz <> wrote:
    > The three rules of Ruby Quiz:
    >
    > 1. Please do not post any solutions or spoiler discussion for this quiz until
    > 48 hours have passed from the time on this message.


    Okay, the time has come to reveal my solution publicly. I'd already
    submitted this privately to JEGII. I solved this in a couple of
    hours, then
    had an idea in the shower yesterday morning which led to a simplification of
    the generate_singly_even method.

    The motherlode of information on the approaches I've used is to be
    found on the mathworld site, the URL is in the code.

    My solution solves all orders of magic squares, odd, singly-even, and
    doubly even. Here's a small command line program which takes a number
    as input and pretty prints a magic square of that order:

    === ms.rb

    #! /usr/local/bin/ruby
    require 'magic_square'

    if ARGV.size == 1

    size = ARGV.first.to_i
    end
    if size && size > 0 && size != 2
    puts MagicSquare.new(size)
    else
    print ["ms.rb prints a magic square of order n", "",
    "Usage:", " ms n", "", " where n is an integer > 0 and not = 2", ""
    ].join("\n")
    end

    =====

    And here's my test/unit testcase which tests orders from -1 to 10

    === ms_test.rb
    require 'magic_square'
    require 'test/unit'

    class TestMagicSquare < Test::Unit::TestCase

    def test_negative_n
    assert_raise(ArgumentError) { MagicSquare.new(-1)}
    end

    def test_2
    assert_raise(ArgumentError) { MagicSquare.new(2)}
    end

    def test_to_ten
    try(1)
    for i in (3..10)
    try(i)
    end
    end

    private
    def try(n)
    m = nil
    assert_nothing_raised { m = MagicSquare.new(n)}
    assert(m.is_magic?)
    end

    end

    ===
    Here's a run of the test case
    rick@frodo:/public/rubyscripts/rubyquiz/trunk/magic_square$ ruby ms_test.rb
    Loaded suite ms_test
    Started
    ...
    Finished in 0.067171 seconds.

    3 tests, 20 assertions, 0 failures, 0 errors

    And here's the crux of the biscuit. I used NArray to hold the 2d
    array for it's speed.

    === magic_square.rb
    require 'narray'
    # Based on
    # http://mathworld.wolfram.com/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



    ---
    Rick DeNatale

    My blog on Ruby
    http://talklikeaduck.denhaven2.com/
     
    Rick DeNatale, May 20, 2007
    #9
  10. Ruby Quiz

    Robert Dober Guest

    Re: [SOLUTION]Re: Magic Squares (#124)

    On 5/20/07, Lloyd Linklater <> wrote:
    > I heard that this approach only works with every other odd sided square.
    > Did you test it with larger squares and does it still work? If not, is
    > there a further quiz for that? What about even sided squares?
    >
    > Just wondering.
    >
    > --
    > 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

    --
    You see things; and you say Why?
    But I dream things that never were; and I say Why not?
    -- George Bernard Shaw
     
    Robert Dober, May 20, 2007
    #10
  11. Re: [SOLUTION]Re: Magic Squares (#124)

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

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


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

    James Edward Gray II
     
    James Edward Gray II, May 20, 2007
    #11
  12. Re: [SOLUTION]Re: Magic Squares (#124)

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

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


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

    James Edward Gray II
     
    James Edward Gray II, May 20, 2007
    #12
  13. 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
     
    James Edward Gray II, May 20, 2007
    #13
  14. Ruby Quiz

    Robert Dober Guest

    Re: [SOLUTION]Re: Magic Squares (#124)

    On 5/20/07, James Edward Gray II <> wrote:
    > On May 20, 2007, at 9:57 AM, Robert Dober wrote:
    >
    > > Can I post the links to the algorithms for the interested or would
    > > this be a spolier?

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

    :))
    For those who did not search or find
    http://www.answers.com/topic/conway-s-lux-method-for-magic-squares
    http://mathworld.wolfram.com/MagicSquare.html

    Robert
    >
    > James Edward Gray II
    >
    >



    --
    You see things; and you say Why?
    But I dream things that never were; and I say Why not?
    -- George Bernard Shaw
     
    Robert Dober, May 20, 2007
    #14
  15. Ruby Quiz

    Drew Olson Guest

    Re: Magic Squares (#124)

    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

    --
    Posted via http://www.ruby-forum.com/.
     
    Drew Olson, May 20, 2007
    #15
  16. ------_=_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--
     
    Ball, Donald A Jr (Library), May 20, 2007
    #16
  17. Ruby Quiz

    Robert Dober Guest

    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__
     
    Robert Dober, May 20, 2007
    #17
  18. Ruby Quiz

    Dan Manges Guest

    Re: Magic Squares (#124)

    #!/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 |
    +--------------------------------------------+

    --
    Posted via http://www.ruby-forum.com/.
     
    Dan Manges, May 20, 2007
    #18
  19. On May 20, 2007, at 2:53 PM, Robert Dober wrote:

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


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

    ;)

    James Edward Gray II
     
    James Edward Gray II, May 20, 2007
    #19
  20. On 5/20/07, Harry Kakueki <> wrote:
    > On 5/18/07, Ruby Quiz <> wrote:
    > >
    > > This week's Ruby Quiz is to write a program that builds magic squares. To keep
    > > the problem easy, I will say that your program only needs to work for odd values
    > > of N. Try to keep your runtimes pretty reasonable even for the bigger values of
    > > N:
    > >

    >


    # 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/
     
    Harry Kakueki, May 21, 2007
    #20
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. venkat
    Replies:
    3
    Views:
    1,579
    Robert Kern
    Jun 1, 2005
  2. IchBin
    Replies:
    0
    Views:
    304
    IchBin
    Oct 17, 2007
  3. Ruby Quiz

    [QUIZ] Magic Fingers (#120)

    Ruby Quiz, Apr 13, 2007, in forum: Ruby
    Replies:
    13
    Views:
    395
    Jesse Merriman
    Apr 19, 2007
  4. Ruby Quiz

    [SUMMARY] Magic Squares (#124)

    Ruby Quiz, May 24, 2007, in forum: Ruby
    Replies:
    0
    Views:
    212
    Ruby Quiz
    May 24, 2007
  5. Giles Bowkett
    Replies:
    9
    Views:
    419
    Giles Bowkett
    Dec 17, 2007
Loading...

Share This Page