[SUMMARY] Magic Squares (#124)

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

  1. Ruby Quiz

    Ruby Quiz Guest

    I was pleasantly surprised by the number of people that tackled the extra credit
    this time around. Essentially, there are different algorithms for building
    magic squares depending on the size of the square. There are in fact three
    different algorithms: one for odd sizes, one for doubly even (divisible by 4)
    sizes, and another for singly even (divisible by 2 but not 4) sizes.

    One solution that did handle all three cases came from David Tran. Let's dive
    right into how David constructs the squares:

    class MagicSquare

    def initialize(size = 3)
    raise "Error: size must greater than 2." if size < 3
    @magic_square = if (size % 2 != 0)
    OddMagicSquare.new(size)
    elsif (size % 4 == 0)
    DoublyEvenMagicSquare.new(size)
    else
    SinglyEvenMagicSquare.new(size)
    end
    end

    # ...

    Here we see the initialization deferred to various classes based on the
    requested square size. These are just the conditions for the various algorithms
    I mentioned earlier.

    One point of interest is that this solution won't construct a magic square of
    size one, though they are legal:

    +---+
    | 1 |
    +---+

    Let's see some of the other methods in this class:

    # ...

    def size
    @magic_square.size
    end

    def [](i,j)
    @magic_square[i,j]
    end

    # ...

    These two methods just delegate to the inner square object. Nothing tricky
    there.

    Next we have the pretty printer:

    # ...

    def to_s
    digits = (size * size).to_s.size
    divider = '+' + '-' * ((digits + 2) * size + (size - 1)) + "+\n"
    (0...size).inject(divider) do |s, i|
    (0...size).inject(s + "|") do |s, j|
    s + " #{self[i,j].to_s.rjust(digits)} |"
    end + "\n" + divider
    end
    end

    # ...

    Most solutions included a routine pretty similar to this. You first have to
    find the width of the largest number and assemble a properly size border. Then
    you can iterate over the rows and cells printing them at the proper width and
    with borders between.

    David also included a method that verifies his work:

    # ...

    def is_magic_square?
    size = self.size
    n = size * size

    array = Array.new(n)
    (0...size).each do |i|
    (0...size).each do |j|
    index = self[i,j] - 1
    return false if (index < 0) || (index >= n) || array[index]
    array[index] = true
    end
    end
    return false unless array.all?

    sum = size * (size * size + 1) / 2
    (0...size).each do |i|
    return false if sum != (0...size).inject(0) { |s,j| s + self[i,j] }
    return false if sum != (0...size).inject(0) { |s,j| s + self[j,i] }
    end
    return false if sum != (0...size).inject(0) { |s,i| s + self[i,i] }
    return false if sum != (0...size).inject(0) { |s,i|
    s + self[i, size-1-i]
    }
    true
    end

    # ...

    This method begins by calculating a few sizes. It then launches into verifying
    that all the numbers in the expected range were used. This code works by
    filling an Array the length of all the numbers with nils. It then walks all
    numbers of the square, replacing that index with a true value. Finally it
    checks that they are all true. The rest of the method does the standard magic
    square validation by row, column, and diagonal.

    We're now ready to examine the three individual algorithms:

    # ...

    private
    class OddMagicSquare
    attr_reader :size

    def initialize(size)
    @size = size
    n = @size * @size
    @array = Array.new(n)
    i, j = 0, @size/2
    (1..n).each do |v|
    @array[get_index(i,j)] = v
    a, b = i-1, j+1
    i, j = self[a,b] ? [i+1, j] : [a, b]
    end
    end

    def [](i, j)
    @array[get_index(i,j)]
    end

    private
    def get_index(i, j)
    (i % @size) * @size + (j % @size)
    end
    end

    # ...

    The algorithm for odd size magic squares is pretty straightforward. You begin
    by placing a one in the top center of the of the square. From there you just
    count, placing each number you come to in the square above and to the right of
    the last square you filled. The board "wraps" for these movements, so moving
    off the top brings you to the bottom and moving off the right side returns you
    to the left. If a normal move would take you to a filled square, you drop one
    square instead.

    The above is a Ruby implementation of this algorithm. The values are all
    calculated at the time of object construction and stored in an instance
    variable. They can then be accessed at any time via the [] method which uses
    row major indexing.

    # ...

    class DoublyEvenMagicSquare
    attr_reader :size

    def initialize(size)
    @size = size
    end

    def [](i, j)
    i, j = i % @size, j % @size
    value = (i * @size) + j + 1
    i, j = i % 4, j % 4
    ((i == j) || (i + j == 3)) ? (@size*@size+1-value) : value
    end
    end

    # ...

    Doubly even squares use an easy algorithm that can calculate a given value given
    just the coordinates. Because of that, no effort is made to pre-calculate the
    values here and all the work is done in the []() method.

    This algorithm divides the overall grid into two kinds of squares. One type is
    all squares that land on any diagonal created by subdividing the grid into four
    by four subgrids. All other squares make up the other type. Once you know
    which type of square you are dealing with, simple counting, from left to right
    and top to bottom, will give you the value of the square. Diagonal squares
    count down from the highest number and the other squares count up from one.

    We have one more algorithm to go:

    class SinglyEvenMagicSquare
    attr_reader :size

    L = [4, 1, 2, 3]
    U = [1, 4, 2, 3]
    X = [1, 4, 3, 2]

    def initialize(size)
    @size = size
    @odd_magic_square = MagicSquare.new(@size/2)
    end

    def [](i, j)
    i, j = i % @size, j % @size
    ii, jj = i / 2, j / 2
    center = @size / 2 / 2
    value = @odd_magic_square[ii, jj]
    case
    when ii < center then L
    when ii == center then (jj == center) ? U : L
    when ii == center+1 then (jj == center) ? L : U
    else X
    end [i%2*2 + j%2] + 4 * (value - 1)
    end
    end
    end

    # ...

    The final algorithm is the trickiest. You divide the grid into two by two
    subgrids. Each subgrid is assigned a letter: L, U, or X. The first (size - 2)
    / 4 + 1 rows are L's, there's one row of U's, and the rest of the rows are X's.
    You also swap the center U with the L just above it. The letters describe the
    order you fill subgrids. You can see these orders defined in constants at the
    top of David's class. The only other element you need to know is the order to
    fill in the subgrids. That is determined by building a size / 2 magic square
    using the odd pattern described early. The order of those numbers dictate the
    order the subgrids are filled in.

    The final piece of the puzzle is the application code:

    # ...

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

    This just builds and prints the correct square object from the choices we have
    been examining. Note that to_s() is called implicitly by puts().

    My thanks to all the brave souls who went above and beyond the quiz requirements
    to show us great solutions.

    Tomorrow we will play with some fractal fun...
    Ruby Quiz, May 24, 2007
    #1
    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,537
    Robert Kern
    Jun 1, 2005
  2. IchBin
    Replies:
    0
    Views:
    290
    IchBin
    Oct 17, 2007
  3. Ruby Quiz

    [SUMMARY] Magic Fingers (#120)

    Ruby Quiz, Apr 19, 2007, in forum: Ruby
    Replies:
    0
    Views:
    149
    Ruby Quiz
    Apr 19, 2007
  4. Ruby Quiz

    [QUIZ] Magic Squares (#124)

    Ruby Quiz, May 18, 2007, in forum: Ruby
    Replies:
    25
    Views:
    472
    Harry Kakueki
    May 26, 2007
  5. Giles Bowkett
    Replies:
    9
    Views:
    394
    Giles Bowkett
    Dec 17, 2007
Loading...

Share This Page