From: Mike Nelson <miken700@...>
Date: 2006-06-27T07:03:35+09:00
Subject: Re: pp Pascal (#84) [SOLUTION]

# Pascal's Triangle (#84)
#   solution by Michael C Nelson
#
# The basic idea is that this takes advantage of the fact that empty 
cells can
# be represented as zeros. For example,
#
#             1                0 1 0
#            1 1   is like,   0 1 1 0
#           1 2 1            0 1 2 1 0
#          1 3 3 1            1 3 3 1
#
# In this way we can just populate the topmost 1 and basically get the 
other
# diagonal edge 1's for free just by going though each row below it one 
at a
# time, and for each cell adding the diagonal upper ones to that cell.
#
# This is taken a step further in that the spaces between each number 
can be
# zeros as well, like,
#
#             1
#            101
#           10201
#          1030301
#
# Since these are zeros as well we can sum up all the spaces in between 
them as
# well, because they will all turn out to be zero in the end. This makes 
the
# code a bit simpler.
#
# Also the zeros are not explicitly set but are implemented in the 
hash's
# default value block (each row is a hash). This also handles values 
outside of
# the specified size range and returns 0 to handle edge cases for the 
final
# row. Also this handles mirroring of the pyramid as only the left half
# (including the middle column) is stored in the hash rows. This allows 
the
# filling out of the pyramid section to only operate on the left half as 
an
# optimization.
#
# When printed, all zeros are displayed as spaces, to make the final 
printout
# of the pyramid.
#
#             1                     000010000
#            1 1   is really like,  000101000
#           1 2 1                   001020100
#          1 3 3 1                  010303010
#
# Also note that the 'size' defined for the hight of the pyramid is also 
the
# same as the width of half the pyramid plus the middle, this is used
# interchangeably in the code.

# get the size from the command line, or use default, helped in testing
size =  (ARGV[0] || 10).to_i
total_width = 2*size-1

# Build an empty pyramid. Only half of the pyramid is held in the Array 
of
# Hashes, the right half is just a mirror of the left.
pascal = (0..size).map do
  Hash.new do |hash, key|
    if key > size && key <= total_width
      # mirror it
      hash[2*size-key]
    else
      # for everything else we can't find return zero
      0
    end
  end
end

# Seed the pyramid (this is the topmost middle "1").
pascal[0][size] = 1

# Build out the pyramid starting from the top down to the bottom. This
# optimizes a bit by only adding one half of the pyramid, which is 
mirrored by
# the Array of Hashes. Also, this only adds the area in the pyramid in 
order to
# avoid adding a bunch of zeros in the upper unused sections (there is 
still a
# bunch of zero adding within the pyramid but this makes the code a bit
# simpler). Note:  this could add the whole area and it would still 
work.
cell_width = 0
(1...size).each do |y|
  (size-y..size).each do |x|
    value = pascal[y-1][x-1] + pascal[y-1][x+1]
    unless value.zero?
      pascal[y][x] = value
      cell_width = value.to_s.length if cell_width < value.to_s.length
    end
  end
end

# Print out the result based on the cell_width.
(0...size).each do |y|
  (1..total_width).each do |x|
    if pascal[y][x].zero?
      print " "*cell_width
    else
      printf("%#{cell_width}d", pascal[y][x])
    end
  end
  print "\n"
end

-- 
Posted via http://www.ruby-forum.com/.