From: James Edward Gray II <james@...>
Date: 2007-01-19T00:11:02+09:00
Subject: Fwd: Ruby Quiz 109 Summary

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
>   A  .  .  .  C
>   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.