From: Derek Poon <dpoon@...>
Date: 2006-06-26T16:58:48+09:00
Subject: Re: [QUIZ] pp Pascal (#84)

This solution works pretty quickly.  On a P4 1.8 GHz:

   $ time ./pp_pascal.rb 185 > /dev/null
   real    0m0.412s
   user    0m0.368s
   sys     0m0.041s

Anything larger than 185 rows fails due to stack overflow.



######################################################################## 
#

class Pascal
   class << self
     # Entry of Pascal's Triangle (numbering rows and columns starting
     # from zero).
     def entry(row, col)
       @entry ||= []
       @entry[row] ||= [1]       # Base case: entry(any_row, 0) => 1

       if 2 * col > row          # Take advantage of symmetry
         entry(row, row - col)
       else                      # Recurse with memoization
         @entry[row][col] ||= entry(row - 1, col - 1) + entry(row -  
1, col)
       end
     end
   end

   attr_accessor :rows

   def initialize(rows)
     self.rows = rows
   end

   def to_s
     # Make each entry wide enough for the largest number and its  
padding
     max_entry = Pascal.entry(rows - 1, (rows - 1) / 2)
     entry_width = 2 + max_entry.to_s.length
     line_width = rows * entry_width

     (0...rows).collect do |row|
       (0..row).collect do |col|
         Pascal.entry(row, col).to_s.center(entry_width)
       end.join.center(line_width)
     end.join("\n")
   end
end

puts Pascal.new(ARGV[0].to_i)