From: flevour <flevour@...>
Date: 2007-01-15T07:30:06+09:00
Subject: [QUIZ] Number Spiral (#109) [solution]

Hi all!
This is my first partecipation to Ruby Quiz. 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 Quiz 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