Asp Forum - [QUIZ] Number Spiral (#109

James Gray

1/12/2007 2:30:00 PM

The three rules of Ruby Quiz:

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 Quiz by submitting ideas as often as you can:

http://www.rub...

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion. Please reply to the original quiz message,
if you can.

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

by Bob Showalter

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

[Editor's Note: This was also a code golf problem a few months back:
http://codegolf.com/oblongular-numb... --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

28 Answers

Josef 'Jupp' Schugt

1/13/2007 11:49:00 PM

* Ruby Quiz, 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

Eric I.

1/14/2007 1:08:00 AM

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 Quiz 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.

Josef 'Jupp' Schugt wrote:
> * Ruby Quiz, 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

Marcel Ward

1/14/2007 3:13:00 PM

On 12/01/07, Ruby Quiz <james@grayproductions.net> 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 Ward <wardies ^a-t^ gmaildotcom>
# Sunday, 14 January 2007
# Solution for Ruby Quiz 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 * x**2 - x - y
else # top side
4 * y**2 - 3 * y + x
end
else # bottom/left side
if x < y # left side
4 * x**2 - 3 * x + y
else # bottom side
4 * y**2 - y - x
end
end
end

spiral(10)

Eric I.

1/14/2007 3:36:00 PM

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| size**2 - 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

Ben Ford

1/14/2007 3:49:00 PM

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 = "%#{(n*n - 1).to_s.length+1}d"
if n % 2 == 0
@top_row = proc{|x| (x*(x-1)).upto(x*x-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

On Jan 12, 9:29 am, Ruby Quiz <j...@grayproductions.net> wrote:
> The three rules of Ruby Quiz:
>
> 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 Quiz by submitting ideas as often as you can:
>
> http://www.rub...
>
> 3. Enjoy!
>
> Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
> on Ruby Talk follow the discussion. Please reply to the original quiz message,
> if you can.
>
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
>
> by Bob Showalter
>
> (Taken from the puzzle by William Wu athttp://www.ocf.berkeley.edu/~wwu/riddle...)
>
> [Editor's Note: This was also a code golf problem a few months back:http://codegolf.com/oblongular-numb... --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

Eric I.

1/14/2007 4:07:00 PM

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

Martin DeMello

1/14/2007 7:16:00 PM

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(" ")}

Martin DeMello

1/14/2007 7:21:00 PM

On 1/15/07, Martin DeMello <martindemello@gmail.com> wrote:
> n = ARGV[0].to_i
> square = Array.new(n+2) { Array.new(n+2) }

oops - didn't read the question carefully enough. ignore.

m.

matthew.moss.coder

1/14/2007 7:25:00 PM

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)

Simon Kröger

1/14/2007 7:50:00 PM

Dear Ruby Quiz,

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-numb... 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

comp.lang.ruby

[QUIZ] Number Spiral (#109

James Gray

Josef 'Jupp' Schugt

Eric I.

Marcel Ward

Eric I.

Ben Ford

Eric I.

Martin DeMello

Martin DeMello

matthew.moss.coder

Simon Kröger

x Login to ForumsZone