Periksa apakah sebuah matriks adalah matriks Toeplitz

11

Anda akan diberikan array dua dimensi dan angka dan Anda diminta untuk menemukan apakah matriks yang diberikan adalah Toeplitz atau tidak.

Masukkan format:

Anda akan diberi fungsi yang akan menggunakan two-dimensionalmatriks sebagai argumen.

Format output:

Kembali 1dari fungsi jika matriksnya adalah Toeplitz , kembalilah lagi -1.

Kendala:

3 < n,m < 10,000,000

di mana njumlah baris sementara makan menjadi jumlah kolom.

Contoh Uji Kasus:

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 

Mencetak gol

Ini adalah , jadi jawaban tersingkat dalam byte menang.

Martin Ender
sumber
8
Ini adalah tantangan yang bagus, tapi kami lebih suka persyaratan I / O yang lebih longgar di sini. Saya sarankan membiarkan kedua program dan fungsi seperti default . Dan untuk memungkinkan Benar / Salah atau 1/0 sebagai output, atau mungkin hanya dua output berbeda yang konsisten yang tampaknya lebih disukai untuk masalah keputusan.
xnor
15
Juga, definisi Toeplitz akan baik, karena akan lebih banyak kasus uji termasuk yang non-Toeplitz. Tidak yakin apa yang Anda maksud tentang menambahkan kode.
xnor
5
Saya pikir Anda harus mengurangi nilai maksimum n, m . Kalau tidak, bagian utama dari tantangan ini adalah menemukan cara untuk memproses matriks 1 terabyte.
Stewie Griffin
1
Apakah elemen matriks selalu bilangan bulat non-negatif?
Martin Ender

Jawaban:

7

Mathematica, 42 byte

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

Mathematica tidak memiliki built-in untuk memeriksa apakah sesuatu adalah matriks Toeplitz, tetapi ia memiliki built-in untuk menghasilkannya. Jadi kami menghasilkan satu dari kolom pertama ( #&@@@#) dan baris pertama ( #&@@#) dari input dan memeriksa apakah itu sama dengan input. Untuk mengonversi True/ Falsehasil ke 1/ -1kami menggunakan Boole(untuk memberi 1atau 0) dan kemudian cukup mengubah hasil dengan 2x-1.

Martin Ender
sumber
6

Oktaf , 30 byte

Saya berasumsi saya tidak harus menangani 1.000.000 x 1.000.000 matriks seperti yang tertulis dalam tantangan. Ini berfungsi untuk matriks yang tidak melebihi memori yang tersedia (kurang dari 1 TB dalam kasus saya).

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

Cobalah online!

Ini mengambil matriks xsebagai input dan membuat matriks Toeplitz berdasarkan nilai pada kolom pertama, dan baris pertama. Kemudian akan memeriksa setiap elemen dari matriks untuk kesetaraan. JIKA semua elemen sama maka inputnya adalah matriks Toeplitz.

Output akan berupa matriks dengan dimensi yang sama dengan input. Jika ada nol dalam output maka itu dianggap falsy menjadi Oktaf.

Edit:

Hanya perhatikan format output yang ketat:

Ini bekerja selama 41 byte. Dimungkinkan untuk bermain golf satu atau dua byte dari versi ini, tapi saya harap aturan output akan sedikit lebih santai.

@(x)2*(0||(x==toeplitz(x(:,1),x(1,:))))-1
Stewie Griffin
sumber
5

Jelly , 5 byte

ŒDE€Ạ

Cobalah online!

Mengikuti definisi di sini .

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

05AB1E , 11 byte

Œ2ùvy`¦s¨QP

Cobalah online!

Penjelasan

Œ             # 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
Emigna
sumber
4

Haskell , 43 byte

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

Cobalah online!

Tidak
sumber
Dang, terlalu rumit lagi. Anehnya, saya menurunkannya menjadi 39 byte dengan output truthy / falsy, jadi jika Toeplitz = Falsediizinkan, saya mungkin telah mengalahkannya dengan satu byte.
Ørjan Johansen
3

Mathematica, 94 byte

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

memasukkan

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

satu lagi berdasarkan algoritma Stewie Griffin

Mathematica, 44 byte

If[#==#[[;;,1]]~ToeplitzMatrix~#[[1]],1,-1]&
J42161217
sumber
2
Apakah Anda perlu mendefinisikan s? Tidak bisakah Anda menggunakan #saja?
Bukan pohon
Iya! kamu benar!
J42161217
3

Java 7, 239 233 220 113 byte

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 byte setelah tip menggunakan algoritma yang lebih efisien berkat @Neil .

Penjelasan:

Coba di sini.

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
Kevin Cruijssen
sumber
apa fungsi r & c dalam fungsi pertama?
Mickey Jack
@MickeyJack Baris dan kolom ( r= ndan c= mjika Anda membandingkannya dengan tantangan).
Kevin Cruijssen
Bukankah Anda seharusnya melewatkan array sebagai parameter ke fungsi? Juga, ada algoritma yang jauh lebih efisien untuk ini, yang akan memotong jumlah byte Anda sekitar 50%.
Neil
1
@KevinCruijssen Cukup periksa bahwa semua elemen yang tidak di baris atau kolom pertama sama dengan elemen diagonal ke atas dan ke kiri darinya.
Neil
1
Ah, Anda bahkan harus menggunakan -->operator!
Neil
3

Haskell , 51 byte

t mengambil daftar daftar bilangan bulat dan mengembalikan bilangan bulat.

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

Cobalah online!

Ini bisa jadi 39 atau 38 byte dengan output truey / falsy.

Ide untuk menggunakan initterinspirasi oleh jawaban 05AB1E Emigna, yang menggunakan metode yang sangat mirip; sebelum itu saya menggunakan zip bersarang.

Bagaimana itu bekerja

  • zipWith((.init).(/=).tail)=<<tailadalah bentuk bebas point dari \m->zipWith(\x y->tail x/=init y)(tail m)m.
  • Ini menggabungkan setiap pasangan baris berturut-turut m, memeriksa apakah elemen pertama dengan elemen pertama dihapus berbeda dari elemen kedua dengan elemen kedua dihapus.
  • The orkemudian menggabungkan cek untuk semua pasangan baris.
  • 1-sum[2|...] mengkonversi format output.
Ørjan Johansen
sumber
2

JavaScript (ES6), 65 54 byte

a=>a.some((b,i)=>i--&&b.some((c,j)=>c-a[i][j-1]))?-1:1
Neil
sumber
Atau menggunakan trik Anda sendiri : a=>a.some(b=>b.some((v,i)=>d[i]-(d[i]=v),d=[,...d]),d=[])?-1:1(62 byte)
Arnauld
1
@Arnauld Terima kasih, tapi ternyata saya terlalu memikirkan masalahnya lagi ...
Neil
2

Ruby , 54 byte

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

Persis seperti yang ditentukan, dapat di-golf lebih jika input / output fleksibel diterima.

Penjelasan:

Iterate pada matriks, dan bandingkan setiap garis dengan garis di atas, bergeser satu ke kanan. Jika berbeda, gunakan array kosong untuk iterasi berikutnya. Pada akhirnya, kembalikan -1 jika array terakhir kosong, atau 1 jika setidaknya 2 elemen (karena matriks terkecil yang mungkin adalah 3x3, ini benar jika semua perbandingan mengembalikan true)

Cobalah online!

GB
sumber
Penggunaan yang bagus <=>untuk menghitung hasilnya!
Neil
Bagaimana kalau |(*x,_),y|Anda tidak perlu memotong x?
Stefan Pochmann
1

PHP, 70 byte

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

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

Tidak efisien sama sekali karena menyentuh setiap elemen n+mkali saat memfilter untuk diagonal. Kemudian periksa apakah ada lebih dari satu elemen unik per diagonal.

DenDenDo
sumber
1

Aksioma, 121 byte

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 harus menjadi Matriks dari beberapa elemen yang memungkinkan ~ =; ungolf itu

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
RosLuP
sumber
1

Retina , 148 byte

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

Cobalah online!

Matriks input 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

pertama-tama dikonversi ke matriks N × (N + M-1) dengan menyelaraskan diagonal dengan cara ini:

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

dan kemudian kolom pertama diperiksa berulang kali untuk mengandung satu nomor unik, dan dihapus jika demikian. Matriksnya adalah Toeplitz jika outputnya kosong.

eush77
sumber
Oh, itu tidak bekerja dengan angka negatif, harus memperbaikinya :)
eush77
1

MATL , 11 byte

T&Xd"@Xz&=v

Cobalah online!

Metode "membuat matriks Toeplitz dan memeriksanya" secara langsung, yang menggunakan beberapa jawaban teratas, terasa membosankan bagi saya (dan sepertinya itu akan menjadi 1 byte lebih lama). Jadi saya pergi untuk metode "periksa setiap diagonal hanya berisi satu nilai unik".

T&Xd - Ekstrak diagonal input dan buat matriks baru dengan mereka sebagai kolom (padding dengan nol sesuai kebutuhan)

" - beralih melalui kolom itu

@Xz - dorong variabel iterasi (kolom saat ini), dan hapus (padding) nol dari itu

&=- Cek kesetaraan siaran - ini menciptakan sebuah matriks dengan semua 1s (kebenaran) jika semua nilai yang tersisa sama satu sama lain, jika tidak, matriks tersebut berisi beberapa 0s yang palsu

v - menyatukan nilai hasil secara bersamaan, untuk membuat satu vektor hasil akhir yang bisa berupa kebenaran (semua 1) atau falsey (beberapa 0)

sundar - Pasang kembali Monica
sumber
0

R , 48 byte

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

Cobalah online!

Nitrodon
sumber
0

Clojure, 94 byte

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