25
\$\begingroup\$

In Pascal's triangle each number is the sum of the two numbers directly above it, treating empty spots as zero:

Source: https://en.wikipedia.org/wiki/File:Pascal_triangle_small.png

By rotating the triangle, we can cut out square matrices of varying sizes and rotations which I will call Pascal's matrices. Note that those matrices always need to contain the top \$1\$. Here are some examples:

1  1  1  1
1  2  3  4
1  3  6 10
1  4 10 20

6  3  1
3  2  1
1  1  1

1  5 15 35 70
1  4 10 20 35
1  3  6 10 15
1  2  3  4  5
1  1  1  1  1

1

1  1
2  1

The Task

Given a square matrix containing positive numbers in any reasonable format, decide if it is a Pascal's matrix.

Decide means to either return truthy or falsy values depending on whether the input is a Pascal's matrix, or to fix two constant values and return one for the true inputs and the other for false inputs.

This is , so try to use as few bytes as possible in the language of your choice. The shortest code in each language wins, thus I will not accept an answer.

Test cases

True

[[1, 1, 1, 1], [1, 2, 3, 4], [1, 3, 6, 10], [1, 4, 10, 20]]
[[6, 3, 1], [3, 2, 1], [1, 1, 1]]
[[1, 5, 15, 35, 70], [1, 4, 10, 20, 35], [1, 3, 6, 10, 15], [1, 2, 3, 4, 5], [1, 1, 1, 1, 1]]
[[1]]
[[1, 1], [2, 1]]

False

[[2]]
[[1, 2], [2, 1]]
[[1, 1], [3, 1]]
[[1, 1, 1, 1], [1, 2, 3, 4], [1, 4, 6, 10], [1, 4, 10, 20]]
[[6, 3, 1], [1, 1, 1], [3, 2, 1]]
[[2, 2, 2, 2], [2, 4, 6, 8], [2, 6, 12, 20], [2, 8, 20, 40]]
[[40, 20, 8, 2], [20, 12, 6, 2], [8, 6, 4, 2], [2, 2, 2, 2]] 
[[1, 5, 15, 34, 70], [1, 4, 10, 20, 34], [1, 3, 6, 10, 15], [1, 2, 3, 4, 5], [1, 1, 1, 1, 1]]
\$\endgroup\$
2
  • \$\begingroup\$ Suggested test case: [[40, 20, 8, 2], [20, 12, 6, 2], [8, 6, 4, 2], [2, 2, 2, 2]]. My initial answer was incorrectly truthy for this one, but correct for all of the current test cases. \$\endgroup\$ Mar 19, 2019 at 9:40
  • \$\begingroup\$ @KevinCruijssen Thanks, added. \$\endgroup\$
    – Laikoni
    Mar 19, 2019 at 12:16

11 Answers 11

7
\$\begingroup\$

Brachylog, 28 24 23 bytes

This feels quite long but here it is anyway

  • -4 bytes thanks to DLosc by compressing the optional flips
  • -1 bytes thanks to DLosc again by doing the partial sums in 1 go

{|↔}\↰₁{k{a₀ᶠ+ᵐ}ᵐ⊆?h=₁}

Explanation

{|↔}\↰₁{k{a₀ᶠ+ᵐ}ᵐ⊆?h=₁}       # Tests if this is a pascal matrix:
{|↔}\↰₁                       #     By trying to get a rows of 1's on top
{|↔}                          #       Through optionally mirroring vertically
     \                        #       Transposing
      ↰₁                      #       Through optionally mirroring vertically

       {k{a₀ᶠ+ᵐ}ᵐ⊆?h=₁}       #     and checking the following
                  ?h=₁        #        first row is a rows of 1's
        k{     }ᵐ             #        and for each row except the last
          a₀ᶠ+ᵐ               #          calculate the partial sum by
          a₀ᶠ                 #             take all prefixes of the input
             +ᵐ               #             and sum each
               ⊆?             #        => as a list is a subsequence of the rotated input

Try it online!

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

JavaScript (ES6), 114 bytes

m=>[m,m,m=m.map(r=>[...r].reverse()),m].some(m=>m.reverse(p=[1]).every(r=>p=!r.some((v,x)=>v-~~p[x]-~~r[x-1])&&r))

Try it online!

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

MATL, 17 bytes

4:"Gas2YLG@X!X=va

Try it online! Or verify all test cases.

Outputs 1 for Pascal matrices, 0 otherwise.

Explanation

4:      % Push [1 2 3 4]
"       % For each
  G     %   Push input: N×N
  a     %   1×N vector containing 1 for matrix columns that have at least a nonzero
        %   entry, and 0 otherwise. So it gives a vector containing 1 in all entries
  s     %   Sum. Gives N
  2YL   %   Pascal matrix of that size
  G     %   Push input
  @     %   Push current iteration index
  X!    %   Rotate the matrix that many times in steps of 90 degress
  X=    %   Are they equal?
  v     %   Concatenate with previous accumulated result
  a     %   Gives 1 if at least one entry of the vector is nonzero
        % End (implicit). Display (implicit)
\$\endgroup\$
2
\$\begingroup\$

R, 104 bytes

function(m,R=row(m)-1,y=nrow(m):1,Z=choose(R+t(R),R))any(sapply(list(Z,Z[,y],Z[y,y],Z[y,]),identical,m))

Try it online!

Nasty...

Creates a canonical Pascal's matrix Z with dimensions equal to that of m, then tests if the input matrix m is identical to any of the rotations of Z.

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

Charcoal, 41 bytes

F‹¹⌈§θ⁰≔⮌θθF‹¹⌈Eθ§ι⁰≦⮌θ⌊⭆θ⭆ι⁼λ∨¬κΣ…§θ⊖κ⊕μ

Try it online! Link is to verbose version of code. Explanation:

F‹¹⌈§θ⁰

If the maximum of its first row is greater than 1,

≔⮌θθ

then flip the input array.

F‹¹⌈Eθ§ι⁰

If the maximum of its first column is greater than 1,

≦⮌θ

then mirror the input array.

⌊⭆θ⭆ι

Loop over the elements of the input array and print the minimum result (i.e. the logical And of all of the results),

⁼λ∨¬κΣ…§θ⊖κ⊕μ

comparing each value to 1 if it is on the first row otherwise the sum of the row above up to and including the cell above.

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

Python 2, 129 bytes

f=lambda M,i=4:i and(set(M[0])=={1}and all(a+b==c for x,y in zip(M,M[1:])for a,b,c in zip(x[1:],y,y[1:]))or f(zip(*M[::-1]),i-1))

Try it online!

Returns True if M is a Pascal's Matrix, else 0.

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

05AB1E, 29 bytes

¬P≠iR}DøнP≠ií}¬PΘsü)ε`sηOQ}P*

Try it online or verify all test cases.

Explanation:

¬P≠i }        # If the product of the first row of the (implicit) input-matrix is NOT 1:
    R         #  Reverse the order of the rows
D             # Duplicate the resulting matrix
 øнP≠i }      # If the product of the first column is NOT 1:
      í       #  Reverse each row individually
¬PΘ           # Check if the product of the first row is exactly 1
           *  # AND
          P   # And check if everything after the following map is truthy:
sü)ε     }    #  Map over each pair of rows:
    `sη       #   Get the prefixes of the first row
       O      #   Sum each prefix
        Q     #   And check if it's equal to the second row
              # (and output the result implicitly)
\$\endgroup\$
1
\$\begingroup\$

Kotlin, 269 bytes

{m:List<List<Int>>->val n=m.size
var r=0
var c=0
fun f()=if(m[0][0]!=1)m[n-r-1][n-c-1]
else if(m[n-1][0]!=1)m[r][n-c-1]
else if(m[0][n-1]!=1)m[n-r-1][c]
else m[r][c]
var g=0<1
for(l in 0..n*2-2){r=l
c=0
var v=1
do{if(r<n&&c<n)g=f()==v&&g
v=v*(l-c)/++c}while(--r>=0)}
g}

Try it online!

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

Julia 0.7, 78 bytes

m->any(i->(n=rotr90(m,i))[1]<2&&all(cumsum(n)'[1:end-1,:]-n[2:end,:].==0),0:3)

Try it online!

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

Java (JDK), 234 bytes

m->{int l=m.length,L=l-1,p=1,s=0,S=0,e=l,E=l,d=1,D=1,i,j;if(m[0][0]>1|m[0][L]>1){s=L;e=d=-1;}if(m[0][0]>1|m[L][0]>1){S=L;E=D=-1;}for(i=s;i!=e;i+=d)for(j=S;j!=E;j+=D)p=(i==s|j==S?m[i][j]<2:m[i][j]==m[i-d][j]+m[i][j-D])?p:0;return p>0;}

Try it online!

Credits

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Nice answer, but dang, loads of variables. ;) Oh, and -1: i==s||j==S to i==s|j==S. \$\endgroup\$ Mar 20, 2019 at 14:26
  • \$\begingroup\$ @KevinCruijssen if you know a better algorithm I take it! But the rotation is the cause for all the variables. Some languages can handle them in 1-2 bytes, in Java, you have to think the code around them. The core algorithm is actually pretty short: m->{int l=m.length,i=0,j;for(;i<l;i++)for(j=0;j<l;j++)p=(i<1|j<1?m[i][j]<2:m[i][j]==m[i-1][j]+m[i][j-1])?p:0;return p>0;} (122 bytes) \$\endgroup\$ Mar 20, 2019 at 15:41
  • \$\begingroup\$ 228 \$\endgroup\$
    – ceilingcat
    Jun 19, 2021 at 3:15
1
\$\begingroup\$

Jelly, 22 bytes

Ż€Iṫ2⁼ṖaFḢ=1Ʋ
,Ṛ;U$Ç€Ẹ

Try it online!

Explanation

Helper link, checks whether this rotation of matrix valid

Ż€            | prepend each row with zero
  I           | find differences within rows
   ṫ2         | drop the first row
     ⁼Ṗ       | compare to the original matrix
              |   with the last row removed
       a      | logical and
        FḢ=1Ʋ | top left cell is 1

Main link

,Ṛ            | copy the matrix and reverse the rows
  ;U$         | append a copy of both of these
              |   with the columns reversed
     ǀ       | run each version of the matrix
              |   through the helper link
       Ẹ      | check if any are valid
\$\endgroup\$

Your Answer

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

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