James Gray
1/18/2007 3:11:00 PM
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.