Pp Pascal (#84)

Ruby
41

Wow…

For the first time I post on this mailing-list, I really did a great
job!
I answered twice (my email client crashed) an already answered
question, without signature.
Sorry about that, I’ll try to think a little bit more next time I post.

Bye,

Eric

42

[email protected] wrote:

calculating all the rows (basically O(N)).

(think binomial coefficients)

If you’ve got a really wide screen, think Stirling’s approximation. :slight_smile:

–
M. Edward (Ed) Borasky

43

The only problem with this is that you need to know the
maximum cell width (on the last row) when you build the
first one. So I iterate twice over all rows. The first time
to determine the last row and its biggest cell and the
second time to format and print each row.

You really don’t need to build the whole triangle to know the
length of the biggest number… I don’t think I’m allowed to
give you the formula, but it should’nt be that hard to figure
out anyway :wink:

I know:

Mathwords: Binomial Coefficients in Pascal's Triangle

gegroet,
Erik V. - http://www.erikveen.dds.nl/

44

On 6/24/06, Matthew M. [email protected] wrote:

With the 80 column wrap on your terminal, try the following # of rows:
27, 34, 45, 55, 69… There are others, I’m just picking a few out.
Here’s the last row of 69 (hopefully comes through, copy and paste
into a doc using a monospace font if the pattern isn’t visible here):

Hmmm, I doubt copy-n-paste will work, but just try running your own
script at varying #'s.

45

Hello,

I had fun doing this, but my output - and thus way of thinking - is a
bit different. But I do like my version more. What about you?

kind regards
Robert

Original:
$ 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

Mine:
$ .\pascal_triangle.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

46

#! /usr/bin/env ruby

num_lines = ARGV[0].to_i - 1
tri = []
(0…num_lines).each do |n|
line = [ 1 ]
(1…n/2).each{|e| line[e] = tri[n-1][e-1] + tri[n-1][e] }
tri[n] = line + line[0…(n%2)-2].reverse
end

width = Math.log10(tri[num_lines][num_lines/2]).ceil + 1

(0…num_lines).each do |n|
print ’ ’ * ((num_lines - n) * width / 2 ) # leading space
tri[n].each{|val| printf("%#{width}d", val) }
print “\n”
end

47

Hi again,

I think my solution ist not very fast, though I don’t use recursion to
build the triangle.

How long does your script take for a 666 levels triangle?

$ measure-command { .\pascal_triangle.rb 666 } | select minutes,
seconds, milliseconds | fl

Minutes : 2
Seconds : 41
Milliseconds : 15

48

Awesome! Did you find them on accident or did you think about the
wrapping? Looks cool, and I think we have an equal working algo :>

Matthew M. schrieb:

49

On 6/23/06, Jacob F. [email protected] wrote:

For another display example, up to row 15:

(Obviously this won’t display well in 80 columns, you’ll want to copy
it out to a wide fixed width scratchpad to see it best. But it does
make pretty patterns when it wraps :slight_smile:

Reminds me of certain chaos theory problems, where a simple rule turns
to chaos, but then becomes reordered at various points.

With the 80 column wrap on your terminal, try the following # of rows:
27, 34, 45, 55, 69… There are others, I’m just picking a few out.
Here’s the last row of 69 (hopefully comes through, copy and paste
into a doc using a monospace font if the pattern isn’t visible here):

               1                                       68
                       2278

50116 814385
10424128 109453344
969443904 7392009768
49280065120
290752384208 1533058025824
7282025622664 31368725759168
123234279768160
443643407165376 1469568786235308
4495151581425648 12736262814039336
33516481089577200
82115378669464140 187692294101632320
400978991944396320 801957983888792640
1503671219791486200
2646461346833015712 4376839919762295216
6808417652963570336 9969468706125227992
13750991318793417920
17876288714431443296 21912870037044995008
25336755980333275478 27640097433090845976
28453041475240576740
27640097433090845976 25336755980333275478
21912870037044995008 17876288714431443296
13750991318793417920
9969468706125227992 6808417652963570336
4376839919762295216 2646461346833015712
1503671219791486200
801957983888792640 400978991944396320
187692294101632320 82115378669464140
33516481089577200
12736262814039336 4495151581425648
1469568786235308 443643407165376
123234279768160
31368725759168 7282025622664
1533058025824 290752384208
49280065120 7392009768
969443904
109453344 10424128
814385 50116
2278 68
1

50

Seconds : 41
Milliseconds : 15

Hi!

That’s indeed pretty slow!
Here are my times:

-In this example, I save some time by not displaying the triangle, just
saving
it in a file:

$ time ./pascal.rb 666 > pascal666

real 0m7.114s
user 0m5.556s
sys 0m0.440s

-In this example, I display the whole triangle:

$ time ./pascal.rb 666

…
real 0m12.748
user 0m5.628
sys 0m4.868

Bye,

Eric

PS : I hope this message won’t show up twice :-/

51

Minutes : 2 Seconds : 41 Milliseconds : 15

That’s indeed pretty slow!

That’s not slow at all, for an old 486 with 8MB of memory… ;]

I mean, mentioning seconds without mentioning the iron and
other running processes is pretty useless.

What about clock cycles?

$ clockcycles pascaltriangle 666 > /dev/null
1.77024e+10 clock cycles

At least, it’s more fun…

gegroet,
Erik V. - http://www.erikveen.dds.nl/

52

Minutes : 2 Seconds : 41 Milliseconds : 15

That’s indeed pretty slow!

That’s not slow at all, for an old 486 with 8MB of memory… ;]

I mean, mentioning seconds without mentioning the iron and
other running processes is pretty useless.

I totally agree, that was rather silly.

What about clock cycles?

$ clockcycles pascaltriangle 666 > /dev/null
1.77024e+10 clock cycles

I didn’t find any “clockcycles” debian package.
Where did you get this binary?

At least, it’s more fun…

gegroet,
Erik V. - http://www.erikveen.dds.nl/

Bye,

Eric

53

On 6/25/06, Robert R. [email protected] wrote:

Awesome! Did you find them on accident or did you think about the
wrapping? Looks cool, and I think we have an equal working algo :>

Matthew M. schrieb:

On 6/23/06, Jacob F. [email protected] wrote:

With the 80 column wrap on your terminal, try the following # of rows:
27, 34, 45, 55, 69… There are others, I’m just picking a few out.

Found one of them on accident, typing the wrong number. Then I started
searching for others…

54

#!/usr/bin/env ruby

pascal.rb - Pretty-print Pascal’s Triangle

Copyright (C) 2006 Louis J. Scoras

This program is free software; you can redistribute it

and/or modify it under the terms of the GNU General Public

License as published by the Free Software Foundation;

either version 2 of the License, or (at your option) any

later version.

This program is distributed in the hope that it will be

useful, but WITHOUT ANY WARRANTY; without even the implied

warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR

PURPOSE. See the GNU General Public License for more

details.

[The GNU General Public License v3.0 - GNU Project - Free Software Foundation]

Here’s my solution for Ruby Q. 84. I realize that you can calculate

the

last row in the expansion using the binomial theorem, but you’ll need

to

iterate through each row anyway to print the numbers out, so I just

went

with a caching method.

I was going to implement a persistant disk cache, but alas I find

myself

currently stuck on a windows machine, which takes all the fun out of

it–

for me at least :slight_smile:

Thanks to Dirk and James for a great quiz.

require ‘enumerator’

class PascalsRow
attr_reader :numbers

def initialize(numbers = [1], depth = 0)
@numbers = numbers
@depth = depth
end

def even?
@depth % 2 == 0
end

def calculate_next
sums = if @numbers.length == 1
[1]
else
@numbers.enum_cons(2).collect {|j,k| j+k}
end

sums = sums << sums.last if even? && @depth != 0
self.class.new([1] + sums, @depth + 1)

end

def canonical
half = @numbers.dup
half.pop
half.pop unless even?
@numbers + half.reverse
end

def to_s
canonical.join(’ ')
end

def padded_string(word_size)
canonical.collect do |n|
digits = n.to_s
padding = ((word_size - digits.length) / 2.0).ceil
make_padding(padding) +
digits +
make_padding(word_size - digits.length - padding, 1)
end.join
end

private
def make_padding(size, min_length = 0)
’ ’ * [size, min_length].max
end
end

class PascalsTriangle
def initialize
@rows = [PascalsRow.new]
end

def iterate_rows(n, &block)
current_row = @rows.first
block.call(current_row) if block

n.times do |n|
  current_row = if @rows[n+1]
    @rows[n+1]
  else
    current_row = current_row.calculate_next
    @rows[n+1]  = current_row
  end
  block.call(current_row) if block
end
current_row

end

def pretty(n)
last_line = iterate_rows(n)
word_size = last_line.numbers.last.to_s.length
width = last_line.padded_string(word_size).length

iterate_rows(n) do |row|
  padded = row.padded_string(word_size)
  puts (' ' * ((width - padded.length) / 2)) + padded
end

end
end

pt = PascalsTriangle.new
pt.pretty((ARGV[0] ? ARGV[0].to_i : 10) - 1)

55

Pascal’s Triangle (Ruby Q. #84)

by Mustafa Yilmaz

This is the second Ruby program I’ve ever written and it’s not

optimized (and probably not

leveraging the power of Ruby), so don’t expect to much :wink: The code

should be self-explanatory,

if you have any questions though don’t hesitate to ask me.

My approach is to create a PDF file using the PDF::Writer libraries in

order to get the

centering right. Furthermore, I’m computing the binomial coefficent as

discussed before to

approximate the width of the largest number in the triangle.

One could improve the program by dynamically adjusting the used text

size to scale the text

depending on the size of the triangle to make use of the whole page

size.

You can download an example pdf file from

http://www.mustafayilmaz.net/pascal.pdf

begin
require ‘pdf/writer’
rescue LoadError => le
if le.message =~ %r{pdf/writer$}
$LOAD_PATH.unshift(“…/lib”)
require ‘pdf/writer’
else
raise
end
end

class Integer
def factorial
self <= 1 ? 1 : self * (self-1).factorial
end
end

class Binomial_Coefficient
def self.compute(n, r)
n.factorial / (r.factorial * (n-r).factorial)
end
end

class Pascal
def self.create_pdf(lines, font_size, filename)
max_width = Binomial_Coefficient.compute(lines, lines /
2).to_s.length + 2
pdf = PDF::Writer.new(:paper => “A4”, :orientation => :landscape)
pdf.select_font “Courier”
pdf.text “Pascal’s Triangle (Ruby Q. #84)\n\n\n”, :font_size =>
10, :justification => :center
previous_result = Array.[](0, 1, 0)
s = “1”.center(max_width)
while lines > 0 do
pdf.text “#{s}\n\n”, :font_size => font_size, :justification =>
:center
current_result = Array.new
previous_result[0…-2].each_index do |i|
current_result << previous_result[i] + previous_result[i+1]
end
s = String.new
current_result.each_index do |i|
s << current_result[i].to_s.center(max_width)
end
current_result = Array..concat(current_result) << 0
previous_result = current_result
lines -= 1
end
pdf.save_as(filename)
end
end

Pascal.create_pdf(20, 8, “pascal.pdf”)

56

Hi everybody,

here’s my solution, next to few examples.
The result might look pretty poor displayed on an email client :-(, but
the
script does print a perfectly equilateral triangle.

Thanks for the interesting quiz!

$ ./pascal.rb 12
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
1 10 45 120 210 252 210 120 45 10 1
1 11 55 165 330 462 462 330 165 55 11 1
1 12 66 220 495 792 924 792 495 220 66 12 1

$ ./pascal.rb 12 -1
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
1 10 45 120 210 252 210 120 45 10 1
1 11 55 165 330 462 462 330 165 55 11 1

$ ./pascal.rb 12 1
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
1 10 45 120 210 252 210 120 45 10 1
1 11 55 165 330 462 462 330 165 55 11 1

$ ./pascal.rb 12 0.7

                               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
 1  10  45 120 210 252 210 120  45  10   1

1 11 55 165 330 462 462 330 165 55 11 1

By tweaking a bit the script you can easily obtain a Sierpinski
triangle, as
mentioned in a previous post:

./sierpinski.rb 32

                           *

                         * * *
                          * *
                       *   *   *

                     * * * * * * *
                      * * * * * *
                   *   * * * * *   *
                        * * * *
                 * * *   * * *   * * *
                  * *     * *     * *
               *   *   *   *   *   *   *

             * * * * * * * * * * * * * * *
              * * * * * * * * * * * * * *
           *   * * * * * * * * * * * * *   *
                * * * * * * * * * * * *
         * * *   * * * * * * * * * * *   * * *
          * *     * * * * * * * * * *     * *
       *   *   *   * * * * * * * * *   *   *   *
                    * * * * * * * *
     * * * * * * *   * * * * * * *   * * * * * * *
      * * * * * *     * * * * * *     * * * * * *
   *   * * * * *   *   * * * * *   *   * * * * *   *
        * * * *         * * * *         * * * *
 * * *   * * *   * * *   * * *   * * *   * * *   * * *
  * *     * *     * *     * *     * *     * *     * *

#! /usr/bin/ruby

############### Pascal Triangle by Eric DUMINIL ###############

This program is free software; you can redistribute it

and/or modify it under the terms of the GNU General Public

License as published by the Free Software Foundation;

either version 2 of the License, or (at your option) any

later version.

How-to use it?

pascal.rb height excentricity

with:

height, pretty self-explanatory

excentricity, float between -1 and 1.

height set to 5 and excentricity set to -1:

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

height set to 5 and excentricity set to 1 :

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

By default, excentricity is set to 0:

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

#Just to make sure we can calculate C(n,n/2)
#without having to build the whole tree
class Fixnum
def fact
return 1 if self<2
self*(self-1).fact
end

def cnp(p)
    self.fact/(p.fact*(self-p).fact)
end

end

class PascalTriangle
def initialize (height=15,excentricity=0)
@height=height
@excentricity=excentricity
#maxLength should be odd, so that the alignment is preserved
@maxLength=(height-1).cnp((height-1)/2).to_s.length|1
createAndShow
end

attr_reader :height, :maxLength, :excentricity

def createAndShow
    previous=[1]
    current=Array.new
    height.times{|i|
        current[0]=current[i]=1
        #Taking care of the symetry
        1.upto(i/2){|j|
            current[j]=current[i-j]=previous[j]+previous[j-1]
        }
        puts " "*((maxLength+1)*(excentricity+1)/2)*(height-i-1)+
             current.map{|number|
                number.to_s.rjust(maxLength)
             }.join(" ")
        #No need to remember the whole triangle,
    #the previous row will be enough
        previous.replace(current)
    }
end

end

PascalTriangle.new(ARGV[0].to_i,ARGV[1].to_f)

###############################################################################

Bye,

Eric

Le Vendredi 23 Juin 2006 15:31, Ruby Q. a écrit :

57

So much for the pp part, but this does the Pascal just fine:

require “rational”

I derived the nCk formula myself, didn’t wanna cheat.

class Fixnum
def choose(k); (1…k-1).inject(1){ |s,e| s *= Rational(self,e) - 1 };
end
end

not to disappoint JEG2, I decided to maintain my record of

“never completing a ruby quiz”, so take the formatting with a grain of

salt.
1.upto(ARGV[0].to_i) { |n| puts((1…n).map {|k| n.choose k }.join("|"))
}

For me the fun part was learning through inspection that the values of
the triangle were simply nCk values, and then deriving the the nCk
formula from the triangle. The above is a bit of a messy version of
that formula, because I did derive it myself, and my math is slow this
summer :wink:

Output (no effort here) :
[sandal@harmonix rubyquiz]$ ruby pascal.rb 15
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
1|10|45|120|210|252|210|120|45|10|1
1|11|55|165|330|462|462|330|165|55|11|1
1|12|66|220|495|792|924|792|495|220|66|12|1
1|13|78|286|715|1287|1716|1716|1287|715|286|78|13|1
1|14|91|364|1001|2002|3003|3432|3003|2002|1001|364|91|14|1

58

On Jun 23, 2006, at 8:31 AM, Ruby Q. wrote:

by Dirk M.

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.

My own solution, used in the quiz examples.

James Edward G. II

59

My solution. While I did play with various options (using memoized
factorials and “chooses”, different column shapings, etc.) this is the
one I stuck with. Maybe I’ll post another solution later which
demonstrates the memoized combinatorics. :slight_smile:

Jacob F.

60

Hello all,

The output is almost perfect on a console, plus different fonts have
different widths for different numbers. So I guess the look of the
triangles will vary with email clients. I’d like to give credit to my
friend Fedor for coming up with much of the output equation. The
output works for any size output (notice how the spacing get smaller
toward the middle).

$ ./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

$ ./pp_pascal.rb 15
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
1 10 45 120 210 252 210 120 45 10
1
1 11 55 165 330 462 462 330 165 55
11 1
1 12 66 220 495 792 924 792 495 220
66 12 1
1 13 78 286 715 1287 1716 1716 1287 715 286
78 13 1
1 14 91 364 1001 2002 3003 3432 3003 2002 1001
364 91 14 1

On an Athlon64 1.8 GHz
$ time ./pp_pascal.rb 666 > /dev/null

real 0m16.337s
user 0m16.147s
sys 0m0.185s

And finally the code:

#!/usr/bin/ruby
$factCache = [ 1 ]
def factorial(n)
return $factCache[n] if n <= $factCache.length
prod = $factCache.last
while $factCache.length <= n
$factCache.push(prod *= $factCache.length)
end
return prod
end

def pascalCombination(n, k)
return factorial(n) / (factorial(k) * factorial(n - k))
end

max = $*[0].to_i - 1
maxDigits = Math.log10(pascalCombination(max, max/2)).floor + 1
spaces = (maxDigits + maxDigits/2).ceil
for row in 0…max
print " " * ((max - row)*spaces/2)
for col in 0…row
combination = pascalCombination(row, col)
digitSpace = Math.log10(combination).floor + 1
digitSpace = 1 if digitSpace == 0
print " " * (spaces - digitSpace) + combination.to_s
end
print “\n”
end