php - regulares - regex preg_match

Coincidencia de expresiones regulares "verticales" en una "imagen" ASCII

Question

Nota: esta es una pregunta sobre las posibilidades de los sabores regex modernos. No se trata de la mejor manera de resolver esto usando otros métodos. Está inspirado en una pregunta anterior , pero esa no está restringida a regex.

El problema

En una "imagen" ASCII / art / map / string como:

....X.......
..X..X...X....
X.X...X..X.....
X....XXXXXX.....
X..XXX...........
.....X..........
..............X
..X...........X....
..X...........X....X...
....X.....

Me gustaría encontrar una formación de línea vertical simple de tres X s:

X
X
X

El número de líneas es variable en la imagen, y el ancho de cada línea también es variable.

Las preguntas)

Con regex (PCRE / PHP, Perl, .NET o similar) es posible:

1. Determinar si existe tal formación
2. Cuente el número de tales formaciones / coincida con el punto de partida de todas ellas (4 en el ejemplo anterior)

Answer 1

Respuesta a la pregunta 1

Para responder la primera pregunta, uno podría usar:

(?xm)                    # ignore comments and whitespace, ^ matches beginning of line
^                        # beginning of line
(?:
    .                    # any character except /n
    (?=                  # lookahead
        .*+/n            # go to next line
        ( /1?+ . )       # add a character to the 1st capturing group
        .*+/n            # next line
        ( /2?+ . )       # add a character to the 2nd capturing group
    )
)*?                      # repeat as few times as needed
X .*+/n                  # X on the first line and advance to next line
/1?+                     # if 1st capturing group is defined, use it, consuming exactly the same number of characters as on the first line
X .*+/n                  # X on the 2nd line and advance to next line
/2?+                     # if 2st capturing group is defined, use it, consuming exactly the same number of characters as on the first line
X                        # X on the 3rd line

Demo en línea

Esta expresión funciona en Perl, PCRE, Java y debería funcionar en .NET.

La expresión usa lookaheads con grupos de captura autorreferenciados para agregar un personaje por cada repetición de la búsqueda anticipada (esto se usa para "contar").

/1?+ Significa que /1 coincide (o está definido) con el consumo, y no se lo devuelve (no retrocede). En este caso, es equivalente a (?(1) /1 ) . Lo que significa que coincide /1 si /1 está definido.

polygenelubricants explica este tipo de lookaheads con referencias muy bien en su respuesta para ¿Cómo podemos unir ^ nb ^ n con Java regex? . (También ha escrito sobre otros trucos impresionantes para expresiones regulares de Java que incluyen referencias retrospectivas y aproximaciones).

Respuesta a la pregunta 2

Juego simple

Cuando se usa el emparejamiento y se requiere la respuesta (conteo) en el número de coincidencias, la respuesta a la pregunta 2 sería:

No se puede resolver directamente en sabores regex que tienen un aspecto limitado detrás. Mientras que otros sabores como Java y .NET podrían (como por ejemplo en la solución .NET de m.buettner ).

Por lo tanto, las coincidencias de expresiones regulares simples en Perl y PCRE (PHP, etc.) no pueden responder directamente a esta pregunta en este caso.

(¿Semi?) A prueba

Suponga que no hay disponibles longitudes de referencia variables.

De alguna manera, debe contar la cantidad de caracteres en una línea antes de una X
La única forma de hacerlo es hacer coincidirlas, y dado que no hay disponibles versiones de longitud variable, debe iniciar la coincidencia (al menos) al principio de la línea.
Si comienzas el partido al comienzo de una línea, solo puedes obtener un partido por línea como máximo.

Dado que puede haber múltiples ocurrencias por línea, esto no los contaría todos y no daría una respuesta correcta.

Longitud / solución indirecta

Por otro lado, si aceptamos la respuesta como la duración de un partido o resultado de sustitución, entonces la segunda pregunta puede responderse en PCRE y Perl (y en otros sabores).

Esta solución está basada / inspirada en la agradable "solución PCRE parcial" de m.buettner .

Uno podría simplemente reemplazar todas las coincidencias de la siguiente expresión con $3 , obteniendo la respuesta a la pregunta dos (el número de patrones de intereses) como la longitud de la cadena resultante.

^
(?:
    (?:                   # match .+? characters
        .
        (?=               # counting the same number on the following two lines
            .*+/n
            ( /1?+ . )
            .*+/n
            ( /2?+ . )
        )
    )+?
    (?<= X )              # till the above consumes an X
    (?=                   # that matches the following conditions
        .*+/n
        /1?+
        (?<= X )
        .*+/n
        /2?+
        (?<= X )
    )
    (?=                   # count the number of matches
        .*+/n
        ( /3?+ . )        # the number of matches = length of $3
    )
)*                        # repeat as long as there are matches on this line
.*/n?                     # remove the rest of the line

Que en Perl podría escribirse como:

$in =~ s/regex/$3/gmx;
$count = length $in;

Demo en línea

Esta expresión es similar a la solución a la pregunta 1 anterior, con algunas modificaciones para incluir X en los caracteres coincidentes en la primera búsqueda anticipada, envuelto con un cuantificador y contando el número de coincidencias del cuantificador.

Excepto por las coincidencias directas, esto es lo más cercano posible (código adicional sabio además de regex), y podría ser una respuesta aceptable a la pregunta 2.

Casos de prueba

Algunos casos de prueba y resultados para la solución anterior. Resultado que muestra la respuesta numérica (longitud de la cadena resultante) y entre paréntesis la cadena resultante después de la (s) sustitución (s).

Test #0:
--------------------
X
X
X

result: 1 (X)


Test #1:
--------------------
..X....
..X....
..X....

result: 1 (.)


Test #2:
--------------------
..X.X..
..X.X..
....X..

result: 1 (.)


Test #3:
--------------------
..X....
..X....
...X...

result: 0 ()


Test #4:
--------------------
..X....
...X...
..X....

result: 0 ()


Test #5:
--------------------
....X..
.X..X..
.X.....

result: 0 ()


Test #6:
--------------------
.X..X..
.X.X...
.X.X...

result: 1 (.)


Test #7:
--------------------
.X..X..
.X..X..
.X..X..

result: 2 (.X)


Test #8:
--------------------
XXX
XXX
XXX

result: 3 (XXX)


Test #9:
--------------------
X.X.X
XXXXX
XXXXX
.X.X.

result: 5 (XXXXX)


Test #10:
--------------------
1....X.......
2..X..X...X....
3X.X...X..X.....
4X....XXXXXX.....
5X..XXX...........
6.....X..........
7.........X....X
8..X......X....X....
9..X......X....X....X...
A....X.....
B.X..X..
C.....
XXX
XXX
XXX
.

result: 8 (3458.XXX)

Answer 2

Editar

Las siguientes soluciones tienen dos graves problemas:

1. No pueden hacer coincidir múltiples secuencias XXX comenzando en la misma línea, ya que la pos avanza demasiado.
2. La segunda solución es incorrecta: coincide con líneas consecutivas donde dos X están una encima de la otra. No necesariamente tiene que ser tres en una fila.

Por lo tanto, todas las votaciones ascendentes (y la recompensa) deberían ir a cualquiera de las m.buettner comprensivas de .NET de m.buettner o a la fascinante respuesta PCRE del propio .

Respuesta original

Esta es una respuesta usando la incrustación del código Perl en expresiones regulares. Como una expresión regular de Perl puede usar código para afirmar condiciones arbitrarias dentro de expresiones regulares o expresiones regulares parciales, no están limitadas a emparejar lenguajes regulares o lenguajes libres de contexto, pero pueden hacer coincidir algunas partes de idiomas más arriba en la jerarquía de Chomsky.

El idioma que desea emparejar se puede describir en términos de expresiones regulares como

^ .{n} X .*/n
  .{n} X .*/n
  .{n} X

donde n es un número. Esto es tan complejo como hacer coincidir el lenguaje a ⁿ b ⁿ c ⁿ , que es el ejemplo canónico para un lenguaje contextual.

Podemos hacer coincidir la primera línea fácilmente y usar algún código Perl para emitir la expresión regular para las otras líneas:

    /^ (.*?) X
       (?: .*/n (??{"." x length($1)}) X){2}
    /mx

¡Eso fue corto! ¿Qué hace?

• ^ (.*?) X Anclas ^ (.*?) X al comienzo de una línea, coincide con el menor número posible de caracteres no nuevos y luego con la X Recordamos la línea hasta la X como grupo de captura $1 .

• Repetimos un grupo dos veces que coincide con el resto de la línea, una nueva línea, y luego inyecta una expresión regular que coincide con una cadena de la misma longitud de $1 . Después de eso, debe haber una X

Esta expresión regular ahora coincidirá con cada cadena que tenga tres X encima de la otra.

Si queremos extraer todas esas secuencias, tendremos que ser ingeniosos. Porque las secuencias pueden superponerse, por ejemplo

.X
XX
XX
X.

la posición donde comienza la próxima partida no debe continuar más allá de la primera X Podemos hacer esto a través de un lookbehind y un lookahead. Perl solo admite lookbehind de longitud constante, pero tiene el escape /K que proporciona una semántica similar. Así

/^ (.*?) /K X
   (?=( (?: .*/n (??{"."x length($1)}) X ){2} ))
/gmx

coincidirá con cada secuencia de tres X verticales. Tiempo de prueba:

$ perl -E''my$_=join"",<>; say "===/n$1X$2" while /^(.*?)/KX(?=((?:.*/n(??{"."x length($1)})X){2}))/gmx'' <<''END''
....X.......
..X..X...X....
X.X...X..X.....
X....XXXXXX.....
X..XXX...........
.....X..........
..............X
..X...........X....
..X...........X....X...
....X.....
END
===
..X..X...X....
X.X...X..X.....
X....XXXXX
===
X.X...X..X.....
X....XXXXXX.....
X
===
X....XXXXXX.....
X..XXX...........
.....X
===
..............X
..X...........X....
..X...........X

Nota: esto se basa en funciones de expresiones regulares experimentales que están disponibles desde al menos Perl 5, v10 en adelante. El código fue probado con un v16 perl.

Solución sin código incrustado

Echemos un vistazo a las líneas

...X.../n
...X../n

Queremos afirmar que la parte principal de cada línea es de la misma longitud. Podemos hacerlo por recursión con el caso base X.*/n :

(X.*/n|.(?-1).)X

Si anclamos eso al comienzo de una línea, podemos unir dos X verticales. Para hacer coincidir más de dos líneas, tenemos que hacer la recursión en una búsqueda anticipada y luego avanzar la posición del partido a la siguiente línea, y repetir. Para esto, simplemente coincidimos .*/n

Esto da como resultado la siguiente expresión regular que puede hacer coincidir una cadena con tres X es verticales:

/ ^
  (?:
    (?=( X.*/n | .(?-1). ) X)
    .*/n # go to next line
  ){2}
/mx

Pero esto no es lo suficientemente bueno, ya que queremos unir todas esas secuencias. Para hacer esto, básicamente ponemos toda la expresión regular en una búsqueda anticipada. El motor regex se asegura de avanzar en la posición cada vez para producir una nueva coincidencia.

/ ^
  (?=
    (
      (?:
          (?= (X.*/n | .(?-1). ) X)
          .*/n # go to next line
      ){2}
      .* # include next line in $1
    )
  )
/mx

Tiempo de prueba:

$ perl -E''my$_=join"",<>; say "===/n$1" while /^(?=((?:(?=(X.*/n|.(?-1).)X).*/n){2}.*))/gmx'' <<''END''
....X.......
..X..X...X....
X.X...X..X.....
X....XXXXXX.....
X..XXX...........
.....X..........
..............X
..X...........X....
..X...........X....X...
....X.....
END
===
..X..X...X....
X.X...X..X.....
X....XXXXXX.....
===
X.X...X..X.....
X....XXXXXX.....
X..XXX...........
===
X....XXXXXX.....
X..XXX...........
.....X..........
===
..............X
..X...........X....
..X...........X....X...

Así que esto funciona tan bien como la solución con código incrustado, es decir, hace coincidir cada grupo de líneas con X verticales, no cada grupo de X es. (En realidad, esta solución me parece más frágil que el código incrustado)

Answer 3

Primero que nada: pregunta brillante. Creo que puede ser muy instructivo intentar llevar los motores regex a sus límites.

La solución básica de .NET

Ustedes dijeron en los comentarios que sería fácil con .NET, pero como aún no hay respuesta, pensé en escribir uno.

Puede resolver las preguntas 1 y 2. utilizando los grupos de equilibrio y la mirada de longitud variable de .NET. La mayor parte del trabajo lo realizan los grupos de equilibrio, pero la apariencia de longitud variable es crucial para poder detectar múltiples coincidencias comenzando en la misma línea.

De todos modos, aquí está el patrón:

(?<=                  # lookbehind counts position of X into stack
  ^(?:(?<a>).)*       # push an empty capture on the ''a'' stack for each character
                      # in front of X
)                     # end of lookbehind

X                     # match X

(?=.*/n               # lookahead checks that there are two more Xs right below
  (?:(?<-a>)(?<b>).)* # while we can pop an element from stack ''a'', push an
                      # element onto ''b'' and consume a character
  (?(a)(?!))          # make sure that stack ''a'' is empty
  X.*/n               # match X and the rest of the line
  (?:(?<-b>).)*       # while we can pop an element from stack ''b'', and consume
                      # a character
  (?(b)(?!))          # make sure that stack ''b'' is empty
  X                   # match a final X
)                     # end of lookahead

Este patrón se debe usar con RegexOptions.Multiline para que ^ coincida con los comienzos de las líneas (y obviamente con RegexOptions.IgnorePatternWhitespace para que funcione el modo freespacing).

Aquí hay algunos comentarios adicionales:

Al poner todo, excepto la X inicial en miradas, no tenemos problemas con la superposición de las coincidencias o incluso las coincidencias que comienzan en la misma línea. Sin embargo, el lookbehind tiene que ser de longitud variable, lo que ciertamente limita cualquier solución de este tipo a .NET.

El resto depende de una buena comprensión de los grupos de equilibrio. No voy a entrar aquí en detalle aquí, porque hace respuestas bastante largas en sí mismo . (consulte MSDN y esta publicación en el blog para obtener más información)

El lookbehind simplemente coincide con ^.* , Así que todo hasta el comienzo de la línea, pero para cada cosa . empujamos una captura vacía en la pila a , contando así la posición de nuestra X como el tamaño de la pila.

Luego, después de consumir el resto de la línea en la búsqueda anticipada, coincidimos nuevamente solo .* , Pero antes de consumir cada uno . , sacamos un elemento de la pila a (que conduce a la falla, una vez que a está vacío) y colocamos una captura vacía en b (para que no olvidemos cuántos caracteres tiene que haber para la tercera línea).

Para asegurarnos de que realmente vaciamos toda la pila, usamos (?(a)(?!)) . Este es un patrón condicional, que intenta hacer coincidir (?!) Si la pila a no está vacía (y de lo contrario simplemente se omite). Y (?!) Es un lookahead negativo vacío, que siempre falla. Por lo tanto, esto simplemente codifica, "¿no está vacío? Falla; de lo contrario, continúa".

Ahora que sabemos que hemos consumido exactamente la cantidad correcta de caracteres en la nueva línea, tratamos de hacer coincidir una X y el resto de la línea. Luego repetimos el mismo proceso nuevamente con la pila b . Ahora no hay necesidad de presionar sobre ninguna pila nueva, porque si esto funciona, hemos terminado. Comprobamos que b está vacío después de esto, y hacemos coincidir una tercera X

Finalmente, una nota al margen de la optimización: este patrón aún funciona si todas las repeticiones están envueltas en grupos atómicos (¡emulando así cuantificadores posesivos, que no son compatibles con .NET)! Esto ahorraría mucho retroceso. Además, si ponemos al menos los cuantificadores de acumulación de pila en grupos atómicos, podemos deshacernos de ambos (?(...)(?!)) controles (ya que estos solo son necesarios para los casos, donde la repetición anterior tuvo que volver hacia atrás).

La solución .NET completa

(Solo los más valientes aventureros deberían seguirme a la cueva realmente oscura a la que estoy a punto de descender ...)

Como se discutió en los comentarios, esta solución tiene un inconveniente: cuenta coincidencias superpuestas. P.ej

..X..
..X..
..X..
..X..

Da dos coincidencias, una en la primera y una en la segunda línea. Nos gustaría evitar esto e informar solo una coincidencia (o dos si hay de 6 a 8 X s y tres si hay de 9 a 11 X s, y así sucesivamente). Además, queremos reportar las coincidencias en el 1 °, 4 °, 7 °, ... X

Podemos ajustar el patrón anterior para permitir esta solución al requerir que la primera X esté precedida por un múltiplo entero de otras 3 X que cumplan con nuestros requisitos. La idea básica de comprobar esto utiliza la misma manipulación de pila que antes (excepto que cambiamos las cosas entre 3 pilas de modo que después de encontrar tres X s terminamos donde comenzamos). Para hacer esto, tenemos que jugar un poco con el lookbehind.

Sin embargo, hay una trampa. El lookbehind de longitud variable de .NET utiliza otra característica exclusiva de .NET, RightToLeftMode , en la que el patrón se lee (y combina) de derecha a izquierda. Por lo general, no es necesario que nos moleste, pero cuando combinamos esto con grupos de equilibrio, podemos encontrar sorpresas desagradables . En particular, al considerar cómo evolucionan nuestras pilas de captura, debemos construir (y leer) la expresión de derecha a izquierda (o de abajo hacia arriba) también.

Por lo tanto, cuando lea la siguiente expresión (y mis anotaciones), comience por el final del aspecto más externo (tendrá que desplazarse un poco), es decir, justo antes de la única X nivel superior; luego lea todo el camino hasta la cima. Y luego continúa después de la mirada detrás.

(?<=                  
  # note that the lookbehind below does NOT affect the state of stack ''a''!
  # in fact, negative lookarounds can never change any capturing state.
  # this is because they have to fail for the engine to continue matching.
  # and if they fail, the engine needs to backtrack out of them, in which
  # case the previous capturing state will be restored.
  (?<!                # if we get here, there is another X on top of the last
                      # one in the loop, and the pattern fails
    ^                 # make sure we reached the beginning of the line
    (?(a)(?!))        # make sure that stack ''a'' is empty
    (?:(?<-a>).)*     # while we can pop an element from stack ''a'', and consume
                      # a character
    X.*/n             # consume the next line and a potential X
  )
  # at this point we know that there are less than 3 Xs in the same column
  # above this position. but there might still be one or two more. these
  # are the cases we now have to eliminate, and we use a nested negative
  # lookbehind for this. the lookbehind simply checks the next row and
  # asserts that there is no further X in the same column.
  # this, together with the loop, below means that the X we are going to match
  # is either the topmost in its column or preceded by an integer multiple of 3
  # Xs - exactly what we are looking for.
  (?:

    # at this point we''ve advanced the lookbehind''s "cursor" by exactly 3 Xs
    # in the same column, AND we''ve restored the same amount of captures on
    # stack ''a'', so we''re left in exactly the same state as before and can
    # potentially match another 3 Xs upwards this way.
    # the fact that stack ''a'' is unaffected by a full iteration of this loop is
    # also crucial for the later (lookahead) part to work regardless of the
    # amount of Xs we''ve looked at here.

    ^                 # make sure we reached the beginning of the line
    (?(c)(?!))        # make sure that stack ''a'' is empty
    (?:(?<-c>)(?<a>).)* # while we can pop an element from stack ''c'', push an
                      # element onto ''a'' and consume a character
    X.*/n             # consume the next line and a potential X
    (?(b)(?!))        # make sure that stack ''b'' is empty
    (?:(?<-b>)(?<c>).)* # while we can pop an element from stack ''b'', push an
                      # element onto ''c'' and consume a character
    X.*/n             # consume the next line and a potential X
    (?(a)(?!))        # make sure that stack ''a'' is empty
    (?:(?<-a>)(?<b>).)* # while we can pop an element from stack ''a'', push an
                      # element onto ''b'' and consume a character
    X.*/n             # consume the next line and a potential X
  )*                  # this non-capturing group will match exactly 3 leading
                      # Xs in the same column. we repeat this group 0 or more
                      # times to match an integer-multiple of 3 occurrences.
  ^                   # make sure we reached the beginning of the line
  (?:(?<a>).)*        # push an empty capture on the ''a'' stack for each
                      # character in front of X
)                     # end of lookbehind (or rather beginning)

# the rest is the same as before    

X                     # match X
(?=.*/n               # lookahead checks that there are two more Xs right below
  (?:(?<-a>)(?<b>).)* # while we can pop an element from stack ''a'', push an
                      # element onto ''b'' and consume a character
  (?(a)(?!))          # make sure that stack ''a'' is empty
  X.*/n               # match X and the rest of the line
  (?:(?<-b>).)*       # while we can pop an element from stack ''b'', and consume
                      # a character
  (?(b)(?!))          # make sure that stack ''b'' is empty
  X                   # match a final X
)                     # end of lookahead

Demostración de trabajo en RegexHero.net.

Intervine todas las explicaciones con el patrón esta vez. Entonces, si lees el patrón de la manera que te recomendé más arriba, obtienes la explicación correcta cuando la necesitas ...

Ahora que era un infierno de una bestia. Pero cumple con la especificación completa ahora y muestra cuán poderoso realmente es el sabor regex de .NET. Y, aunque esto parece bastante horrible, creo que (una vez que se da cuenta de lo que es de derecha a izquierda) es mucho más fácil de entender que una solución comparable con PCRE (utilizando recursividad o de otro tipo).

Como mencionó Kobi en un comentario a continuación, esto podría acortarse un poco, si acepta que sus resultados se encuentran en múltiples capturas de una sola coincidencia (por ejemplo, si tiene una columna de 7 X s solo obtiene una coincidencia, pero con 2 capturas en un cierto grupo). Puede hacer esto repitiendo la parte principal (mirar hacia adelante) 1 o más veces y capturar la X inicial (sin embargo, ponga todo en un vistazo). Entonces la mirada hacia atrás no necesita contar triples de X s, pero solo tiene que verificar que no haya una X principal. Esto probablemente reduciría el tamaño del patrón a la mitad.

La solución PCRE parcial

(Si el más valiente de los aventureros me siguió hasta la última solución, probablemente me quedaré solo con locos en el próximo viaje ...)

Para probar lo que acabo de decir acerca de cómo la solución anterior se compara con PCRE, veamos cómo podemos resolver remotamente el problema completo en PCRE. Tendremos que trabajar un poco más duro sin tener que mirar hacia atrás y balancear grupos de longitud variable.

Qtax (el OP) brindó una solución brillante a su primera pregunta (verificando si la cadena contiene cualquier columna X ) usando grupos autorreferenciales para contar. Esta es una solución muy elegante y compacta. Pero debido a que cada partida va desde el comienzo de la línea hasta la X que inicia la columna, y las coincidencias no se pueden superponer, no podemos obtener varias coincidencias por línea. Podríamos tratar de poner todo en un primer plano (para que nada coincida), pero dos coincidencias de ancho cero tampoco comenzarán nunca en la misma posición, por lo que todavía obtendremos una sola coincidencia por cada línea candidata.

Sin embargo, es posible resolver al menos la primera parte de la pregunta 2 con PCRE: cuente el número de columnas que comienzan en cada línea (y, por tanto, a la cantidad total de X columnas). Dado que no podemos obtener este conteo en forma de coincidencias individuales (consulte el párrafo anterior), y no podemos obtener este conteo en forma de grupos individuales o capturas (ya que PCRE proporciona solo un número fijo y finito de capturas, en comparación con .NET ) Lo que podemos hacer en cambio es codificar el número de columnas en las coincidencias.

Aquí se muestra cómo: para cada línea verificamos si hay una columna comenzando. Si es así, incluimos un personaje en un cierto grupo de captura. Luego, antes de informar una coincidencia exitosa, tratamos de encontrar tantas columnas adicionales como sea posible, para cada una agregando un personaje a ese grupo en particular. Al hacer esto, codificamos el número de columnas que comienzan en cada línea en la longitud de esa captura en particular.

En realidad, darse cuenta de este concepto en una expresión regular es mucho más complicado de lo que parece (y suena bastante complicado). De todos modos, aquí está:

^                        
(?:(?|
  (?(5)(?![/s/S]*+/5))      
  (?!(?!)()()) 
  (?=
    (?:
      .                  
      (?=                
        .*+/n            
        ( /3? . )   
        .*+/n        
        ( /4? . )    
      )
    )*?              
    X .*+/n          
    /3               
    X .*+/n          
    /4               
  )
  ()
|
  (?(5)(?=[/s/S]*+/5)|(?!))
  (?:
    .
    (?=
      .*+/n
      ( /1? .)
      .*+/n
      ( /2? .)
    )
  )+?
  (?=
    (?<=X).*+/n
    (/1)         
    (?<=X).*+/n
    (/2)         
    (?<=X)     
  )
  (?=
    ([/s/S])   
    [/s/S]*
    ([/s/S] (?(6)/6))
  )
){2})+

(En realidad, es un poco más fácil que eso, consulte la respuesta de Qtax sobre cómo simplificar este enfoque. De todos modos, dejaré este enfoque por razones académicas, ya que se pueden aprender algunas técnicas muy avanzadas e interesantes; vea el resumen en fin.)

Sí, no hay anotaciones. Pensé que nadie los leería de todos modos, así que trataré de dividir esta expresión en partes (iré por un enfoque de arriba hacia abajo).

Así que veamos la capa exterior de la cebolla del infierno:

^                        
(?:(?|
  checkForNextColumn
|
  countAndAdvance
){2})+

Entonces nuestros partidos están nuevamente anclados al comienzo de las líneas. Entonces tenemos un (?:...{2})+ que significa un número par de repeticiones de algo. Y ese algo es una alternancia de dos subpatrones. Estos subpatrones representan los pasos que mencioné anteriormente. El primero comprueba que hay otra columna que comienza en la línea actual, la segunda registra un conteo y prepara el estado del motor para otra aplicación del primer subpatrón. Por lo tanto, se le da control al segundo patrón: el primero solo verifica otra columna usando una anticipación y, por lo tanto, tiene un patrón de ancho cero. Esta es la razón por la que no puedo simplemente envolver todo en + pero tengo que hacer lo {2})+ lo contrario, el componente de ancho cero se probaría solo una vez; esa es una optimización necesaria aplicada por casi todos los motores para evitar bucles infinitos con patrones como (a*)+ .

Hay uno más (detalle muy importante): utilicé (?|...) para la alternancia. En este tipo de agrupamiento, cada alternativa comienza con el mismo número de grupo. Por lo tanto, en /(?|(a)|(b))/ tanto a como b se pueden capturar en el grupo 1 . Este es el truco crucial que permite la "comunicación" entre subpatrones, ya que pueden modificar los mismos grupos.

De todos modos ... entonces tenemos estos dos subpatrones. Queremos asegurarnos de que el control realmente se alterna entre ellos. Para que cada grupo falle si fue el último que coincidió. Hacemos esto al envolver el patrón en alguna magia de agrupamiento y referencia:

^(?:(?|
  (?(5)(?![/s/S]*+/5))       # if group 5 has matched before make sure that
                             # it didn''t match empty
  checkForNextColumn         # contains 4 capturing groups
  ()                         # this is group 5, match empty
|
  (?(5)(?=[/s/S]*+/5)|(?!))  # make sure that group 5 is defined and that it
                             # matched empty
  advanceEngineState         # contains 4 capturing groups
  (?=
    ([/s/S])                 # this is group 5, match non-empty
    [/s/S]*                  # advance to the end very end of the string
    ([/s/S] (?(6)/6))             # add a character from the end of the string to
                             # group 6
  )
){2})+

Entonces, al final de cada alternativa, invalidaremos la condición de esta alternativa para incluso comenzar a emparejar. Al final de la segunda alternativa también incluiremos un personaje en el grupo 6 , usando la técnica descrita por Qtax. Este es el paso de contar. Es decir, el grupo 6 contendrá tantos caracteres como columnas comenzando en la línea actual.

Ahora, checkForNextColumn realmente solo será la solución de Qtax dentro de un futuro. Sin embargo, necesita una modificación más y, para justificar esto, examinaremos primero el advanceEngineState avanzado del advanceEngineState .

Pensemos en cómo quisiéramos modificar el estado, para que la solución de Qtax coincida con una segunda columna en una fila. Digamos que tenemos entrada

..X..X..
..X..X..
..X..X..

y queremos encontrar la segunda columna. Esto podría lograrse iniciando el emparejamiento desde la posición justo después de la primera X y teniendo los grupos /1 y /2 ya inicializados a los primeros tres caracteres (... ..X ) de las filas 2 y 3, respectivamente (en lugar de estar vacíos) )

Ahora intentemos hacer esto: haga coincidir todo hasta e incluyendo la siguiente X que comience una columna, luego llene dos grupos con los prefijos de línea correspondientes para usar en el patrón checkForNextColumn . De nuevo, esto es más o menos el patrón de Qtax, excepto que contamos la X (en lugar de detenernos justo antes) y que necesitamos agregar la captura en un grupo separado. Así que aquí está advanceEngineState :

(?:
  .
  (?=
    .*+/n
    ( /1? .)
    .*+/n
    ( /2? .)
  )
)+?
(?=
  (?<=X) .*+/n
  (/1)        
  (?<=X) .*+/n
  (/2)        
  (?<=X)
)

Fíjese cómo di la vuelta a las X en lookbehinds, para ir más allá de un personaje y cómo copio efectivamente los contenidos finales de /1 en /3 y los de /2 en /4 .

Entonces, si ahora usamos la solución de checkForNextColumn como checkForNextColumn en una búsqueda checkForNextColumn , usando los grupos /3 y /4 lugar de /1 y /2 , deberíamos estar listos.

¿Pero cómo hacemos esos grupos /3 y /4 lugar de /1 y /2 ? Podríamos comenzar el patrón con ()() , que siempre coincidiría, sin afectar el cursor del motor, pero aumentaríamos el conteo del grupo por 2. Sin embargo, esto es problemático: esto restablece los grupos 1 y 2 a cadenas vacías, que si encontramos una segunda columna, advanceEngineState estará en un estado inconsistente (ya que la posición global del motor se ha avanzado, pero los grupos de conteo son cero nuevamente). Por lo tanto, queremos que esos dos grupos sigan el patrón, pero sin afectar lo que están capturando actualmente. Podemos hacer esto utilizando algo que ya mencioné con las soluciones .NET: los grupos en las versiones negativas no afectan los contenidos capturados (porque el motor necesita dar marcha atrás para continuar). Por lo tanto, podemos usar (?!(?!)()()) (Un lookahead negativo que nunca puede hacer que el patrón falle) para incluir dos conjuntos de paréntesis en nuestro patrón, que nunca se utilizan. Esto nos permite trabajar con los grupos 3 y 4 en nuestro primer subpatrón, mientras se mantienen intactos los grupos 1 y 2 para los segundos subpatrones en la siguiente iteración. In conclusion this is checkForNextColumn :

(?!(?!)()()) 
(?=
  (?:
    .                  
    (?=                
      .*+/n            
      ( /3? . )   
      .*+/n        
      ( /4? . )    
    )
  )*?              
  X .*+/n          
  /3               
  X .*+/n          
  /4               
)

Which, for the most part actually looks really familiar.

So this is it. Running this against some input will give us a group 6 which contains one capture for each line that has a column starting - and the capture''s length will tell us how many columns started there.

Yes, it really works (live demo).

Note that this (like the basic .NET solution) will overcount columns that are more than 3 X s long. I suppose it is possible to correct this count with lookaheads (in a similar way to the lookbehind of the full .NET solution), but this is left as an exercise to the reader.

It''s a bit unfortunate that the base problem of this solution is already very convoluted and bloats the solution (75% of the lines are mostly just copies of Qtax''s solution). Because the surrounding framework has some really interesting techniques and lessons:

• We can have multiple subpatterns that accomplish specific matching/counting tasks, and have them "communicate" through mutual capturing groups, by putting them in a (?|...) alternation and looping over them.
• We can force zero-width alternatives to be carried out over and over again by wrapping them in a finite quantifier like {2} before putting everything into + .
• Group numbers can be skipped in one subpattern (without affecting the captured contents) by putting them into a never-failing negative lookahead like (?!(?!)()) .
• Control can be passed back and forth between subpatterns by capturing something or nothing in a certain group that is checked upon entering the alternation.

This allows for some very powerful computations (I''ve seen claims that PCRE is in fact Turing-complete) - although this is certainly the wrong approach for productive use. But still trying to understand (and come up) with such solutions can be a very challenging and somehow rewarding exercise in problem solving.

Answer 4

If you want to find a single "vertical" pattern, here''s a solution. If you want to also match a "horizontal" pattern, try doing it with a separate match, perhaps checking for overlapping match positions. Remember that the computer has not idea what a line is. It''s an arbitrary thing made up by humans. The string is just a one-dimensional sequence where we denote some character(s) to be a line ending.

#!/usr/local/perls/perl-5.18.0/bin/perl
use v5.10;

my $pattern = qr/XXX/p;

my $string =<<''HERE'';
....X.......
..X..X...X....
X.X...X..X.....
X....XXXXXX.....
X..XXX...........
.....X..........
..............X
..X...........X....
..X...........X....X...
....X.....
HERE


$transposed = transpose_string( $string );

open my $tfh, ''<'', / $transposed;
while( <$tfh> ) {
    while( /$pattern/g ) {
        my $pos = pos() - length( ${^MATCH} );
        push @found, { row => $pos, col => $. - 1 };
        pos = $pos + 1; # for overlapping matches
        }
    }

# row and col are 0 based
print Dumper( /@found ); use Data::Dumper;

sub transpose_string {
    my( $string ) = @_;

    open my $sfh, ''<'', / $string;

    my @transposed;
    while( <$sfh> ) {
        state $row = 0;
        chomp;
        my @chars = split //;

        while( my( $col, $char ) = each @chars ) {
            $transposed[$col][$row] = $char;
            }

        $row++;
        }

    my @line_end_positions = ( 0 );
    foreach my $col ( 0 .. $#transposed ) {
        $transposed .= join '''', @{ $transposed[$col] };
        $transposed .= "/n";
        }
    close $sfh;

    return $transposed;
    }

Answer 5

My approach to match vertical patterns using PHP.

First of all, let''s rotate our input by 90°:

// assuming $input contains your string
$input = explode("/n", $input);
$rotated = array();
foreach ($input as $line)
{
    $l = strlen($line);
    for ($i = 0; $i < $l; $i++)
    {
        if (isset($rotated[$i]))
            $rotated[$i] .= $line[$i];
        else
            $rotated[$i] = $line[$i];
    }
}
$rotated = implode("/n", $rotated);

This results in

..XXX.....
..........
.XX....XX.
....X.....
X...X....X
.X.XXX....
..XX......
...X......
...X......
.XXX......
...X.....
.........
........
........
....XXX
.....
...
..
..
X
.
.
.

Now this might look strange, but actually brings us closer since we can now simply preg_match_all() over it:

if (preg_match_all(''//bXXX/b/'', $rotated, $m))
var_dump($m[0]);

et voila:

array(4) {
  [0] =>
  string(3) "XXX"
  [1] =>
  string(3) "XXX"
  [2] =>
  string(3) "XXX"
  [3] =>
  string(3) "XXX"
}

If you also want to match the same horizontal pattern, simply use the same expression on the non-rotated input.

Answer 6

You could rotate the image, and then search for XXX .