Pp Pascal (#84)

Ruby
81

Erik V. [email protected] writes:

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…

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

Running your code first mangles the value of “row”. It’s not fair if
you don’t give the same value for “row” to my code :slight_smile:

Incidentally:

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

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!

Yeah; I’m not surprised I had an off-by-one error - what the quiz
calls the first row I’d call the “zeroth” row.

82

“Suraj N. Kurapati” [email protected] writes:

Daniel M. wrote:

I’m a little bit surprised at the paucity of solutions based around
sprintf-format strings.

Same here. So far I have seen only two solutions, including mine,
which use sprintf-format strings.

So here’s one more addition to the sprintf-formatted solution pool:

#!ruby

solution to Ruby quiz #84

lnnb stands for “ln of n-bang”

value is from Stirling’s approximation

def lnnb(n);
nMath.log(n)-n+Math.log(2nMath::PI)/2 + 1/(12n) - 1/(360nn*n);
end

how many digits in the largest number in row “n”

where the rows get counted from 0

def npasdig(n)
return 1 if (n < 5)
nh = n/2
((lnnb(n)-lnnb(nh)-lnnb(n-nh))/Math.log(10)).ceil
end

def pp_pascal(n)
width = npasdig(n-1)
fmt = “%#{width}s” * (2n-1)
row = [0] * (n-1) + [1] + [0] * n
while true do
puts(fmt % row.map{|a|if a==0 then “” else a end})
return if row[0] > 0
row = row[1,2n].zip([0]+row).map{|a,b|a+b}+[0]
end
end

if FILE == $0
n = 4
n = ARGV[0].to_i if ARGV[0]
pp_pascal(n)
end

83

Here’s my solution.
It’s not brief but works anyway.

class PascalTriangle

include Enumerable

attr_reader :rows

def initialize row_count
	raise ArgumentException unless row_count.class == Fixnum
	raise "row_count must be greater than 0." unless row_count > 0
	@row_count = row_count
	generate_rows
end

def to_s
	max_width = @rows.flatten.max.to_s.size
	max_count = @rows.map{ |i| i.size }.max
	line_width = max_count * max_width * 2 - max_width
	separator = " " * max_width
	self.map do |row|
		row.map { |num| num.to_s.center(max_width)

}.join(separator).center(line_width)
end.join("\n")
end

def each
	@rows.each { |row| yield row }
end

private

def generate_rows
	row = []
	@rows = (0...@row_count).to_a.inject([]) do |m, i|
		m << row = generate_row(row)
	end
	@rows.freeze
	@rows.each { |r| r.freeze }
end

def generate_row row
	result = [1]
	row.each_with_index do |el, idx|
		result << (idx == row.size - 1 ? 1 : el + row[idx + 1])
	end
	result
end

end

if ARGV[0].nil? or ARGV[0] !~ /^\d+$/
puts “Example: ruby pascal.rb 10”
exit
end

row_count = ARGV[0].to_i
puts PascalTriangle.new(row_count).to_s

Sam K.

84

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

Daniel M. wrote:

I’m a little bit surprised at the paucity of solutions based around
sprintf-format strings.

Same here. So far I have seen only two solutions, including mine,
which use sprintf-format strings.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2.2 (GNU/Linux)

iD8DBQFEnzsmmV9O7RYnKMcRArwIAJ4iFPQJb0iMAOwwucJIX9/fOiPnKQCeJ0DP
l2I6PGmZQc4079GtDersldM=
=eVoE
-----END PGP SIGNATURE-----

85

On 26/06/2006, at 3:52 AM, Erik V. wrote:

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]

For contrast, here’s a way to do the same thing using enum_cons:

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

A few more characters, but probably a little quicker to run given it
doesn’t have to construct so many intermediate arrays.

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

86

Hi all,

Here’s my solution to the quiz:
I attached two different solutions actually.

First is pascal.rb, which is the first I did before asking for
any clarifications/hints :slight_smile: The triangle resulted is far from
perfect, but I liked being able to use the ‘multi’ module which
I just learned about :slight_smile:

The second, pascal-mini, does output a perfect triangle, and allows for
playing with two options: ‘B’ and ‘S’. B represents the numerotation
based. By default it is 10, so nothing unusual, but you can change it
to 16 and display hexa numbers, or even to 32 and display numbers in
the 32 based numerotation system :slight_smile: Looks nicer and more compact for
larger triangles. All triangles in the attached sample.txt are from
this script. The Ruby code however is very ugly I agree, I just wanted
to find out how much I can squeeze it :slight_smile:

Thanks for the fun Ruby quiz!

Have a great day everyone,
Alex

87

Here’s my solution. It’s not very efficient but it works:

numberOfRows = ARGV[0].to_i

Handles the case where the number of rows asked for is 1

numberOfRows.eql?(1) ? (puts(“1”);exit) : nil

Genereate Pascal’s Triangle

rows = [[1],[1,1]]

2.upto(numberOfRows-1) do |currentRowIndex|

rows[currentRowIndex] = [1]

1.upto(currentRowIndex-1) do |elementIndex|

rows[currentRowIndex] << rows[currentRowIndex-1][elementIndex-1] +

rows[currentRowIndex-1][elementIndex]

end

rows[currentRowIndex] << 1

end

Get the length in characters of the largest element

maxElementLength = rows[numberOfRows - 1][numberOfRows/2].to_s.length

Format and ouput the triangle

puts(rows.map do |row|

’ 'maxElementLength(numberOfRows - row.length) +

row.map do |element|

element.to_s +

' '*(maxElementLength-element.to_s.length) +

' '*maxElementLength

end.join

end.join("\n"))

88

My solution does have one aspect I haven’t noticed in everyone’s great
submissions so it might be illustrative, if nothing else - I wrote my
implementation test first. Other than that, there isn’t too much
novelty in my solution.

Sean C.
http://sean-carley.blogspot.com/

89

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

Running your code first mangles the value of “row”. It’s not fair if
you don’t give the same value for “row” to my code :slight_smile:

Sorry…

gegroet,
Erik V.

90

Daniel M. [email protected] writes:

“Suraj N. Kurapati” [email protected] writes:

Daniel M. wrote:

I’m a little bit surprised at the paucity of solutions based around
sprintf-format strings.

Same here. So far I have seen only two solutions, including mine,
which use sprintf-format strings.

So here’s one more addition to the sprintf-formatted solution pool:

And because I felt like tweaking it a bit more, here’s a variation
that shows off some more ruby-specific features, like singleton
objects and the coerce method that numeric types use. Following how
the “g” object in the pp_pascal method works is an exercise in some of
ruby’s more unique features. (uncommenting the two “p” lines may help)

Now, who’s going to write up some benchmarking code to test the speed
of all these solutions? Also, how do we test them for correctness? I
suppose we could test that the last row of output contains the right
values, but I don’t know how to test whether the output “looks right”
in any automated fashion.

#!ruby

solution to quiz 84

require ‘enumerator’

lnnb stands for “ln of n-bang”

value is from Stirling’s approximation

def lnnb(n)
return 0 if n <= 1
nMath.log(n) - n +
Math.log(2nMath::PI)/2 + 1/(12n) - 1/(360nn*n);
end

how many digits in the largest number in row “n”

where the rows get counted from 0

def npasdig(n)
return 1 if (n < 5)
nh = n/2
((lnnb(n)-lnnb(nh)-lnnb(n-nh))/Math.log(10)).ceil
end

def pp_pascal(n)
width = npasdig(n-1)
fmt = “%0s” + “%-#{width}s” * (2n-2) + “%1s”
g = Object.new
class << g
def coerce(o); 0.coerce(o); end
def +(o); o; end
def to_s; “”; end
def inspect; “g”; end
end
row = [g](2*n+1)
row[n] = 1

p fmt

while true do

p row

puts(fmt % row)
return if row[1] == 1
row = row.enum_cons(3).map{|a,b,c|a+c}
row = [g] + row + [g]

end
end

if FILE == $0
n = 4
n = ARGV[0].to_i if ARGV[0]
pp_pascal(n)
end

END

My sig needs work; it’s nowhere as obfuscated as my perl version…

91

Here’s the factorial solution I came up with. I wrote a shorter
last-line-based implementation first, but I preferred this one:

#!/usr/bin/env ruby
n = ARGV[0].to_i

Centre text t with spaces to width w

def ct(t,w) u=t.length;r=w-(l=w/2-u/2)-u;’ ‘*l+t+’ '*r end

Factorial

def f(n) n==0?1:n*f(n-1) end

String value of triangle at row r, column c, using binomial

coefficient
def v(r,c) (f®/f©/f(r-c)).to_s end

Width of largest value

d=v(n-1,n/2).length

Width of last line

w=n*d+n-1

Triangle

n.times{|y|puts(ct((0…y).map{|x|ct(v(y,x),d)}*’ ',w))}

Paul.

92

On 25/06/06, Christian N. [email protected] wrote:

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

Aha! I had a go at it in Haskell, too, and used the same zipWith
technique.

Actually, that got me thinking: why doesn’t zip in Ruby take a block?
It could handle Haskell’s zip (and zip3 etc.) and zipWith then…

Paul.

93

better?

class CachedLambda < Struct.new(:block, :cache)

If we’re thinking Lispy, well, why don’t we stay in that
mode?.. ;]

We could implement such a cache for lambda functions with one,
uh, two, more lambda functions…

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

cache = lambda{|f| h={} ; lambda{|*args| h[args] ||= f[*args]}}

fac = cache[fac]
tri = cache[tri]
size = cache[size]
line = cache[line]
lines = cache[lines]
pascal = cache[pascal]

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

Refactoring gives us shorter, but less readable code:

def c_lambda(&b)
lambda{|f| h={} ; lambda{|*args| h[*args] ||= f[*args]}}[lambda(&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]

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

94

On Jun 25, 2006, at 2:08 PM, Boris P. wrote:

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

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

This is a pretty common idiom covered by the standard library, just FYI:

require “enumerator”
=> true

[1, 3, 3, 1].each_cons(2) do |l, r|
?> puts “#{l} + #{r} = #{l + r}”

end
1 + 3 = 4
3 + 3 = 6
3 + 1 = 4
=> nil

Thanks for the solution!

James Edward G. II

95

On Jun 26, 2006, at 2:31 AM, Farrel L. wrote:

Here’s my solution. It’s not very efficient but it works:

numberOfRows = ARGV[0].to_i

Just thought you might want to know that we generally use this_style
for variables and methods in Ruby, as opposed to thisStyle.

Thanks for the solution!

James Edward G. II

96

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

Sean C. wrote:

My solution does have one aspect I haven’t noticed in everyone’s great
submissions so it might be illustrative, if nothing else - I wrote my
implementation test first. Other than that, there isn’t too much
novelty in my solution.

IMHO there is too much re-computation of nth_row() in this
implementation. See for yourself with this patch:

  • — pascal.rb 2006-06-26 12:27:51.000000000 -0700
    +++ pascal-2.rb 2006-06-26 12:27:43.000000000 -0700
    @@ -1,5 +1,6 @@
    class Pascal
    def self.nth_row(n)
  • puts “computing nth_row for n=#{n}”, caller
    case n
    when 1
    [1]

I would use cached results of nth_row to avoid re-calculating
previously calculated results.

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

iD8DBQFEoDd2mV9O7RYnKMcRAh1cAKChM701IcAIAnFhr5Pqs/Qy6wnRHgCeLBlc
uJD+aZn1FFQ9aCAnxITTmTA=
=nYrF
-----END PGP SIGNATURE-----

97

“Paul B.” [email protected] writes:

Aha! I had a go at it in Haskell, too, and used the same zipWith technique.
Nice to see you doing Haskell… :slight_smile:

Actually, that got me thinking: why doesn’t zip in Ruby take a block?
It could handle Haskell’s zip (and zip3 etc.) and zipWith then…

It actually takes a block, but only yields and doesn’t map. It would
take a lot of memory if it had to map in every case—not sure that is
a good reason, though.

98

Pascal’s Triangle (#84)

solution by Michael C Nelson

The basic idea is that this takes advantage of the fact that empty

cells can

be represented as zeros. For example,

1 0 1 0

1 1 is like, 0 1 1 0

1 2 1 0 1 2 1 0

1 3 3 1 1 3 3 1

In this way we can just populate the topmost 1 and basically get the

other

diagonal edge 1’s for free just by going though each row below it one

at a

time, and for each cell adding the diagonal upper ones to that cell.

This is taken a step further in that the spaces between each number

can be

zeros as well, like,

1

101

10201

1030301

Since these are zeros as well we can sum up all the spaces in between

them as

well, because they will all turn out to be zero in the end. This makes

the

code a bit simpler.

Also the zeros are not explicitly set but are implemented in the

hash’s

default value block (each row is a hash). This also handles values

outside of

the specified size range and returns 0 to handle edge cases for the

final

row. Also this handles mirroring of the pyramid as only the left half

(including the middle column) is stored in the hash rows. This allows

the

filling out of the pyramid section to only operate on the left half as

an

optimization.

When printed, all zeros are displayed as spaces, to make the final

printout

of the pyramid.

1 000010000

1 1 is really like, 000101000

1 2 1 001020100

1 3 3 1 010303010

Also note that the ‘size’ defined for the hight of the pyramid is also

the

same as the width of half the pyramid plus the middle, this is used

interchangeably in the code.

get the size from the command line, or use default, helped in testing

size = (ARGV[0] || 10).to_i
total_width = 2*size-1

Build an empty pyramid. Only half of the pyramid is held in the Array

of

Hashes, the right half is just a mirror of the left.

pascal = (0…size).map do
Hash.new do |hash, key|
if key > size && key <= total_width
# mirror it
hash[2*size-key]
else
# for everything else we can’t find return zero
0
end
end
end

Seed the pyramid (this is the topmost middle “1”).

pascal[0][size] = 1

Build out the pyramid starting from the top down to the bottom. This

optimizes a bit by only adding one half of the pyramid, which is

mirrored by

the Array of Hashes. Also, this only adds the area in the pyramid in

order to

avoid adding a bunch of zeros in the upper unused sections (there is

still a

bunch of zero adding within the pyramid but this makes the code a bit

simpler). Note: this could add the whole area and it would still

work.
cell_width = 0
(1…size).each do |y|
(size-y…size).each do |x|
value = pascal[y-1][x-1] + pascal[y-1][x+1]
unless value.zero?
pascal[y][x] = value
cell_width = value.to_s.length if cell_width < value.to_s.length
end
end
end

Print out the result based on the cell_width.

(0…size).each do |y|
(1…total_width).each do |x|
if pascal[y][x].zero?
print " “*cell_width
else
printf(”%#{cell_width}d", pascal[y][x])
end
end
print “\n”
end

99

I realize I’m late submitting this, and its already been swamped by all
the other submissions, but here is mine (including symmetric output,
erroring to the outside when centering isn’t possible).

a quick helper method

module Enumerable
def product
inject(1){|p,j| p*j}
end
end

class PascalPrinter
def initialize(n)
@n = n

# get middle element of last row to calculate cell size
# nCr = n! / ( r! * (n-r)! )
# this reduces to the following:
a = @n/2
r = @n - a
max = ((r+1)..@n).product / (2..a).product

@cell_size = max.to_s.size
@cell_size += 1 if (@cell_size % 2).zero? # require odd cell size
@row_size = (@cell_size + 1) * @n  - 1

end

def next_row(a)
j = k = 0;
a.map { |i|
k = i + j;
j = i;
k
} + [1]
end

def row_to_s(row)
mid = row.size / 2 - 1
i = 0
out = row.collect { |v|
s = v.to_s
pad = (@cell_size - s.size)
lpad = pad / 2
rpad = pad - lpad
lpad, rpad = rpad, lpad if i <= mid
i+= 1
(’ ’ * lpad) + s + (’ ’ * rpad)
}.join(" ")

((' ' * ((@row_size - out.size) / 2)) + out)

end

def output
a=[]
@n.times { puts row_to_s(a=next_row(a)) }
end
end

p = PascalPrinter.new(ARGV[0].to_i)
p.output

100

Wow… If this quiz hasn’t set the record for number of entries and
new quizzers, it’s gotta be durned close.