Are there N consecutive occurrences of a number in a row/column in a matrix?

Question

Take a matrix A consisting positive integers, and a single positive integer N as input, and determine if there are at least N consecutive occurrences of the same number in any row or column in the matrix.

You need only test horizontally and vertically.

Test cases

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

Explanations are always a good thing :)

Answer 1

Husk, 9 bytes

≤▲mLṁgS+T

Takes a 2D array and a number, returns 0 for falsy instances and a positive number for truthy instances. Try it online!

Explanation

Husk is a functional language, so the program is just a composition of several functions.

≤▲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.

Answer 2

Jelly, 9 8 bytes

;ZjṡƓE€S

Takes the matrix as arguments and reads the integer from STDIN.

Try it online!

How it works

;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.

Example run

;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

Answer 3

Dyalog APL, 27 25 23 bytes

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

Try It Online!

Thanks to @MartinEnder and @Zgarb for -2 bytes each (composition removes the need to use w and pointless parens)

Alert me if there are any problems and/or bytes to golf. Left argument is N, right argument is A.

Explanation:

{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

Answer 4

MATL, 12 bytes

t!YdY'wg)>~a

Try it online! Or verify all test cases.

Explanation

A non-square matrix cannot be properly concatenated to its transpose, either vertically or horizontally. So the code concatenates them diagonally, by creating a block-diagonal matrix.

The resulting matrix is linearized in column-major order and run-length encoded. The zeros resulting from the block-diagonal concatenation serve to isolate the runs of actual values.

The results from run-length encoding are an array of values and an array of run-lengths. The run-lengths corresponding to non-zero values are kept. The output is 1 if some of those lengths is greater than or equal to the input number, and 0 otherwise.

Let's see the intermediate results to make it clearer. Consider inputs

[10 10 10;
 20 20 30]

and

3

The block diagonal matrix containing the input matrix and its transpose (code t!Yd) is:

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

This matrix is implicit linearized in column-major order (down, then across):

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 (code Y') gives the following two vectors (shown here as row vectors; actually they are column vectors): vector with values

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

and vector with run lengths

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

Keeping only the lengths correspoinding to non-zero values (code wg)) gives

1 1 1 1 1 1 3 2 1

Comparing to see which lengths are greater than or equal to the input number (code >~) produces the vector

0 0 0 0 0 0 1 0 0

Finally, the output should be true (shown as 1) if the above vector contains at least a true entry (code a). In this case the result is

1

Answer 5

Perl 6, 60 bytes

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

Try it online!

• @^m is the input matrix (first argument) and $^n is the number of consecutive occurrences to check for (second argument).
• [Z,] @^m is the transpose of the input matrix.
• (@^m | [Z,] @^m) is an or-junction of the input matrix and its transpose. The following map evaluates to a truthy value if $^n consecutive equal values occur in any row of the invocant. Applied to the input matrix OR its transpose, it evaluates to a truthy value if either the input matrix or its transpose contain $^n consecutive equal values in any row; if the transpose meets that condition, that means the input matrix has $^n consecutive equal values in one of its columns.
• *.rotor($^n => $^n - 1) turns each row into a sequence of $^n-element slices. For example, if $^n is 3 and a row is <1 2 2 2 3>, this evaluates to (<1 2 2>, <2 2 2>, <2 2 3>).
• .map({ [==] $_ }) turns each slice into a boolean that indicates whether all elements of the slice are equal. Continuing the previous example, this becomes (False, True, False).
• .any turns that sequence of booleans into an or-junction which is truthy if any of the booleans are true.

The output is a truthy or-junction value which is true if either the input matrix OR its transpose have ANY row where $^n consecutive values are equal.

Answer 6

Octave, 77 70 bytes

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

Try it online!

Explanation: Since tha matrix only contains non-zero integers we can add a border of 0s around the matrix and compute runlength encoding of the matrix(reshaped to a vector)

@(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                                                              
      

Answer 7

Python 3, 129 128 125 120 104 101 bytes

Huge thanks to @Zachary T, @Stewie Griffin, @Mr. Xcoder, @Rod, @totallyhuman for improving this by a lot.

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

Try it online!

Answer 8

Python 2, 60 92 91 bytes

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

Try it online!

Instead of counting, a list with size n (for each element in the matrix) is generated and checked if it's on the matrix

Without strings, 94 bytes

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,()))

Try it online!

Answer 9

Octave, 59 bytes

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

Try it online! Or verify all test cases.

This uses the same approach as my MATL answer (see explanation there).

Answer 10

Japt, 18 15 14 bytes

cUy)d_ò¦ d_ʨV

Test it

• 3 bytes saved with some help from ETHproductions.

---

Explanation

    :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.

Answer 11

CJam, 16 bytes

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

Try it online!

Explanation

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.

Answer 12

05AB1E, 16 14 12 bytes

Døìvyγ€gM²‹_

Try it 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

Answer 13

Jelly, 18 bytes

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

Try it 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?

Returns 0 for false and a non-zero integer for truthy.

Ew, this is bad. And very long. Golfing tips would be appreciated :)

Answer 14

JavaScript (ES6), 99 bytes

Takes the matrix m and the expected number of occurrences n in currying syntax (m)(n). Returns a boolean.

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

How?

This code is not particularly short, but I wanted to try an approach purely based on regular expressions.

Conversion of the matrix to a string

We use m.join('|') to transform the 2D-array into a string. This first causes an implicit coercion of the matrix rows to comma-separated strings.

For instance, this input:

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

will be transformed into:

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

Row matching

We look for consecutive occurrences in a row with:

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

This is matching:

• \b a word boundary
• \d+ followed by a number
• (){n-1} followed n-1 times by:
  • , a comma
  • \1 followed by our reference: a word boundary + the first number
• \b followed by a word boundary

Column matching

We look for consecutive occurrences in a column with:

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

where L is the length of a row.

This is matching:

• \b a word boundary
• \d+ followed by a number
• (){n-1} followed n-1 times by:
  • (){L-1} L-1 times:
    • . any character (in effect: either a comma or a pipe)
    • \d+? followed by a number (this one must be non-greedy)
  • . followed by any character (again: either a comma or a pipe)
  • \1 followed by our reference: a word boundary + the first number
• \b followed by a word boundary

Test cases

let f=

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

console.log(f([
  [ 1 ]
])(1))

console.log(f([
  [ 1, 1, 1 ],
  [ 2, 2, 3 ]
])(3))

console.log(f([
  [ 1, 1, 1 ],
  [ 2, 2, 3 ]
])(4))

console.log(f([
  [ 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 ]
])(3))

console.log(f([
  [ 5, 2, 3, 8 ]
])(1))

console.log(f([
  [ 111,  23,  12,   6 ],
  [ 111,  53,   2,   5 ],
  [ 112, 555,   5, 222 ]
])(3))

console.log(f([
  [  4,  2,  6,  2,  1,  5 ],
  [  2,  3,  3,  3,  3,  3 ],
  [ 11, 34,  4,  2,  9,  7 ]
])(2))

Answer 15

Octave, 58 bytes

f=@(A)runlength([A;nan*A](:))
F=@(A,n)max([f(A),f(A')])>=n

Try it online!

Answer 16

BQN, 21 bytes

-⊸≢1=⊣≠∘⍷˘∘↕˘⎊0¨⋈⟜⍉∘⊢

Anonymous tacit function; takes the number n as left argument and the 2D array a as right argument. Try it at BQN online!

Explanation

So. Many. Modifiers. ○_○

-⊸≢1=⊣≠∘⍷˘∘↕˘⎊0¨⋈⟜⍉∘⊢
                      ∘⊢  With the right argument (a),
                 ⋈⟜⍉     pair it with its transpose
                ¨         Apply this function to each of those arrays
     ⊣                    and the original left argument (n):
             ˘              Within each row of the array,
            ↕               get all sublists of length n
          ˘∘                Then, with each of those sublists,
       ≠∘⍷                  uniquify and get the length (1 iff all elements are equal)
              ⎊0           If that function errored because n is too big, use 0 instead
                          We now have a list of two elements, each of which is either
                          an array of integers or a 0
   1=                     Compare each integer to 1 (0 if not equal, 1 if equal)
 ⊸≢                      Is that nested list different from
-                         the same list with each integer negated?

If there are no sublists where all items are identical, we'll get a nested list containing only zeros, which remains the same under negation; thus, ≢ will return 0. If there is at least one sublist with identical items, we'll get a nested list that contains a 1 somewhere, which changes under negation; thus, ≢ will return 1.

Answer 17

Vyxal, 9 bytes

:∩JvøĖ≤fa

Try it Online!

Answer 18

Python 2, 64 bytes

lambda M,n:(', 0'*n)[5:]in`[map(cmp,l,l[1:])for l in M+zip(*M)]`

Try it online!

Answer 19

Clojure, 77 bytes

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

Creates all consecutive partitions p of length N (symbol %2) and counts how many distinct values it has. Then it forms the set of these lengths and returns 1 if it is found from the set and nil otherwise. for construct was the perfect fit for this, my original attempt used flatten, concat or something of that short.

Answer 20

05AB1E, 8 bytes

Dø«δÅγ›ß

First input is the matrix \$A\$, second is the integer \$N\$.
Outputs an inverted boolean: 0 for truthy and 1 for falsey.

Try it online or verify all test cases.

Explanation:

D         # Duplicate the (implicit) input-matrix
 ø        # Zip/transpose its copy; swapping rows/columns
  «       # Merge it to the input-matrix
          # (we now have a list of all rows and all columns)
          #  e.g. input=[[1,1,1],[2,2,3]] → [[1,1,1],[2,2,3],[1,2],[1,2],[1,3]]
   δ      # Map† over each inner list:
    Åγ    #  Run-length encode it; pushing the list of items and list of lengths
          #  separately to the stack, only leaving the top list of lengths
          #   → [[3],[2,1],[1,1],[1,1],[1,1]]
       ›  # Check for each inner-most length if it's smaller than the second (implicit)
          # input-integer
        ß # Pop and push the flattened minimum to check if any was falsey
          # (after which the result is output implicitly)

† δ is technically an 'apply double-vectorized', which also uses the second (implicit) input-integer as argument. It's usually used to create tables from two lists, or to apply a builtin that takes a single argument on each inner item of a list.
In this case, the implicit input-integer is simply ignored since builtin Åγ takes no arguments, and δ therefore acts as a map. We use this, because map εÅγ} is 1 byte longer and map €Åγ would also keep the lists of items (so the example above would become [[3],[1],[2,1],[2,3],[1,1],[1,2],[1,1],[1,2],[1,1],[1,3]] instead).

Answer 21

Julia, 90,84 70 bytes

A\n=(~X=occursin("0"^(n-1),[X;0X[1,:]'][:]|>diff.|>sign|>join);~A|~A')

(A>0 is exploited.)

Attempt This Online!

and a StatsBase-based vari:

16+54 bytes

using StatsBase
A\n=(~X=any(eachrow(X).|>x->any(rle(x)[2].≥n));~A|~A')