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.
4299e35bacef054df40583da2d51edea?d=identicon&s=25 James Gray (bbazzarrakk)
on 2007-05-24 14:19
(Received via mailing list)
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...
This topic is locked and can not be replied to.