From: Ruby Quiz <james@...>
Date: 2006-06-29T21:51:43+09:00
Subject: [SUMMARY] pp Pascal (#84)

My wife, Dana, is the one working through Learning to Program and the reason I
added the note to the quiz.  Those watching the solutions will know that she did
submit, but she also told me in a private message:

	But I thought you should know that that problem was HARD!!!!!

I said in the quiz that you can do it with only the knowledge you've gained in
the first eight chapters, and you can, but it does involve some tricky steps
compared to the book problems.  If you decide to build up the triangle in memory
for example, you either need one long Array and some clever index work to
determine where rows start and stop or you need to work with nested Arrays. 
Nested Arrays have a single example in chapter eight and the only the briefest
of mentions, so that might be a bit of a leap.

However, if you hound your pet geek, he'll give you enough hints to get through
it.  Here's the proof, Dana Gray's solution:

	rows = ARGV[0].to_i
	triangle = []
	if rows >= 1
	 triangle.push([1])
	end
	if rows >= 2
	  triangle.push([1, 1])
	end
	last_row = [1, 1]
	
	count = 3
	while count <= rows
	  next_row = [1]
	  index = 0
	  while index < last_row.length - 1
	    next_row.push last_row[index]+last_row[index + 1]
	    index = index + 1
	  end
	  next_row.push(1)
	  triangle.push(next_row)
	  last_row = next_row
	  count = count + 1
	end
	
	number_length = last_row[last_row.length / 2].to_s.length
	triangle_length = last_row.length * number_length + last_row.length - 1
	triangle.each do |row|
	  final_row = []
	  row.each do | number|
	    final_row.push(number.to_s.center(number_length))
	  end
	  puts final_row.join(' ').center(triangle_length)
	end

The first line is the one I gave to handle the command-line argument.  I'm not
sure if Learn to Program ever covers those, but it hasn't by chapter eight. 
It's not too tricky though; ARGV is just an Array holding the arguments passed
to your program.

In the next couple of lines, Dana creates an Array to hold the triangle, and
pushes the first two rows (as long as we are going that far).  She then declares
the last_row shortcut, to save typing triangle[triangle.length - 1] all over the
place.  That's the only way Learn to Program has taught to fetch the last
element of an Array, by chapter eight.

In the middle section of code, Dana builds up Pascal's Triangle row by row.  The
code works by creating a next_row with the leading 1 already in it, walking the
last_row to add up numbers for next_row, and slotting the final 1.  Then,
last_row is replaced with next_row, so the next run of the loop will have the
new data to work with.

The final chunk of the code finds the length of the largest number in the
triangle and the length of the longest row in the triangle and then uses those
to print results.  Note that an extra Array is used here to copy the numbers
into while converting them to Strings and sizing them correctly, before the
result is join()ed and sent to the screen.

Dana's output doesn't exactly match the quiz examples, because only one space is
used to separate numbers where the quiz uses as many spaces as there are digits
in the largest number.  If we want to do that, we need to change the line length
calculation to account for the bigger spaces:

	triangle_length = last_row.length * number_length +
	                  (last_row.length - 1) * number_length

and add the extra spaces to the final output:

	  puts final_row.join(' ' * number_length).center(triangle_length)

Now, I have great news for all you Learn to Program students.  The more you
learn, the easier this problem gets.  You will be surprised how the code just
melts away.  To show what I mean, here's a solution from Matthew Moss using a
very similar process but with a couple of iterators not yet covered in the book:

	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
	
	pascal (ARGV[0] || 10).to_i

This is the same process we examined before, with less variable maintenance
work.  Here the triangle is built with some clever use of inject() that uses the
last slot of the row being built as a kind of short term memory that gets shaved
back off as it is used each time (note the ... in the 0 to -1 Range). 
Converting the rows is also much easier here, thanks to the collect() iterator.

Now, my good friend Greg Brown tells me real programmers use formulas to build
the triangle.  I'm just an imaginary programmer sadly, but Matthew Moss must be
real.  Here's another Matthew solution, this one filled with formula-slinging
code:

	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

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

What is of interest here are the fact() and binom() methods.  This is the
binomial coefficient formula that can be used to derive any number in the
triangle.

More interesting to me though, is that Matthew only uses this to fetch a single
number.  You can see that the first action of the pascal() method uses the
formula to conjure the middle element of the last row, for field width purposes.
Once you have that, you can build the triangle normally and print rows as you
go, as Matthew does here, because you have all the information you need to
format them correctly.

Now folks, those are only three solutions of over 50!  You should definitely
poke around in the others.  Make sure you catch the clever fixes people used to
clean up triangle output, like left justifying the left side while right
justifying the right side.  Don't miss the example that makes use of
multi-methods and certainly don't skip the first ever de-optimized Ruby Quiz
solution.  Fun tricks are hiding in so many of the solutions, you must give them
a glance.

My thanks to Pascal's fans who appear to be legion in numbers.

Tomorrow we will try something a little different.  Instead of celebrating
Ruby's niceties over other common languages, we will see if we can't dumb it
down a bit and put some of the limits back...