Otrzymasz dwuwymiarową tablicę i liczbę i zostaniesz poproszony o sprawdzenie, czy dana macierz to Toeplitz, czy nie.

Format wejściowy:

Otrzymasz funkcję, która przyjmie two-dimensionalmacierz jako argument.

Format wyjściowy:

Wróć 1z funkcji, jeśli macierzą jest Toeplitz , w przeciwnym razie powróć -1.

Ograniczenia:

3 < n,m < 10,000,000

gdzie njest liczba wierszy, a mbędzie liczba kolumn.

Przykładowy przypadek testowy:

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 

Punktacja

To jest golf golfowy , więc wygrywa najkrótsza odpowiedź w bajtach.

Mathematica, 42 bajty

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

Mathematica nie ma wbudowanej funkcji sprawdzania, czy coś jest macierzą Toeplitz, ale ma wbudowaną funkcję generowania. Tak więc generujemy jeden z pierwszej kolumny ( #&@@@#) i pierwszego wiersza ( #&@@#) wejścia i sprawdzamy, czy jest on równy wejściowi. Aby przekonwertować True/ Falsewynik na 1/ -1używamy Boole(do podania 1lub 0), a następnie po prostu przekształcamy wynik za pomocą 2x-1.

Oktawa , 30 bajtów

Zakładam, że nie muszę obsługiwać 1 000 000 x 1 000 000 matryc, jak mówi wyzwanie. Działa to dla matryc, które nie przekraczają dostępnej pamięci (w moim przypadku mniej niż 1 TB).

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

Wypróbuj online!

Pobiera to macierz xjako dane wejściowe i tworzy macierz Toeplitz na podstawie wartości z pierwszej kolumny i pierwszego wiersza. Następnie sprawdzi każdy element macierzy pod kątem równości. JEŻELI wszystkie elementy są równe, wówczas wejściem jest macierz Toeplitza.

Wyjście będzie macierzą o takich samych wymiarach jak dane wejściowe. Jeśli na wyjściu są jakieś zera, to falsy to oktawa.

Edytować:

Właśnie zauważyłem ścisły format wyjściowy:

Działa to dla 41 bajtów. Może być możliwe zagranie w golfa z bajtu lub dwóch z tej wersji, ale mam nadzieję, że reguły wyjściowe zostaną nieco złagodzone.

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

Galaretka , 5 bajtów

ŒDE€Ạ

Wypróbuj online!

Zgodnie z definicją tutaj .

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

05AB1E , 11 bajtów

Œ2ùvy`¦s¨QP

Wypróbuj online!

Wyjaśnienie

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

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

Wypróbuj online!

Mathematica, 94 bajty

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

Wejście

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

inny oparty na algorytmie Stewie Griffin

Mathematica, 44 bajty

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

Java 7, 239 233 220 113 bajtów

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 bajtów po użyciu bardziej wydajnego algorytmu dzięki @Neil .

Wyjaśnienie:

Wypróbuj tutaj.

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 bajtów

t pobiera listę liczb całkowitych i zwraca liczbę całkowitą.

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

Wypróbuj online!

Może to być 39 lub 38 bajtów z wynikiem prawda / fałsz.

Pomysł do wykorzystania init został zainspirowany odpowiedzią Emigny 05AB1E, która wykorzystuje bardzo podobną metodę; wcześniej użyłem zagnieżdżonego zipowania.

Jak to działa

• zipWith((.init).(/=).tail)=<<tail jest bez punktową formą \m->zipWith(\x y->tail x/=init y)(tail m)m .
• Łączy to każdą kolejną parę rzędów m , sprawdzając, czy pierwszy z usuniętym pierwszym elementem różni się od drugiego z usuniętym drugim elementem.
• orNastępnie łączy kontrole dla wszystkich par wierszy.
• 1-sum[2|...] konwertuje format wyjściowy.

JavaScript (ES6), 65 54 bajtów

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

Rubinowy , 54 bajty

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

Dokładnie tak, jak określono, można grać w golfa bardziej, jeśli akceptowane są elastyczne wejścia / wyjścia.

Wyjaśnienie:

Iteruj po macierzy i porównaj każdą linię z linią powyżej, przesuniętą o jedną w prawo. Jeśli są różne, użyj pustej tablicy do następnej iteracji. Na koniec zwróć -1, jeśli ostatnia tablica jest pusta, lub 1, jeśli są to co najmniej 2 elementy (ponieważ najmniejszą możliwą macierzą jest 3x3, jest to prawdą, jeśli wszystkie porównania zwracają prawdę)

Wypróbuj online!

PHP, 70 bajtów

<?=!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)])

W ogóle nie jest wydajny, ponieważ dotyka każdego elementu n+mpodczas filtrowania pod kątem przekątnych. Następnie sprawdza, czy na przekątnej jest więcej niż jeden unikalny element.

Aksjomat, 121 bajtów

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 musi być macierzą jakiegoś elementu, który pozwala ~ =; zagrać w golfa

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

Siatkówka , 148 bajtów

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

Wypróbuj online!

Matryca wejściowa 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

jest najpierw konwertowany na macierz N × (N + M-1) przez wyrównanie przekątnych w ten sposób:

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

a następnie pierwsza kolumna jest wielokrotnie sprawdzana pod kątem pojedynczego unikalnego numeru i usuwana, jeśli tak jest. Matryca to Toeplitz, jeśli dane wyjściowe są puste.

MATL , 11 bajtów

T&Xd"@Xz&=v

Wypróbuj online!

Prosta metoda „konstruowania macierzy Toeplitza i porównania z nią”, której używa kilka pierwszych odpowiedzi, wydawała mi się nudna (i wygląda na to, że i tak byłby o 1 bajt dłużej). Wybrałem więc metodę „sprawdź, czy każda przekątna zawiera tylko jedną unikalną wartość”.

T&Xd - Wyodrębnij przekątne wejścia i utwórz nową macierz z nimi jako kolumnami (wypełnienie zerami w razie potrzeby)

" - iteruj przez kolumny tego

@Xz - wciśnij zmienną iteracyjną (bieżącą kolumnę) i usuń z niej (wypełniające) zera

&=- kontrola równości transmisji - tworzy macierz ze wszystkimi 1 (prawda), jeśli wszystkie pozostałe wartości są sobie równe, w przeciwnym razie macierz zawiera kilka zer, co jest fałszem

v - połącz wartości wyników razem, aby utworzyć jeden końcowy wektor wyników, który jest albo prawdziwy (wszystkie 1), albo falsey (niektóre 0)

R , 48 bajtów

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

Wypróbuj online!

Clojure, 94 bajty

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