Code-golf: generate pascal's triangle

Question

Generate a list of lists (or print, I don't mind) a Pascal's Triangle of size N with the least lines of code possible!

Here goes my attempt (118 characters in python 2.6 using a trick):

c,z,k=locals,[0],'_[1]'
p=lambda n:[len(c()[k])and map(sum,zip(z+c()[k][-1],c()[k][-1]+z))or[1]for _ in range(n)]

Explanation:

• the first element of the list comprehension (when the length is 0) is [1]
• the next elements are obtained the following way:
• take the previous list and make two lists, one padded with a 0 at the beginning and the other at the end.
  • e.g. for the 2nd step, we take [1] and make [0,1] and [1,0]
• sum the two new lists element by element
  • e.g. we make a new list [(0,1),(1,0)] and map with sum.
• repeat n times and that's all.

usage (with pretty printing, actually out of the code-golf xD):

result = p(10)
lines = [" ".join(map(str, x)) for x in result]
for i in lines:
    print i.center(max(map(len, lines)))

output:

             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

Answer 1

Haskell, 164C with formatting:

i l=zipWith(+)(0:l)$l++[0]
fp=map (concatMap$(' ':).show)f$iterate i[1]
c n l=if(length l<n)then c n$' ':l++" "else l
cl l=map(c(length$last l))l
pt n=cl$take n fp

Without formatting, 52C:

i l=zipWith(+)(0:l)$l++[0]
pt n=take n$iterate i[1]

A more readable form of it:

iterateStep row = zipWith (+) (0:row) (row++[0])
pascalsTriangle n = take n $ iterate iterateStep [1]

-- For the formatted version, we reduce the number of rows at the final step:
formatRow r = concatMap (\l -> ' ':(show l)) r
formattedLines = map formatRow $ iterate iterateStep [1]
centerTo width line =
    if length line < width
        then centerTo width (" " ++ line ++ " ")
        else line
centerLines lines = map (centerTo (length $ last lines)) lines
pascalsTriangle n = centerLines $ take n formattedLines

And perl, 111C, no centering:

$n=<>;$p=' 1 ';for(1..$n){print"$p\n";$x=" ";while($p=~s/^(?= ?\d)(\d* ?)(\d* ?)/$2/){$x.=($1+$2)." ";}$p=$x;}

Answer 2

Another python solution, that could be much shorter if the builtin functions had shorter names... 106 characters.

from itertools import*
r=range
p=lambda n:[[len(list(combinations(r(i),j)))for j in r(i+1)]for i in r(n)]

Answer 3

Perl, 63 characters:

for(0..9){push@z,1;say"@z";@z=(1,map{$z[$_-1]+$z[$_]}(1..$#z))}

Answer 4

Shorter prolog version (112 instead of 164):

n([X],[X]).
n([H,I|T],[A|B]):-n([I|T],B),A is H+I.
p(0,[[1]]):-!.
p(N,[R,S|T]):-O is N-1,p(O,[S|T]),n([0|S],R).

Answer 5

Ruby, 83c:

def p(n);n>0?(m=p(n-1);k=m.last;m+[([0]+k).zip(k+[0]).map{|x|x[0]+x[1]}]):[[1]];end

test:

irb(main):001:0> def p(n);n>0?(m=p(n-1);k=m.last;m+[([0]+k).zip(k+[0]).map{|x|x[0]+x[1]}]):[[1]];end
=> nil
irb(main):002:0> p(5)
=> [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1], [1, 5, 10, 10, 5, 1]]
irb(main):003:0>