Le jeu vidéo Minecraft consiste à placer et à supprimer différents types de blocs dans le réseau d’entiers 3D qui constitue le monde virtuel. Chaque point du réseau peut contenir exactement un bloc ou être vide (un bloc " air " officiellement). Dans ce défi, nous ne nous intéresserons qu’à un seul plan vertical 2D du monde 3D et à un type de bloc: l’ obsidienne .

Lorsque l'obsidienne forme le contour d'un rectangle vide dans un plan vertical, un portail vers le bas peut être créé. Le rectangle vide peut avoir toute taille allant de 2 unités de largeur sur 3 unités de hauteur à 22 unités de largeur sur 22 unités de hauteur. Les coins du rectangle n'ont pas besoin d'être délimités en obsidienne, mais uniquement les côtés.

Supposons, par exemple, qu’il s’agisse d’une Xobsidienne et d’un .vide: (Les chiffres ne servent qu’à des fins d’identification et sont également vides.)

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

Cette grille contient 3 portails valides:

• Le portail 1 est composé de 2 unités sur 3, totalement vide et entouré d'obsidienne. Donc c'est valide.
• Le portail 2 est 4 par 3, totalement vide et bordé d'obsidienne. Donc c'est valide.
• Portal 3 n'est pas totalement vide. Donc c'est invalide.
• Le portail 4 est 3 par 3, totalement vide et bordé d'obsidienne. Donc c'est valide.
• Le portail 5 correspond à 3 unités sur 2, ce qui est trop petit. Donc c'est invalide.
• Le portail 6 manque une partie de la frontière. Donc c'est invalide.

Défi

Ecrivez un programme ou une fonction qui prend en charge ces représentations sous forme de chaînes de grilles d'obsidienne et de vide, et affiche ou renvoie le nombre de portails nether valides présents.

• L'entrée peut être à partir de stdin ou d'un argument de fichier ou de fonction.

• Vous pouvez supposer que la saisie est toujours bien formée - c'est-à-dire une grille de texte parfaitement rectangulaire, d'au moins 1 caractère de large et de hauteur, contenant uniquement les caractères Xet .. Vous pouvez éventuellement supposer qu'il y a une fin de ligne après la dernière ligne.

• Si vous le souhaitez, vous pouvez utiliser deux caractères ASCII imprimables distincts à la place de Xet ..

• L'obsidienne peut être sur les bords de la grille. Tout ce qui se trouve au-delà des frontières est considéré comme vide.

Exemple d'entrée - la sortie devrait être 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

Notation

La soumission avec le moins d'octets gagne.

Perl, 81 86

Utilisation de plusieurs expressions rationnelles.

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

L'expression rationnelle pour une largeur spécifique d'un portail est beaucoup plus simple qu'un générique: X{$m}..{$n}(X\.{$m}X.{$n}){3,22}.X{$m}où mest la largeur du portail et nest total width - 1 - m. L'expression rationnelle doit être placée dans une assertion avant de largeur nulle, (?=...)car les correspondances peuvent se chevaucher. Ensuite, j'itère 21 fois sur ce paramètre d'expression régulière $net $.. "@-"évalue la position de départ de la dernière correspondance ( /.\n/) qui correspond à la largeur totale - 1. $.est utilisée comme autre variable comme elle est initialisée 1avec -p0.

Regex (saveur NET), 182 181 145 132 126 114 104 100 98 97 96 octets

Reconnaissance de motifs artistiques en ASCII 2D? Cela ressemble à un travail pour regex! (Ce n'est pas le cas.)

Je sais que cela va lancer à nouveau des discussions sans fin sur le point de savoir si les soumissions de regex sont des programmes valides ou non, mais je doute que cela vaincra de toute façon APL ou CJam, donc je ne vois pas de mal à le faire. (Cela étant dit, ils font passer notre test die-hard pour « Qu'est - ce qu'un langage de programmation? » .)

Cela prend input comme chaîne à faire correspondre et le résultat est le nombre de correspondances trouvées. Il utilise _à la place de ., car je devrais échapper à ce dernier. Cela nécessite également un retour à la ligne.

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

Vous pouvez le tester en direct sur RegexHero ou RegexStorm ). Les matchs seront les premières rangées d'obsidienne des portails. Si vous pouvez trouver un cas de test où il échoue, s'il vous plaît faites le moi savoir!

Quelle est cette sorcellerie?

L'explication suivante suppose une compréhension de base des groupes d'équilibrage .NET . L'essentiel est que les captures sont des piles dans les expressions rationnelles .NET - chaque nouvelle capture portant le même nom est insérée dans la pile, mais il existe également une syntaxe pour extraire à nouveau les captures de ces piles, ainsi que la syntaxe pour extraire des captures d'une pile et des captures sur un autre en même temps. Pour une image plus complète, vous pouvez consulter ma réponse à Stack Overflow, qui devrait couvrir tous les détails.

L'idée de base est de faire correspondre un modèle tel que:

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

Où nest entre 2 et 22 (inclus). La difficulté est de faire en sorte que tous les ns et tous les ms soient les mêmes. Étant donné que les caractères réels ne seront pas les mêmes, nous ne pouvons pas utiliser simplement une référence arrière.

Notez que la regex doit incorporer des nouvelles lignes, que j'écrirai comme ci \n-dessous.

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

Voici une fonction complète C #, juste pour en faire une entrée valide. Il est temps que j'écrive un "interprète" en ligne de commande pour les expressions régulières .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 octets

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

Mieux que Java, mais les quintuples boucles imbriquées font mal. Le for/inpeut être légèrement compressible en utilisant la %ssubstitution, mais cela ne fera pas économiser beaucoup.

Étendu:

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 octets

C'est beaucoup plus long qu'une expression régulière. Il itère simplement sur tous les carrés possibles de l'entrée. S'il s'agit d'un portail valide, un compteur est incrémenté de 1. Il renvoie ensuite le compteur. Cela peut probablement être joué beaucoup plus loin. Toutes les suggestions sont les bienvenues.

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

Dentelé:

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

Programme complet:

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

}