Apakah ada N kemunculan berurutan dari suatu angka dalam satu baris / kolom dalam sebuah matriks?

20

Ambil matriks A yang terdiri dari bilangan bulat positif, dan satu bilangan bulat positif N sebagai input, dan tentukan apakah setidaknya ada N kejadian berurutan dari nomor yang sama di setiap baris atau kolom dalam matriks.

Anda hanya perlu menguji secara horizontal dan vertikal.

Uji kasus

N = 1
A = 
1
Result: True
----------------
N = 3
A = 
1 1 1
2 2 3
Result: True
----------------
N = 4
A = 
1 1 1
2 2 3
Result: False
----------------
N = 3
A = 
3 2 3 4 2 1
4 1 4 2 4 2
4 2 3 3 4 1
1 1 2 2 3 4
3 2 3 1 3 1
1 1 2 2 3 4
Result: True
----------------
N = 1
A = 
5 2 3 8
Result: True
----------------
N = 3
111   23  12    6
111   53   2    5
112  555   5  222
Result: False
----------------
N = 2
 4  2  6  2  1  5
 2  3  3  3  3  3
11 34  4  2  9  7
Result: True

Penjelasan selalu merupakan hal yang baik :)

Stewie Griffin
sumber
5
Anda tampaknya suka matriks.
Okx
4
Yah, aku pria MATLAB ... Mat rix Lab oratory =)
Stewie Griffin
Apakah itu cukup untuk mengembalikan nilai kebenaran / kepalsuan?
Dennis
@Dennis tentu saja :)
Stewie Griffin
5
Menjengkelkan, karena Anda adalah seorang pria Matlab, Anda membuat tantangan yang tampaknya mudah di MATLAB tetapi memiliki sedikit twist yang mengesampingkan solusi yang jelas ...
Sanchises

Jawaban:

7

Sekam , 9 byte

≤▲mLṁgS+T

Mengambil array 2D dan angka, mengembalikan 0untuk contoh falsy dan angka positif untuk contoh yang benar. Cobalah online!

Penjelasan

Sekam adalah bahasa fungsional, jadi programnya hanyalah komposisi dari beberapa fungsi.

≤▲mLṁgS+T
        T  Transpose the array
      S+   and concatenate with original.
           We get a list of the rows and columns of the input array.
    ṁ      Map and concatenate
     g     grouping of equal consecutive elements.
           This gives all consecutive runs on rows and columns.
  mL       Map length over the runs,
 ▲         take the maximum of the results
≤          and see if it's at least the second input.
Zgarb
sumber
5

Dyalog APL, 27 25 23 byte

{1∊∊⍷∘⍵¨(⊢,⍪¨)⍺/¨⍳⌈/∊⍵}

Cobalah secara Online!

Terima kasih kepada @MartinEnder dan @Zgarb untuk masing-masing -2 byte (komposisi menghilangkan kebutuhan untuk menggunakan wdan parens tidak berguna)

Beri tahu saya jika ada masalah dan / atau byte untuk golf. Argumen kiri adalah N , argumen kanan adalah A .

Penjelasan:

{1∊∊⍷∘⍵¨(⊢,⍪¨)⍺/¨⍳⌈/∊⍵}
                     ⍵    - Right argument
                    ∊     - Flatten the array
                 ⍳⌈/      - 1 ... the maximum (inclusive)
              ⍺/¨         - Repeat each item ⍺ (left argument) times.
        (⊢,⍪¨)            - Argument concatenated with their transposes.
    ⍷∘⍵¨                  - Do the patterns occur in ⍵?
   ∊                      - Flatten (since we have a vector of arrays)
 1∊                       - Is 1 a member?
{                     }   - Function brackets
Zacharý
sumber
4

Perl 6 , 60 byte

{(@^m|[Z,] @^m).map(*.rotor($^n=>$^n-1).map({[==] $_}).any)}

Cobalah online!

  • @^m adalah matriks input (argumen pertama) dan $^n merupakan jumlah kejadian berurutan untuk diperiksa (argumen kedua).
  • [Z,] @^m adalah transpos dari matriks input.
  • (@^m | [Z,] @^m)adalah atau-persimpangan dari matriks input dan transposnya. Berikut ini mapmengevaluasi nilai kebenaran jika $^nnilai yang sama berturut-turut terjadi di setiap baris undangan. Diterapkan pada matriks input ATAU transposinya, ia mengevaluasi ke nilai kebenaran jika matriks input atau transposinya mengandung $^nnilai yang sama berturut-turut di setiap baris; jika transpos memenuhi kondisi itu, itu berarti matriks input memiliki $^nnilai yang sama berturut-turut di salah satu kolomnya.
  • *.rotor($^n => $^n - 1)mengubah setiap baris menjadi urutan $^nirisan -element. Misalnya, jika $^n3 dan berturut-turut adalah <1 2 2 2 3>, ini dievaluasi menjadi (<1 2 2>, <2 2 2>, <2 2 3>).
  • .map({ [==] $_ })mengubah setiap irisan menjadi boolean yang menunjukkan apakah semua elemen irisan sama. Melanjutkan contoh sebelumnya, ini menjadi (False, True, False).
  • .any mengubah urutan boolean menjadi sebuah atau-persimpangan yang benar jika salah satu boolean itu benar.

Outputnya adalah nilai true-junction yang benar jika salah satu matriks input ATAU transposnya memiliki baris APA PUN di mana $^nnilai berturut-turut sama.

Sean
sumber
4

MATL , 12 byte

t!YdY'wg)>~a

Cobalah online! Atau verifikasi semua kasus uji .

Penjelasan

Matriks non-kuadrat tidak dapat digabungkan dengan benar untuk transposnya, baik secara vertikal maupun horizontal. Jadi kode menyatukan mereka secara diagonal , dengan membuat matriks blok-diagonal.

Matriks yang dihasilkan dilinearisasi dalam urutan kolom-utama dan run-length dikodekan. Nol yang dihasilkan dari penyatuan blok-diagonal berfungsi untuk mengisolasi nilai-nilai aktual.

Hasil dari pengkodean run-length adalah array nilai dan array run-lengths. Run-length yang sesuai dengan nilai-nilai bukan nol disimpan. Outputnya adalah 1jika beberapa dari panjang tersebut lebih besar dari atau sama dengan jumlah input, dan 0sebaliknya.

Mari kita lihat hasil antara untuk membuatnya lebih jelas. Pertimbangkan input

[10 10 10;
 20 20 30]

dan

3

Matriks blok diagonal yang berisi matriks input dan transposinya (kode t!Yd) adalah:

10 10 10  0  0
20 20 30  0  0
 0  0  0 10 20
 0  0  0 10 20
 0  0  0 10 30

Matriks ini tersirat linierisasi dalam urutan kolom-utama (turun, lalu lintas):

10 20  0  0  0 10 20  0  0  0 10 30  0  0  0  0  0 10 10 10  0  0 20 20 30

Run-length encoding (kode Y') memberikan dua vektor berikut (ditampilkan di sini sebagai vektor baris; sebenarnya mereka adalah vektor kolom): vektor dengan nilai

10 20  0 10 20  0 10 30  0 10  0 20 30

dan vektor dengan panjang run

1 1 3 1 1 3 1 1 5 3 2 2 1

Menyimpan hanya panjang yang sesuai dengan nilai yang bukan nol (kode wg)) berikan

1 1 1 1 1 1 3 2 1

Membandingkan untuk melihat panjang mana yang lebih besar dari atau sama dengan nomor input (kode >~) menghasilkan vektor

0 0 0 0 0 0 1 0 0

Akhirnya, output harus true(ditampilkan sebagai 1) jika vektor di atas mengandung setidaknya satu trueentri (kode a). Dalam hal ini hasilnya adalah

1
Luis Mendo
sumber
4

Oktaf, 77 70 byte

@(A,N)any(([x y]=runlength([(p=padarray(A,[1 1]))(:);p'(:)]))(!!y)>=N)

Cobalah online!

Penjelasan: Karena matriks ini hanya berisi bilangan bulat bukan nol, kita dapat menambahkan batas 0s di sekitar matriks dan menghitung enkode runlength dari matriks (dibentuk kembali menjadi vektor)

@(A,N)any(([x y]=runlength([(p=padarray(A,[1 1]))(:);p'(:)]))(!!y)>=N)
                             p=padarray(A,[1 1])                        % add a border of 0s around the matrix 
                            (                   )(:)                    % reshape the matrix to a column vector
                                                     p'(:)              % transpose of the matrix reshaped to a column vector
                           [                        ;     ]             % concatenate two vectors vertically
           [x y]=runlength(                                )            % runlength encoding of the vector[x=count,y=value]
          (                                                 )           % take x,counts.
                                                             (!!y)      % extrect those counts that their valuse aren't 0
      any(                                                        >=N)  % if we have at least a count that is greater than or equal to N                                                              
rahnema1
sumber
3
Saya sangat suka solusi Anda (tidak hanya yang ini), tetapi mereka pasti bisa mendapat manfaat dari beberapa penjelasan! :) Saya tidak tahu Octave punya runlength... Mempelajari sesuatu yang baru setiap hari ...
Stewie Griffin
Terima kasih telah mengingatkan saya tentang runlength! Menjadi lebih fokus pada Matlab, saya tidak ingat yang ada di Octave
Luis Mendo
@StewieGriffin Terima kasih, jawabnya diperbarui setelah bangun!
rahnema1
@LuisMendo Setelah salah satu posting Anda, saya menyadari fungsi bernama runlength.
rahnema1
4

Jelly , 9 8 byte

;ZjṡƓE€S

Mengambil matriks sebagai argumen dan membaca integer dari STDIN.

Cobalah online!

Bagaimana itu bekerja

;ZjṡƓE€S  Main link. Argument: M (matrix / row array)

 Z        Zip/transpose M.
;         Concatenate the row array with the column array.
  j       Join the rows and columns, separating by M.
    Ɠ     Read an integer n from STDIN.
   ṡ      Split the result to the left into overlapping slices of length 2.
     E€   Test the members of each resulting array for equality.
       S  Take the sum.

Contoh dijalankan

;ZjṡƓE€S  Argument: [[1, 2], [3, 2]]. STDIN: 2

 Z        [[1, 3], [2, 2]]

;         [[1, 2], [3, 2], [1, 3], [2, 2]]

  j       [1, 2, [1, 2], [3, 2], 3, 2, [1, 2], [3, 2], 1, 3, [1, 2], [3, 2], 2, 2]

    Ɠ     2

   ṡ      [[1, 2],             [2, [1, 2]],        [[1, 2], [3, 2]],   [[3, 2], 3],
           [3, 2],             [2, [1, 2]],        [[1, 2], [3, 2]],   [[3, 2], 1],
           [1, 3],             [3, [1, 2]],        [[1, 2], [3, 2]],   [[3, 2], 2],
           [2, 2]                                                                 ]

     E€   [     0,                       0,                       0,             0,
                0,                       0,                       0,             0,
                0,                       0,                       0,             0,
                1                                                                 ]

       S  1
Dennis
sumber
Saya memiliki ide yang sama dengan ;Z, meskipun di Japt daripada Jelly ...
ETHproduksi
Sekarang saya mengerti mengapa Anda bertanya tentang nilai kebenaran / kepalsuan . Definisi Jelly itu diilhami oleh MATLAB (atau MATL) bukan?
Stewie Griffin
Tidak, Jelly menggunakan kondisional Python secara internal. The Ȧatom terinspirasi oleh MATL sekalipun.
Dennis
Oh well, milik saya terlalu lama>. <Benar, Ebuiltin adalah cara untuk melakukannya. Bagus :)
HyperNeutrino
3

Python 2 , 60 92 91 byte

def f(n,x):x=[map(str,i)for i in x];print any(`[i]*n`[1:-1]in`x+zip(*x)`for i in sum(x,[]))

Cobalah online!

Alih-alih menghitung, daftar dengan ukuran n(untuk setiap elemen dalam matriks) dihasilkan dan diperiksa jika ada pada matriks

Tanpa string, 94 byte

lambda n,x:any((e,)*n==l[i:i+n]for l in x+zip(*x)for i in range(len(l)-n+1)for e in sum(x,()))

Cobalah online!

tongkat
sumber
Saya pikir ini dapat memberikan hasil positif palsu dengan angka multidigit.
xnor
@ xnor di sana, diperbaiki
Rod
3

Oktaf , 59 byte

@(A,N)any({[l,v]=runlength(blkdiag(A,A')(:)),l(v>=0)}{2}>=N)

Cobalah online! Atau verifikasi semua kasus uji .

Ini menggunakan pendekatan yang sama dengan jawaban MATL saya (lihat penjelasan di sana).

Luis Mendo
sumber
1
blkdiag(A,A'). Sangat bagus!
rahnema1
3

Japt , 18 15 14 byte

cUy)d_ò¦ d_ʨV

Menguji

  • 3 byte disimpan dengan bantuan dari ETHproductions.

Penjelasan

    :Implicit input of 2D array U and integer V
c   :Append to U...
Uy  :U transposed.
d   :Check if any of the elements (sub-arrays) in U return true when...
_   :Passed through a function that...
ò   :Partitions the current element by...
¦   :Checking for inequality.
d   :Check if any of the partitions return true when...
_   :Passed through a function that checks if...
Ê   :The length of the current element...
¨V  :Is greater than or equal to V.
    :Implicit output of resulting boolean.
Shaggy
sumber
1
Oh wow, saya tidak melihat ini sebelum memposting milik saya. Anda dapat menyimpan 2 byte dengan cUy)®ò¦ d_l ¨V\nd, dan yang lain dengan cUy)d_ò¦ d_l ¨V, dan kemudian Anda praktis memiliki solusi (dihapus) saya.
ETHproduk
Ha ha; pikiran hebat ..., @ETHproductions :) Saya kaget saya jari tercepat setelah obarakon mengalahkan saya sepanjang hari hari ini! Terima kasih atas tip-tip itu, sudah melihat satu tapi belum yang lain.
Shaggy
2

CJam , 16 byte

q~_z+N*e`:e>0=>!

Cobalah online!

Penjelasan

q~    e# Read and eval input.
_z+   e# Append the matrix's transpose to itself.
N*    e# Join with linefeeds to flatten without causing runs across rows.
e`    e# Run-length encode.
:e>   e# Get maximum run (primarily sorted by length).
0=    e# Get its length.
>!    e# Check that it's not greater than the required maximum.
Martin Ender
sumber
Saya selalu bertanya-tanya mengapa CJam's RLE memberikan nilai run-length, kemudian nilai. Ya, ternyata berguna di sini :-)
Luis Mendo
@LuisMendo Saya rasa karena itulah cara Anda mengatakannya "3 a, 5 b, 2 c's". Saya benar-benar menemukan pesanan ini cukup berguna.
Martin Ender
Sebenarnya, runlengthfungsi Oktaf memberikan output dalam urutan itu juga. Tapi entah kenapa aku merasakan tatanan yang value, lengthlebih alami
Luis Mendo
2

Python 3 , 129 128 125 120 104 101 bytes

Terima kasih banyak kepada @ Zakary T, @Stewie Griffin, @Mr. Xcoder, @Rod, @totallyhuman sudah banyak memperbaiki ini.

def f(n,m):
 a=b=c=0;m+=zip(*m)
 for r in m:
  for i in r:b,a=[1,b+1][a==i],i;c=max(c,b)
 return n<=c

Cobalah online!

rusak
sumber
Anda tidak perlu ruang antara 1dan if.
Zacharý
Simpan empat byte dengan menggantinya a=b;b=0;c=0dengana=b=c=0
Tn. Xcoder
(Saya tidak yakin) tetapi saya pikir Anda dapat menggunakan m+zip(*m)sebagai gantinya mpada baris ke-4, dan lepaskan seluruhnya dari baris ke-1, memindahkannya n<=max()ke baris terakhir sebagain<=c
Rod
120 bytes
totallyhuman
Alih-alih b=b+1menggunakan b+=1... Ahh, Ninja'd oleh @StewieGriffin
Mr. Xcoder
2

05AB1E , 16 14 12 byte

Døìvyγ€gM²‹_

Cobalah online!

Dø           # Duplicate the input and transpose one copy
  ì          # Combine the rows of both matrixes into one array
   vy        #   For each row...
     γ       #     Break into chunks of the same element
      €g     #     get the length of each chunk
        M    #     Get the largest length so far
         ²‹_ #     Check if that is equal to or longer than required
Riley
sumber
1
@ MagicOctopusUrn Saya tidak yakin apa yang Anda maksud. Contoh itu memiliki 3 berturut-turut 0di baris kedua, jadi itu harus benar.
Riley
@MagicOctopusUrn Jika Anda memecah run (TIO) itu mengembalikan false.
Riley
Bukankah perintah ketiga menyatukan baris yang ditransformasikan ke baris yang asli?
Magic Gurita Guci
Juga, saya pikir itu seharusnya hanya mengembalikan true selama 3 ketika ada [3,3,3]. Saya salah membaca tantangan dalam kasus itu, jadi saya pikir saya salah di sini.
Magic Octopus Guci
@MagicOctopusUrn 3 perintah pertama akan membuat array yang berisi setiap baris dan setiap kolom sebagai elemen individual.
Riley
1

Jelly , 18 byte

ŒrFUm2<⁴$ÐḟL
ZÇo³Ç

Cobalah online!

ŒrFUm2<⁴$ÐḟL  Helper Link
Œr            Run-length encode
  F           Flatten the whole thing, giving the numbers in the odd indices and the lengths of the runs in the even indices
   U          Reverse
    m2        Take every other element (thus only keeping the run lengths)
         Ðḟ   Discard the elements that are
      <⁴$                                   less than the required run length
           L  And find the length
ZÇo³Ç         Main Link
Z             Zip the matrix
 Ç            Call the helper link on it
   ³Ç         Call the helper link on the original matrix
  o           Are either of these truthy?

Pengembalian 0untuk bilangan bulat palsu dan bilangan nol untuk kebenaran.

Ew, ini buruk. Dan sangat panjang. Tips bermain golf akan dihargai :)

HyperNeutrino
sumber
1

JavaScript (ES6), 99 byte

Mengambil matriks mdan jumlah kejadian yang diharapkan ndalam sintaks currying (m)(n). Mengembalikan boolean.

m=>n=>[',',`(.\\d+?){${m[0].length-1}}.`].some(s=>m.join`|`.match(`(\\b\\d+)(${s}\\1){${n-1}}\\b`))

Bagaimana?

Kode ini tidak terlalu pendek, tetapi saya ingin mencoba pendekatan murni berdasarkan pada ekspresi reguler.

Konversi dari matriks ke string

Kita gunakan m.join('|') untuk mengubah 2D-array menjadi sebuah string. Ini pertama-tama menyebabkan pemaksaan implisit dari baris-baris matriks ke string yang dipisah koma.

Misalnya, input ini:

[
  [ 1, 2, 3 ],
  [ 4, 5, 6 ]
]

akan diubah menjadi:

"1,2,3|4,5,6"

Pencocokan baris

Kami mencari kejadian berturut-turut dengan:

/(\b\d+)(,\1){n-1}\b/

Ini cocok:

  • \b batas kata
  • \d+ diikuti oleh angka
  • (){n-1}diikuti n-1 kali oleh:
    • , koma
    • \1 diikuti oleh referensi kami: batas kata + angka pertama
  • \b diikuti oleh batas kata

Pencocokan kolom

Kami mencari kejadian berturut-turut di kolom dengan:

/(\b\d+)((.\d+?){L-1}.\1){n-1}\b/

di mana Lpanjang baris.

Ini cocok:

  • \b batas kata
  • \d+ diikuti oleh angka
  • (){n-1}diikuti n-1 kali oleh:
    • (){L-1} L-1 kali:
      • . setiap karakter (berlaku: koma atau pipa)
      • \d+? diikuti oleh angka (yang ini harus tidak serakah)
    • . diikuti oleh karakter apa saja (lagi: koma atau pipa)
    • \1 diikuti oleh referensi kami: batas kata + angka pertama
  • \b diikuti oleh batas kata

Uji kasus

Arnauld
sumber
0

Clojure, 77 byte

#((set(for[I[%(apply map vector %)]i I p(partition %2 1 i)](count(set p))))1)

Membuat semua ppanjang partisi N(simbol %2) berturut-turut dan menghitung berapa banyak nilai berbeda yang dimilikinya. Kemudian membentuk himpunan panjang ini dan kembali 1jika ditemukan dari himpunan dan nilsebaliknya. forkonstruk adalah yang paling cocok untuk ini, upaya awal saya digunakan flatten, concatatau sesuatu yang singkat.

NikoNyrh
sumber