From: Matthew Moss <matthew.moss.coder@...>
Date: 2006-06-26T01:23:11+09:00
Subject: Re: [QUIZ] pp Pascal (#84)

My first solution, a straightforward implementation that was
originally recursive, turned iterative:

def pascal n
   rows = []

   # generate data
   (0...n).each do |i|
      rows << if i.zero?
         [1]
      else
         rows[i-1].inject([0]) do |m, o|
            m[0...-1] << (m[-1] + o) << o
         end
      end
   end

   # calc field width
   width = rows[-1].max.to_s.length

   # space out each row
   rows.collect! do |row|
      row.collect { |x| x.to_s.center(2 * width) }.join
   end

   # display triangle
   rows.each { |row| puts row.center(rows[-1].length) }
end



My second solution, after reading some of the discussion, was an
attempt to not generate the whole tree in memory, but only one row at
a time:

class Integer
   def fact
      zero? ? 1 : (1..self).inject { |m, o| m * o }
   end

   def binom(k)
      self.fact / (k.fact * (self - k).fact)
   end
end

def pascal n
   # calc field width
   width = (n - 1).binom(n / 2).to_s.length

   # keep only one row in memory
   row = [1]

   1.upto(n) do |i|
      # print row
      space = ' ' * width * (n-i)
      puts space + row.collect { |x| x.to_s.center(2*width) }.join

      # generate next row
      row = row.inject([0]) { |m, o| m[0...-1] << (m[-1] + o) << o }
   end
end


Either solution started with:

pascal (ARGV[0] || 10).to_i


I could have done some error checking (i.e. bad input) or cached some
values for speed (Integer.fact and Integer.binom, particularly), but I
got lazy...