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 : size2 - size + col
elsif col == 0 : size2 - 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…