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

on 2007-01-18 14:38

on 2007-09-25 22:34

```
On Jan 17, 2007, at 2:31 PM, Krishna Dole wrote:
> My first submission to Ruby Quiz:
Welcome and thanks for sharing.
James Edward Gray II
```

on 2007-09-25 22:39

William James 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

on 2007-09-25 22:41

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.