On Tue, Jun 27, 2006 at 08:30:43AM +0900, Matthew M. wrote:
Wow… If this quiz hasn’t set the record for number of entries and
new quizzers, it’s gotta be durned close.
Definitely. Vastly differing styles, also. I’ve been following the
quizes off and on for a while (I think this is the third I’ve submitted;
many more I’ve done after the fact).
Thanks again to those of you who organize all this.
On 6/25/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.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 xsmain = pp 666
Muhuhaha. Would it be too horrible to say that I like the common lisp
version?
(defun pascal (n &optional (op (constantly t)))
(labels
((compute (row n fn)
(if (= n 0)
row
(let* ((head (cons 0 row))
(tail (reverse head))
(next (mapcar #'+ head tail)))
(funcall fn next)
(compute next (- n 1) fn)))))
(let ((p0 '(1)))
(funcall op p0)
(compute p0 n op))))
Feel free to pass a pretty printer as the second arg Oh, and it’s
runs pretty briskly for me on cmucl.
I had one more try… to see how small I could make the code without
golfing it. This is pretty straightforward, and I thought the direct
calculation of the binomial coefficients (given a cached factorial)
would be faster than array manipulations, but somehow it’s slower:
My earlier version:
Gondor:~ mattmoss$ time ruby pascal.rb 666 > /dev/null
real 0m9.303s
user 0m8.619s
sys 0m0.659s
This version:
Gondor:~ mattmoss$ time ruby pascal.rb 666 > /dev/null
real 0m15.310s
user 0m14.530s
sys 0m0.719s
Not sure why it should be so slow, but offhand (without knowing how to
function-level profile) it seems nearly all the time is spent in
binom().
$fact = Hash.new do |h, n|
stack.
h[n] = (n < 2) ? 1 : n * (n - 1) * h[n - 2]
end
def binom(n, k)
$fact[n] / ($fact[k] * $fact[n - k])
end
def pascal n
fw = binom(n - 1, n / 2).to_s.length # field width
rw = (n * 2) * fw # row width
(0…n).each do |i| # generate and print each row
puts((0…i).map { |x| binom(i, x).to_s.center(2 * fw)
}.join.center(rw))
end
end
pascal (ARGV[0] || 10).to_i
On 6/26/06, Matthew M. [email protected] wrote:
I had one more try… to see how small I could make the code without
golfing it. This is pretty straightforward, and I thought the direct
calculation of the binomial coefficients (given a cached factorial)
would be faster than array manipulations, but somehow it’s slower:
[snipped run-times]
Not sure why it should be so slow, but offhand (without knowing how to
function-level profile) it seems nearly all the time is spent in
binom().
My guess: When calculating binomials, you are running into bignum
territory much faster than iterating and summing. Depending on your
machine, you may be getting up there at around 13! or perhaps 21!
May or may not be a problem, but it’s a thought.
#!/usr/bin/env ruby
def center_str s, len
n = (len - s.length) / 2.0
’ '(n.floor) + s + ’ '(n.ceil)
end
n = ARGV[0].to_i
rows = [[1]]
for i in 1…(n)
k = -1; r = rows[i-1] + [0]
rows << r.map{ |x| j = k; k+=1; x + r[j] }
end
m = rows.last[n/2].to_s.length * 2
n = rows.last.length * m
rows.each do |r|
puts center_str(r.collect{|x| center_str(x.to_s, m)}.join, n)
end
On Jun 26, 2006, at 4:48 PM, Christian N. wrote:
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.
Yet another great use of enumerator
[1,2,3].to_enum(:zip, [4, 5, 6]).map { |x, y| x + y }
Sure, it’s a little verbose, but it works.
One could even do
class Array
def zip_with(array, &block)
to_enum(:zip, array).map(&block)
end
end
if the above is too much typing.
On 6/26/06, Suraj N. Kurapati [email protected] wrote:
IMHO there is too much re-computation of nth_row() in this
implementation. See for yourself with this patch:
Suraj,
You are absolutely right that my implementation is not the most
efficient.
You could even call it wasteful. The thing is, I believe you should
never
optimize prematurely. Without specific data telling me my solution is
too
slow, I would almost never rewrite it to be faster. I would make
changes to
make things more clear but not to make them faster. I wouldn’t optimize
until I knew the speed requirements. For example, if the client came
back
and said we need to complete the pascal triangle of 1000 in under 10
seconds, then I would start profiling to find out how to make that
happen.
Sean
Mike N. [email protected] writes:
This is taken a step further in that the spaces between each number
can be zeros as well, like,
This with the zeros is what I did in my first solution; however, I
didn’t think of this trick, letting the hash’s default values fill in
the rest.
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.
I think we might get a nice solution combining this trick with the
object I used in my second solution that behaved like 0 with regards
to arithmetic, but had a to_s method that returned “”.
I do worry about the memory used by your solution, since you need to
have half of the whole tree in memory at once.
I might do to fix it. Personally, I’d rather have code that is easier to
read or finish faster than take up a chunk of memory. But this is maybe
just my preference.
I don’t think people are examining the memory issue because of this
particular problem; you’re right, this triangle could probably grow
pretty damn large before anyone really noticed.
I think people look at the memory issues more as an exercise. If this
problem were such that we needed around 1,000,000 rows or more, or
perhaps this problem were on an embedded device with 64K RAM (ignore
the Ruby libs/exe), then you’ll have issues with a solution that just
allocates the whole triangle. Some folks are curious (self-included)
as to how they might solve the problem with that consideration.
(You’ll also see people here going the opposite route, to make it as
fast as possible no holds bars… both are optimization problems.)
As they say, the root of all evil is “vi”… I mean, premature
optimization. But if it’s just an exercise to see how to do it, I
say, let them use emacs… err, optimize.
Daniel M. wrote:
I think we might get a nice solution combining this trick with the
object I used in my second solution that behaved like 0 with regards
to arithmetic, but had a to_s method that returned “”.
I like that solution. I was thinking that I wanted something like this
when I was working on my solution.
I do worry about the memory used by your solution, since you need to
have half of the whole tree in memory at once.
I know a lot of people mentioned this as a possible issue with solutions
in general here, but this really doesn’t seem like an issue to me. The
whole tree for say 1000 rows is only something like around 250,250
digits here, (n(n+1)/2)/2 (as stored in the Hashes). I’m not sure of the
size of the digits in actual RAM but that doesn’t really seem like a
lot. I’m guessing not more than maybe 5M total, counting the keys
(another digit for each). Seems like a pretty minor cost to me for what
I might do to fix it. Personally, I’d rather have code that is easier to
read or finish faster than take up a chunk of memory. But this is maybe
just my preference.
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
Sean C. wrote:
The thing is, I believe you should never optimize prematurely.
Without specific data telling me my solution is too slow, I would
almost never rewrite it to be faster. I would make changes to
make things more clear but not to make them faster. I wouldn’t
optimize until I knew the speed requirements.
Ah, good approach. 
I keep hearing about this, but it’s hard for
me after being ruined by years of C programming.
For example, if the client came back and said we need to complete
the pascal triangle of 1000 in under 10 seconds, then I would
start profiling to find out how to make that happen.
This is more of the situation I was thinking of: “How does this
implementation scale to large triangles?”
In this implementation, nth_row is called n+1 times for a given n.
That’s fine if nth_row had a constant access time O(1). However,
nth_row(x) recursively calls itself x-1 times. So the upper bound of
computation for a triangle with n rows is:
O((n rows) * (x-1 recursions per row)) = O(n**2)
This motivated me to suggest caching in your implementation, so that
you could bring down the execution time to O(n).
BASIC is to computer programming as QWERTY is to typing.
– Seymour Papert
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2.2 (GNU/Linux)
iD8DBQFEoZBAmV9O7RYnKMcRAslaAJ42EM31xC9/ZCKR/wblNT+/PgaJpACgr/H8
Zm9068I7/fwBgbI7DPIUCSI=
=tAFw
-----END PGP SIGNATURE-----
OMG WTF BBQ!
“Matthew M.” [email protected] writes:
(You’ll also see people here going the opposite route, to make it as
fast as possible no holds bars… both are optimization problems.)
I’m now tempted to /really/ go the opposite route, and make the
calculation as painfully slow as possible, and use up gobs of memory
while I’m at it.
Something like this monstrosity.
It’s not just expensive memory-wise, creating temporary two-element
arrays all over the place, and pre-filling the hash with a load of
different singleton objects, it’s also expensive CPU-wise: the code
depends on a slew of callcc invocations, which are slow to begin with
and to top that the algorithm itself is fundamentally O(n*2^n), so will
take ages on even the fastest hardware.
On my fast machine, I really didn’t want to run this for more than 20
rows. I’m not letting this code anywhere near my slow machine.
$ time ruby painful_ppt.rb 20 > /dev/null
real 0m54.559s
user 0m53.421s
sys 0m0.921s
For comparison, on the same machine my second solution gives these
times:
$ time ruby ppt.rb 1000 > /dev/null
real 0m27.440s
user 0m25.186s
sys 0m2.171s
Despite its usefulness as an example of how NOT to program, though, I
do think that this code illustrates a nice feature of Pascal’s
triangle: namely, that the number at any spot represents the number of
paths to that spot from the top point in the triangle, if you only
move down-and-right or down-and-left.
================ painful_ppt.rb ===============
#!ruby
$coin_spots = []
def flip_coin
callcc { |c|
$coin_spots.push(c)
return true
}
false
end
def reflip
$coin_spots.pop.call
end
def pp_pascal(n)
ptri = {}
n.times { |p|
(2*n - 1).times { |q|
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
ptri[[p,q]] = g
}
}
if flip_coin then
(0 … n).inject(n-1){ |q,p|
ptri[[p,q]] = ptri[[p,q]]+1
q + (flip_coin ? 1 : -1)
}
reflip
else
width = (ptri[[n-1,n-1]]+ptri[[n-1,n]]).to_s.length
fmt = [“%#{width}s”] * 2 * n
fmt.pop
fmt[0] = “%1s”
fmt[-1] = “%s”
n.times { |p|
pascal_row = (0 … fmt.size).map{|q| ptri[[p,q]]}
pascal_row.zip(fmt){|v,f| print(f%v)}
puts “”
}
end
end
if FILE == $0
n = 4
n = ARGV[0].to_i if ARGV[0]
pp_pascal(n)
end
END
On Jun 26, 2006, at 6:30 PM, Matthew M. wrote:
Wow… If this quiz hasn’t set the record for number of entries and
new quizzers, it’s gotta be durned close.
It’s the most popular quiz ever by no small margin!
James Edward G. II
P.S. Can you see me struggling to keep up? 
On Jun 28, 2006, at 3:31 AM, Dirk M. wrote:
James Edward G. II
P.S. Can you see me struggling to keep up?
I’m sorry that i’m putting you through this, James
but it’s great to see so many enlightning solutions to the problem!
I’ll survive. Thanks for the terrific quiz Dirk!
James Edward G. II
James Edward G. II wrote:
Ok, I wasn’t going to send this in, but if it means making the most
popular quiz ever even more popular …
My pascal triangle solution aims for single expression hideousness. 
puts (0…ARGV.first.to_i).inject([[1]]) { |a,x|
a.unshift a.first.inject([0,[]]) { |b,y|
[y,b.last << (b.first + y)]
}.last + [1]
}.inject([]) { |c,z|
next [z[z.length/2].to_s.length*2,z.length,“”] if c.empty?
[c[0],c[1], z.map { |j|
j.to_s.center(c[0])
}.join(‘’).center(c[0]*c[1])+“\n#{c.last}”]
}.last
Kelly Norton wrote:
Ok, I wasn’t going to send this in, but if it means making the most
popular quiz ever even more popular …
My pascal triangle solution aims for single expression hideousness.
Wow, I realy had a good time trying to figure out what’s going on in
that expression of yours. I really like this one, very clever. I learned
a couple of new tricks there (new to me at least).
2006/6/28, James Edward G. II [email protected]:
P.S. Can you see me struggling to keep up?
I’m sorry that i’m putting you through this, James
but it’s great to see so many enlightning solutions to the problem!
greetings, Dirk.
hoho
monster~~~~came
Hi,
I just had to do this on myself. And because I can’t rest until it
looks perfect, I couldn’t submit my first version and had to polish it
this whole night, so here it is.
~/ruby/% time ./pascal.rb 666 >/dev/null
./pascal.rb 666 > /dev/null 34,36s user 0,82s system 99% cpu 35,508
total
… which isn’t too shabby for a very limited P2-350.
#!/usr/bin/ruby
module Pascal
def triangle(lines, &pretty_printer)
!block_given? && pretty_printer = std_pretty_printer(lines)
line = [ ]
lines.times do
prev = 0
line = line.map { |v| r, prev = prev + v, v; r } + [ 1 ]
pretty_printer.call(line)
end
end
def std_pretty_printer(lines)
width = cell_width(lines)
linewidth = lines * width
proc do |l|
puts l.map { |n| n.to_s.center(width) }.join.center(linewidth)
end
end
def sierpinski_pretty_printer(lines, odd=" “, even=”**")
w = lines*odd.length
proc do |l|
puts l.map { |n| if (n%2).zero? then even else odd end
}.join.center(w)
end
end
private
def factorial(n)
(2…n).inject(1) { |a,b| a*b }
end
def cell_width(l)
a = l - 1
b = a/2.floor
c = (factorial(a) / (factorial(b) * factorial(a-b))).to_s.length
c + 2 - (c % 2)
end
module_function :triangle, :std_pretty_printer,
:sierpinski_pretty_printer
module_function :factorial, :cell_width
end
if FILE == $0
lines = ARGV[0] ? ARGV[0].to_i : 10
Pascal::triangle(lines)
#Pascal::triangle(lines) { |l| puts l.join(" ") }
#Pascal::triangle(lines, &Pascal::sierpinski_pretty_printer(lines,
“/\”, " "))
end
##########snip
~/ruby/% ./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
-Jürgen
This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.
Sponsor our Newsletter | Privacy Policy | Terms of Service | Remote Ruby Jobs