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 M.
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 M.
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…
I’m kidding.