O videogame Minecraft é sobre colocar e remover diferentes tipos de blocos na rede inteira 3D que compõe o mundo virtual. Cada ponto de rede pode conter exatamente um bloco ou estar vazio (um bloco " aéreo " oficialmente). Neste desafio, nos preocuparemos apenas com um plano 2D vertical do mundo 3D e um tipo de bloco: obsidiana .

Quando a obsidiana forma o contorno de um retângulo vazio em um plano vertical, um portal inferior pode ser criado. O retângulo vazio pode ter qualquer tamanho, de 2 unidades de largura por 3 unidades de altura a 22 unidades de largura por 22 unidades de altura. Os cantos do retângulo não precisam ser delimitados em obsidiana, apenas os lados.

Por exemplo, suponha que Xseja obsidiana e .vazia: (os números são apenas para fins de identificação e também estão vazios.)

...................................
..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 grade contém 3 portais válidos:

• O Portal 1 é de 2 por 3 unidades, totalmente vazio e delimitado em obsidiana. Portanto, é válido.
• O Portal 2 é 4 por 3, totalmente vazio e delimitado em obsidiana. Portanto, é válido.
• O Portal 3 não está totalmente vazio. Portanto, é inválido.
• O portal 4 é 3 por 3, totalmente vazio e delimitado em obsidiana. Portanto, é válido.
• O Portal 5 é de 3 por 2 unidades, o que é muito pequeno. Portanto, é inválido.
• O portal 6 está faltando uma parte da borda. Portanto, é inválido.

Desafio

Escreva um programa ou função que capte essas representações de cadeias de grades de obsidiana e de vazio e imprima ou retorne o número de portais inferiores válidos presentes.

• A entrada pode ser de stdin ou arquivo ou argumento de função.

• Você pode assumir que a entrada está sempre bem formada - ou seja, uma grade perfeitamente retangular de texto, com pelo menos 1 caractere de largura e altura, contendo apenas Xe .. Opcionalmente, você pode assumir que há uma nova linha à direita após a última linha.

• Se desejar, você pode usar dois caracteres ASCII imprimíveis distintos no lugar de Xe ..

• Obsidiana pode estar nas bordas da grade. Qualquer coisa além das fronteiras é considerada vazia.

Exemplo de entrada - a saída deve 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

Pontuação

O envio com o menor número de bytes vence.

Perl, 81 86

Usando mais de um regexp.

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

A regexp para uma largura específica de um portal é muito mais simples que uma genérica: X{$m}..{$n}(X\.{$m}X.{$n}){3,22}.X{$m}onde mestá a largura do portal e nestá total width - 1 - m. A regexp deve ser colocada em uma declaração de largura zero, (?=...)porque as correspondências podem se sobrepor. Então eu itero 21 vezes sobre essa configuração de regexp $ne $.. "@-"avalia a posição inicial da última correspondência ( /.\n/) que é a largura total - 1. $.é usada como a outra variável conforme inicializada 1quando usada com -p0.

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

Reconhecimento de padrões de arte ASCII 2D? Parece um trabalho para regex! (Não.)

Sei que isso vai desencadear discussões intermináveis ​​novamente sobre se os envios de regex são programas válidos ou não, mas duvido que isso possa superar o APL ou o CJam de qualquer maneira, para que não haja nenhum dano. (Dito isto, eles fazem passar o nosso teste die-hard para "O que é uma linguagem de programação?" .)

Isso leva a entrada como a sequência a ser correspondida e o resultado é o número de correspondências encontradas. Ele usa _no lugar de ., porque eu teria que escapar do último. Também requer uma nova linha à direita.

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

Você pode testá-lo ao vivo no RegexHero ou RegexStorm ). As correspondências serão as principais linhas de obsidiana dos portais. Se você encontrar um caso de teste em que ele falhe, entre em contato!

O que é essa feitiçaria?

A explicação a seguir pressupõe um entendimento básico dos grupos de balanceamento do .NET . A essência é que as capturas são pilhas no regex .NET - toda nova captura com o mesmo nome é inserida na pilha, mas também há sintaxe para capturar capturas dessas pilhas novamente, bem como sintaxe para capturar capturas de uma pilha e capturar push para outro ao mesmo tempo. Para uma imagem mais completa, você pode dar uma olhada na minha resposta no Stack Overflow, que deve cobrir todos os detalhes.

A ideia básica é combinar um padrão como:

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

Onde nestá entre 2 e 22 (inclusive). O difícil é conseguir que todos ne todos msejam iguais. Como os personagens reais não serão os mesmos, não podemos simplesmente usar uma referência anterior.

Observe que o regex precisa incorporar novas linhas, que escreverei como \na seguir.

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

Aqui está uma função C # completa, apenas para tornar essa entrada válida. Está na hora de escrever um "intérprete" de linha de comando para expressões regulares do .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))])

Melhor do que Java, mas, menino, os quíntuplos loops aninhados doem. O for/inpode ser um pouco compressível usando %ssubstituição, mas não iria economizar muito.

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

Isso é muito mais longo do que uma expressão regular. Ele simplesmente itera sobre todos os quadrados possíveis na entrada. Se for um portal válido, ele incrementa um contador em 1. Em seguida, retorna o contador. Provavelmente isso pode ser jogado muito mais longe. Todas as sugestões são bem-vindas.

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

Recuado:

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

}