¿Hay N ocurrencias consecutivas de un número en una fila / columna en una matriz?

20

Tome una matriz A que consta de enteros positivos y un solo entero positivo N como entrada, y determine si hay al menos N ocurrencias consecutivas del mismo número en cualquier fila o columna de la matriz.

Solo necesita probar horizontal y verticalmente.

Casos de prueba

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

Las explicaciones siempre son buenas :)

Stewie Griffin
fuente
55
Parece que te encantan las matrices.
Okx
44
Bueno, soy un chico de MATLAB ... Mat rix Lab oratory =)
Stewie Griffin
¿Es suficiente devolver un valor verdadero / falso?
Dennis
@Dennis, por supuesto :)
Stewie Griffin
55
Molesto, porque eres un chico de Matlab, haces desafíos que parecen fáciles en MATLAB pero tienen un pequeño giro que descarta la solución obvia ...
Sanchises

Respuestas:

7

Casco , 9 bytes

≤▲mLṁgS+T

Toma una matriz 2D y un número, devuelve las 0instancias falsas y un número positivo para las instancias verdaderas. Pruébalo en línea!

Explicación

Husk es un lenguaje funcional, por lo que el programa es solo una composición de varias funciones.

≤▲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
fuente
5

Dyalog APL, 27 25 23 bytes

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

¡Pruébelo en línea!

Gracias a @MartinEnder y @Zgarb por -2 bytes cada uno (la composición elimina la necesidad de usar w y parens sin sentido)

Avisarme si hay algún problema y / o bytes al golf. Argumento izquierdo es N , argumento de la derecha es una .

Explicación:

{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ý
fuente
4

Perl 6 , 60 bytes

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

Pruébalo en línea!

  • @^mes la matriz de entrada (primer argumento) y $^nes el número de ocurrencias consecutivas para verificar (segundo argumento).
  • [Z,] @^m es la transposición de la matriz de entrada.
  • (@^m | [Z,] @^m)es una unión o de la matriz de entrada y su transposición. Lo siguiente se mapevalúa como un valor verdadero si $^nse producen valores iguales consecutivos en cualquier fila del invocante. Aplicado a la matriz de entrada O su transposición, se evalúa a un valor verdadero si la matriz de entrada o su transposición contienen $^nvalores iguales consecutivos en cualquier fila; si la transposición cumple esa condición, eso significa que la matriz de entrada tiene$^n valores iguales consecutivos en una de sus columnas.
  • *.rotor($^n => $^n - 1)convierte cada fila en una secuencia de $^ncortes de elementos. Por ejemplo, si $^nes 3 y una fila es <1 2 2 2 3>, esto se evalúa como (<1 2 2>, <2 2 2>, <2 2 3>).
  • .map({ [==] $_ })convierte cada sector en un valor booleano que indica si todos los elementos del sector son iguales. Continuando con el ejemplo anterior, esto se convierte (False, True, False).
  • .any convierte esa secuencia de booleanos en una unión o que es verdadera si alguno de los booleanos es verdadero.

La salida es un valor verdadero o de unión que es verdadero si la matriz de entrada O su transposición tienen CUALQUIER fila donde los $^nvalores consecutivos son iguales.

Sean
fuente
4

MATL , 12 bytes

t!YdY'wg)>~a

Pruébalo en línea! O verificar todos los casos de prueba .

Explicación

Una matriz no cuadrada no se puede concatenar adecuadamente a su transposición, ya sea vertical u horizontalmente. Entonces el código los concatena diagonalmente , creando una matriz de bloques en diagonal.

La matriz resultante se linealiza en orden de columna principal y se codifica por longitud de ejecución. Los ceros resultantes de la concatenación de bloque diagonal sirven para aislar las corridas de valores reales.

Los resultados de la codificación de longitud de ejecución son una matriz de valores y una matriz de longitudes de ejecución. Se mantienen las longitudes de ejecución correspondientes a valores distintos de cero. La salida es 1si alguna de esas longitudes es mayor o igual que el número de entrada, y de lo 0contrario.

Veamos los resultados intermedios para hacerlo más claro. Considerar entradas

[10 10 10;
 20 20 30]

y

3

La matriz diagonal de bloque que contiene la matriz de entrada y su transposición (código t!Yd) es:

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

Esta matriz está linealizada implícitamente en el orden de columnas principales (abajo, luego a través):

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

La codificación de longitud de ejecución (código Y') proporciona los siguientes dos vectores (mostrados aquí como vectores de fila; en realidad son vectores de columna): vector con valores

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

y vector con longitudes de ejecución

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

Mantener solo las longitudes correspondientes a valores distintos de cero (código wg)) da

1 1 1 1 1 1 3 2 1

Al comparar para ver qué longitudes son mayores o iguales que el número de entrada (código >~) produce el vector

0 0 0 0 0 0 1 0 0

Finalmente, la salida debería ser true(mostrada como 1) si el vector anterior contiene al menos una trueentrada (código a). En este caso el resultado es

1
Luis Mendo
fuente
4

Octava, 77 70 bytes

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

Pruébalo en línea!

Explicación: Dado que la matriz solo contiene enteros distintos de cero, podemos agregar un borde de 0 alrededor de la matriz y calcular la codificación de longitud de ejecución de la matriz (reformada en un 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                                                              
rahnema1
fuente
3
Realmente me gustan sus soluciones (no solo esta), ¡pero definitivamente podrían beneficiarse de algunas explicaciones! :) No sabía que Octave tenía runlength... Aprende algo nuevo todos los días ...
Stewie Griffin
Gracias por recordarme runlength! Al estar más centrado en Matlab, no recordaba que existiera en Octave
Luis Mendo
@StewieGriffin Gracias, respuesta actualizada después de despertar!
rahnema1
@LuisMendo Después de una de tus publicaciones, me di cuenta de una función llamada runlength .
rahnema1
4

Jalea , 9 8 bytes

;ZjṡƓE€S

Toma la matriz como argumentos y lee el entero de STDIN.

Pruébalo en línea!

Cómo funciona

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

Ejecución de ejemplo

;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
fuente
Tuve la misma idea ;Z, aunque en Japt en lugar de Jelly ...
ETHproductions
Ahora veo por qué preguntaste acerca de los valores de verdad / falsedad . Esa definición en Jelly fue inspirada por MATLAB (o MATL) ¿no?
Stewie Griffin
No, Jelly usa los condicionales de Python internamente. Sin Ȧembargo, el átomo fue inspirado por MATL.
Dennis
Oh bueno, el mío fue demasiado largo>. <Correcto, la Econstrucción fue la forma de hacerlo. Nice :)
HyperNeutrino
3

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

Pruébalo en línea!

En lugar de contar, una lista con tamaño n se genera (para cada elemento en la matriz) y se verifica si está en la matriz

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

Pruébalo en línea!

varilla
fuente
Creo que esto puede dar falsos positivos con números de múltiples dígitos.
xnor
@xnor allí, arreglado
Rod
3

Japt , 18 15 14 bytes

cUy)d_ò¦ d_ʨV

Pruébalo

  • 3 bytes guardados con alguna ayuda de ETHproductions.

Explicación

    :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.
Lanudo
fuente
1
Oh wow, no vi esto antes de publicar el mío. Puede guardar 2 bytes con cUy)®ò¦ d_l ¨V\nd, y otro con cUy)d_ò¦ d_l ¨V, y luego prácticamente tiene mi solución (eliminada).
ETHproductions
Jaja; grandes mentes ..., @ETHproductions :) ¡Estoy sorprendido de haber sido el dedo más rápido después de que Obarakon me golpeó todo el día hoy! Gracias por esos consejos, ya había visto uno pero no el otro todavía.
Shaggy
2

CJam , 16 bytes

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

Pruébalo en línea!

Explicación

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
fuente
Siempre me pregunté por qué el RLE de CJam da duración de la ejecución, luego valor. Bueno, resulta útil aquí :-)
Luis Mendo
@LuisMendo, supongo que así es como lo dirías "3 a's, 5 b's, 2 c's". De hecho, encuentro este pedido útil con bastante frecuencia.
Martin Ender
En realidad, la runlengthfunción de Octave también proporciona salidas en ese orden. Pero de alguna manera siento el orden value, lengthmás natural
Luis Mendo
2

Python 3 , 129 128 125 120 104 101 bytes

Muchas gracias a @Zachary T, @Stewie Griffin, @Mr. Xcoder, @Rod, @totallyhuman por mejorar mucho esto.

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

Pruébalo en línea!

irapsaged
fuente
No necesitas un espacio entre 1y if.
Zacharý
Ahorre cuatro bytes reemplazándolos a=b;b=0;c=0cona=b=c=0
Mr. Xcoder
(No estoy seguro), pero creo que podría usar m+zip(*m)en su lugar men la cuarta línea y soltar por completo la primera línea, moviendo n<=max()la última línea comon<=c
Rod
120 bytes
totalmente humano
En lugar de b=b+1usar b+=1... Ahh, Ninja'd por @StewieGriffin
Mr. Xcoder
2

05AB1E , 16 14 12 bytes

Døìvyγ€gM²‹_

Pruébalo en línea!

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
fuente
1
@MagicOctopusUrn No estoy seguro de lo que quieres decir. Ese ejemplo tiene 3 0s consecutivos en la segunda fila, por lo que debería ser cierto.
Riley
@MagicOctopusUrn Si interrumpe esa ejecución (TIO) , devuelve falso.
Riley
¿El tercer comando no concatena las filas transpuestas a las filas originales?
Magic Octopus Urn
Además, pensé que se suponía que solo debía devolver verdadero para 3 cuando hay [3,3,3] . Leí mal el desafío en ese caso, así que creo que estoy equivocado aquí.
Magic Octopus Urn
@MagicOctopusUrn Los primeros 3 comandos crearán una matriz que contiene cada fila y cada columna como elementos individuales.
Riley
1

Jalea , 18 bytes

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

Pruébalo en línea!

Œ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?

Devoluciones 0 falso y un entero distinto de cero para verdad.

Ew, esto es malo. Y muy largo Se agradecerían consejos de golf :)

Hiperneutrino
fuente
1

JavaScript (ES6), 99 bytes

Toma la matriz my el número esperado de ocurrenciasn en la sintaxis de curry (m)(n). Devuelve un booleano.

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

¿Cómo?

Este código no es particularmente corto, pero quería probar un enfoque basado exclusivamente en expresiones regulares.

Conversión de la matriz a una cadena.

Usamos m.join('|') para transformar la matriz 2D en una cadena. Esto primero provoca una coerción implícita de las filas de la matriz a cadenas separadas por comas.

Por ejemplo, esta entrada:

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

se transformará en:

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

Coincidencia de fila

Buscamos sucesos consecutivos en una fila con:

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

Esto es coincidente:

  • \b un límite de palabras
  • \d+ seguido de un número
  • (){n-1}seguido n-1 veces por:
    • , una coma
    • \1 seguido de nuestra referencia: un límite de palabra + el primer número
  • \b seguido de un límite de palabra

Coincidencia de columna

Buscamos ocurrencias consecutivas en una columna con:

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

dónde L es la longitud de una fila.

Esto es coincidente:

  • \b un límite de palabras
  • \d+ seguido de un número
  • (){n-1}seguido n-1 veces por:
    • (){L-1} L-1 veces:
      • . cualquier personaje (en efecto: una coma o una barra)
      • \d+? seguido de un número (este no debe ser codicioso)
    • . seguido de cualquier carácter (de nuevo: una coma o una barra)
    • \1 seguido de nuestra referencia: un límite de palabra + el primer número
  • \b seguido de un límite de palabra

Casos de prueba

Arnauld
fuente
0

Clojure, 77 bytes

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

Crea todas las particiones consecutivas p de longitud N(símbolo %2) y cuenta cuántos valores distintos tiene. Luego forma el conjunto de estas longitudes y regresa 1si se encuentra del conjunto y de lo nilcontrario. forLa construcción fue el ajuste perfecto para esto, mi intento original utilizado flatten, concato algo así de corto.

NikoNyrh
fuente