by Dirk Meijer
I recently showed a friend what an amazing language Ruby was, by quickly programming up a script to calculate Fibonacci's Sequence, and his first response was: "Can you do Pascal's Triangle?" So I did, which proved harder than expected.
For those not familiar with Pascal's Triangle, it is very similar to Fibonacci's Sequence. It's a pyramid of numbers. The outside of the pyramid is all ones, the other numbers are the sum of the two numbers above, like this:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
The input and output should be as follows:
$ ruby pp_pascal.rb 10
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
A number should be given as command-line argument. This is the amount of rows the triangle has. For the output, there should be spacing between the numbers based on the size of the numbers with the most digits, so it will look like a proper triangle.
Good luck!
[Editor's Note: If you are working through Chris Pine's Learn to Program, you can do this problem using only things you learned in the first eight chapters. Since he doesn't teach how to grab the row count in those pages though, just add this as the first line of your program: `rows = ARGV[0].to_i`. After that, the rows variable will hold the number of rows to print. --JEG2]
Quiz Summary
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:
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:
(last_row.length - 1) * number_length
and add the extra spaces to the final output:
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:
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:
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...
