Number Spiral (#109)
in [Ruby]
|
From: Josef 'Jupp' Schugt on 13 Jan 2007 18:48 * 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
From: Eric I. on 13 Jan 2007 20:08 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
From: Marcel Ward on 14 Jan 2007 10:13 On 12/01/07, Ruby Quiz <james(a)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)
From: Ben Ford on 14 Jan 2007 10:49 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...(a)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.rubyquiz.com/ > > 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/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
From: Martin DeMello on 14 Jan 2007 14:16
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(" ")} |