Forum: Ruby Number Spiral (#109)

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-01-18 15:38
(Received via mailing list)
I had trouble with this problem when it appeared on Code Golf.  It
seemed easy
enough but I just couldn't come up with a solid strategy.  Luckily, the
people
who solved this week's quiz are much smarter than me and I have learned
some
great tricks from them.

For our first approach, let's examine Bill Dolinar's code.  Bill
provided a
wonderful description of the algorithm he used in the comments of the
code, so
we can start there:

  Let item with value 0 be at x, y coordinate (0, 0).  Consider the
  spiral to be rings of numbers.  For the numbers 1 through 8 make
  up ring level 1, and numbers 9 through 24 make up ring level 2.
  To figure out the value at a particular x, y position, note that
  the first value at any level is (2 * level - 1) ** 2 and use that
  value to count up or down to the coordinate.

I suggest referring back to that description as we go.  It unlocks each
piece of
the code puzzle as you begin to take it all in.

Here's the beginning of the primary class:

  class Spiral

    def initialize(size)
      @size = size
      @center = size/2
    end

    # ...

You can see that a spiral stores both its size and the center point,
where
counting should begin.

Skipping ahead in the methods a little, let's see how the center is
used:

    # ...

    def coordinate_for(row, col)
      [col - @center, @center - row]
    end

    # ...

Remembering Bill's description, the zero cell of the spiral is suppose
to be
coordinate x = 0, y = 0.  The center is used to calculate this.  For
example,
here are the outputs of this method for the square right around the
center of a
size eight spiral:

  >> Spiral.new(8).coordinate_for(4, 4)
  => [0, 0]
  >> Spiral.new(8).coordinate_for(4, 5)
  => [1, 0]
  >> Spiral.new(8).coordinate_for(4, 3)
  => [-1, 0]
  >> Spiral.new(8).coordinate_for(5, 4)
  => [0, -1]
  >> Spiral.new(8).coordinate_for(3, 4)
  => [0, 1]

Note that the method parameters go in as a row then column, but come
back out as
an x coordinate followed by a y.

Now that we've seen the coordinate system, let's tackle the actual work
horse of
the class:

    # ...

    # returns the value for a given row and column of output
    def position_value(row, col)
      x, y = coordinate = coordinate_for(row, col)
      level = [x.abs, y.abs].max
      if x < level && y > -level
        first_number(level) +
            steps_between(first_coordinate(level), coordinate)
      else
        last_number(level) -
            steps_between(last_coordinate(level), coordinate)
      end
    end

    # ...

First we see the row and column switched into coordinates.  From
coordinates,
the ring level is determined.  (Glance back to Bill's description if you
need to
remember what that's for.)  The if statement then checks to see where we
are in
the current ring and either pulls the first number of the ring to count
up to
our location, or the last number to count down.  The result of either
process is
the value of the requested cell.

Here are the methods that give the first and last numbers of a ring:

    # ...

    def first_number(level)
      (2 * level - 1) ** 2
    end

    def last_number(level)
      first_number(level + 1) - 1
    end

    # ...

The first_number() method is right out of Bill's description.  For
last_number(), the code just calls first_number() for the next level and
subtracts one.

Similarly, here are the methods that calculate the coordinates of these
numbers:

    # ...

    def first_coordinate(level)
      [-level, -level + 1]
    end

    def last_coordinate(level)
      [-level, -level]
    end

    # ...

Armed with both pairs of methods, counting steps is just simple
subtraction:

    # ...

    def steps_between(point1, point2)
      (point1[0] - point2[0]).abs + (point1[1] - point2[1]).abs
    end

    # ...

Finally, the class provides one more convenience method for calculating
the
largest number in the spiral:

    # ...

    def maximum_value
      @size * @size - 1
    end
  end

  # ...

You see the minus one there because our spirals are zero-based.

Here's the code that puts that class to work solving the problem:

  # ...

  if __FILE__ == $0
    size = ARGV[0].to_i
    spiral = Spiral.new(size)
    width = spiral.maximum_value.to_s.length + 3
    (0...size).each do |row|
      (0...size).each do |col|
        print spiral.position_value(row, col).to_s.rjust(width)
      end
      print "\n\n"
    end
  end

Here we see the size pulled in from the command-line arguments, a Spiral
object
constructed, and a cell width calculated large enough to hold the
biggest number
plus some padding.  The code then walks each line, calculating and
printing each
cell.

Other solvers, had different approaches.  One such approach was based on
the
knowledge that an even sized spiral is just a smaller odd sized spiral
with an
extra number at the beginning of each row and a new row across the top.
Along
the same lines, and odd sized spiral is a smaller even sized spiral with
the
extra numbers at the ends of rows and along the bottom.  You can use
these facts
to recursively calculate numbers in the spiral.

Here's some code from Eric I. that does just that:

  def odd_spiral(size, row, col)
    if row == size - 1 : size**2 - 1 - col
    elsif col == size - 1 : (size - 1)**2 + row
    else even_spiral(size - 1, row, col)
    end
  end

  def even_spiral(size, row, col)
    if row == 0 : size**2 - size + col
    elsif col == 0 : size**2 - size - row
    else odd_spiral(size - 1, row - 1, col - 1)
    end
  end

  size = (ARGV[0] || 8).to_i
  (0...size).each do |row|
    (0...size).each do |col|
      v = size % 2 == 0 ? even_spiral(size, row, col) :
                          odd_spiral(size, row, col)
      print v.to_s.rjust((size**2 - 1).to_s.length), ' '
    end
    puts
  end

Starting with the odd_spiral() method, we see that it calculates the
extra last
row or column if we are in that, or recurses into the smaller even
spiral.  Then
even_spiral() builds the new first row or column when we are in that, or
recurses into the smaller odd spiral.

The rest of the code is pretty similar to Bill's version walking each
cell,
calculating the value, and printing the result with padding.

My thanks to all who showed me how this problem is actually done.  It's
a fun
little challenge and the submitted solutions capture that well.

Tomorrow we will play with run-time auto-completion for Ruby code...
James G. (Guest)
on 2007-09-26 00:34
(Received via mailing list)
On Jan 17, 2007, at 2:31 PM, Krishna D. wrote:

> My first submission to Ruby Q.:

Welcome and thanks for sharing.

James Edward G. II
Simon Kröger (Guest)
on 2007-09-26 00:39
(Received via mailing list)
William J. wrote:

>
> An invisible extra space is printed at the end of each line.


It may be invisible but it will void your solution on codegolf.com.

cheers

Simon
William J. (Guest)
on 2007-09-26 00:41
(Received via mailing list)
Simon Kröger wrote:
> >
> ruby 1.8.5 (2006-08-25) [i386-mswin32]
> 1...6
>
>
> cheers
>
> Simon

E:\Ruby>ruby -v
ruby 1.8.2 (2004-12-25) [i386-mswin32]

So it seems that this won't work without modification under 1.8.2.

As for making it shorter,
  change
puts f[w=gets(' ').to_i,gets.to_i].map{|i|['%3i']*w*' '%i}
  to
puts f[w=gets.to_i,$_[-3,2].to_i].map{|i|"%3d "*w%i}

An invisible extra space is printed at the end of each line.
This topic is locked and can not be replied to.