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…