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
on Ruby T. follow the discussion. Please reply to the original quiz
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

Marcel W. <wardies ^a-t^ gmaildotcom>

Sunday, 14 January 2007

Solution for Ruby Q. number 109 - Number Spiral

Prints a clockwise spiral, starting with zero at the centre (0,0).

Note, here x increases to the east and y increases to the north.

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
spirals that are not quadratic.

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.

However, addressing your narrower point, the sample output provided in
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

Script to print an N by N spiral as shown in the following example:

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

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.

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

add a number

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

Francesco Levorato aka flevour <flevour ^a-t^ gmaildotcom>

Sunday, 14 January 2007

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

sort of a hackish method to remove unwanted numbers from @left and

@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

this solution addresses clockwise from center to outside filling

method

my approach is based on the observation that each row of the matrix

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

the 3 following methods, h,l,d are were the funniest part of the

quiz: finding

the relationships intercurring between special elements of the

spiral.

they are used to build only the first (N/2 + 1) rows, as the other

ones are

built according only to the data structures @left and @right

to explain these 3 methods, define the following function

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

of the second part

of the row (the part containing the consecutive

numbers)

given a row number

returns the distance from the pivot to the first “spiral wall”

below it

subtracts 1 not to overlap with l(x) results

in a 8x8: given row 7 returns length from 54 down to 50

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

given a row number

returns the width of the next horizontal segment going from pivot

toward

the center of the spiral

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

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

given a row number, returns the difference between the pivot and

the number

just at its right

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
spirals that are not quadratic.

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

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) :slight_smile:
Only if you’re under windoze and you neglect to remove
the carriage-returns before uploading. Using vile, for example,
I do :set-unix-mode and save before uploading. If you’re not
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:

spiral.rb

RubyQuiz #109

Bob S.

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

This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.

| Privacy Policy | Terms of Service | Remote Ruby Jobs