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 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…

Kudos to Dana ! I really like Learning to Program though as some here
know, the “rite to passage” (sorting with 3 arrays) is killing me ,
literally :).

Stuart

Ruby Q. [email protected] writes:

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 Q. solution. Fun
tricks are hiding in so many of the solutions, you must give them a
glance.

Well, I know which one is the de-optimized solution, because I wrote
it ([ruby-talk:199337]), but which one is the multi-method solution?

Personally, I’m still disentangling the abuse of inject that is Kelly
Norton’s solution ([ruby-talk:199444])

On 6/29/06, Ruby Q. [email protected] wrote:

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:

All that Ruby is pretty interesting, but far more interesting is that
you got your wife programming! Unless she’s already a programmer? How
did you do that?

L

On Jun 29, 2006, at 8:27 AM, Daniel M. wrote:

Well, I know which one is the de-optimized solution, because I wrote
it ([ruby-talk:199337]), but which one is the multi-method solution?

http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/199031

James Edward G. II

On Jun 29, 2006, at 9:01 AM, Leslie V. wrote:

On 6/29/06, Ruby Q. [email protected] wrote:

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:

All that Ruby is pretty interesting, but far more interesting is that
you got your wife programming!

I think so too.

Unless she’s already a programmer?

Nope. She’s an above average Excel and Access user, but that’s as
close as she gets.

How did you do that?

Well, if she can talk about my quizzes being tough, does that mean I
can complain about her being a tough student? :wink: I’m kidding.
She’s mostly quit yelling at me about how dumb of a sport this is.

I’ve tried teaching her a little before, during my Perl years, with
that language. It didn’t take then, which is totally my fault for
teaching it poorly. We’re giving it another shot now with Ruby as
the language, Learn to Program as the primary teacher, and me as the
guy to yell at when you’re stuck. That seems to be the right mix.

Dana is someone who could really benefit from a little bit of
programming knowledge. Her job involves lots of reporting, with the
information often coming from oddly formatted text files. (See the
“To Excel” Ruby Q., for an example.) She does quite a bit of data
munging, but thus far has had to use some tough tools to accomplish
that.

My goal is to give her a better tool to use on the job. I have no
intention of making her an expert Ruby programmer. I just want to
give her enough pieces of the puzzle that she can code
straightforward data query and filter scripts.

She’s doing well so far. She’s currently in that horrible period we
all go through where she’s learning to get along with a compiler
that, to her, seems to have a one-word vocabulary: Error. I’m sure
she doesn’t believe me when I tell her it is just a phase and it will
pass, but I can already see it easing up on her. She’s threatening
to divorce me a lot less now.

Ironically, she has no trouble with, and actually seems to enjoy,
regular expressions (a James lesson, not Learn to Program). I know
several programmers that can’t say that.

I couldn’t be more proud. :wink:

James Edward G. II

This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.

| Privacy Policy | Terms of Service | Remote Ruby Jobs