11
\$\begingroup\$

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.

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 , so the shortest answer in bytes wins.

\$\endgroup\$
  • 8
    \$\begingroup\$ 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. \$\endgroup\$ – xnor May 18 '17 at 5:59
  • 15
    \$\begingroup\$ 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. \$\endgroup\$ – xnor May 18 '17 at 6:00
  • 5
    \$\begingroup\$ 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. \$\endgroup\$ – Stewie Griffin May 18 '17 at 7:25
  • 1
    \$\begingroup\$ Will the matrix elements always be non-negative integers? \$\endgroup\$ – Martin Ender May 18 '17 at 13:52

17 Answers 17

7
\$\begingroup\$

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.

\$\endgroup\$
6
\$\begingroup\$

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
\$\endgroup\$
5
\$\begingroup\$

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
\$\endgroup\$
5
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

Haskell, 43 bytes

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

Try it online!

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Ørjan Johansen May 19 '17 at 2:04
3
\$\begingroup\$

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]&
\$\endgroup\$
  • 2
    \$\begingroup\$ Do you need to define s? Can't you just use # instead? \$\endgroup\$ – Not a tree May 18 '17 at 7:51
  • \$\begingroup\$ yes! you are right! \$\endgroup\$ – J42161217 May 18 '17 at 8:04
3
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ what is r & c in first function? \$\endgroup\$ – Mickey Jack May 18 '17 at 7:43
  • \$\begingroup\$ @MickeyJack Rows and columns (r = n and c = m if you compare it to the challenge). \$\endgroup\$ – Kevin Cruijssen May 18 '17 at 7:45
  • \$\begingroup\$ 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%. \$\endgroup\$ – Neil May 18 '17 at 9:14
  • 1
    \$\begingroup\$ @KevinCruijssen Simply check that all elements not in the first row or column equal the element diagonally up and left from it. \$\endgroup\$ – Neil May 18 '17 at 9:57
  • 1
    \$\begingroup\$ Ah, you even got to use the --> operator! \$\endgroup\$ – Neil May 18 '17 at 12:44
3
\$\begingroup\$

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.
\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES6), 65 54 bytes

a=>a.some((b,i)=>i--&&b.some((c,j)=>c-a[i][j-1]))?-1:1
\$\endgroup\$
  • \$\begingroup\$ 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) \$\endgroup\$ – Arnauld May 18 '17 at 8:45
  • 1
    \$\begingroup\$ @Arnauld Thanks, but it turns out I was over-thinking the problem again... \$\endgroup\$ – Neil May 18 '17 at 9:02
2
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ Nice use of <=> to compute the result! \$\endgroup\$ – Neil May 18 '17 at 9:09
  • \$\begingroup\$ How about |(*x,_),y| so you don't need to slice x? \$\endgroup\$ – Stefan Pochmann Jan 22 '18 at 12:09
1
\$\begingroup\$

PHP, 70 bytes

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

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.

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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 N×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×(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.

\$\endgroup\$
  • \$\begingroup\$ Oh, it doesn't work with negative numbers, gotta fix this :) \$\endgroup\$ – eush77 May 19 '17 at 1:29
1
\$\begingroup\$

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)

\$\endgroup\$
0
\$\begingroup\$

R, 48 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

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)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy