39
\$\begingroup\$

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
\$\endgroup\$
6
  • \$\begingroup\$ NB In a sense this is a simplified version of Distributing the balls \$\endgroup\$ – Peter Taylor Oct 21 '11 at 11:03
  • \$\begingroup\$ @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. \$\endgroup\$ – Steven Rumbalski Oct 21 '11 at 20:57
  • \$\begingroup\$ @StevenRumbalski He's fine. There's a newline between each row, and there is a space between each number, so it meets the criteria. \$\endgroup\$ – Peter Olson Oct 21 '11 at 21:32
  • \$\begingroup\$ @Peter Olson: Thanks for the clarification. What about Tomas T's assumption that n is defined already? \$\endgroup\$ – Steven Rumbalski Oct 21 '11 at 21:50
  • 4
    \$\begingroup\$ @Gaffi Probably not, accepting an answer makes me feel like I'm ending the contest and discouraging new and possibly better answers. \$\endgroup\$ – Peter Olson Jun 8 '12 at 4:05

61 Answers 61

3
\$\begingroup\$

Maple, 46

seq(print(seq(binomial(i,k),k=0..i)),i=0..n-1)

Usage:

> f:=n->seq(print(seq(binomial(i,k),k=0..i)),i=0..n-1);
> f(3)
    1
   1 1
  1 2 1
\$\endgroup\$
3
\$\begingroup\$

VBA, 162 142 102 80 bytes

Saved 22 bytes thanks to Taylor Scott.

This is an old question now but I saw a shorter solution for VBA.

[B2].Resize([A1],[A1])="=IF(COLUMN()>ROW(),"""",IF(ROW()=2,1,IFERROR(A1+B1,1)))"

This is meant to be run in the immediate window. Input is in cell A1 of the active worksheet. Output is in the active worksheet starting at B2 and using however many cells are required based on the input. The COLUMN()>ROW() check keeps the top right of the triangle blank. The ROW()=2 check makes the first value 1 to initiate the triangle. I could have shifted the output down and dropped this check, but it introduces a lot of extraneous output before the actual triangle and I didn't feel that it was in the spirit of the challenge.

I originally posted a much more complicated method that calculated every value based on its row and column. All this method does, though, is to use in-cell formulas. I start at B2 so I can reference the row above it without #REF! errors. Then, it copies and pastes the same formula over a block of cells n wide and n tall. The input and output for n=25 looks like this:

Output

\$\endgroup\$
7
  • \$\begingroup\$ Very cool answer, but you can golf this quite a bit. Converting Function p(r) to Sub p(r) since you have no function output value, removing the space from debug.? c(n,k); and converting the multiline if-then-else statement to a single line (If k Then c=c(n-1,k-1)*n/k Else c=1) brings the byte-count down to 130 by my count \$\endgroup\$ – Taylor Scott Mar 28 '17 at 21:43
  • \$\begingroup\$ @TaylorScott Thanks! I'm pretty new at golfing and only slightly less new to programming in general. I counted 142 because of the line breaks. From what I could find, those are supposed to count. \$\endgroup\$ – Engineer Toast Mar 29 '17 at 12:08
  • \$\begingroup\$ Ah, you are right, I did forget to count my newlines, and as it turns out, at least one other golfing trick For n=0 To... can be condensed to For n=0To... bringing my version of the code to Sub p(r):For n=0To r-1:For k=0To n:Debug.?c(n,k);:Next:Debug.?:Next:End Sub Function c(n,k):If k Then c=1 Else c=c(n-1,k-1)*n/k [char(10)] End Function with a byte count of 139 \$\endgroup\$ – Taylor Scott Mar 30 '17 at 2:44
  • \$\begingroup\$ A second look at this suggests that if you break it down into an immediate window function with a helper function, you can get it down to 112 Bytes (Immediate Window Function: For n=0To[A1-1]:For k=0To n:?c(n,k);:Next:?:Next Helper Function: Function c(n,k) If k Then c=c(n-1,k-1)*n/k Else c=1 End Function) \$\endgroup\$ – Taylor Scott Sep 18 '17 at 1:57
  • 1
    \$\begingroup\$ @TaylorScott What about just dropping them entirely? With a change in the formula, it works just fine. I think that output starting at B2 instead of A1 is acceptable. \$\endgroup\$ – Engineer Toast Sep 20 '17 at 12:23
3
\$\begingroup\$

Perl, 37 bytes

s/\d+/$&+$'/eg,say$_="1 $_"for($a)x<>

Try it online!

\$\endgroup\$
2
\$\begingroup\$

05AB1E, 14 bytes

FN©>F®Ne})ˆ}¯»

Try it online!


1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

PHP, 66+1 bytes

for($a[]=1;$k||$argn>=$k=++$i;)echo$a[--$k]+=$a[$k-1],$k?" ":"
";

65+1 bytes in PHP 5.5 or later:

for($a=[1];$k||$argn>=$k=++$i;)echo$a[--$k]+=$a[$k-1]," 
"[!$k];

Note that the first line has a trailing space!

Run as pipe with -nR or try them online.

\$\endgroup\$
2
\$\begingroup\$

05AB1E, 8 bytes

<ÝεDÝc}»

Try it online!

\$\endgroup\$
6
  • \$\begingroup\$ I... you... I.... what?! \$\endgroup\$ – Magic Octopus Urn Feb 14 '18 at 18:37
  • \$\begingroup\$ 1¸=©sF®NF®«ü+®ì}®«=... I'm ashamed tbh lol. nCr, never seen it used until this answer. \$\endgroup\$ – Magic Octopus Urn Feb 14 '18 at 18:43
  • \$\begingroup\$ @MagicOctopusUrn: I have used it before, but I can't remember in what/which answer(s). Sometimes I wish I had a searchable version of all answers that I could check when I feel like I've done something similar (and maybe better) in the past. \$\endgroup\$ – Emigna Feb 14 '18 at 18:49
  • \$\begingroup\$ Maybe a search for all answers by user:## then extract all indented code blocks that follow a line starting with #[05AB1E] using the SE API :P? \$\endgroup\$ – Magic Octopus Urn Feb 14 '18 at 18:54
  • 2
    \$\begingroup\$ 7 bytes by using a ranged loop without }. \$\endgroup\$ – Kevin Cruijssen Sep 25 '19 at 11:17
2
\$\begingroup\$

K (ngn/k), 16 15 bytes

{x#x{+':x,0}\1}

Try it online!

\$\endgroup\$
2
+50
\$\begingroup\$

Forth (gforth), 58 53 bytes

: P 0 ?do 1 i for dup . i * j i - 1+ / next cr loop ;

Try it online!

This is a heavily shortened version of the implementation here, which was in turn, translated from C.

-5 bytes from Bubbler.

The function is called like: <input> P.

\$\endgroup\$
1
1
\$\begingroup\$

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
\$\endgroup\$
2
  • 2
    \$\begingroup\$ You can spare 4 characters with list slice: replace B.insert(0,1) with B[:0]=[1]. \$\endgroup\$ – manatwork May 23 '12 at 17:51
  • \$\begingroup\$ Yeah! I'm not a very advanced python programmer. And I've changed both of them. \$\endgroup\$ – Rushil Paul May 23 '12 at 19:31
1
\$\begingroup\$

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]);}
\$\endgroup\$
1
\$\begingroup\$

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
)
\$\endgroup\$
1
  • \$\begingroup\$ nice one, though predefined variables are no valid input method. \$\endgroup\$ – Titus Dec 15 '17 at 13:07
1
\$\begingroup\$

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')
\$\endgroup\$
1
  • \$\begingroup\$ I think you output one line too many every time (though neat solution indeed). \$\endgroup\$ – plannapus Dec 15 '17 at 8:59
1
\$\begingroup\$

Prolog (SWI), 124 118 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.

Ungolfed, with comments

% 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).
\$\endgroup\$
1
\$\begingroup\$

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)]]

\$\endgroup\$
1
\$\begingroup\$

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);}
\$\endgroup\$
0
1
\$\begingroup\$

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<.TVac`uY*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) {
        fprintf(stderr, "File not found: %s\n",argv[1]);
        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();
        result = fread(&cell->low,1,1,file);
        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;
}

It's working (very slowly!)

enter image description here

\$\endgroup\$
1
\$\begingroup\$

Python 3, 68 Bytes

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

Japt -R, 16 13 bytes

_ä+T p1}h[1â]

Try it

_äÈ+Y}0 p1}      // f = prepend 0 to array and sums each pairs, then appends 1
           h[1â] // run f input times starting with [[1]]

saved 3 thanks to @Shaggy

\$\endgroup\$
1
  • 1
    \$\begingroup\$ ä+T will work here, too. \$\endgroup\$ – Shaggy Nov 26 '19 at 22:07
1
\$\begingroup\$

Pip -s, 22 21 bytes

La{PooMP:_+BoPU1oPB1}

Try it online!

This was simpler than trying to map an iterable, and probably shorter.

-1 byte from Dlosc, using the PU and PB functions.

Explanation (old)

La{Poo:1AL(_+BMPo)AL1} a → input, o → 1(predefined)
La{                  } loop a times
   Po                  print variable o(joined by spaces due to -s)
     o:                assign o to:
          (_+BMPo)     sums of pairs of it's elements
       1AL        AL1  with 1 added on both sides
\$\endgroup\$
1
  • \$\begingroup\$ I just remembered that PU and PB return lvalues, so: 19 bytes. \$\endgroup\$ – DLosc Oct 3 '20 at 17:44
1
\$\begingroup\$

Pip -s, 14 11 bytes

LaPl+:lPE!l

Try it online!

Explanation

Each row of the triangle, represented as a list, can be obtained by adding two copies of the previous row with an offset:

 [1 2 1]
+  [1 2 1]
----------
 [1 3 3 1]

Pip's default behavior when adding two lists is almost perfect: it matches up the elements and adds them pairwise, and if one list is longer, the extra numbers in that list are retained unchanged. So all we have to do is offset one list by prepending a 0:

 [1 2 1]
+[0 1 2 1]
----------
 [1 3 3 1]

Here's the version I started with before golfing:

Y[1]La{Pyy+:yPE0}
                   a is command-line argument (implicit)
Y[1]               Yank list representing the first row into y
    La{         }  Loop a times:
       Py           Print the current row (space-separated, thanks to -s flag)
            yPE0    Construct a list which is y with 0 prepended
         y+:        Add that to y and assign the result back to y

My original golfed version applied a few tricks:

  • Using this tip, [1]^1.
  • We can save the curly braces if the loop body is one statement, which we can accomplish by printing y in the expression that updates y: y+:(Py)PE0.
  • We can then save the parentheses by changing yPE0 (y with 0 prepended) to 0ALy (0 with the list y appended; 0 gets promoted to a singleton list [0] first). This leaves us with y+:0AL(Py), but since P is unary we can drop the parentheses (though we still need a space between the operators): y+:0AL Py.

The resulting solution is 14 bytes:

Y^1Lay+:0AL Py

But we can do better!

  • It would be nice to save the space before P; also, the initialization Y^1 is rather expensive.
  • If we could start from an empty list (as the "0th" row) and print each row after it is updated, we could solve both problems: we could use l (which is preinitialized to the empty list) instead of y, and the P would come immediately after the loop header and therefore not require a separator.
  • The problem is that our update logic, "prepend a 0 and add," doesn't work for the first row: it gives [] + [0] = [0], when we need [1].
  • But, if we can prepend a 1 on the first iteration and a 0 every other time, we'll be golden. On the first iteration, l is empty (falsey); on every other iteration, l is nonempty (truthy). So we can simply prepend !l.

This approach gives us our 11-byte solution:

LaPl+:lPE!l
La           Loop a times:
         !l   1 if l is empty, 0 otherwise
      lPE     Construct a list which is l with that value prepended
   l+:        Add that to l and assign the result back to l
  P           Print (space-separated: -s flag)
\$\endgroup\$
1
  • \$\begingroup\$ I knew mine wasn't the shortest, but not by this much. What a clean solution. \$\endgroup\$ – Razetime Oct 4 '20 at 3:10
1
\$\begingroup\$

Julia 0.7, 37 bytes

f(x)=@show 1(x<2||[0;F=f(x-1)]+[F;0])

Try it online!

It outputs a lot of garbage but it's allowed:

1 * (x < 2 || [0; F = f(x - 1)] + [F; 0]) = 1
1 * (x < 2 || [0; F = f(x - 1)] + [F; 0]) = [1, 1]
1 * (x < 2 || [0; F = f(x - 1)] + [F; 0]) = [1, 2, 1]
1 * (x < 2 || [0; F = f(x - 1)] + [F; 0]) = [1, 3, 3, 1]
1 * (x < 2 || [0; F = f(x - 1)] + [F; 0]) = [1, 4, 6, 4, 1]
\$\endgroup\$
1
\$\begingroup\$

Google Sheets, 58

Input in arbitrary cell. Assign it named range "N". (+1 count)

Then use

=ArrayFormula(IFERROR(COMBIN(SEQUENCE(N,1,),SEQUENCE(1,N,
\$\endgroup\$
0
\$\begingroup\$

Axiom 64 bytes

p(n)==for j in 0..n-1 repeat output[binomial(j,i) for i in 0..j]

results

(74) -> p 1
   Compiling function p with type PositiveInteger -> Void
   [1]
                                                               Type: Void
(75) -> p 2
   [1]
   [1,1]
                                                               Type: Void
(76) -> p 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]
                                                               Type: Void
\$\endgroup\$
0
\$\begingroup\$

C, 178 bytes

#define x p[i][j]
p[25][51]={0};i;j;f(n){p[0][25]=1;for(i=1;i<n;i++)for(j=1;j<50;j++)x=p[i-1][j-1]+p[i-1][j+1];for(i=0;i<n;i++,putchar(10))for(j=0;j<51;j++)if(x)printf("%d ",x);}

Uniformly Padded, 244 bytes

#define x p[i][j]
s[25]={1,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,5,5,5,5,6,6,6,7,7};p[25][51]={0};i;j;f(n){p[0][25]=1;for(i=1;i<n;i++)for(j=1;j<50;j++)x=p[i-1][j-1]+p[i-1][j+1];for(i=0;i<n;i++,putchar(10))for(j=0;j<51;j++)if(x)printf("%*d ",s[n-1],x);}

Live Demo

Detailed

#include <stdio.h>

int main(void)
{
    int n = 15;
    int s[25]={1,1,1,1,1, 2,2,2,2, 3,3,3,3, 4,4,4, 5,5,5,5, 6,6,6, 7,7};
    int p[25][25+1+25] = { 0 };
    p[0][25] = 1;

    for(int i = 1; i < n; i++)
    {
        for(int j = 1; j < (25+1+24); j++)
        {
            p[i][j] = p[i-1][j-1] + p[i-1][j+1];
        }
    }

    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < (25+1+25); j++)
        {
            if(p[i][j])
            {
                printf("%*d ",s[n-1],p[i][j]);
            }
        }
        printf("\n");
    }

    return 0;
}
\$\endgroup\$
0
\$\begingroup\$

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++];}
}
\$\endgroup\$
0
\$\begingroup\$

Husk, 17 bytes

¶↑:;1´o¡ȯmΣ∂Ṫ*´e1

Try it online!

Explanation

Idea is to use polynomial multiplication beginning with [1,1] and iterate multiplication, take N elements from the resulting infinite list:

¶↑:;1´(¡(mΣ∂Ṫ*))´e1  -- implicit input N
                ´e1  -- duplicate 1 & listify: [1,1]
     ´(        )     -- duplicate [1,1] and apply to:
       ¡(mΣ∂Ṫ*)      --   iterate the function (see below*)
                     -- [[1,1],[1,2,1],[1,3,3,1],…
   ;1                -- listify 1: [1]
  :                  -- prepend: [[1],[1,1],[1,2,1],[1,3,3,1],…
 ↑                   -- take N elements
¶                    -- join with newlines

* That function handles the multiplication, as described here.

\$\endgroup\$
0
\$\begingroup\$

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)
\$\endgroup\$
0
\$\begingroup\$

Scala, 97 bytes

n=>{var p=Seq(1);for(i<-0 to n-1){println(p mkString " ");p=1+:0.to(i-1).map(j=>p(j)+p(j+1)):+1}}

A for loop computes the next line's number sequence from the previous one via simple index-based addition and by concatenating 1's via +: and :+. Unfortunately this iterative approach is slightly shorter than a "nicer" monadic approach via scanLeft :)

Edit: Thanks to all commentors for tips & corrections!

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ I don't think you can accept input through variables that aren't passed to a function. Luckily, it only costs 2 bytes more if you golf it some more. \$\endgroup\$ – user Oct 31 '20 at 18:17
  • \$\begingroup\$ You can actually get 71 bytes using scanLeft. \$\endgroup\$ – user Oct 31 '20 at 18:26
0
\$\begingroup\$

Scala, 58 bytes

Seq.iterate(Seq(1),_){r=>1+:(r,r.tail).zipped.map(_+_):+1}

Try it online!

Somewhat based upon this other Scala answer.

Seq.iterate(                 //Make a Seq
  Seq(1),                      //starting with just [1]
  _                            //of length n (_ is shorthand for n=>...n...
){ r =>                      //Function to get next row from previous row r
  (r,r.tail).zipped.map(_+_)    //Add each cell with the one on its right
1+:                         :+1 //Put two 1's around it
}

Scala 3, 54 bytes

Seq.iterate(Seq(1),_){r=>1+:r.zip(r.tail).map(_+_):+1}

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.