I had trouble with this problem when it appeared on Code Golf. It
enough but I just couldn’t come up with a solid strategy. Luckily, the
who solved this week’s quiz are much smarter than me and I have learned
great tricks from them.
For our first approach, let’s examine Bill Dolinar’s code. Bill
wonderful description of the algorithm he used in the comments of the
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
the code puzzle as you begin to take it all in.
Here’s the beginning of the primary class:
def initialize(size) @size = size @center = size/2 end # ...
You can see that a spiral stores both its size and the center point,
counting should begin.
Skipping ahead in the methods a little, let’s see how the center is
# ... def coordinate_for(row, col) [col - @center, @center - row] end # ...
Remembering Bill’s description, the zero cell of the spiral is suppose
coordinate x = 0, y = 0. The center is used to calculate this. For
here are the outputs of this method for the square right around the
center of a
size eight spiral:
=> [0, 0]
=> [1, 0]
=> [-1, 0]
=> [0, -1]
=> [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
# ... # 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
the ring level is determined. (Glance back to Bill’s description if you
remember what that’s for.) The if statement then checks to see where we
the current ring and either pulls the first number of the ring to count
our location, or the last number to count down. The result of either
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
Similarly, here are the methods that calculate the coordinates of these
# ... 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
# ... def steps_between(point1, point2) (point1 - point2).abs + (point1 - point2).abs end # ...
Finally, the class provides one more convenience method for calculating
largest number in the spiral:
# ... def maximum_value @size * @size - 1 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.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)
Here we see the size pulled in from the command-line arguments, a Spiral
constructed, and a cell width calculated large enough to hold the
plus some padding. The code then walks each line, calculating and
Other solvers, had different approaches. One such approach was based on
knowledge that an even sized spiral is just a smaller odd sized spiral
extra number at the beginning of each row and a new row across the top.
the same lines, and odd sized spiral is a smaller even sized spiral with
extra numbers at the ends of rows and along the bottom. You can use
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)
def even_spiral(size, row, col)
if row == 0 : size2 - size + col
elsif col == 0 : size2 - size - row
else odd_spiral(size - 1, row - 1, col - 1)
size = (ARGV || 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), ’ ’
Starting with the odd_spiral() method, we see that it calculates the
row or column if we are in that, or recurses into the smaller even
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
calculating the value, and printing the result with padding.
My thanks to all who showed me how this problem is actually done. It’s
little challenge and the submitted solutions capture that well.
Tomorrow we will play with run-time auto-completion for Ruby code…