24
\$\begingroup\$

Pascal's triangle is a triangular diagram where the values of two numbers added together produce the one below them.

This is the start of it:

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

You can see that the outside is all 1s, and each number is the sum of the two above it. This continues forever.

Your challenge is to check whether a non-empty array of positive integers is a row of Pascal's triangle, somewhere down the line.

You should output two distinct values for truthy and falsy.

Scoring

This is , shortest wins.

Testcases

Truthy:

[1]
[1,2,1]
[1,3,3,1]
[1,5,10,10,5,1]
[1,6,15,20,15,6,1]
[1,7,21,35,35,21,7,1]

Falsy:

[2]
[1,2]
[1,1,2]
[2,2,2,2]
[1,2,10,2,1]
[1,2,3,4,5,6]
[1,3,5,10,5,3,1]
\$\endgroup\$
3
  • \$\begingroup\$ Can we take the length of the input as input as well? \$\endgroup\$ Commented Sep 15, 2021 at 20:09
  • \$\begingroup\$ Darn you for preventing sum of n = 2^n. 😂 \$\endgroup\$
    – Taco
    Commented Sep 15, 2021 at 21:06
  • \$\begingroup\$ @DLosc No, you don't. \$\endgroup\$
    – emanresu A
    Commented Sep 20, 2021 at 3:59

27 Answers 27

10
\$\begingroup\$

Jelly, 6 bytes

L’cŻ$⁼

Try it online!

As each row of Pascal's triangle has a unique length \$n\$, all we have to do is reconstruct the row, given its length, and check if it equals the original input. As each row is given by \$\binom{n-1}{i}, 0 \le i < n\$, we just calculate that (as Jelly has a 1 byte for binomial coefficient)

In fact, if we can take the length of the input as a second input, we can get 5 bytes

How it works

L’cŻ$⁼ - Main link. Takes a list L on the left
L      - Length of L
 ’     - Decrement
    $  - Last 2 links as a monad f(len-1):
   Ż   -   Range from 0 to len-1
  c    -   Binomial coefficient of len-1 and each element in the range
     ⁼ - Does that equal the input?
\$\endgroup\$
10
\$\begingroup\$

Haskell, 36 31 26 bytes

f[1]=1
f(1:b)=f$scanr1(-)b

Try it online!

This version errors as a false indicator and returns 1 as the true indicator. It's short but I generally find these sorts of answers a little cheaty so below I have a version with a more traditional output method:

42 37 32 bytes

f[1]=1
f(1:b)=f$scanr1(-)b
f _=0

Try it online!

Outputs 1 for yes and 0 for no.

This is I believe the only answer here using this method. We use scanr1(-) to calculate what the layer above would have to be in order to produce the input, and check if that new smaller layer holds. If we encounter [1] we halt with yes, because that is the first layer of Pascal's triangle. And if we encounter something starting with something other than 1 we halt with no.

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

R, 43 bytes

Or R>=4.1, 36 bytes by replacing the word function by \.

function(r)any(r-choose(x<-sum(r|1)-1,0:x))

Try it online!

Taking also length of input as second argument, we can shave 6 bytes off: Try it online!.

\$\endgroup\$
7
\$\begingroup\$

C (clang), 66 bytes

i,c,t;f(*p,n){for(t=c=i=1;i<=n;c=c*(n-i)/i++)t=t&&p[i-1]==c;*p=t;}

Try it online!

C (clang), 55 bytes

i,c;f(*p,n){for(c=i=1;i<=n;c=c*(n-i)/i++)c/=p[i-1]==c;}

Inspired by Wheat Wizards' post. Triggers a floating point exception for falsey.

Try it online!

\$\endgroup\$
3
  • \$\begingroup\$ t isn't initialised so this won't over multiple runs. Copy and paste your single line of calling f and the second time f is run is incorrect. \$\endgroup\$
    – Noodle9
    Commented Sep 16, 2021 at 0:13
  • 1
    \$\begingroup\$ @Noodle9 it is fixed. \$\endgroup\$
    – jdt
    Commented Sep 16, 2021 at 0:45
  • 2
    \$\begingroup\$ Suggest n/i instead of i<=n \$\endgroup\$
    – ceilingcat
    Commented Sep 25, 2021 at 19:02
6
\$\begingroup\$

APL (Dyalog Unicode), 11 9 bytes

Saved 2 bytes thanks to Bubbler

⊢≡⍳∘≢!≢-≡

Try it online!

Requires 0-indexing.

⊢≡⍳∘≢!≢-≡
⊢         ⍝ Does the input
 ≡        ⍝ equal
  ⍳∘≢!≢-≡  ⍝ the row of Pascal's triangle with the same length?
     ≢-≡  ⍝ The number r of the real row that has the same length
     ≢    ⍝ The length of the input
      -≡  ⍝ Decremented/Minus the depth (which is always one)
  ⍳∘≢      ⍝ The column numbers for that row (a range [0..r])
    !     ⍝ Get the number at row r and column c for each element in the previous range
\$\endgroup\$
2
  • 1
    \$\begingroup\$ (⍳≢) → ⍳∘≢, 1-⍨≢ → ≢-≡ (depth of an integer vector is always 1) \$\endgroup\$
    – Bubbler
    Commented Sep 16, 2021 at 1:02
  • \$\begingroup\$ @Bubbler Thanks, the ≢-≡ trick is quite clever! \$\endgroup\$
    – user
    Commented Sep 16, 2021 at 16:22
6
\$\begingroup\$

Lean, 187 176 143 131 bytes

def q:list ℕ→bool:=λx,by{induction x,exact[],apply(::)1,induction x_ih with h t i,exact[],cases t,exact[h],exact(h+t_hd)::i}=x

Try it online!

A simpler version of this can be found below:

Lean, 190 185 169 bytes

def f:ℕ→list ℕ:=λn,by{induction n,exact[],apply(::)1,induction n_ih with h t i,exact[],cases t,exact[h],exact(h+t_hd)::i}
def g:list ℕ→bool:=λx,f(x.length)=x

Try it online!

This version defines a helper function f which gives the \$n\$th row of pascal's triangle. From here we check if the input is equal to the \$m\$th row where \$m\$ is the length of the input.

This is the straightforward way to do things.

The shorter version rolls these two into one. Instead of doing induction on the length of the list, it just does induction on the list itself. This turns the already hairy induction into a real mess.

\$\endgroup\$
2
  • \$\begingroup\$ Does Lean have a SBCS, or are and λ counted as multiple bytes? \$\endgroup\$
    – emanresu A
    Commented Oct 5, 2021 at 22:06
  • \$\begingroup\$ @emanresuA They are multiple bytes. I'm not actually even sure if saves any bytes over nat. \$\endgroup\$
    – Wheat Wizard
    Commented Oct 5, 2021 at 22:06
5
\$\begingroup\$

Vyxal r, 6 bytes

₌ẏL‹ƈ⁼

Try it Online!

vyxal (and lyxal) is the best?

₌ẏL‹ƈ⁼
        (implicit input)
₌       parallel stuffs, do the next two command both on the stack top 
 ẏ      range of len(top)
  L     len(top)            currently stack [range(0,len),len]
   ‹    -1                                                len-1
    ƈ                       do combination caculation C(i,len-1) i= range(0,len)
     ⁼                      check equal     stack are not enough so input is used

\$\endgroup\$
5
\$\begingroup\$

BQN, 15 13 bytesSBCS

-2 bytes thanks to Marshall Lochbaum

-˜`⍟≠≡1‿¯1⥊˜≠

Try it here.

Unlike many array languages, BQN doesn't have a binomial primitive, so a more creative solution is required.

-˜`⍟≠≡1‿¯1⥊˜≠ #
-˜`           # swapped minus scan
   ⍟≠         # repeated input length number of times
     ≡        # matches
      1‿¯1⥊˜≠ # alternating 1,-1 .. extended to the input length
\$\endgroup\$
5
\$\begingroup\$

Julia, 47 38 34 bytes

!l=binomial.((n=[l;0][2];),0:n)==l

Try it online!

Explanation

We just generate the n-th row of the Pascal triangle and test equality.

Thanks to amelies, we can get it down to 38 bytes!

Thanks to MarkMush, we can get it further down to 34 bytes!

\$\endgroup\$
7
  • \$\begingroup\$ You can compute n inside the function an get down to 44 \$\endgroup\$
    – amelies
    Commented Feb 20, 2022 at 20:54
  • \$\begingroup\$ Actually all is not needed: 38 without it. !l=(n=length(l)-1;binomial.(n,0:n)==l) \$\endgroup\$
    – amelies
    Commented Feb 20, 2022 at 20:58
  • \$\begingroup\$ This is really nice! I need to get used to vectorization \$\endgroup\$ Commented Feb 20, 2022 at 21:47
  • 1
    \$\begingroup\$ 34 bytes \$\endgroup\$
    – MarcMush
    Commented Feb 20, 2022 at 22:47
  • 1
    \$\begingroup\$ Instead of getting n from the length of l, we get it from l[2], to which we add a zero to recognize l=[1] as n=0. The rest is the same \$\endgroup\$
    – MarcMush
    Commented Feb 21, 2022 at 10:28
4
\$\begingroup\$

Factor + math.combinatorics, 47 bytes

[ dup length 1 - dup [0,b] [ nCk ] with map = ]

Try it online!

Explanation:

It's a quotation (anonymous function) that takes a sequence of numbers from the data stack as input and leaves a boolean on the data stack as output. Assuming { 1 3 3 1 } is on the data stack when this quotation is called...

  • dup Duplicate the top object on the data stack.

    Stack: { 1 3 3 1 } { 1 3 3 1 }

  • length Get the length of a sequence.

    Stack: { 1 3 3 1 } 4

  • 1 - Subtract one.

    Stack: { 1 3 3 1 } 3

  • dup Duplicate the top object on the data stack.

    Stack: { 1 3 3 1 } 3 3

  • [0,b] Create a range from 0 to whatever is on top of the data stack, inclusive.

    Stack: { 1 3 3 1 } 3 T{ range f 0 4 1 }

  • [ nCk ] with map Take \$\binom{3}{0}\$, \$\binom{3}{1}\$, ... \$\binom{3}{3}\$

    Stack: { 1 3 3 1 } { 1 3 3 1 }

  • = Are the top two objects on the data stack equal?

    Stack: t

\$\endgroup\$
4
\$\begingroup\$

Python 3, 66 bytes

f=lambda a,*r:r<a[1:]and f(a,*map(sum,zip(r,(1,*r))),1)or(1,*r)==a

Try it online!

Constructs the rows of Pascal's triangle recursively until a match is found or the generated row is larger than the input.

\$\endgroup\$
4
\$\begingroup\$

JavaScript (ES6), 46 bytes

Returns a Boolean value.

a=>!a.some(v=>v-n|(n*=a.length/q++-1)-n,q=n=1)

Try it online!

\$\endgroup\$
4
\$\begingroup\$

05AB1E, 6 bytes

g<DÝcQ

Port of @cairdCoinheringaahing's Jelly answer.

Try it online or verify all test cases.

Explanation:

g       # Get the length of the (implicit) input-list
 <      # Decrease it by 1
  D     # Duplicate it
   Ý    # Pop the copy, and push a list in the range [0,length-1]
    c   # Get the binomial coefficient of length-1 with each integer in this list
     Q  # Check if this list is now equal to the (implicit) input-list
        # (after which the result is output implicitly)
\$\endgroup\$
4
\$\begingroup\$

Wolfram Language (Mathematica), 30 bytes

(i=-1;r=++i&/@#)!#==i!/(i-r)!&

Try it online!


Wolfram Language (Mathematica), 38 36 bytes

FromDigits[#,i=-1;r=++i&/@#]==++r^i&

Try it online!

Checks that the polynomial of degree \$n\$ in \$x\$ with these coefficients is equal to \$(x+1)^n\$ by testing it at \$0,...,n\$.

\$\endgroup\$
4
\$\begingroup\$

Pascal (FPC), 165 147 bytes

function f(a:array of word):word;var n,i,c:word;begin
n:=high(a)+1;c:=1;f:=1;for i:=1 to n do begin
if a[i-1]<>c then f:=0;c:=c*(n-i)div i;end;end;

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Python 3.8 (pre-release), 69 bytes

lambda l:[math.comb(~-len(l),x)for x in range(len(l))]==l
import math

Try it online!

Luckily python 3.8 has a built-in for n choose k

\$\endgroup\$
3
\$\begingroup\$

Pip -x, 20 14 bytes

L#al+:lPE!ll=a

Try it here! TIO doesn't support the -x flag, but you can simulate it using the header: Try it online!

Explanation

We generate the nth row of Pascal's triangle, where n is the length of the input list; then we output truthy if the row and the input are equal, falsey otherwise. Heavily based on my answer to Generate Pascal's triangle, which I recommend you read for a better explanation of the core algorithm.

                a is 1st cmdline arg, evaluated (-x flag); l is empty list
L               Loop
 #a              len(a) times:
         !l       1 if l is empty, 0 otherwise
      lPE         l with that value prepended
   l+:            Add to l itemwise and assign back to l
           l=a  1 if l equals a, 0 otherwise
\$\endgroup\$
3
\$\begingroup\$

Charcoal, 20 bytes

⬤θ⎇κ⁼×⁻Lθκ§θ⊖κ×κι⁼¹ι

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - if it's a row, nothing if not. Explanation: The first element must always be 1. Subsequent elements obey the recurrence relation that the previous element multiplied by the inclusive number of elements remaining equals the current element multiplied by its index.

 θ                      Input array
⬤                       Do all elements satisfy
  ⎇κ                    If not first element then
          §θ⊖κ          Previous element
     ×                  Multiplied by
      ⁻Lθκ              Number of elements remaining
    ⁼                   Equals
              ×κι       Current element multiplied by its index
                 ⁼¹ι    If first element then it is `1`
                        Implicitly print
\$\endgroup\$
2
\$\begingroup\$

Desmos, 62 48 bytes

Thanks Bubbler for -14 bytes.

The function \$f(l)\$ takes in a list of numbers, and returns 0 for falsey, 1 for truthy.

a=length(l)-1
f(l)=\min(\{l=\nCr(a,[0...a]),0\})

Try It On Desmos!

Try It On Desmos! - Prettified

\$\endgroup\$
2
  • \$\begingroup\$ You could use "minimum" on the second one if Desmos has such a built-in. \$\endgroup\$
    – Bubbler
    Commented Sep 16, 2021 at 0:32
  • \$\begingroup\$ @Bubbler Why didn't think about that... \$\endgroup\$
    – Aiden Chow
    Commented Sep 16, 2021 at 3:04
2
\$\begingroup\$

Perl 5, 45 44 bytes

sub{$n=$q=1;!grep$_-$n|($n*=@_/$q++-1)*0,@_}

Try it online!

A translation of the JavaScript answer from @Arnauld.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ *0 would be shorter than -$n in Perl. \$\endgroup\$
    – Arnauld
    Commented Sep 15, 2021 at 22:45
2
\$\begingroup\$

Pari/GP, 20 bytes

a->a==binomial(#a-1)

When binomial takes only one argument, it returns the n'th row of the Pascal's triangle.

Try it online!

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

Ruby, 51 bytes

->l{l.all?{r=0;*l,r=l.map{|x|r=x-r};r==(l[0]?0:1)}}

Try it online!

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

Python 3.8 (pre-release), 71 68 bytes

lambda l:[*map(math.comb,(a:=len(l))*[a-1],range(a))]==l
import math

Try it online!

Using some list expansion shenanigans, it can be slightly shorter.

Old answer:

lambda l:list(map(math.comb,(a:=len(l))*[a-1],range(a)))==l
import math

Try it online!

Happily, Python has a built-in combination function. This just uses a simple mapping of that to build the row of Pascal's triangle corresponding to the length of the input list and compares that to the input.

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

Octave, 40 bytes

@(x)all(bincoeff((n=sum(x|1)-1),0:n)==x)

Try it online!

Port of @cairdCoinheringaahing's Jelly answer. Based on the bincoeff function that outputs \$n^{th}-1\$ line of the triangle.

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

JavaScript (Node.js), 42 bytes

a=>a+-1==a.map((v,i)=>n=i?n*a[1]--/i:1)+-n

Try it online!

From Arnauld's. Removing - Fails 1,11,55,165,330,462,462,330,165,55,111

JavaScript (Node.js), 44 bytes

f=a=>(t=a.map(n=>g=n-g,g=0)).pop()?a==1:f(t)

Try it online!

Mine.

\$\endgroup\$
1
  • \$\begingroup\$ positive integers so yes no zeros \$\endgroup\$
    – emanresu A
    Commented Jul 12 at 1:41
1
\$\begingroup\$

Pyt, 14 bytes

ĐŁř⁻ĐŁĐ⑴*⁻⇹ć=Π

Try it online!

                        implicit input (of length n)
ĐŁř⁻                    push [0,1,...,n-1]
    ĐŁĐ⑴*⁻              push [n-1,n-1,...,n-1] (of length n)
           ⇹ć           swap and calculate nCr element-wise
             =          check for equality element-wise
              Π         take product (1 if all true, 0 otherwise); implicit print
\$\endgroup\$
1
\$\begingroup\$

Uiua, 23 characters

/×=≡(÷∩/×⊃(+1)-⇡):⊢⇌.°⊏

It's just the binomial coefficient again, though I didn't realize at first.

Uiua, 14 characters

≡°0°1°⊂?⍥\--1⧻.

My attempt at the scan approach inspired by @Wheat Wizard's Haskell Answer. (error for no, nothing for yes)
I don't know whether this is sufficient, but propably. Even though this abuses the given first value in the input as a 1 from the row above, this is fine because the value in the first position never changes during the process and must be 1 in the end.

Try it here!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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