# Number Spiral (#109)

**URL:** <https://www.ruby-forum.com/t/number-spiral-109/82245>\
**Category:** Ruby\
**Created:** [January 18, 2007, 2:38pm UTC](https://www.ruby-forum.com/t/number-spiral-109/82245 "2007-01-18T14:38:32Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [January 18, 2007, 2:38pm UTC](https://www.ruby-forum.com/t/number-spiral-109/82245/1 "2007-01-18T14:38:32Z")

</div>

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…

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [September 25, 2007, 10:34pm UTC](https://www.ruby-forum.com/t/number-spiral-109/82245/2 "2007-09-25T22:34:50Z")

</div>

On Jan 17, 2007, at 2:31 PM, Krishna D. wrote:

> My first submission to Ruby Q.:

Welcome and thanks for sharing.

James Edward G. II

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [September 25, 2007, 10:39pm UTC](https://www.ruby-forum.com/t/number-spiral-109/82245/3 "2007-09-25T22:39:23Z")

</div>

William J. 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](http://codegolf.com).

cheers

Simon

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [September 25, 2007, 10:41pm UTC](https://www.ruby-forum.com/t/number-spiral-109/82245/4 "2007-09-25T22:41:39Z")

</div>

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.