El videojuego Minecraft se trata de colocar y eliminar diferentes tipos de bloques en la red de enteros 3D que conforma el mundo virtual. Cada punto de la red puede contener exactamente un bloque o estar vacío (un bloque " aéreo " oficialmente). En este desafío, solo nos ocuparemos de un plano vertical 2D del mundo 3D y un tipo de bloque: obsidiana .

Cuando la obsidiana forma el contorno de un rectángulo vacío en un plano vertical, se puede crear un portal inferior . El rectángulo vacío puede ser de cualquier tamaño desde 2 unidades de ancho por 3 unidades de alto hasta 22 unidades de ancho por 22 unidades de alto. Las esquinas del rectángulo no necesitan estar bordeadas en obsidiana, solo los lados.

Por ejemplo, supongamos que Xes obsidiana y .es vacío: (los números son solo para fines de identificación y también están vacíos).

...................................
..XXXX....XXXX....XXXXXXXXX........
..X..X...X....X..X.........X..XXXX.
..X.1X...X.2..X..X...3...X.X..X....
..X..X...X....XXXX.........X..X.6X.
..XXXX....XXXX...XXXXXXXXXXX..X..X.
.............X.4.X....X.5.X...XXXX.
.............X...X....X...X........
..............XXX......XXX.........
...................................

Esta cuadrícula contiene 3 portales válidos:

• El Portal 1 es de 2 por 3 unidades, totalmente vacío y bordeado en obsidiana. Por lo tanto, es válido.
• Portal 2 es de 4 por 3, totalmente vacío y bordeado en obsidiana. Por lo tanto, es válido.
• Portal 3 no está totalmente vacío. Por lo tanto, no es válido.
• Portal 4 es 3 por 3, totalmente vacío y bordeado en obsidiana. Por lo tanto, es válido.
• Portal 5 es de 3 por 2 unidades, que es demasiado pequeño. Por lo tanto, no es válido.
• Al portal 6 le falta una parte de la frontera. Por lo tanto, no es válido.

Desafío

Escriba un programa o función que tome en estas representaciones de cadenas de cuadrículas de obsidiana y vacío, e imprima o devuelva el número de portales inferiores válidos presentes.

• La entrada puede ser de stdin o archivo o argumento de función.

• Puede suponer que la entrada siempre está bien formada, es decir, una cuadrícula de texto perfectamente rectangular, de al menos 1 carácter de ancho y alto, que solo contiene Xy .. Opcionalmente, puede suponer que hay una nueva línea final después de la última fila.

• Si lo desea, puede usar cualquiera de los dos caracteres ASCII imprimibles distintos en lugar de Xy ..

• La obsidiana puede estar en los bordes de la cuadrícula. Cualquier cosa más allá de las fronteras se considera vacía.

Ejemplo de entrada: la salida debe ser 4:

................................................................
...................................XXXXXXXXXXXXXXXXXXXXXXXXX....
..XXXX....XXXX....XXXXXXXXX........X.......................X....
..X..X...X....X..X.........X..XXXX.X.......................X....
..X..X...X....X..X.......X.X..X....X.......................X....
..X..X...X....XXXX.........X..X..X..XXXXXXXXXXXXXXXXXXXXXXXX....
..XXXX....XXXX...XXXXXXXXXXX..X..X.X......................X..XXX
.............X...X....X...X...XXXX.X......................X..X..
.............X...X....X...X........X......................X..X..
..............XXX......XXX........XXXXXXXXXXXXXXXXXXXXXXXX...X..
..................................XX.........................XXX

Puntuación

El envío con la menor cantidad de bytes gana.

Perl, 81 86

Usando más de una expresión regular.

#!perl -p0
$_=map{/.
/;$n="@-"-++$.;/(?=X{$.}..{$n}(X\.{$.}X.{$n}){3,22}.X{$.})/gs}($_)x21

La expresión regular para un ancho específico de un portal es mucho más simple que una genérica: X{$m}..{$n}(X\.{$m}X.{$n}){3,22}.X{$m}dónde mestá el ancho del portal y cuál nes total width - 1 - m. La expresión regular se debe poner en una aserción directa de ancho cero (?=...)porque las coincidencias pueden superponerse. Luego itero 21 veces sobre esta configuración de expresión regular $ny $.. "@-"evalúa la posición de inicio de la última coincidencia ( /.\n/) que resulta ser el ancho total: 1. $.se usa como la otra variable a la que se inicializa 1cuando se usa con -p0.

Regex (sabor .NET), 182 181 145 132 126 114 104 100 98 97 96 bytes

Reconocimiento de patrones de arte 2D ASCII? Suena como un trabajo para expresiones regulares! (No lo hace)

Sé que esto va a desatar discusiones interminables sobre si las presentaciones de expresiones regulares son programas válidos o no, pero dudo que esto supere a APL o CJam de todos modos, por lo que no veo ningún daño. (Una vez dicho esto, se hacen pasar nuestra prueba recalcitrante para "¿Qué es un lenguaje de programación?" .)

Esto toma la entrada como la cadena que debe coincidir, y el resultado es el número de coincidencias encontradas. Se usa _en lugar de ., porque tendría que escapar de este último. También requiere una nueva línea final.

(X(X){1,21})(?=\D+((?>(?<-2>_)+)_))(?=.((?!\7)(.)*
.*(X\3X|()\1.)(?=(?<-5>.)*(?(5)!)
)){4,23}\7)

Puede probarlo en vivo en RegexHero o RegexStorm ). Los partidos serán las filas superiores de obsidiana de los portales. Si puede encontrar un caso de prueba donde falla, ¡hágamelo saber!

¿Qué es esta hechicería?

La siguiente explicación supone una comprensión básica de los grupos de equilibrio de .NET . La esencia es que las capturas son pilas en .NET regex: cada nueva captura para el mismo nombre se inserta en la pila, pero también hay sintaxis para capturar capturas de esas pilas nuevamente, así como sintaxis para capturar capturas desde una pila y capturas de inserción en otro al mismo tiempo. Para una imagen más completa, puede echar un vistazo a mi respuesta en Stack Overflow que debe cubrir todos los detalles.

La idea básica es hacer coincidir un patrón como:

 X{n}..{m}
X_{n}X.{m} |
X_{n}X.{m} |  3 to 22 times
X_{n}X.{m} |
 X{n}..{m} 

Dónde nestá entre 2 y 22 (inclusive). Lo complicado es hacer que todos los nsy todos msean iguales. Como los caracteres reales no serán los mismos, no podemos usar una referencia inversa.

Tenga en cuenta que la expresión regular tiene que incluir nuevas líneas, que escribiré como \nen el siguiente.

(                     # Open capturing group 1. This will contain the top of a portal, which
                      # I can reuse later to match the bottom (being of the same length).
  X                   # Match a single X.
  (X){1,21}           # Match 1 to 21 X's, and push each separately on the <2> stack. Let's
                      # Call the number of X's captured N-1 (so N is the inner width of the
                      # portal).
)                     # End of group 1. This now contains N X's.
(?=                   # Start a lookahead. The purpose of this lookahead is to capture a 
                      # string of N underscores in group 2, so I can easily use this to match 
                      # the inside rows of the portal later on. I can be sure that such a 
                      # string can always be found for a valid portal (since it cannot have 0 
                      # inner height).
  \D+                 # Skip past a bunch of non-digits - i.e. *any* of the vaild characters
                      # of the input (_, X, \n). This to make sure I search for my N 
                      # underscores anywhere in the remainder of the input.
  (                   # Open capturing group 3. This will contain a portal row.
    (?>               # This is an atomic group. Once the engine hass successfully matched the
                      # contents of this group, it will not go back into the group and try to
                      # backtrack other possible matches for the subpattern.
      (?<-2>_)+       # Match underscores while popping from the <2> stack. This will match as
                      # many underscores as possible (but not more than N-1).
    )                 # End of the atomic group. There are two possible reasons for the
                      # subpattern stopping to match: either the <2> stack is empty, and we've
                      # matched N-1 underscores; or we've run out of underscores, in which 
                      # case we don't know how many underscores we matched (which is not 
                      # good).
    _                 # We simply try to match one more underscore. This ensures that we 
                      # stopped because the <2> stack was empty and that group 3 will contain
                      # exactly N underscores.
  )                   # End of group 3.
)                     # End of the lookahead. We've got what we want in group 2 now, but the
                      # regex engine's "cursor" is still at the end of the portal's top.
(?=                   # Start another lookahead. This ensures that there's actually a valid
                      # portal beneath the top. In theory, this doesn't need to be a 
                      # lookahead - I could just match the entire portal (including the lines
                      # it covers). But matches cannot overlap, so if there were multiple
                      # portals next to each other, this wouldn't return all of them. By 
                      # putting the remainder of the check in a lookahead the actual matches
                      # won't overlap (because the top cannot be shared by two portals).
  .                   # Match either _ or X. This is the character above the portal side.

  (                   # This group (4) is where the real magic happens. It's purpose is to to
                      # count the length of the rest of the current line. Then find a portal
                      # row in the next line, and ensure that it's the same distance from the
                      # end of the line. Rinse and repeat. The tricky thing is that this is a
                      # single loop which matches both inner portal rows, as well as the 
                      # bottom, while making sure that the bottom pattern comes last.

    (?!\7)            # We didn't have a group 7 yet... group 7 is further down the pattern.
                      # It will capture an empty string once the bottom row has been matched.
                      # While the bottom row has not been matched, and nothing has been
                      # captured, the backreference will fail, so the negative lookahead will
                      # pass. But once we have found the bottom row, the backreference will
                      # always match (since it's just an empty string) and so the lookahead
                      # will fail. This means, we cannot repeat group 4 any more after the
                      # bottom has been matched.
    (.)*              # Match all characters until the end of the line, and push each onto
                      # stack <5>.
    \n                # Match a newline to go to the next line.
    .*                # Match as many characters as necessary to search for the next portal
                      # row. This conditions afterwards will ensure that this backtracks to
                      # the right position (if one exists).
    (                 # This group (6) will match either an inner portal row, or the bottom
                      # of the portal.
      X\3X            # Match X, then N underscores, then X - a valid inner portal row.
    |                 # OR
      ()              # Capture an empty string into group 7 to prevent matching further rows.
      \1.             # Use the captured top to match the bottom and another character.
    )
    (?=               # This lookahead makes sure that the row was found at the same 
                      # horizontal position as the top, by checking that the remaining line
                      # is the same length.
      (?<-5>.)*       # Match characters while popping from the <5> stack.
      (?(5)!)\n       # Make sure we've hit end of the line, *and* the <5> stack is empty.
    )
  ){4,23}             # Repeat this 4 to 23 times, to ensure an admissible portal height.
                      # Note that this is one more than the allowed inner height, to account
                      # for the bottom row.
  \7                  # Now in the above repetition there is nothing requiring that we have
                      # actually matched any bottom row - it just ensured we didn't continue
                      # if we had found one. This backreference takes care of that. If no
                      # bottom row was found, nothing was captured into group 7 and this
                      # backreference fails. Otherwise, this backreference contains an empty
                      # string which always matches.
)

C #, 185 bytes

Aquí hay una función completa de C #, solo para hacer de esta una entrada válida. Es hora de que escriba un "intérprete" de línea de comandos para expresiones regulares .NET ...

static int f(string p){return System.Text.RegularExpressions.Regex.Matches(p,@"(X(X){1,21})(?=\D+((?>(?<-2>_)+)_))(?=.((?!\7)(.)*
.*(X\3X|()\1.)(?=(?<-5>.)*(?(5)!)
)){4,23}\7)").Count;}

Python, 219 bytes

def f(s):s=s.split();L=len;R=range;return L([r for r in R(L(s))for a in R(L(s[0]))for w in R(2,23)for h in R(3,min(L(s)+~r,23))if(s[r][a:a+w]==s[r-~h][a:a+w]==w*"X")*all(s[r-~k][a-1:a+w+1]=="X"+"."*w+"X"for k in R(h))])

Mejor que Java, pero vaya, los quintuples bucles anidados duelen. El for/inpodría ser ligeramente compresible usando %ssustitución, pero no ahorraría mucho.

Expandido:

def f(s):
  s=s.split()
  L=len
  R=range
  return L([r for r in R(L(s))
              for a in R(L(s[0]))
              for w in R(2,23)
              for h in R(3,min(L(s)+~r,23))
              if(s[r][a:a+w]==s[r-~h][a:a+w]==w*"X")* 
                 all(s[r-~k][a-1:a+w+1]=="X"+"."*w+"X"for k in R(h))])

Java, 304 bytes

Esto es mucho más largo que una expresión regular. Simplemente itera sobre cada cuadrado posible en la entrada. Si es un portal válido, incrementa un contador en 1. Luego devuelve el contador. Esto probablemente se pueda jugar mucho más. Cualquier sugerencia es bienvenida.

int a(String...a){a=a[0].split("\n");int b=0,c=0,d,e,f,g,h,i=a.length,j=a[0].length();for(;c<j;c++)for(d=0;d<i;d++)for(e=c+2;++e<j&e<c+24;)a:for(f=d+3;++f<i&f<d+24;){for(g=c;g<=e;g++)for(h=d;h<=f;h++){if(g==c|g==e&&h==d|h==f)continue;if((g==c|g==e|h==d|h==f)^a[h].charAt(g)>60)continue a;}b++;}return b;}

Sangrado:

int a(String...a){
    a=a[0].split("\n");
    int b=0,c=0,d,e,f,g,h,i=a.length,j=a[0].length();
    for(;c<j;c++)
        for(d=0;d<i;d++)
            for(e=c+2;++e<j&e<c+24;)
                a:for(f=d+3;++f<i&f<d+24;){
                    for(g=c;g<=e;g++)
                        for(h=d;h<=f;h++){
                            if(g==c|g==e&&h==d|h==f)
                                continue;
                            if((g==c|g==e|h==d|h==f)^a[h].charAt(g)>60)
                                continue a;
                        }
                    b++;
                }
    return b;
}

Programa completo:

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;

public class B {

    public static void main(String[] args) throws FileNotFoundException {
        String blocks = new BufferedReader(new FileReader(args[0])).lines().reduce((a,b)->a+"\n"+b).get();
        System.out.println(new B().a(blocks));
    }

    int a(String...a){
        a=a[0].split("\n");
        int b=0,c=0,d,e,f,g,h,i=a.length,j=a[0].length();
        for(;c<j;c++)
            for(d=0;d<i;d++)
                for(e=c+2;++e<j&e<c+24;)
                    a:for(f=d+3;++f<i&f<d+24;){
                        for(g=c;g<=e;g++)
                            for(h=d;h<=f;h++){
                                if(g==c|g==e&&h==d|h==f)
                                    continue;
                                if((g==c|g==e|h==d|h==f)^a[h].charAt(g)>60)
                                    continue a;
                            }
                        b++;
                    }
        return b;
    }

}