Check if a matrix is a Toeplitz matrix

Question

You will be given a two-dimensional array and a number and you are asked to find whether the given matrix is Toeplitz or not. A matrix is a Toeplitz matrix if every descending diagonal, going from left to right, has only one distinct element. That is, it should be in the form:

Form

Input Format:

You will be given a function which will take two-dimensional matrix as argument.

Output Format:

Return 1 from the function if the matrix is Toeplitz, else return -1.

Constraints:

3 < n,m < 10,000,000

where n is the number of rows while m will be the number of columns.

Sample Test Case:

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 

Scoring

This is code-golf, so the shortest answer in bytes wins.

• xnor: This is a good challenge, but we prefer laxer I/O requirements here. I'd suggest allowing both programs and functions as is the default. And to allow True/False or 1/0 as outputs, or perhaps just any two consistent distinct outputs as seems to be preferred for decision problems.
• xnor: Also, a definition of Toeplitz would be good, as would be more test cases including non-Toeplitz ones. Not sure what you mean about adding code.
• Stewie Griffin: I think you must reduce the maximum value of n,m. Otherwise the main part of this challenge is to find a way to process a 1 terabyte matrix.
• Martin Ender: Will the matrix elements always be non-negative integers?

Answer 1

Mathematica, 42 bytes

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

Mathematica doesn't have a built-in to check whether something is a Toeplitz matrix, but it does have a built-in to generate one. So we generate one from the first column (#&@@@#) and the first row (#&@@#) of the input and check whether it's equal to the input. To convert the True/False result to 1/-1 we use Boole (to give 1 or 0) and then simply transform the result with 2x-1.

Answer 2

Octave, 30 bytes

I'm assuming I don't have to handle 1,000,000x1,000,000 matrices as it says in the challenge. This works for matrices that don't exceed the available memory (less than 1 TB in my case).

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

Try it online!

This takes a matrix x as input and creates a Toeplitz matrix based on the values on the first column, and the first row. It will then check each element of the matrices for equality. IF all elements are equal then the input is a Toeplitz matrix.

The output will be a matrix of the same dimensions as the input. If there are any zeros in the output then that's considered falsy be Octave.

Edit:

Just noticed the strict output format:

This works for 41 bytes. It might be possible to golf off a byte or two from this version, but I hope the output rules will be relaxed a bit.

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

Answer 3

Jelly, 5 bytes

ŒDE€Ạ

Try it online!

Following the definition here.

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

Answer 4

05AB1E, 11 bytes

Œ2ùvy`¦s ̈QP

Try it online!

Explanation

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

Answer 5

Haskell, 43 bytes

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

Try it online!

• Ørjan Johansen: Dang, overcomplicating it again. Curiously, I get that down to 39 bytes with truthy/falsy output, so if Toeplitz = False were allowed I might have beaten it by one byte.

Answer 6

Mathematica, 94 bytes

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

input

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

another one based on Stewie Griffin's algorithm

Mathematica, 44 bytes

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

• Not a tree: Do you need to define s? Can't you just use # instead?
• ZaMoC: yes! you are right!

Answer 7

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 after a tip of using a more efficient algorithm thanks to @Neil.

Explanation:

Try it here.

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

• Mickey Jack: what is r & c in first function?
• Kevin Cruijssen: @MickeyJack Rows and columns (r = n and c = m if you compare it to the challenge).
• Neil: Shouldn't you pass the array as a parameter to the function? Also, there is a much more efficient algorithm for this, which would cut your byte count by about 50%.
• Neil: @KevinCruijssen Simply check that all elements not in the first row or column equal the element diagonally up and left from it.
• Neil: Ah, you even got to use the --> operator!

Answer 8

Haskell, 51 bytes

t takes a list of lists of integers and returns an integer.

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

Try it online!

This could have been 39 or 38 bytes with truthy/falsy output.

The idea to use init was inspired by Emigna's 05AB1E answer, which uses a very similar method; before that I used a nested zipping.

How it works

• zipWith((.init).(/=).tail)=<<tail is a point-free form of \m->zipWith(\x y->tail x/=init y)(tail m)m.
• This combines each consecutive pair of rows of m, checking if the first with first element removed is different from the second with second element removed.
• The or then combines the checks for all pairs of rows.
• 1-sum[2|...] converts the output format.

Answer 9

Husk, (削除) 6 (削除ここまで) 4 bytes

ΛE∂↔

Try it online!

-2 bytes from Zgarb.

My first Husk answer! (Language Of The Month)

Takes matrix as command line argument.

Returns length of longest diagonal for true, and 0 otherwise.

Explanation

ΛE∂↔
 ↔ reverse the rows
 ∂ get antidiagonals
Λ Check if all elements satisfy condition:
 E Are all the elements equal?

• Dominic van Essen: 3 days to learn a completely new golfing language? Pretty darn good!
• Razetime: Nothing is impossible with the power of well written tutorials and surprisingly convenient builtins @DominicvanEssen

Answer 10

JavaScript (ES6), (削除) 65 (削除ここまで) 54 bytes

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

• Arnauld: Or using your own trick: a=>a.some(b=>b.some((v,i)=>d[i]-(d[i]=v),d=[,...d]),d=[])?-1:1 (62 bytes)
• Neil: @Arnauld Thanks, but it turns out I was over-thinking the problem again...

Answer 11

Ruby, 54 bytes

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

Exactly as specified, can be golfed more if flexible input/output is accepted.

Explanation:

Iterate on the matrix, and compare each line with the line above, shifted by one to the right. If they are different, use an empty array for the next iteration. At the end, return -1 if the final array is empty, or 1 if it's at least 2 elements (since the smallest possible matrix is 3x3, this is true if all comparisons return true)

Try it online!

• Neil: Nice use of <=> to compute the result!
• Stefan Pochmann: How about |(*x,_),y| so you don't need to slice x?

Answer 12

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 has to be a Matrix of some element that allow ~=; 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

Answer 13

PHP, 70 bytes

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

Answer 14

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

Not efficient at all since it touches every element n+m times while filtering for diagonals. Then checks if there are more than one unique element per diagonal.

Answer 15

R, 48 bytes

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

Try it online!

Answer 16

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

Try it online!

An ×ばつM input matrix

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

is first converted to an ×ばつ(N+M-1) matrix by aligning the diagonals this way:

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

and then the first column is repeatedly checked to contain a single unique number, and removed if this is so. The matrix is Toeplitz iff the output is blank.

• eush77: Oh, it doesn't work with negative numbers, gotta fix this :)

Answer 17

MATL, 11 bytes

T&Xd"@Xz&=v

Try it online!

The straightforward "construct a Toeplitz matrix and check against it" method, that the top few answers use, somehow felt boring to me (and it looks like that would be 1 byte longer anyway). So I went for the "check each diagonal only contains one unique value" method.

T&Xd - Extract the diagonals of the input and create a new matrix with them as columns (padding with zeros as needed)

" - iterate through the columns of that

@Xz - push the iteration variable (the current column), and remove (padding) zeros from it

&= - broadcast equality check - this creates a matrix with all 1s (truthy) if all the remaining values are equal to one another, otherwise the matrix contains some 0s which is falsy

v - concatenate result values together, to create one final result vector which is either truthy (all 1s) or falsey (some 0s)

Answer 18

Japt, 9 bytes

I think this is right.

äÏÅeX ×ばつ

Try it

äÏÅeX ×ばつ :Implicit input of 2D-array
ä :Consecutive pairs
 Ï :Reduced by
 Å : Slice the first element off the second array
 e : Check for equality with
 X : First array
 ̄J : Slice off the last element
 Ã :End reduce
 ×ばつ :Reduce by multiplication

Answer 19

Vyxal g, 23 bits^v2 , 2.875 bytes

ÞDv≈

Try it Online!

Bitstring:

00101000011111111111011

checks if diagonals have the same value, the g flag will output the minimum which is 0 if any false and 1 if all truthy

Answer 20

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)