Se le dará una matriz bidimensional y un número y se le pedirá que encuentre si la matriz dada es Toeplitz o no.

Formato de entrada

Se le dará una función que tomará la two-dimensionalmatriz como argumento.

Formato de salida:

Regrese 1de la función si la matriz es Toeplitz , de lo contrario regrese -1.

Restricciones:

3 < n,m < 10,000,000

donde nes el número de filas, mientras mque será el número de columnas.

Caso de prueba de muestra:

Sample Input :
4 
5
6 7 8 9 2
4 6 7 8 9
1 4 6 7 8
0 1 4 6 7 

Sample Output : 
1 

Puntuación

Este es el código de golf , por lo que gana la respuesta más corta en bytes.

Mathematica, 42 bytes

2Boole[#==ToeplitzMatrix[#&@@@#,#&@@#]]-1&

Mathematica no tiene una función integrada para verificar si algo es una matriz de Toeplitz, pero sí tiene una función integrada para generar una. Entonces generamos uno desde la primera columna ( #&@@@#) y la primera fila ( #&@@#) de la entrada y verificamos si es igual a la entrada. Para convertir el True/ Falseresultado a 1/ -1usamos Boole(para dar 1o 0) y luego simplemente transformamos el resultado con 2x-1.

Octava , 30 bytes

Supongo que no tengo que manejar 1,000,000x1,000,000 matrices como se dice en el desafío. Esto funciona para matrices que no exceden la memoria disponible (menos de 1 TB en mi caso).

@(x)x==toeplitz(x(:,1),x(1,:))

Pruébalo en línea!

Esto toma una matriz xcomo entrada y crea una matriz Toeplitz basada en los valores de la primera columna y la primera fila. Luego verificará la igualdad de cada elemento de las matrices. SI todos los elementos son iguales, entonces la entrada es una matriz de Toeplitz.

La salida será una matriz de las mismas dimensiones que la entrada. Si hay ceros en la salida, entonces eso se considera falso como octava.

Editar:

Acabo de notar el formato de salida estricto:

Esto funciona para 41 bytes. Puede ser posible jugar golf un byte o dos desde esta versión, pero espero que las reglas de salida se relajen un poco.

@(x)2*(0||(x==toeplitz(x(:,1),x(1,:))))-1

Jalea , 5 bytes

ŒDE€Ạ

Pruébalo en línea!

Siguiendo la definición aquí .

ŒDE€Ạ
ŒD     all diagonals
   €   for each diagonal ...
  E       all elements are equal
    Ạ  all diagonal return true

05AB1E , 11 bytes

Œ2ùvy`¦s¨QP

Pruébalo en línea!

Explicación

Π            # get all sublists of input
 2ù           # keep only those of length 2
   v          # for each such pair
    y`        # split to separate lists
      ¦       # remove the first element of the second list
       s¨     # remove the last element of the first list
         Q    # compare for equality
          P   # product of stack

Haskell , 43 bytes

f(a:b:t)|init a==tail b=f$b:t|1>0= -1
f _=1

Pruébalo en línea!

Mathematica, 94 bytes

l=Length;If[l@Flatten[Union/@Table[#~Diagonal~k,{k,-l@#+1,l@#[[1]]-1}]]==l@#+l@#[[1]]-1,1,-1]&

entrada

{{6, 7, 8, 9, 2}, {4, 6, 7, 8, 9}, {1, 4, 6, 7, 8}, {0, 1, 4, 6, 7}}

otro basado en el algoritmo de Stewie Griffin

Mathematica, 44 bytes

If[#==#[[;;,1]]~ToeplitzMatrix~#[[1]],1,-1]&

Java 7, 239 233 220 113 bytes

int c(int[][]a){for(int i=a.length,j;i-->1;)for(j=a[0].length;j-->1;)if(a[i][j]!=a[i-1][j-1])return -1;return 1;}

-107 bytes después de usar un algoritmo más eficiente gracias a @Neil .

Explicación:

Pruébalo aquí.

int c(int[][]a){                // Method with integer-matrix parameter and integer return-type
  for(int i=a.length,j;i-->1;)  //  Loop over the rows (excluding the first)
    for(j=a[0].length;j-->1;)   //   Loop over the columns (excluding the first)
      if(a[i][j]!=a[i-1][j-1])  //    If the current cell doesn't equal the one top-left of it:
        return -1;              //     Return -1
                                //   End of columns loop (implicit / single-line body)
                                //  End of rows loop (implicit / single-line body)
  return 1;                     //  Return 1
}                               // End of method

Haskell , 51 bytes

t toma una lista de listas de enteros y devuelve un entero.

t m=1-sum[2|or$zipWith((.init).(/=).tail)=<<tail$m]

Pruébalo en línea!

Esto podría haber sido 39 o 38 bytes con salida verdadero / falso.

La idea de usar initse inspiró en la respuesta 05AB1E de Emigna, que usa un método muy similar; antes de eso usé una compresión anidada.

Cómo funciona

• zipWith((.init).(/=).tail)=<<tailes una forma libre de puntos \m->zipWith(\x y->tail x/=init y)(tail m)m.
• Esto combina cada par de filas consecutivas de m, comprobando si el primero con el primer elemento eliminado es diferente del segundo con el segundo elemento eliminado.
• El orcombina entonces los controles para todos los pares de filas.
• 1-sum[2|...] Convierte el formato de salida.

JavaScript (ES6), 65 54 bytes

a=>a.some((b,i)=>i--&&b.some((c,j)=>c-a[i][j-1]))?-1:1

Ruby , 54 bytes

->a,b,m{m.reduce{|x,y|x[0..-2]==y[1,b]?y:[]}.size<=>1}

Exactamente como se especifica, se puede jugar más si se acepta entrada / salida flexible.

Explicación:

Itere en la matriz y compare cada línea con la línea de arriba, desplazada una a la derecha. Si son diferentes, use una matriz vacía para la próxima iteración. Al final, devuelve -1 si la matriz final está vacía, o 1 si tiene al menos 2 elementos (dado que la matriz más pequeña posible es 3x3, esto es cierto si todas las comparaciones devuelven verdadero)

Pruébalo en línea!

PHP, 70 bytes

<?=!preg_match('/\[([\d,]+?),\d+\],\[\d+,(?!\1)/',json_encode($_GET));

Python, 108

r=range
f=lambda x,n,m:all([len(set([x[i][j] for i in r(n) for j in r(m) if j-i==k]))==1 for k in r(1-n,m)])

No es eficiente en absoluto, ya que toca cada elemento cada n+mvez que filtra las diagonales. Luego verifica si hay más de un elemento único por diagonal.

Axioma, 121 bytes

f(m)==(r:=nrows(m);c:=ncols(m);for i in 1..r-1 repeat for j in 1..c-1 repeat if m(i,j)~=m(i+1,j+1)then return false;true)

m tiene que ser una matriz de algún elemento que permita ~ =; deshacerse de él

f m ==
  r := nrows(m)
  c := ncols(m)
  for i in 1..(r - 1) repeat
    for j in 1..(c - 1) repeat
      if m(i,j)~=m(i + 1,j + 1)     then return(false)
  true

Retina , 148 bytes

m(1`\d+
$*#
1`#\n\d+\n
@
+`(#*)#@([^#\n]*(#*)\n)(.*)$
$1# $2$1@$4 #$3
@

+`##
# #
+(+s`^(\d+)\b(.*)^\1\b
$1$2#
s`.*^\d.*^\d.*
-1
)%`^[^- ]+ ?

\s+
1

Pruébalo en línea!

Una matriz de entrada N × M

6 7 8 9 2 0
4 6 7 8 9 2
1 4 6 7 8 9
0 1 4 6 7 8

se convierte primero en una matriz N × (N + M-1) alineando las diagonales de esta manera:

# # # 6 7 8 9 2 0
# # 4 6 7 8 9 2 #
# 1 4 6 7 8 9 # #
0 1 4 6 7 8 # # #

y luego la primera columna se verifica repetidamente para que contenga un único número único, y se elimina si es así. La matriz es Toeplitz si la salida está en blanco.

MATL , 11 bytes

T&Xd"@Xz&=v

Pruébalo en línea!

El sencillo método de "construir una matriz de Toeplitz y verificarlo", que utilizan las pocas respuestas principales, de alguna manera me pareció aburrido (y de todos modos parece que sería 1 byte más largo). Así que elegí el método "comprobar que cada diagonal solo contiene un valor único".

T&Xd - Extraiga las diagonales de la entrada y cree una nueva matriz con ellas como columnas (relleno con ceros según sea necesario)

" - iterar a través de las columnas de ese

@Xz - empuje la variable de iteración (la columna actual) y elimine (rellenando) ceros de ella

&=- comprobación de igualdad de difusión : esto crea una matriz con todos los 1 (verdad) si todos los valores restantes son iguales entre sí; de lo contrario, la matriz contiene algunos 0, lo cual es falso

v - concatenar valores de resultados juntos, para crear un vector de resultado final que sea verdadero (todos 1s) o falsey (algunos 0s)

R , 48 bytes

pryr::f(all(x[-1,-1]==x[-nrow(x),-ncol(x)])*2-1)

Pruébalo en línea!

Clojure, 94 bytes

#(if(=(+ %2 %3 -1)(count(set(for[Z[zipmap][i r](Z(range)%)[j v](Z(range)r)][(- i j)v]))))1 -1)