Pp Pascal (#84)

Ruby
61

Having followed the discussion of this quiz, I suspect this is going
to look a bit bloated compared to some other solutions, as I took the
simple approach of building up the entire triangle in memory, then
printing it out afterwards. Anyway, here it is:

#!/usr/bin/env ruby
size = ARGV[0].to_i
rows = Array.new(size)

calculate the numbers

rows[0] = [1]
(1…size - 1).each do |n|
rows[n] = Array.new(n)
m = 0
rows[n - 1].inject 0 do |prev, current|
rows[n][m] = prev + current
m += 1
current
end
rows[n] << 1
end

longest number will be in the middle of the bottom row

max_length = rows[size - 1][size/2 - 1].to_s.length

pad, centre and output

padded = rows.collect do |row|
row.inject “” do |line, element|
line + element.to_s.center(max_length + 2)
end
end
width = padded[size - 1].length
padded.each {|row| puts row.center(width)}

Output with 13 rows (the most that’ll fit in 80 characters):

                             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

That looks wrong in my mail program, but it does all line up nicely
in a monospaced font!

Kerry

62

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hello,

This is the first Ruby Q. I have tried and I’m glad to have done
it :). Attached is my solution to the quiz.

Cheers.

BASIC is to computer programming as QWERTY is to typing.
– Seymour Papert
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2.2 (GNU/Linux)

iD8DBQFEnrg/mV9O7RYnKMcRAhReAJ48f6EzmH0SfskdFCzox+v3VAvUiACeMFd6
pcnMckae8KWvkg7nj4Kxd38=
=odnD
-----END PGP SIGNATURE-----

63

My first solution, a straightforward implementation that was
originally recursive, turned iterative:

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

My second solution, after reading some of the discussion, was an
attempt to not generate the whole tree in memory, but only one row at
a time:

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

Either solution started with:

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

I could have done some error checking (i.e. bad input) or cached some
values for speed (Integer.fact and Integer.binom, particularly), but I
got lazy…

64

Hi,

of course I have a solution that solves the original problem, but there
are already many of those.

So, instead of solving the original problem, the code below produces
nice
images of Pascal’s triangle modulo any number.

Example:

$ for i in seq 2 20; do ruby pascal_mod_pgm.rb 500 $i; done

Dominik

pascal_mod_pgm.rb

def pascal_rows_mod(rows, mod)
row = [1]
rows.times do
yield row
row = [1] + (0…row.size-1).map do |i|
(row[i] + row[i + 1]) % mod
end + [1]
end
end

if $0 == FILE
rows = ARGV.shift.to_i
mod = (ARGV.shift || 2).to_i
row_w = rows * 2 - 1
File.open(“pas_#{rows}_#{mod.to_s.rjust(3, “0”)}.pgm”, “w”) do |f|
f.puts “P5 #{row_w} #{rows} 1”
pascal_rows_mod(rows, mod) do |row|
f.print(row.map do |x|
x == 0 ? “\1” : “\0”
end.join("\1").center(row_w, “\1”))
end
end
end

65

Here is another solution that I came with up with. The output is not
pretty here, but its very fast:

time ruby pascal.rb 666 > /dev/null

real 0m6.023s
user 0m5.934s
sys 0m0.086s

#!usr/bin/ruby
max = $*[0].to_i - 2
spaces = (3 + 3/2).ceil
row = [ 1, 1 ]
rows = 0
print " " * (2 + (max - rows + 1) * spaces/2)
print “1\n”
print " " * ((max - rows + 1) * spaces/2)
print “1 1\n”
nextRow = []
while (rows < max)
nextRow.push(1)
print " " * ((max - rows) * spaces/2) + “1”
for temp in (1…(rows + 1))
first = row.shift
second = row.shift
row.unshift(second)
comb = first.to_i + second.to_i
print " " + comb.to_s
nextRow.push(comb.to_i)
end
print " 1"
nextRow.push(1)
row = nextRow
nextRow = []
print “\n”
rows = rows + 1
end

66

“Gregory B.” [email protected] writes:

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(“|”)) }

Given this, I can’t resist but “break the rules” even further—by not
even writing the solution in Ruby. :wink: It’s pretty nice to do in
Haskell:

pascal = iterate (\last → zipWith (+) ([0] ++ last) (last ++ [0])) [1]

pp n = mapM_ (putStrLn . join “|” . map (show)) $ take n $ pascal
where join s (x:xs) | xs == [] = x
| otherwise = x ++ s ++ join s xs

main = pp 666

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
…

67

Here’s an explanation about how to calculate the next row,
based on the previous row. You only need the last line.

row ===> [1, 3, 3, 1]
[0]+row ===> [0, 1, 3, 3, 1]
row+[0] ===> [1, 3, 3, 1, 0]
([0]+row).zip(row+[0]) ===> [[0, 1], [1, 3], [3, 3],
[3, 1], [1, 0]]
([0]+row).zip(row+[0]).map{|a,b|a+b} ===> [1, 4, 6, 4, 1]

You can replace the last line by the next line, but this one
modifies the previous row, which might be tricky. Though it
does save you one extra byte ;]

([0]+row).zip(row<<0).map{|a,b|a+b} ===> [1, 4, 6, 4, 1]

You could build and store the complete triangle with this:

t=[r=[1]]+(2…n).map{r=([0]+r).zip(r+[0]).map{|a,b|a+b}}

(But that’s not what we are going to do in this script…)

I added pretty printing as well. First of all, the width of
each cell (excluding the separator) shouldn’t be even, in order
to be able to align properly.

Secondly, if we can’t center the contents within a cell, we
error to the right on the left hand side of the triangle and to
the left at the right hand side.

Thirdly, because the last line could be stripped by half a cell
width at both the left and the right hand side, we simply strip
every line by half a cell width on both sides.

You can find the source in the attachment.

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

68

Hi!

At Fri, 23 Jun 2006 22:31:52 +0900, Ruby Q. wrote:

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.

Besides the necessary comment that the triangle presented as “Pascal’s
Triangle” is already present in the famous Chinese mathematician Zhu
Shijie’s “Precious Mirror of the Four Elements” that dates back to
1303 here’s my solution:

exit 1 if ARGV.length != 1 || ARGV[0] =~ /[^\d]/
rows = Array.new
current = [1]
rows.push current.dup
(ARGV[0].to_i + 1).times do |row|
(current.length - 2).times { |i| current[i] += current[i + 1] }
current[0…0], current[-1] = 1, 1
rows.push current.dup
end
fieldsize = rows.last.map { |n| n.to_s.length }.max
rows.each_with_index do |row, n|
print ’ ’ * (fieldsize + 1) * (rows.length - n - 1)
puts row.map { |elem| elem.to_s.rjust(fieldsize) + ’ ’ * (fieldsize +
2) }.join
end

Concerning performance:

time ruby pascal.rb 666 > /dev/null

real 0m7.683s
user 0m7.608s
sys 0m0.044s

I’m using the 32 bit edition of Fedora Core 5 on an Athlon 3700+
running at 2,2 GHz featured with 1 GB RAM.

Josef ‘Jupp’ Schugt

69

Hi,

I do like your solution, though I didn’t know lambda nor zip before.
Cool way to build the new row!

Oh, and you wrote :

width = biggest.to_s.length
width +=1 if width % 2 == 0

which is actually :
width = biggest.to_s.length|1

At first, I used :
width = biggest.to_s.length/2*2+1
but tried to find an easier way to increment to the next odd number!

Bye,

Eric

Le Dimanche 25 Juin 2006 19:52, Erik V. a écrit :

70

I like this excentricity. Added it to my script.

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

Traditionally, this is done by number%2==0, but this 2 could be
a 3 or a 4 has well, giving different results:

cell = row[cell_nr]%sierpinski==0 ? " " : “*”

I patched my script.

Thanks.

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

71

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.

Two solutions from me (you may choose if like at least one :))

The first uses hashes to store the values of a line. makes it
pretty obvious what is going on (at least for the author g)

require ‘enumerator’

pascal = [{0, 1}] + (1…ARGV[0].to_i).map{Hash.new(0)}

pascal.each_cons(2) do |last, this|
last.each{|p, v| this[p - 1] += v; this[p + 1] += v}
end

size = pascal.last.fetch(0, pascal.last[1]).to_s.size + 1

pascal.each do |row|
line = row.sort.map{|p, v| v.to_s.center size}.join
puts line.center(size * pascal.last.size).rstrip
end

And the other one with a completely different approach:

fac = lambda{|n| n < 2 ? 1 : (1…n).inject{|f, i| f * i}}
tri = lambda{|n, r| fac[n] / (fac[r] * fac[n-r])}
size = lambda{|r| tri[r-1, r / 2].to_s.size + 1}
line = lambda{|y, r| (0…y).map{|x| tri[y,x].to_s.center size[r]}}
lines = lambda{|r| (0…r).map{|y| line[y, r]}}
pascal = lambda{|r| lines[r].map{|l| l.join.center(size[r] * r).rstrip}}

puts pascal[(ARGV[0] || 15).to_i]

which is more like a case study of functional programming in
ruby (comments welcome, that’s not my primary domain)

cheers

Simon

72

Hi,

here is my solution and a unit test. The triangle is calculated and
stored as an array of
arrays first. Then it’s converted to a string.

I couldn’t resist to add a pair iterator to class Array…

Regards,
Boris

pascal.rb

class Array

iterate through pairs of consecutive elements

def each_pair
(0…size-2).each do |i|
yield(self[i], self[i+1])
end
end
end

class Pascal
def initialize(n)
@triangle = [[1]]
2.upto(n) do
@triangle << calc_row(lastrow)
end
end

def lastrow; @triangle[-1]; end

calculate row given the previous row

def calc_row(previous)
thisrow = [1]
previous.each_pair do |x, y|
thisrow << x + y
end
thisrow << 1
end

def to_s
cellwidth = lastrow.max.to_s.size
indentation = lastrow.size - 1
emptycell = ’ ’ * cellwidth
s = ‘’
@triangle.each do |row|
s << emptycell * indentation
s << row.map{|cell| cell.to_s.center(cellwidth)}.join(emptycell)
s << “\n”
indentation -= 1
end
s
end
end

if $0 == FILE
puts Pascal.new(ARGV[0].to_i).to_s
end

pascal_test.rb

require ‘pascal’
require ‘test/unit’

class PascalTest < Test::Unit::TestCase
def test_1
expected = “1\n”
assert_equal expected, Pascal.new(1).to_s
end

def test_2
assert_equal <<EXPECTED, Pascal.new(2).to_s
1
1 1
EXPECTED
end

def test_3
assert_equal <<EXPECTED, Pascal.new(3).to_s
1
1 1
1 2 1
EXPECTED
end

def test_10
assert_equal <<EXPECTED, Pascal.new(10).to_s
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
EXPECTED
end
end

73

Erik V. wrote:

fac = lambda{|n| n < 2 ? 1 : (1…n).inject{|f, i| f * i}}
tri = lambda{|n, r| fac[n] / (fac[r] * fac[n-r])}
size = lambda{|r| tri[r-1, r / 2].to_s.size + 1}
line = lambda{|y, r| (0…y).map{|x| tri[y,x].to_s.center size[r]}}
lines = lambda{|r| (0…r).map{|y| line[y, r]}}
pascal = lambda{|r| lines[r].map{|l| l.join.center(size[r] *
r).rstrip}}
puts pascal[(ARGV[0] || 15).to_i]

Nice, but very, very slow…

better?

class CachedLambda < Struct.new(:block, :cache)
def [] *args
cache[args] ||= block.call(*args)
end
end

def c_lambda &b
CachedLambda.new b, {}
end

fac = c_lambda{|n| n < 2 ? 1 : (1…n).inject{|f, i| f * i}}
tri = c_lambda{|n, r| fac[n] / (fac[r] * fac[n-r])}
size = c_lambda{|r| tri[r-1, r / 2].to_s.size + 1}
line = c_lambda{|y, r| (0…y).map{|x| tri[y,x].to_s.center size[r]}}
lines = c_lambda{|r| (0…r).map{|y| line[y, r]}}
pascal = c_lambda{|r| lines[r].map{|l| l.join.center(size[r]*r).rstrip}}

puts pascal[(ARGV[0] || 15).to_i]

cheers

Simon

74

My code(in the spirit of golf,as ever)

def c(r,i)[r,i].min==1||r==i ?1:c(r-1,i)+c(r-1,i-1)end
def d(n)w=Math.log10(c(n,n/2)).ceil+1;(0…n).map{|z|print "
“*((n-z)*w/2);(1…z).map{|b|printf(”%#{w}d",c(z,b))};puts}end
d(5)

Or just code to generate the triangle:
def c(r,i)[r,i].min==1||r==i ?1:c(r-1,i)+c(r-1,i-1)end
def g(n)(1…n).map{|i|(1…i).map{|b|c(i,b)}}end

Another fun quiz!

j`ey
http://www.eachmapinject.com

75

fac = lambda{|n| n < 2 ? 1 : (1…n).inject{|f, i| f * i}}
tri = lambda{|n, r| fac[n] / (fac[r] * fac[n-r])}
size = lambda{|r| tri[r-1, r / 2].to_s.size + 1}
line = lambda{|y, r| (0…y).map{|x| tri[y,x].to_s.center size[r]}}
lines = lambda{|r| (0…r).map{|y| line[y, r]}}
pascal = lambda{|r| lines[r].map{|l| l.join.center(size[r] *
r).rstrip}}

puts pascal[(ARGV[0] || 15).to_i]

Nice, but very, very slow…

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

76

Erik V. [email protected] writes:

([0]+row).zip(row+[0]).map{|a,b|a+b} ===> [1, 4, 6, 4, 1]

You can replace the last line by the next line, but this one
modifies the previous row, which might be tricky. Though it
does save you one extra byte ;]

([0]+row).zip(row<<0).map{|a,b|a+b} ===> [1, 4, 6, 4, 1]

Actually, you can save two characters by a simple variation on the
initial zip version that removes the need for parens, with no in-place
modification of “row”:

row.zip([0]+row).map{|a,b|a+b}+[1]

You could build and store the complete triangle with this:

t=[r=[1]]+(2…n).map{r=([0]+r).zip(r+[0]).map{|a,b|a+b}}

Minimal-number-of-characters-wise, at this point you’re better off not
using the pascal triangle recurrence relation and just using the
properties of binomial coefficients:

t=(0…n).map{|i|r=1;[1]+(1…i).map{|a|r=r*(i+1-a)/a}}

I’m a little bit surprised at the paucity of solutions based around
sprintf-format strings. I’ll have to write up my sprintf-based idea
tonight or tomorrow.

77

Nice, but very, very slow…

better?

It’s getting better, yes… ;]

Have you tried to build big triangles? Caching is MB-expensive
and still not really fast… ;]

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

$ time ruby yourversion.rb 666 > /dev/null
[[“troep2.rb:16:in c_lambda'", "troep2.rb:24"], 1] [["troep2.rb:16:in c_lambda’”, “troep2.rb:23”], 1]
[[“troep2.rb:16:in c_lambda'", "troep2.rb:22"], 666] [["troep2.rb:16:in c_lambda’”, “troep2.rb:21”], 1]
[[“troep2.rb:16:in c_lambda'", "troep2.rb:20"], 222111] [["troep2.rb:16:in c_lambda’”, “troep2.rb:19”], 666]

real 1m29.039s
user 1m20.466s
sys 0m0.571s

$ time ruby myversion.rb 666 > /dev/null

real 0m10.232s
user 0m9.613s
sys 0m0.030s

clas CachedLambda < Struct.new(:block, :cache)
def initialize(*args)
super
@caller = caller
at_exit do
$stderr.puts [@caller, cache.size].inspect
end
end

def [] *args
cache[args] ||= block.call(*args)
end
end

78

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?

clock_cycles = elapsed_time * cpu_speed

Unless you run a lot of other processes…

It’s a little Ruby script.

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

79

([0]+row).zip(row<<0).map{|a,b|a+b} ===> [1, 4, 6, 4, 1]

Actually, you can save two characters by a simple variation
on the initial zip version that removes the need for parens,
with no in-place modification of “row”:

row.zip([0]+row).map{|a,b|a+b}+[1]

row = [1, 4, 6, 4, 1]
p ([0]+row).zip(row<<0).map{|a,b|a+b} ===> [1, 5, 10, 10, 5, 1]
p row.zip([0]+row).map{|a,b|a+b}+[1] ===> [1, 5, 10, 10, 5, 1, 1]

Different results…

You could build and store the complete triangle with this:

t=[r=[1]]+(2…n).map{r=([0]+r).zip(r+[0]).map{|a,b|a+b}}

Minimal-number-of-characters-wise, at this point you’re
better off not using the pascal triangle recurrence relation
and just using the properties of binomial coefficients:

t=(0…n).map{|i|r=1;[1]+(1…i).map{|a|r=r*(i+1-a)/a}}

Add one extra dot (0…n instead of 0…n) and you win!

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

80

OK, here’s my solution. I’ve tried to make it as compact, neat and
ruby-ish as possible. (It’s not space efficient, in that it stores
the entire triangle before printing it.)

require ‘enumerator’

Generate the triangle.

n = ARGV[0].to_i
rows = (2…n).inject([[1]]) do |rows, i|
rows << ([0]+rows[-1]+[0]).enum_cons(2).map{|a,b| a+b }
end

Work out the length in digits of the longest number.

m = rows[-1][n/2].to_s.length

Print each row with appropriate spacing.

rows.each do |row|
print ’ ‘m(n-row.length)
print row.collect {|i| sprintf(“%#{m}d”, i) }.join(’ '*m)
print “\n”
end

Output looks like this:

                                   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

Pete Y.
http://9cays.com/