Ruby Quiz 109 Summary

[James_Edward_Gray_II]

I made a huge mistake this morning and summarized a quiz that Bob wanted to do himself. I'm so sorry about that.

Here's Bob's summary and I will get it on the site shortly...

James Edward Gray II

···

Begin forwarded message:

From: "Bob Showalter" <showaltb@gmail.com>
Date: January 18, 2007 8:53:36 AM CST
To: "James Edward Gray II" <james@grayproductions.net>
Subject: Ruby Quiz 109 Summary

James,

Here is my summary for the Number Spiral quiz. Thanks, Bob

RubyQuiz 109
Number Spiral

Summary

This was an interesting little puzzle, because it isn't immediately obvious
just how to write out a spiral line by line. The rule against building up the
data in an array was intended to make it bit more challenging, although I'm
not sure using an array simplifies things all that much.

The solutions tended to fall into one of two groups, each taking a different
approach to the problem. The first group noticed that a spiral of any given
order contained within it all the spirals of lower orders. So, a 4x4 spiral
contains the 3x3, which in turn contains the 2x2, and so on. This leads to a
recursive algorithm.

The other group derived a function that could generate the number to be
emitted for any "cell", given the order of the spiral and the cell's row and
column.

Krishna Dole's compact solution is an example of the latter approach. Let's
analyze his algorithm:

He defines a method called spiral, which takes a pair of coordinates that are
relative to the center of the spiral. At this point, I'm not sure what the
method does; we'll have to get to that later. I note that it doesn't take the
order of the spiral as a parameter, so we'll have to see how he's handling
that.

The main program looks like this:

n = ARGV[0].to_i

for row in 0..(n - 1)
   puts (0..(n - 1)).map{|col|
     spiral(col - (n / 2), (n / 2) - row).to_s.rjust(4) }.join
end

The first line sets n to the "order" of the spiral as taken from the command
line argument. So n=5 would mean a 5x5 spiral.

The for loop iterates over the rows of the spiral, starting at 0. So for our
5x5 spiral, we would have rows 0, 1, 2, 3, and 4.

The next two lines pack a lot into a small space. If we ignore the call to
spiral for a moment, it looks like this:

puts (0..(n - 1)).map{|col| ... }.join

The map operation iterates over the columns of the spiral (e.g. 0 through 4),
setting the variable col to the column number. The results of the block (i.e.
whatever the code represented by the ellipsis does) are concatenated by join
into a single string and then written out (followed by a newline) by puts.

So we know that the code in the elipsis must give us a single "cell", and
these cells are strung together to make a row, which is output. Looking back
at the original code, we can see that the return from spiral is converted to a
string and right-justified in a 4-character field. So the return from spiral
is the number to be written in the current cell.

OK, so lets look at how he calculates the number to go in a cell. Remember,
when spiral is called, row is the current row number (0=top) and col is the
current column number (0=left). The call to spiral looks like:

  spiral(col - (n / 2), (n /2) - row)

(n / 2) is a constant. It's half the size of the spiral. Note that
because n is an Integer, (n / 2) is also an Integer, so a value of 5
for n would yield 2 for (n / 2), and not 2.5.

Remember the comment in the code above the definition of spiral? It told us
that the coordinates were relative to the center of the spiral. So this code
is adjusting the row and col values to be relative to the center. The top-left
corner of our 5x5 spiral would be row=0 and col=0. The values passed to spiral
would be

  x = col - (n / 2)
    = 0 - (5 / 2)
    = 0 - 2
    = -2

  y = (n / 2) - row
    = (5 / 2) - 0
    = 2 - 0
    = 2

The subtraction is reversed for the y coordinate so that y values increase
moving "up" the screen even though row values increase moving "down".

Why make the coordinates relative to the center of the spiral? Because for any
given (x, y) pair relative to the center of the spiral, the number to be
output at that position is the same, *regardless of the order of the spiral*.
So that is why we don't see the order referenced in the spiral method: it
isn't needed.

OK, now it's time to figure out how the spiral method does its magic. Krishna
starts by computing two values max_xy, and offset:

max_xy = [x,y].collect{|num| num.abs}.max
offset = (max_xy * 2 - 1)**2 - 1

max_xy is obviously the larger of x or y, considered in absolute terms. If you
think of the spiral as a set of concentric "rings" surrounding the digit zero,
max_xy would tell us which "ring" we are on. This is part of the key to the
algorithm: he doesn't treat the spiral as a spiral at all, but as a set of
rings. For a spiral of odd order, the rings are completely filled in; for a
spiral of even order, the outermost ring is only partially filled.

Each ring is a sequence of numbers. Here are the sequences for the first few
"rings":

max_xy=0 0
max_xy=1 1..8
max_xy=2 9..24
max_xy=3 25..48

offset is simply one less than the starting value of each ring. So for
max_xy=3, offset is 24.

The remainder of the code is an "if" statement that evaluates to the number to
be output for the curent cell. It computes this by treating the "ring" as a
sequence of four "legs", and computing the value given the "leg" and position
within the leg. For the outermost ring of a 5x5 spiral, the "legs" look like
this:

  A B B B B
  A . . . C
  D D D D C

The different branches of the if statement handle each leg. Let's consider the
bottom-most "A" cell of this ring. It would have the coordinates (-2, -1). The
code for this leg is:

if -(x) == max_xy and x != y
   y + offset + max_xy

The test is true, because -(-2) == 2 and -2 != -1. So the value is (-1) + 24 +
2, or 25. The calculations for the remaining legs proceed in a similar manner.