Sie erhalten ein zweidimensionales Array und eine Zahl und werden gefragt, ob die angegebene Matrix Toeplitz ist oder nicht.

Eingabeformat:

Sie erhalten eine Funktion, die die two-dimensionalMatrix als Argument verwendet.

Ausgabeformat:

Rückkehr 1von der Funktion, wenn die Matrix Toeplitz ist , andernfalls Rückkehr -1.

Einschränkungen:

3 < n,m < 10,000,000

Wo nist die Anzahl der Zeilen, während mdie Anzahl der Spalten ist.

Beispieltestfall:

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 

Wertung

Dies ist Code-Golf , daher gewinnt die kürzeste Antwort in Bytes.

Mathematica, 42 Bytes

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

Mathematica verfügt nicht über eine integrierte Funktion, um zu überprüfen, ob es sich bei einer Toeplitz-Matrix um eine integrierte Toeplitz-Matrix handelt. Wir generieren also eine aus der ersten Spalte ( #&@@@#) und der ersten Zeile ( #&@@#) der Eingabe und prüfen, ob sie der Eingabe entspricht. Um das True/ FalseErgebnis in 1/ umzuwandeln , verwenden -1wir Boole(um 1oder zu geben 0) und transformieren dann einfach das Ergebnis mit 2x-1.

Oktave , 30 Bytes

Ich gehe davon aus, dass ich nicht mit 1.000.000 x 1.000.000 Matrizen umgehen muss, wie es in der Herausforderung heißt. Dies funktioniert für Matrizen, die den verfügbaren Speicher nicht überschreiten (in meinem Fall weniger als 1 TB).

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

Probieren Sie es online aus!

Dies nimmt eine Matrix xals Eingabe und erstellt eine Toeplitz-Matrix basierend auf den Werten in der ersten Spalte und der ersten Zeile. Anschließend wird jedes Element der Matrizen auf Gleichheit überprüft. Wenn alle Elemente gleich sind, ist die Eingabe eine Toeplitz-Matrix.

Die Ausgabe ist eine Matrix mit den gleichen Abmessungen wie die Eingabe. Wenn die Ausgabe Nullen enthält, wird dies als Oktave angesehen.

Bearbeiten:

Habe gerade das strenge Ausgabeformat bemerkt:

Dies funktioniert für 41 Bytes. Es könnte möglich sein, ein oder zwei Bytes aus dieser Version zu spielen, aber ich hoffe, dass die Ausgaberegeln etwas gelockert werden.

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

Gelee , 5 Bytes

ŒDE€Ạ

Probieren Sie es online aus!

Folgen Sie der Definition hier .

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

05AB1E , 11 Bytes

Œ2ùvy`¦s¨QP

Probieren Sie es online aus!

Erläuterung

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

Probieren Sie es online aus!

Mathematica, 94 Bytes

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

Eingang

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

eine andere basiert auf dem Algorithmus von 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 nach einem Tipp zur Verwendung eines effizienteren Algorithmus dank @Neil .

Erläuterung:

Probieren Sie es hier aus.

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 Nimmt eine Liste von Ganzzahllisten und gibt eine Ganzzahl zurück.

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

Probieren Sie es online aus!

Dies könnten 39 oder 38 Bytes mit wahrheitsgemäßer / falscher Ausgabe gewesen sein.

Die Idee initwurde von Emignas 05AB1E-Antwort inspiriert, die eine sehr ähnliche Methode verwendet. davor habe ich einen verschachtelten Reißverschluss verwendet.

Wie es funktioniert

• zipWith((.init).(/=).tail)=<<tailist eine punktfreie Form von \m->zipWith(\x y->tail x/=init y)(tail m)m.
• Dies kombiniert jedes aufeinanderfolgende Reihenpaar von mund prüft, ob sich das erste mit entferntem ersten Element von dem zweiten mit entferntem zweiten Element unterscheidet.
• Das orkombiniert dann die Prüfungen für alle Zeilenpaare.
• 1-sum[2|...] konvertiert das Ausgabeformat.

JavaScript (ES6), 65 54 Byte

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}

Genau wie angegeben, kann mehr Golf gespielt werden, wenn eine flexible Eingabe / Ausgabe akzeptiert wird.

Erläuterung:

Iterieren Sie in der Matrix und vergleichen Sie jede Zeile mit der obigen Zeile, die um eins nach rechts verschoben ist. Wenn sie unterschiedlich sind, verwenden Sie ein leeres Array für die nächste Iteration. Geben Sie am Ende -1 zurück, wenn das endgültige Array leer ist, oder 1, wenn es mindestens 2 Elemente enthält (da die kleinstmögliche Matrix 3x3 ist, gilt dies, wenn alle Vergleiche true zurückgeben).

Probieren Sie es online aus!

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

Überhaupt nicht effizient, da es n+mbeim Filtern nach Diagonalen jedes Element mal berührt . Überprüft dann, ob es mehr als ein eindeutiges Element pro Diagonale gibt.

Axiom, 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 muss eine Matrix eines Elements sein, das ~ = erlaubt; ungolf es

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

Netzhaut , 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

Probieren Sie es online aus!

Eine N × M-Eingabematrix

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

wird zuerst in eine N × (N + M-1) -Matrix umgewandelt, indem die Diagonalen folgendermaßen ausgerichtet werden:

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

und dann wird die erste Spalte wiederholt überprüft, um eine einzelne eindeutige Nummer zu enthalten, und entfernt, wenn dies der Fall ist. Die Matrix ist Toeplitz, wenn die Ausgabe leer ist.

MATL , 11 Bytes

T&Xd"@Xz&=v

Probieren Sie es online aus!

Die unkomplizierte Methode "Konstruiere eine Toeplitz-Matrix und überprüfe sie", die die wenigen Antworten verwenden, fühlte sich für mich irgendwie langweilig an (und es sieht so aus , als wäre das sowieso 1 Byte länger). Also habe ich mich für die Methode "Überprüfen, ob jede Diagonale nur einen eindeutigen Wert enthält" entschieden.

T&Xd - Extrahieren Sie die Diagonalen der Eingabe und erstellen Sie eine neue Matrix mit ihnen als Spalten (Auffüllen mit Nullen nach Bedarf)

" - durch die Spalten davon iterieren

@Xz - Drücken Sie die Iterationsvariable (die aktuelle Spalte) und entfernen Sie (Auffüllen) Nullen daraus

&=- Broadcast Equality Check - Hiermit wird eine Matrix mit allen Einsen (wahr) erstellt, wenn alle verbleibenden Werte gleich sind. Andernfalls enthält die Matrix einige Nullen, was falsch ist

v - Verketten Sie die Ergebniswerte miteinander, um einen Endergebnisvektor zu erstellen, der entweder wahr (alle Einsen) oder falsch (einige Nullen) ist.

R , 48 Bytes

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

Probieren Sie es online aus!

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)