20
\$\begingroup\$

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

\$\endgroup\$
  • 5
    \$\begingroup\$ You seem to love matrixes. \$\endgroup\$ – Okx Jun 27 '17 at 18:00
  • 4
    \$\begingroup\$ Well, I'm a MATLAB guy... Matrix Laboratory =) \$\endgroup\$ – Stewie Griffin Jun 27 '17 at 18:01
  • \$\begingroup\$ Is it enough to return a truthy/falsy value? \$\endgroup\$ – Dennis Jun 27 '17 at 18:22
  • \$\begingroup\$ @Dennis of course :) \$\endgroup\$ – Stewie Griffin Jun 27 '17 at 18:22
  • 5
    \$\begingroup\$ Annoyingly, because you are a Matlab guy, you make challenges that seem easy in MATLAB but have a slight twist that rule out the obvious solution... \$\endgroup\$ – Sanchises Jun 27 '17 at 18:57

16 Answers 16

7
\$\begingroup\$

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

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

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.

\$\endgroup\$
4
\$\begingroup\$

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

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                                                              
\$\endgroup\$
  • 3
    \$\begingroup\$ I really like your solutions (not only this one), but they could definitely benefit from some explanations! :) I didn't know Octave had runlength... Learn something new everyday... \$\endgroup\$ – Stewie Griffin Jun 27 '17 at 19:39
  • \$\begingroup\$ Thanks for reminding me about runlength! Being more focused on Matlab, I didn't remember that existed in Octave \$\endgroup\$ – Luis Mendo Jun 27 '17 at 21:52
  • \$\begingroup\$ @StewieGriffin Thanks, answer updated after waking up! \$\endgroup\$ – rahnema1 Jun 28 '17 at 3:03
  • \$\begingroup\$ @LuisMendo After one of your posts I became aware of a function named runlength. \$\endgroup\$ – rahnema1 Jun 28 '17 at 3:06
4
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ I had the same idea with ;Z, though in Japt rather than Jelly... \$\endgroup\$ – ETHproductions Jun 27 '17 at 18:16
  • \$\begingroup\$ Now I see why you asked about truthy/falsy values. That definition in Jelly was inspired by MATLAB (or MATL) wasn't it? \$\endgroup\$ – Stewie Griffin Jun 27 '17 at 18:31
  • \$\begingroup\$ No, Jelly uses Python's conditionals internally. The Ȧ atom was inspired by MATL though. \$\endgroup\$ – Dennis Jun 27 '17 at 18:32
  • \$\begingroup\$ Oh well mine was way too long >.< Right, the E builtin was the way to do it. Nice :) \$\endgroup\$ – HyperNeutrino Jun 27 '17 at 18:49
3
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ I think this can give false positives with multidigit numbers. \$\endgroup\$ – xnor Jun 27 '17 at 18:50
  • \$\begingroup\$ @xnor there, fixed \$\endgroup\$ – Rod Jun 27 '17 at 19:04
3
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ blkdiag(A,A'). Very nice! \$\endgroup\$ – rahnema1 Jun 28 '17 at 3:17
3
\$\begingroup\$

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.
\$\endgroup\$
  • 1
    \$\begingroup\$ Oh wow, I didn't see this before posting mine. You could save 2 bytes with cUy)®ò¦ d_l ¨V\nd, and another with cUy)d_ò¦ d_l ¨V, and then you practically have my (deleted) solution. \$\endgroup\$ – ETHproductions Jun 27 '17 at 18:30
  • \$\begingroup\$ Ha-Ha; great minds ..., @ETHproductions :) I'm shocked I was fastest finger after obarakon beating me all day today! Thanks for those tips, had spotted one already but not the other yet. \$\endgroup\$ – Shaggy Jun 27 '17 at 18:40
2
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ I always wondered why CJam's RLE gives run-length, then value. Well, it turns out to be useful here :-) \$\endgroup\$ – Luis Mendo Jun 27 '17 at 22:03
  • \$\begingroup\$ @LuisMendo I guess because that's the way you'd say it "3 a's, 5 b's, 2 c's". I actually find this order useful quite often. \$\endgroup\$ – Martin Ender Jun 27 '17 at 22:05
  • \$\begingroup\$ Actually, Octave's runlength function gives outputs in that order too. But somehow I feel the order value, length more natural \$\endgroup\$ – Luis Mendo Jun 27 '17 at 22:07
2
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ You don't need a space between 1 and if. \$\endgroup\$ – Zacharý Jun 27 '17 at 18:22
  • \$\begingroup\$ Save four bytes by replacing a=b;b=0;c=0 with a=b=c=0 \$\endgroup\$ – Mr. Xcoder Jun 27 '17 at 18:25
  • \$\begingroup\$ (I'm not sure) but I think that you could use m+zip(*m) instead mon the 4th line, and drop entirely the 1st line, moving the n<=max() to the last line as n<=c \$\endgroup\$ – Rod Jun 27 '17 at 18:25
  • \$\begingroup\$ 120 bytes \$\endgroup\$ – totallyhuman Jun 27 '17 at 18:26
  • \$\begingroup\$ Instead of b=b+1 use b+=1... Ahh, Ninja'd by @StewieGriffin \$\endgroup\$ – Mr. Xcoder Jun 27 '17 at 18:26
2
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ @MagicOctopusUrn I'm not sure what you mean. That example has 3 consecutive 0s in the second row, so it should be true. \$\endgroup\$ – Riley Jun 27 '17 at 19:15
  • \$\begingroup\$ @MagicOctopusUrn If you break up that run (TIO) it returns false. \$\endgroup\$ – Riley Jun 27 '17 at 19:17
  • \$\begingroup\$ Doesn't the third command concatenate the transposed rows to the original rows? \$\endgroup\$ – Magic Octopus Urn Jun 27 '17 at 19:59
  • \$\begingroup\$ Also, I thought it was supposed to only return true for 3 when there is [3,3,3]. I misread the challenge in that case, so I think I'm wrong here. \$\endgroup\$ – Magic Octopus Urn Jun 27 '17 at 20:00
  • \$\begingroup\$ @MagicOctopusUrn The first 3 commands will create an array that contains each row and each column as individual elements. \$\endgroup\$ – Riley Jun 27 '17 at 20:02
1
\$\begingroup\$

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

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

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

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

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!

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

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.

\$\endgroup\$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.