¿Es esta la matriz de Pascal?

25

En el triángulo de Pascal cada número es la suma de los dos números directamente encima de él, tratando los espacios vacíos como cero:

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

Al girar el triángulo, podemos cortar matrices cuadradas de diferentes tamaños y rotaciones que llamaré las matrices de Pascal . Tenga en cuenta que esas matrices siempre deben contener el 1 superior . Aquí hay unos ejemplos:

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

La tarea

Dada una matriz cuadrada que contiene números positivos en cualquier formato razonable, decida si es una matriz de Pascal .

Decidir significa devolver valores verdaderos o falsos dependiendo de si la entrada es una matriz de Pascal , o fijar dos valores constantes y devolver uno para las entradas verdaderas y el otro para las entradas falsas.

Este es el , así que trate de usar la menor cantidad de bytes posible en el idioma que elija. El código más corto en cada idioma gana, por lo tanto no aceptaré una respuesta.

Casos de prueba

Cierto

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

Falso

[[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]]
Laikoni
fuente
Caso de prueba sugerida: [[40, 20, 8, 2], [20, 12, 6, 2], [8, 6, 4, 2], [2, 2, 2, 2]]. Mi respuesta inicial fue incorrectamente veraz para esta, pero correcta para todos los casos de prueba actuales.
Kevin Cruijssen
@KevinCruijssen Gracias, agregó.
Laikoni

Respuestas:

6

Brachylog , 28 24 23 bytes

Esto se siente bastante largo pero aquí está de todos modos

  • -4 bytes gracias a DLosc al comprimir los flips opcionales
  • -1 bytes gracias a DLosc nuevamente haciendo las sumas parciales de una vez

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

Explicación

{|↔}\↰₁{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

Pruébalo en línea!

Kroppeb
fuente
4

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

Pruébalo en línea!

Arnauld
fuente
4

MATL , 17 bytes

4:"Gas2YLG@X!X=va

Pruébalo en línea! O verificar todos los casos de prueba .

Salidas 1para matrices de Pascal, de lo 0contrario.

Explicación

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)
Luis Mendo
fuente
2

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

Pruébalo en línea!

Asqueroso...

Crea matriz de un Pascal canónica Zcon dimensiones iguales a la de m, a continuación, pruebas si la matriz de entrada mes identicala anyde las rotaciones de Z.

Giuseppe
fuente
2

Carbón , 41 bytes

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

Pruébalo en línea! El enlace es a la versión detallada del código. Explicación:

F‹¹⌈§θ⁰

Si el máximo de su primera fila es mayor que 1,

≔⮌θθ

luego voltee la matriz de entrada.

F‹¹⌈Eθ§ι⁰

Si el máximo de su primera columna es mayor que 1,

≦⮌θ

luego refleje la matriz de entrada.

⌊⭆θ⭆ι

Recorra los elementos de la matriz de entrada e imprima el resultado mínimo (es decir, el lógico Y de todos los resultados),

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

comparando cada valor a 1 si está en la primera fila, de lo contrario, la suma de la fila de arriba hasta la celda de arriba incluida.

Neil
fuente
1

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

Pruébalo en línea!

Devuelve Truesi Mes una matriz de Pascal, de lo contrario0 .

Chas Brown
fuente
1

05AB1E , 29 bytes

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

Pruébalo en línea o verifique todos los casos de prueba .

Explicación:

¬Pi }        # 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
 øнPi }      # 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)
Kevin Cruijssen
fuente
1

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}

Pruébalo en línea!

JohnWells
fuente
1

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;}

Pruébalo en línea!

Créditos

Olivier Grégoire
fuente
1
Buena respuesta, pero dang, un montón de variables. ;) Ah, y -1: i==s||j==Sa i==s|j==S.
Kevin Cruijssen
@KevinCruijssen si conoces un algoritmo mejor, ¡lo tomo! Pero la rotación es la causa de todas las variables. Algunos lenguajes pueden manejarlos en 1-2 bytes, en Java, debes pensar en el código que los rodea. El algoritmo central es bastante corto: 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)
Olivier Grégoire
0

Jalea , 22 bytes

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

Pruébalo en línea!

Explicación

Enlace auxiliar, comprueba si esta rotación de matriz es válida

Ż€            | 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

Enlace principal

,Ṛ            | 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
Nick Kennedy
fuente