Você receberá uma matriz bidimensional e um número e será solicitado que descubra se a matriz fornecida é Toeplitz ou não.

Formato de entrada:

Você receberá uma função que terá two-dimensionalmatriz como argumento.

Formato de saída:

Retorne 1da função se a matriz for Toeplitz , caso contrário, retorne -1.

Restrições:

3 < n,m < 10,000,000

onde né o número de linhas enquanto mserá o número de colunas.

Exemplo de caso de teste:

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 

Pontuação

Isso é código-golfe , então a resposta mais curta em bytes vence.

Mathematica, 42 bytes

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

O Mathematica não possui um built-in para verificar se algo é uma matriz de Toeplitz, mas possui um built-in para gerar uma. Então, geramos uma da primeira coluna ( #&@@@#) e da primeira linha ( #&@@#) da entrada e verificamos se é igual à entrada. Para converter o True/ Falseresult em 1/ -1usamos Boole(para dar 1ou 0) e, em seguida, basta transformar o resultado com 2x-1.

Oitava , 30 bytes

Suponho que não precise lidar com 1.000.000 x 1.000.000 de matrizes, como está escrito no desafio. Isso funciona para matrizes que não excedem a memória disponível (menos de 1 TB no meu caso).

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

Experimente online!

Isso leva uma matriz xcomo entrada e cria uma matriz Toeplitz com base nos valores na primeira coluna e na primeira linha. Ele verificará cada elemento das matrizes quanto à igualdade. Se todos os elementos forem iguais, a entrada será uma matriz de Toeplitz.

A saída será uma matriz das mesmas dimensões que a entrada. Se houver zeros na saída, isso será considerado falso como oitava.

Editar:

Só notei o formato de saída estrito:

Isso funciona para 41 bytes. Pode ser possível obter um byte ou dois dessa versão, mas espero que as regras de saída sejam um pouco mais relaxadas.

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

Gelatina , 5 bytes

ŒDE€Ạ

Experimente online!

Seguindo a definição aqui .

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

05AB1E , 11 bytes

Œ2ùvy`¦s¨QP

Experimente online!

Explicação

Π            # 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

Experimente online!

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

outro baseado no 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 após uma dica de uso de um algoritmo mais eficiente, graças ao @Neil .

Explicação:

Experimente aqui.

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 pega uma lista de listas de números inteiros e retorna um número inteiro.

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

Experimente online!

Isso poderia ter sido de 39 ou 38 bytes com saída truthy / falsy.

A idéia de usar initfoi inspirada na resposta 05AB1E de Emigna, que usa um método muito semelhante; antes disso, usei um zip aninhado.

Como funciona

• zipWith((.init).(/=).tail)=<<tailé uma forma sem pontos de \m->zipWith(\x y->tail x/=init y)(tail m)m.
• Isso combina cada par consecutivo de linhas de m, verificando se o primeiro com o primeiro elemento removido é diferente do segundo com o segundo elemento removido.
• O orentão combina as verificações para todos os pares de linhas.
• 1-sum[2|...] converte o formato de saída.

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}

Exatamente como especificado, pode ser jogado mais se a entrada / saída flexível for aceita.

Explicação:

Itere na matriz e compare cada linha com a linha acima, deslocada uma para a direita. Se forem diferentes, use uma matriz vazia para a próxima iteração. No final, retorne -1 se a matriz final estiver vazia ou 1 se tiver pelo menos 2 elementos (como a menor matriz possível é 3x3, isso é verdade se todas as comparações retornarem verdadeiras)

Experimente online!

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

Não é eficiente, pois toca todos os elementos n+mdurante a filtragem de diagonais. Em seguida, verifica se há mais de um elemento exclusivo 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 tem que ser uma matriz de algum elemento que permita ~ =; ungolf it

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

Experimente online!

Uma 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

é primeiro convertido em uma matriz N × (N + M-1) alinhando as diagonais da seguinte maneira:

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

e a primeira coluna é repetidamente verificada para conter um único número único e removida, se for o caso. A matriz é Toeplitz se a saída estiver em branco.

MATL , 11 bytes

T&Xd"@Xz&=v

Experimente online!

O método simples "construa uma matriz de Toeplitz e verifique com ela", que as poucas respostas mais usadas, de alguma forma me pareceu chato (e parece que isso seria 1 byte mais longo de qualquer maneira). Então, eu fui para o método "verificar cada diagonal contém apenas um valor único".

T&Xd - Extraia as diagonais da entrada e crie uma nova matriz com elas como colunas (preenchendo com zeros, conforme necessário)

" - percorra as colunas desse

@Xz - empurre a variável de iteração (a coluna atual) e remova (preenchimento) zeros dela

&=- verificação de igualdade de transmissão - isso cria uma matriz com todos os 1s (verdade) se todos os valores restantes forem iguais um ao outro, caso contrário, a matriz contém alguns 0s que são falsos

v - concatenar valores de resultados juntos, para criar um vetor de resultado final que seja verdadeiro (todos os 1s) ou falsey (alguns 0s)

R , 48 bytes

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

Experimente online!

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)