Generate Pascal's triangle

Pascal's triangle is generated by starting with a 1 on the first row. On subsequent rows, the number is determined by the sum of the two numbers directly above it to the left and right.

To demonstrate, here are the first 5 rows of Pascal's triangle:

    1
1 1
1 2 1
1 3 3 1
1 4 6 4 1


The Challenge

Given an input n (provided however is most convenient in your chosen language), generate the first n rows of Pascal's triangle. You may assume that n is an integer inclusively between 1 and 25. There must be a line break between each row and a space between each number, but aside from that, you may format it however you like.

This is code-golf, so the shortest solution wins.

Example I/O

> 1
1
> 9
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

• NB In a sense this is a simplified version of Distributing the balls – Peter Taylor Oct 21 '11 at 11:03
• @Peter Olson: What's your opinion of ratchet freak's interpretation of "you may format it however you like"? If I followed his interpretation I could shave 18 characters. – Steven Rumbalski Oct 21 '11 at 20:57
• @StevenRumbalski He's fine. There's a newline between each row, and there is a space between each number, so it meets the criteria. – Peter Olson Oct 21 '11 at 21:32
• @Peter Olson: Thanks for the clarification. What about Tomas T's assumption that n is defined already? – Steven Rumbalski Oct 21 '11 at 21:50
• @Gaffi Probably not, accepting an answer makes me feel like I'm ending the contest and discouraging new and possibly better answers. – Peter Olson Jun 8 '12 at 4:05

Python 105 chars

A=[1]
for i in range(input()):
B=[sum(A[j:j+2])for j in range(i)]
B[:0]=[1]
B[i+1:]=[1]
print A
A=B

• You can spare 4 characters with list slice: replace B.insert(0,1) with B[:0]=[1]. – manatwork May 23 '12 at 17:51
• Yeah! I'm not a very advanced python programmer. And I've changed both of them. – Rushil Paul May 23 '12 at 19:31

C, 108 (126)

Length depends on whether the #include can be omitted, as it is some other C examples. Code uses edk.h as the shortest (Microsoft) standard C header with stdio.h included.

#include <edk.h>
int a[25]={1},b,c,d;main(){for(scanf("%d",&d);c++<d;)for(b=c;b--;printf("%d%c",a[b],b?32:10),a[b+1]+=a[b]);}


PHP, 105 92 characters

for($e=1;$e++<=$i;$n=$a,$a=''){
foreach($n as$k=>$v)$a[]=$v+$n[$k-1];$a[]=1;print_r($a);}  Input: $i = 9;

Output:

Array
(
[0] => 1
)
Array
(
[0] => 1
[1] => 1
)
Array
(
[0] => 1
[1] => 2
[2] => 1
)
Array
(
[0] => 1
[1] => 3
[2] => 3
[3] => 1
)
Array
(
[0] => 1
[1] => 4
[2] => 6
[3] => 4
[4] => 1
)
Array
(
[0] => 1
[1] => 5
[2] => 10
[3] => 10
[4] => 5
[5] => 1
)
Array
(
[0] => 1
[1] => 6
[2] => 15
[3] => 20
[4] => 15
[5] => 6
[6] => 1
)
Array
(
[0] => 1
[1] => 7
[2] => 21
[3] => 35
[4] => 35
[5] => 21
[6] => 7
[7] => 1
)
Array
(
[0] => 1
[1] => 8
[2] => 28
[3] => 56
[4] => 70
[5] => 56
[6] => 28
[7] => 8
[8] => 1
)

• nice one, though predefined variables are no valid input method. – Titus Dec 15 '17 at 13:07

Perl, 111 characters

I know this can be improved on, just a first try:

$r=<>; @p=(1); while($r--){
print join(' ',@p)."\n";
@q=@p;
unshift @q,0;
push @p,0;
$i=0; foreach(@p){$_+=$q[$i++];}
}


R, 38 bytes

for(i in 0:scan())print(choose(i,0:i))


Try it online!

The other R answer is good, but this is shorter, and that one still needs a call to scan()!

In R, choose is vectorized over k so this is a neat solution. print also prints out the element number at the start of each line, so if that's not valid, I can change this to a 41 byte solution,

for(i in 0:scan())cat(choose(i,0:i),'\n')

• I think you output one line too many every time (though neat solution indeed). – plannapus Dec 15 '17 at 8:59

Jelly, 17 bytes

3Bj+2\
1Ç⁸’¤Ð¡K€Y


Try it online!

If "provided however is most convenient in your chosen language" means that I can use 0-indexed input instead of 1-indexed, then ’¤ can be removed for -2.

Prolog (SWI), 124118 114 bytes

r([A,B|R],[C|S]):-C is A+B,r([B|R],S).
r(L,L).
t(L,I):-I=0;write(L),nl,r([0|L],M),J is I-1,t(M,J).
t(N):-t([1],N).


The predicate t(N) outputs N rows of Pascal's triangle. Try it online!

Note that if you're running this locally, Prolog will probably tell you there's more than one result; if you ask for the next result, it might either output some invalid row(s) or print ever-increasing rows of the triangle till it crashes. I don't think this invalidates the solution, since it behaves exactly as desired on TIO. At any rate, a 4-byte fix is to add a couple of "cuts": insert ,! before the period at the end of line 1, and again after I=0 in line 3.

% nextRow/2 takes the current row (with a zero prepended) and builds the next row
% Example: nextRow([0, 1, 2, 1], X) gives X = [1, 3, 3, 1]

% Base case: we've gotten down to the final 1, which stays the same in the next row
nextRow([1], [1]).
% Recursive case: an element in the next row is the sum of the two elements
% above it in the current row
nextRow([A, B | Tail], [C | NewTail]) :- C is A+B, nextRow([B | Tail], NewTail).

% triangle/2 takes the current row and the number of rows left and outputs that
% many rows

% Base case: no rows left; we're done
triangle(_, 0) :- !.
% Recursive case: output the current row, build the next row, and recurse with
% decremented number of rows left
triangle(Row, RowsLeft) :-
write(Row), nl,
nextRow([0 | Row], NewRow),
NewRowsLeft is RowsLeft-1,
triangle(NewRow, NewRowsLeft).

% triangle/1 takes the number of rows N and outputs that many rows starting from [1]

triangle(N) :- triangle([1], N).


JavaScript, 70 69 bytes

Generating Pascal's Triangle in a golfy manner has always given me brain ache but every time it comes up, I give it another try. Last night, armed with a few beers, I finally cracked it and came up with a working solution I was happy with. Fitting, then, that this should be my 500th (undeleted) solution here.

0-indexed and includes a trailing newline and a trailing space on each line.

n=>(g=x=>x++>n?:(h=z=>y>x?:z+ +h(z*(x-y)/y++))(y=1)+
+g(x))


Try it

o.innerText=(f=
n=>(g=x=>x++>n?:(h=z=>y>x?:z+ +h(z*(x-y)/y++))(y=1)+
+g(x)))(i.value=8);oninput=_=>o.innerText=f(+i.value)
<input id=i type=number><pre id=o></pre>

Perl, 37 bytes

"[!$k];  Note that the first line has a trailing space! Run as pipe with -nR or try them online. Pyt, 9 bytes If the output format was less restrictive, then this could be 8 bytes (just remove 'Á') řĐř⁻⇹⁻⇹ćÁ  Explanation:  Implicit input (n) ř Push [1,2,...,n] Đ Duplicate top of stack ř Push [[1],[1,2],[1,2,3],...,[1,2,...,n]] ⁻ Decrement element-wise [[0],[0,1],[0,1,2],...,[0,1,...,n-1]] ⇹ Swap top two elements on stack ⁻ Decrement [0,1,2,...,n-1] ⇹ Swap top of stack ć Compute nCr† Á Push contents of array on top of stack to the stack  Try it online! † - This yields [[0C0],[1C0,1C1],[2C0,2C1,2C2],...,[(n-1)C0,(n-1)C1,...,(n-1)C(n-1)]] Pyth, 6 bytes m.cLdh  Try it online! Code |Explanation --------+------------------------------ m.cLdh |Full code m.cLdhdQ|With implicit variables filled --------+------------------------------ m Q|For each d in [0, input): L hd | For each k in [0, d]: .c d | dCk L | Collect results in a list m |Collect results in a list |Print result (implicit)  Java 10, 143 138 bytes r->{var s="";for(int i=0,j;i++<r;s+="\n")for(j=0;j++<i;s+=p(i,j)+" ");return s;}int p(int r,int k){return--r<1|k<2|k>r?1:p(r,k-1)+p(r,k);}  -2 bytes thanks to @ceilingcat. Explanation: Try it online. r->{ // Method with integer parameter and String return-type var s=""; // Result-String, starting empty for(int i=0,j;i++<r; // Loop i in the range [1, r]: s+="\n") // After every iteration: Append a new-line for(j=0;j++<i; // Inner loop j in the range [1, i]: s+=p(i,j) // Append the j'th Pascal Triangle number on the i'th row +" "); // and also append a space return s;} // Return the result-String // Separated recursive method to get the k'th value of the r'th row in the Pascal Triangle int p(int r,int k){return--r<1|k<2|k>r?1:p(r,k-1)+p(r,k);}  Malbolge Unshackled (20-trit rotation variant), 3,2485e7 bytes Size of this answer exceeds maximum postable program size (eh), so the code is located in my GitHub repository. It's a slow monstrosity, but I love this one. The digits are being displayed in hexadecimal form. Btw, the code is compressed using 7Zip and PPMd algorithm, because the program is plain too big to post to Github in it's state of art. How to run this? This might be a tricky part, because naive Haskell interpreter will take ages upon ages to run this. TIO has decent Malbogle Unshackled interpreter, but sadly I won't be able to use it (limitations). The best one I could find is the fixed 20-trit rotation width variant, that performs very well. To make the interpreter a bit faster, I've removed all the checks from Matthias Lutter's Malbolge Unshackled interpreter. My modified version can run around 6,3% faster. #include <malloc.h> #include <stdio.h> #include <stdlib.h> #include <string.h> const char* translation = "5z]&gqtyfr$(we4{WP)H-Zn,[%\\3dL+Q;>U!pJS72Fh"
"OA1CB6v^=I_0/8|jsb9m<.TVacuY*MK'X~xDl}REokN:#?G\"i@";

typedef struct Word {
unsigned int area;
unsigned int high;
unsigned int low;
} Word;

void word2string(Word w, char* s, int min_length) {
if (!s) return;
if (min_length < 1) min_length = 1;
if (min_length > 20) min_length = 20;
s[0] = (w.area%3) + '0';
s[1] = 't';
char tmp[20];
int i;
for (i=0;i<10;i++) {
tmp[19-i] = (w.low % 3) + '0';
w.low /= 3;
}
for (i=0;i<10;i++) {
tmp[9-i] = (w.high % 3) + '0';
w.high /= 3;
}
i = 0;
while (tmp[i] == s[0] && i < 20 - min_length) i++;
int j = 2;
while (i < 20) {
s[j] = tmp[i];
i++;
j++;
}
s[j] = 0;
}

unsigned int crazy_low(unsigned int a, unsigned int d){
unsigned int crz[] = {1,0,0,1,0,2,2,2,1};
int position = 0;
unsigned int output = 0;
while (position < 10){
unsigned int i = a%3;
unsigned int j = d%3;
unsigned int out = crz[i+3*j];
unsigned int multiple = 1;
int k;
for (k=0;k<position;k++)
multiple *= 3;
output += multiple*out;
a /= 3;
d /= 3;
position++;
}
return output;
}

Word zero() {
Word result = {0, 0, 0};
return result;
}

Word increment(Word d) {
d.low++;
if (d.low >= 59049) {
d.low = 0;
d.high++;
if (d.high >= 59049) {
fprintf(stderr,"error: overflow\n");
exit(1);
}
}
return d;
}

Word decrement(Word d) {
if (d.low == 0) {
d.low = 59048;
d.high--;
}else{
d.low--;
}
return d;
}

Word crazy(Word a, Word d){
Word output;
unsigned int crz[] = {1,0,0,1,0,2,2,2,1};
output.area = crz[a.area+3*d.area];
output.high = crazy_low(a.high, d.high);
output.low = crazy_low(a.low, d.low);
return output;
}

Word rotate_r(Word d){
unsigned int carry_h = d.high%3;
unsigned int carry_l = d.low%3;
d.high = 19683 * carry_l + d.high / 3;
d.low = 19683 * carry_h + d.low / 3;
return d;
}

// last_initialized: if set, use to fill newly generated memory with preinitial values...
Word* ptr_to(Word** mem[], Word d, unsigned int last_initialized) {
if ((mem[d.area])[d.high]) {
return &(((mem[d.area])[d.high])[d.low]);
}
(mem[d.area])[d.high] = (Word*)malloc(59049 * sizeof(Word));
if (!(mem[d.area])[d.high]) {
fprintf(stderr,"error: out of memory.\n");
exit(1);
}
if (last_initialized) {
Word repitition[6];
repitition[(last_initialized-1) % 6] =
((mem[0])[(last_initialized-1) / 59049])
[(last_initialized-1) % 59049];
repitition[(last_initialized) % 6] =
((mem[0])[last_initialized / 59049])
[last_initialized % 59049];
unsigned int i;
for (i=0;i<6;i++) {
repitition[(last_initialized+1+i) % 6] =
crazy(repitition[(last_initialized+i) % 6],
repitition[(last_initialized-1+i) % 6]);
}
unsigned int offset = (59049*d.high) % 6;
i = 0;
while (1){
((mem[d.area])[d.high])[i] = repitition[(i+offset)%6];
if (i == 59048) {
break;
}
i++;
}
}
return &(((mem[d.area])[d.high])[d.low]);
}

unsigned int get_instruction(Word** mem[], Word c,
unsigned int last_initialized,
int ignore_invalid) {
Word* instr = ptr_to(mem, c, last_initialized);
unsigned int instruction = instr->low;
instruction = (instruction+c.low + 59049 * c.high
+ (c.area==1?52:(c.area==2?10:0)))%94;
return instruction;
}

int main(int argc, char* argv[]) {
Word** memory[3];
int i,j;
for (i=0; i<3; i++) {
memory[i] = (Word**)malloc(59049 * sizeof(Word*));
if (!memory) {
fprintf(stderr,"not enough memory.\n");
return 1;
}
for (j=0; j<59049; j++) {
(memory[i])[j] = 0;
}
}
Word a, c, d;
unsigned int result;
FILE* file;
if (argc < 2) {
// read program code from STDIN
file = stdin;
}else{
file = fopen(argv[1],"rb");
}
if (file == NULL) {
return 1;
}
a = zero();
c = zero();
d = zero();
result = 0;
while (!feof(file)){
unsigned int instr;
Word* cell = ptr_to(memory, d, 0);
(*cell) = zero();
if (result > 1)
return 1;
if (result == 0 || cell->low == 0x1a || cell->low == 0x04)
break;
instr = (cell->low + d.low + 59049*d.high)%94;
if (cell->low == ' ' || cell->low == '\t' || cell->low == '\r'
|| cell->low == '\n');
else if (cell->low >= 33 && cell->low < 127 &&
(instr == 4 || instr == 5 || instr == 23 || instr == 39
|| instr == 40 || instr == 62 || instr == 68
|| instr == 81)) {
d = increment(d);
}
}
if (file != stdin) {
fclose(file);
}
unsigned int last_initialized = 0;
while (1){
*ptr_to(memory, d, 0) = crazy(*ptr_to(memory, decrement(d), 0),
*ptr_to(memory, decrement(decrement(d)), 0));
last_initialized = d.low + 59049*d.high;
if (d.low == 59048) {
break;
}
d = increment(d);
}
d = zero();

unsigned int step = 0;
while (1) {
unsigned int instruction = get_instruction(memory, c,
last_initialized, 0);
step++;
switch (instruction){
case 4:
c = *ptr_to(memory,d,last_initialized);
break;
case 5:
if (!a.area) {
printf("%c",(char)(a.low + 59049*a.high));
}else if (a.area == 2 && a.low == 59047
&& a.high == 59048) {
printf("\n");
}
break;
case 23:
a = zero();
a.low = getchar();
if (a.low == EOF) {
a.low = 59048;
a.high = 59048;
a.area = 2;
}else if (a.low == '\n'){
a.low = 59047;
a.high = 59048;
a.area = 2;
}
break;
case 39:
a = (*ptr_to(memory,d,last_initialized)
= rotate_r(*ptr_to(memory,d,last_initialized)));
break;
case 40:
d = *ptr_to(memory,d,last_initialized);
break;
case 62:
a = (*ptr_to(memory,d,last_initialized)
= crazy(a, *ptr_to(memory,d,last_initialized)));
break;
case 81:
return 0;
case 68:
default:
break;
}

Word* mem_c = ptr_to(memory, c, last_initialized);
mem_c->low = translation[mem_c->low - 33];

c = increment(c);
d = increment(d);
}
return 0;
}


Python 3, 68 Bytes

b=lambda n,a=[1]:n and[print(a),b(n-1,[*map(sum,zip([0]+a,a+[0]))])]


C, 311 bytes

r(int*s,int*o,int n){int h=1;while(h<=n){if(h==2){printf("%d %d\n",1,1);o[0]=1;o[1]=1;}else if(h==1){printf("%d\n",1);o[0]=1;}else{int j=0;int*s_p=s,*o_p=o;*o_p++=1;printf("1 ");while(j<(h-2)){*o_p+=*s_p++;*o_p+++=*s_p;printf("%d ",*(o_p-1));j++;}*o_p=1;printf("1\n");}memcpy(s,o,100);memset(o,0,100);h++;}}


The complete, readable version of the program is below:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void row(int *s,int *o,int n)
{   int h = 1;

while (h <= n)
{

if(h==2){printf("%d %d\n",1,1);o[0]=1;o[1]=1;}

else if(h==1){printf("%d\n",1);o[0]=1;}

else
{
int j = 0; int *s_p=s,*o_p=o;*o_p++ =1;printf("1 ");

while(j<(h-2))
{
*o_p += *s_p++;

*o_p++ += *s_p;

printf("%d ",*(o_p-1));

j++;
}

*o_p=1;printf("1 ");puts("");
}
memset(s,0,100);memcpy(s,o,100);memset(o,0,100);h++;

}

}

int main(int argc,char ** argv)
{
const int n = strtol(argv[1],0,10);

row(n);
}

• You can use a shorter function name to save some bytes. – mbomb007 Aug 4 at 20:16
• I renamed the function to r. Thanks. – T. Salim Aug 4 at 20:19
• Extra whitespace, long variable names, unecessary parentheses, lists can be declared outside the function to remove the static int, first memset is not needed, 100s can be 99, the puts can be combined with the printf, second o[0]=1; can be removed – Jo King Aug 4 at 22:36
• Got rid of the first memset and unnecessary puts. I don't know what you mean by replacing 100 with 99 because if n == 25 and since sizeof(int)==4, then I think it should remain a 100. – T. Salim Aug 4 at 22:42
• You don't need to reset the last element since you don't need to support the 26th iteration. Why did you put the lists back in the input? The question only specifies n as input, and you aren't using them as output? You still have the long variable names and the extra o[0]=1` – Jo King Aug 4 at 23:14