# Number Spiral (#109)

The three rules of Ruby Q.:

1. Please do not post any solutions or spoiler discussion for this quiz
until
48 hours have passed from the time on this message.

2. Support Ruby Q. by submitting ideas as often as you can:

http://www.rubyquiz.com/

1. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps
everyone
message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Bob S.

(Taken from the puzzle by William Wu at
http://www.ocf.berkeley.edu/~wwu/riddles/cs.shtml)

[Editor’s Note: This was also a code golf problem a few months back:
http://codegolf.com/oblongular-number-spirals --JEG2]

Write a Ruby program to print out a “spiral” of numbers that fill a NxN
square.
Your program will take a single argument to specify the dimensions of
the square
(1 or higher). The number zero represents the center of the spiral, and
the
succeeding integers spiral out in a clockwise (or counterclockwise; your
choice)
direction from the center until the square is filled.

Your program should write the output line by line, without using an
array to
build up the data first.

Here’s the output for an 8x8 spiral:

56 57 58 59 60 61 62 63

55 30 31 32 33 34 35 36

54 29 12 13 14 15 16 37

53 28 11 2 3 4 17 38

52 27 10 1 0 5 18 39

51 26 9 8 7 6 19 40

50 25 24 23 22 21 20 41

49 48 47 46 45 44 43 42

On 12/01/07, Ruby Q. [email protected] wrote:

Write a Ruby program to print out a “spiral” of numbers that fill a NxN square.
Your program will take a single argument to specify the dimensions of the square
(1 or higher). The number zero represents the center of the spiral, and the
succeeding integers spiral out in a clockwise (or counterclockwise; your choice)
direction from the center until the square is filled.

Your program should write the output line by line, without using an array to
build up the data first.

Ok, I like a challenge and my maths needed some dusting down.

Here is my solution, after a fair bit of scribbling on paper to work
out the formula for sprial_value_at(x,y).

I found it a bit frustrating that ranges in Ruby can only be
ascending; but soon found that we have #downto, which achieves the
desired result.

Thanks to Bob & James for setting this quiz.

Marcel

#! /usr/bin/env ruby

def spiral(size)

# maximum -ve/+ve reach from the centre point “0” at (0,0)

neg_reach = -pos_reach = size/2

# we miss out the bottom/left sides for even-sized spirals

neg_reach += 1 if size % 2 == 0

# Compute width to allocate a cell based on the max value printed

cell_width = (size**2 - 1).to_s.size + 3

pos_reach.downto(neg_reach) do
|y|
spiral_line((neg_reach…pos_reach), y, cell_width)
end
end

def spiral_line(x_range, y, cell_width)
x_range.each do
|x|
print spiral_value_at(x, y).to_s.center(cell_width)
end
puts
end

# calculate the value in the spiral at location (x,y)

def spiral_value_at(x, y)
if x + y > 0 # top/right side
if x > y # right side
4 * x2 - x - y
else # top side
4 * y
2 - 3 * y + x
end
else # bottom/left side
if x < y # left side
4 * x2 - 3 * x + y
else # bottom side
4 * y
2 - y - x
end
end
end

spiral(10)

• Ruby Q., 01/12/2007 03:29 PM:

The number zero represents the center of the spiral

Let me suggest that you address the issue of the centre being
ill-defined under the condition that the number of columns/rows is
even. Given that altogether four positions meet the condition leaving
this question open will result in a multitude of different outputs
that are solutions of the task. In my opinion a programming quiz
should use a well-posed problem so that the different programs can be
compared directly. Especially if the problem can be solved by
constructing a clever mathematical formula which my intuition suggest
to be the case with the number spiral problem (I did not yet try to
verify this).

Jupp

Dear Ruby Q.,

this isn’t really a solution to the quiz 109 because it violates
some (if not all) of the rules. But as James noted there was a
code golf problem very similar to this quiz and here is my
solution to that.
(see http://codegolf.com/oblongular-number-spirals for detailed
description of the code golf problem)

## s,f=1,proc{|x,y|y<1?[]:[[*s…s+=x]]+f[y-1,x].reverse.transpose} puts f[w=gets(’ ‘).to_i,gets.to_i].map{|i|[’%3i’]w’ '%i}

It draws a number spiral, starting with ‘1’ in the upper left
corner and the highest number in the middle, it also features

Yes, you will get some score at the codegolf site if you repost
this solution there - but nowadays you will only get to Rank 9
with this solution and of course you will start to feel ill and
you won’t be able to sleep for days and other nasty things might
happen if you do so.

If someone can derive an even shorter solution from this i would
be very interested to see it (the best ruby solution today has 7
bytes less)

cheers

Simon

Quiz #109 even leaves it up to the implementer whether to go clockwise
or counter-clockwise. So it’s designed to have some flexibility in it.
In fact, it’s typical of the Ruby Q. to define a core problem and
leave many of the details up to the individual implementers. And given
that the Quiz is designed to enhance understanding and appreciation of
Ruby (and not to be an exam or contest) that seems reasonable.

the quiz statement does use an even number (8) to define the size. And
as you can see from the sample output, the 0 is located just to the
right and just below the exact center. So you could reasonably use
that to nail down that detail.

Eric

================

Hands-on Ruby training at your location is available from
www.LearnRuby.com . Read reviews from actual students there.

My second attempt/solution… Slightly different in that it does a
counter-clockwise spiral, but basically follows a similar idea as my
previous solution, though I think this looks nicer.

N = ARGV[0].to_i
FW = (N ** 2 - 1).to_s.size + 2

def fmt(x)
" " * (FW - x.to_s.size) + x.to_s
end

def o(n, r, c)
x = (n - 1) ** 2
if c == 0 then x + r
elsif r == n - 1 then x + r + c
else e(n - 1, r, c - 1)
end
end

def e(n, r, c)
x = (n ** 2) - 1
if r == 0 then x - c
elsif c == n - 1 then x - c - r
else o(n - 1, r - 1, c)
end
end

def spiral(n)
(0…n).map do |r|
if (n % 2).zero? # even
(0…n).map { |c| fmt(e(n, r, c)) }
else
(0…n).map { |c| fmt(o(n, r, c)) }
end.join
end.join("\n")
end

puts spiral(N)

Here’s my solution to the quiz. I used a recursive solution. An
odd-sized spiral is the smaller-by-one even-sized spiral with a number
added to the end of each row, and a new row across the bottom. And an
even-sized spiral is the smaller-by-one odd-sized spiral with a number
added to the beginning of each row and a new row across the top.

I decided to make my solution use relatively few lines of code.
However in doing that I added some inefficiencies, where a value might
be calculated multiple times in a loop/iterator when it would have been
better to calculate it once before the loop/iterator, and use that
stored value in the loop/iterator.

With respect to not building the solution in an array and then
displaying the array, I read that to mean not creating a
two-dimensional array (i.e., array of arrays) in which to build the
entire spiral. I assemble each line of output in an array before
displaying that line, but each line is displayed before any subsequent
lines are calculated. The solution could be adapted to avoid even the
one-dimensional array.

## Eric

Interested in on-site, hands-on Ruby training? At www.LearnRuby.com
you can read previous students’ reviews!

================

def odd_spiral(size, row)
if row < size - 1 : even_spiral(size - 1, row) << (size - 1)2 + row
else (0…size).collect { |n| size
2 - 1 - n }
end
end

def even_spiral(size, row)
if row == 0 : (0…size).collect { |n| size2 - size + n }
else odd_spiral(size - 1, row - 1).unshift(size
2 - size - row)
end
end

size = (ARGV[0] || 8).to_i
(0…size).each do |row|
puts ((size % 2 == 0 ? even_spiral(size, row) : odd_spiral(size,
row)).
map { |n| n.to_s.rjust((size**2 - 1).to_s.length) }.join("
"))
end

#!/usr/bin/env ruby

# value to count up or down to the coordinate.

class Spiral

def initialize(size)
@size = size
@center = size/2
end

# 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
# return number for top left portion of ring
first_number(level) +
steps_between(first_coordinate(level), coordinate)
else
last_number(level) -
steps_between(last_coordinate(level), coordinate)
end
end

def maximum_value
@size * @size - 1
end

def first_number(level)
(2 * level - 1) ** 2
end

def last_number(level)
first_number(level + 1) - 1
end

def first_coordinate(level)
[-level, -level + 1]
end

def last_coordinate(level)
[-level, -level]
end

def coordinate_for(row, col)
[col - @center, @center - row]
end

def steps_between(point1, point2)
(point1[0] - point2[0]).abs + (point1[1] - point2[1]).abs
end
end

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

n = ARGV[0].to_i
square = Array.new(n+2) { Array.new(n+2) }

# boundaries

(n+1).times {|i|
square[i][0] = square[i][n+1] = square[0][i] = square[n+1][i] = 0
}

dirs = [[1, 0], [0, -1], [-1, 0], [0, 1]]

# spiral inwards from a corner

x, y, i, d = 1, 1, n*n - 1, 0

while i >= 0 do

square[x][y] = i

# move to the next square in line

x += dirs[d][0]
y += dirs[d][1]
if square[x][y]
# if it is already full, backtrack
x -= dirs[d][0]
y -= dirs[d][1]
# change direction
d = (d - 1) % 4
# and move to the new next square in line
x += dirs[d][0]
y += dirs[d][1]
end
i -= 1
end

# remove the boundaries

square.shift; square.pop
square.map {|i| i.shift; i.pop}

puts square.map {|i| i.map {|j| “%02s” % j}.join(" ")}

Here is my solution. I used a recursive printing routine to handle the
insides of the middle rows.

Ben

class NumberSpiral
def initialize(n)
@size = n
@format = "%#{(nn - 1).to_s.length+1}d"
if n % 2 == 0
@top_row = proc{|x| (x
(x-1)).upto(xx-1) {|i| print_num(i) } }
@bottom_row = proc{|x| ((x-1)
(x-1)).downto((x-1)(x-2)) {|i|
print_num(i) } }
@middle_first = proc{|x,row| print_num(x
(x-1)-row) }
@middle_last = proc{|x,row| print_num((x-2)(x-2)-1+row) }
else
@top_row = proc{|x| ((x-1)
(x-2)).upto((x-1)(x-1)) {|i|
print_num(i) } }
@bottom_row = proc{|x| (x
x-1).downto(x*(x-1)) {|i| print_num(i)
} }
@middle_first = proc{|x,row| print_num((x-1)(x-2)-row) }
@middle_last = proc{|x,row| print_num((x-1)
(x-1)+row) }
end
end

def print_num(i)
printf @format, i
end

def print_row(size, row)
if row == 0
@top_row.call(size)
elsif row == size - 1
@bottom_row.call(size)
else
@middle_first.call(size, row)
print_row(size-2, row-1)
@middle_last.call(size, row)
end
end

def print_clockwise
@size.times {|i| print_row(@size, i) ; puts ; puts if i < @size-1 }
end
end

if ARGV.size == 0 or not ARGV[0] =~ /^\d+\$/
puts “Usage: #\$0 N”
puts “Output: Prints a “spiral” of numbers that fill a NxN
square.”
else
NumberSpiral.new(ARGV[0].to_i).print_clockwise
end

My first attempt… A recursive solution recognizing than a spiral of
even dimension can be formed by a top row, a left column, and an odd
spiral. Likewise, an odd spiral is a smaller even spiral with a right
column and bottom row.

The functions erow and orow reflect the even/odd-ness of the spiral,
not the row.

DIM = ARGV[0].to_i
FLD = (DIM ** 2 - 1).to_s.size + 2

def fmt(x)
" " * (FLD - x.to_s.size) + x.to_s
end

def orow(n, i)
m = n ** 2
x = m - n

if i == n - 1
(1…n).inject("") { |o, v| o + fmt(m - v) }
else
erow(n - 1, i) + fmt(x - n + i + 1)
end
end

def erow(n, i)
m = n ** 2
x = m - n

if i == 0
(0…n).inject("") { |o, v| o + fmt(x + v) }
else
fmt(x - i) + orow(n - 1, i - 1)
end
end

def spiral(n)
if (n % 2).zero?
n.times { |i| puts erow(n, i) }
else
n.times { |i| puts orow(n, i) }
end
end

spiral(ARGV[0].to_i)

Hi all!
This is my first partecipation to Ruby Q… I developed a pretty messy
solution for clockwise (ck) solution. When I started to tackle the
counter-ck solution I started messing around with lambdas everywhere,
but eventually I found out that I just could reverse each line of a ck
solution to have the correct output. Also I didnt code the ck/cck
picking part, so you need to change it manually in initialize
My approach is still of the kind “over-use all the power of the
language” to crack the solution instead of a more reccomendable
mathematical one. But there is time to it.
I tried to comment my code extensively, maybe to understand it you need
to go through the example spiral output and check what it does …
I loved all the really compact solutions that have been posted so far,
keep them coming!
This community just rocks!
Take care you all!
Francesco Levorato aka flevour

#! /usr/bin/env ruby

# Solution for Ruby Q. number 109 - Number Spiral

class Array
def decrease_all
self.map! { |x| x = x - 1}
end
def increase_all
self.map! { |x| x = x + 1}
end
def enqueue(x)
self.insert(0, x)
end

@right

# i haven’t figured out a valid reason to explain why i need to

remove these values

# but otherwise things won’t work and I haven’t time to think more on

the topic
def delete_invalid
self.map! {|x| (x > 1) ? x : nil}
self.compact!
end
end

class NumberSpiral

method

is composed

# of 3 parts: 0 or more columns, a series of consecutive numbers, 0

or more columns
def initialize(n, direction = :ck)
@n = n
@dim = @n*@n
# left contains the first part of a row
# right contains the third part of a row
# in a 8x8: if the row is 54,29,12,13,14,15,16,37
# left: [54, 29], right: [37]
@left = []
@right = []
# just wanted to try out this block thingie Ruby is so famous about
@format = Proc.new { |x| print sprintf("%3s", x.to_s + " ") }
@direction = direction # :ck or :cck
end

quiz: finding

spiral.

ones are

# pivot(row): returns the number at given row just before the start

of the second part

numbers)

below it

def h(x)
2*x - @n - 1
end

toward

# in a 8x8: given row 6 returns length from 25 to 20

def l(x)
2 * ( x + 1 ) - @n
end

the number

# in a 8x8: given 7 returns the difference between 55 and 30

def d(x)
2 * ( l(x) + h(x) ) - 1
end

def print_me
row = @n
start = @dim - @n
# prints first row
print_row(consecutive_numbers(start))
print “\n”

``````# prepare for loop
pivot = start - 1
@left << pivot

# prints the top rows, it stops after printing the row containing
``````

the zero
while(pivot >= 0) do
row = row - 1
pivot = pivot - d(row)

``````  # gets middle consecutive numbers
middle = consecutive_numbers(pivot)
print_row(middle)

@left << pivot
@left.decrease_all

@right.enqueue(middle.last) # last number of consecutive series
``````

will be in the right part in next iteration
@right.increase_all

``````  pivot = @left.last
print "\n"
end

@left.delete_invalid
@right.delete_invalid
row = row -1

# prints the remainder of the spiral
while(row > 0) do
from= @left.pop

middle = consecutive_numbers(from, :down)
last_printed = middle.last
print_row(middle)

@right.delete_at(0)

@left.decrease_all
@right.increase_all
row = row - 1
print "\n"
end
``````

end

def consecutive_numbers(n, go = :up)
array = []
(@n - @left.size - @right.size).times do
array << n
if go == :up
n = n + 1
else # go == :down
n = n - 1
end
end
array
end

def print_row(middle)
if @direction == :ck
(@left + middle + @right).each(&@format)
else
(@left + middle + @right).reverse.each(&@format)
end
end
end

if ARGV[0]
NumberSpiral.new(ARGV[0].to_i).print_me
else
puts “Call me: #{\$0} <matrix_dim>\n”
end

Simon Kröger wrote:

s,f=1,proc{|x,y|y<1?[]:[[*s…s+=x]]+f[y-1,x].reverse.transpose}
you won’t be able to sleep for days and other nasty things might
happen if you do so.

If someone can derive an even shorter solution from this i would
be very interested to see it (the best ruby solution today has 7
bytes less)

A reduction:

[“stuff”]+[[4,5,6],[:x,:y,:z]].reverse.transpose
==>[“stuff”, [:x, 4], [:y, 5], [:z, 6]]
[“stuff”]+(a,b=[[4,5,6],[:x,:y,:z]];b.zip a)
==>[“stuff”, [:x, 4], [:y, 5], [:z, 6]]

Simon Kröger wrote:

s,f=1,proc{|x,y|y<1?[]:[[*s…s+=x]]+f[y-1,x].reverse.transpose}
This is more obfuscated than

s=1
f=proc{|x,y|y<1?[]:[[*s…s+=x]]+f[y-1,x].reverse.transpose}

and is no shorter.

## puts f[w=gets(’ ‘).to_i,gets.to_i].map{|i|[’%3i’]w’ '%i}

It draws a number spiral, starting with ‘1’ in the upper left
corner and the highest number in the middle, it also features

Yes, you will get some score at the codegolf site if you repost
this solution there

If the site accepted this, then it wasn’t tested thoroughly
enough. ‘%3i’ gives every number-spiral a column-width
of 3; the column-width should equal the width of the
largest number.

William J. wrote:

s,f=1,proc{|x,y|y<1?[]:[[*s…s+=x]]+f[y-1,x].reverse.transpose}

This is more obfuscated than

s=1
f=proc{|x,y|y<1?[]:[[*s…s+=x]]+f[y-1,x].reverse.transpose}

and is no shorter.

depends on your line end character(s)

If the site accepted this, then it wasn’t tested thoroughly
enough. ‘%3i’ gives every number-spiral a column-width
of 3; the column-width should equal the width of the
largest number.

Well, consider it cheating, most spirals have a column width of
3 - so you may have to post it twice to have it accepted.

cheers

Simon

Simon Kröger wrote:

depends on your line end character(s)
Only if you’re under windoze and you neglect to remove
doing this, then you are really hurting your score.

By the way, in the ASCII Art contest I got the size
down to 76. I would pay to see how “flagitious” did it
in 71 bytes!

If the site accepted this, then it wasn’t tested thoroughly
enough. ‘%3i’ gives every number-spiral a column-width
of 3; the column-width should equal the width of the
largest number.

Well, consider it cheating, most spirals have a column width of
3 - so you may have to post it twice to have it accepted.

The site really should do more thorough testing.

Here’s the solution I came up with before submitting this idea:

class Integer

def odd?
self % 2 == 1
end

end

class Spiral

# order must be > 0

def initialize(order)
raise ArgumentError, “order must be > 0” unless order.to_i > 0
@order = order
end

# writes the spiral to stdout

def output
puts “\n”
0.upto(@order - 1) do |r|
row_for(@order, r)
puts “\n\n”
end
end

private

# emits row r for spiral of order p

def row_for(p, r)
if p <= 1
cell(0)
elsif p.odd?
if r == p - 1
row§
else
row_for(p - 1, r)
col(p, r)
end
else
if r == 0
row§
else
col(p, r)
row_for(p - 1, r - 1)
end
end
end

# emits the full row (top or bottom) for spiral of order p

def row§
x = p * (p - 1)
y = x + p - 1
x.upto(y) {|i| cell(p.odd? ? x - i + y : i) }
end

# emits the single column cell for row r of spiral of order p

def col(p, r)
x = p * (p - 1)
r = p - r - 1 if p.odd?
cell(x - r)
end

# emits a single cell

def cell(i)
printf ’ %3d ', i
end

end

n = (ARGV.first || 3).to_i
Spiral.new(n).output

Simon Kröger wrote:

s,f=1,proc{|x,y|y<1?[]:[[*s…s+=x]]+f[y-1,x].reverse.transpose}
you won’t be able to sleep for days and other nasty things might
happen if you do so.

If someone can derive an even shorter solution from this i would
be very interested to see it (the best ruby solution today has 7
bytes less)

cheers

Simon

I can’t get this to work.

E:\Ruby>ruby try.rb
4 4
try.rb:2:in `%': too few arguments. (ArgumentError) from try.rb:2 from try.rb:2:in`map’
from try.rb:2

Here’s a modified version of my previous solution that uses no arrays
other than ARGV. For the general approach, see the discussion in my
previous posting. And please note that it’s written to favor brevity
over clarity.

Eric

On-site, hands-on Ruby training is available from www.LearnRuby.com !

================

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

Here is my solution:

n = (ARGV[0] || 8).to_i
(0…n).each do |row|
lev = (row-n/2).abs
m = [2lev+1,n].min
p = (n-m+1)/2
(0…p).each do |col|
s = (n/2-col)2
s = s
(s-1)-(row-col)
printf "%2d ",s
end
delta = n/2<=>row
s = lev
2
s *= (s-delta)
s += m-1 if delta<0
m.times do
printf "%2d ",s
s += delta
end
(0…n-p-m).each do |col|
s = (lev+col+1)2
s = s
(s+1)-(p+m+col-row)
printf "%2d ",s
end
puts
end