In dem Videospiel Minecraft geht es darum, verschiedene Arten von Blöcken in dem 3D- Ganzzahlgitter , aus dem die virtuelle Welt besteht, zu platzieren und zu entfernen . Jeder Gitterpunkt kann genau einen Block enthalten oder leer sein ( offiziell ein " Luft " -Block). In dieser Herausforderung werden wir uns nur mit einer vertikalen 2D-Ebene der 3D-Welt und einem Blocktyp befassen: Obsidian .

Wenn der Obsidian den Umriss eines leeren Rechtecks ​​in einer vertikalen Ebene bildet, kann ein Unterportal erstellt werden. Das leere Rechteck kann eine beliebige Größe von 2 Einheiten breit und 3 Einheiten hoch bis 22 Einheiten breit und 22 Einheiten hoch haben. Die Ecken des Rechtecks ​​müssen nicht in Obsidian umrandet sein, sondern nur die Seiten.

Angenommen, es Xhandelt sich um Obsidian und .Leere: (Die Zahlen dienen nur zu Identifikationszwecken und sind ebenfalls leer.)

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

Dieses Raster enthält 3 gültige Portale:

• Portal 1 ist 2 mal 3 Einheiten groß, völlig leer und in Obsidian eingefasst. Deshalb ist es gültig.
• Portal 2 ist 4 mal 3, völlig leer und in Obsidian eingefasst. Deshalb ist es gültig.
• Portal 3 ist nicht ganz leer. Daher ist es ungültig.
• Portal 4 ist 3 mal 3, völlig leer und in Obsidian eingefasst. Deshalb ist es gültig.
• Portal 5 ist 3 mal 2 Einheiten, was zu klein ist. Daher ist es ungültig.
• In Portal 6 fehlt ein Teil der Grenze. Daher ist es ungültig.

Herausforderung

Schreiben Sie ein Programm oder eine Funktion, die diese Zeichenfolgendarstellungen von Gittern aus Obsidian und Leere aufnimmt und die Anzahl der gültigen Unterportale ausgibt oder zurückgibt.

• Die Eingabe kann von stdin oder einem Datei- oder Funktionsargument erfolgen.

• Sie können davon ausgehen, dass die Eingabe immer gut strukturiert ist - dh ein perfekt rechteckiges Textgitter, das mindestens 1 Zeichen breit und hoch ist und nur Xund enthält .. Optional können Sie davon ausgehen, dass nach der letzten Zeile eine nachgestellte Zeile steht.

• Falls gewünscht, können Sie anstelle von und zwei beliebige druckbare ASCII- Zeichen verwenden .X.

• Obsidian kann sich an den Rändern des Gitters befinden. Alles jenseits der Grenzen gilt als leer.

Beispiel Eingabe - die Ausgabe sollte sein 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

Wertung

Die Einsendung mit den wenigsten Bytes gewinnt.

Perl, 81-86

Verwenden von mehr als einem regulären Ausdruck.

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

Die regexp für eine bestimmte Breite eines Portals ist viel einfacher als Standardversion : X{$m}..{$n}(X\.{$m}X.{$n}){3,22}.X{$m}wo mdie Breite des Portals ist und nist total width - 1 - m. Der reguläre Ausdruck muss in eine Forward-Assertion mit (?=...)der Breite Null gestellt werden, da sich die Übereinstimmungen überlappen können. Dann iteriere ich 21 mal über diese Regexp-Einstellung $nund $.. "@-"Wertet die Startposition der letzten Übereinstimmung ( /.\n/) aus, die zufällig die Gesamtbreite - 1 $.hat. Wird als die andere Variable verwendet, auf die sie 1bei Verwendung mit initialisiert wird -p0.

Regex (.NET-Version), 182 181 145 132 126 114 104 100 98 97 96 Byte

2D ASCII Kunstmustererkennung? Klingt nach einem Job für Regex! (Tut es nicht.)

Ich weiß, dass dies zu endlosen Diskussionen darüber führen wird, ob Regex-Einreichungen gültige Programme sind oder nicht, aber ich bezweifle, dass dies APL oder CJam ohnehin schlagen wird, sodass ich keinen Schaden sehe. ( Aber sagen, dass sie tun unser hartnäckiger Test bestehen für „Was ist eine Programmiersprache?“ .)

Dies nimmt Eingaben als die zu vergleichende Zeichenfolge und das Ergebnis ist die Anzahl der gefundenen Übereinstimmungen. Es wird _anstelle von verwendet ., weil ich letzterem entkommen müsste. Es erfordert auch einen nachgestellten Zeilenumbruch.

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

Sie können es live bei RegexHero oder RegexStorm testen . Die Übereinstimmungen sind die obersten Obsidianreihen der Portale. Wenn Sie einen Testfall finden, bei dem dies fehlschlägt, lassen Sie es mich bitte wissen!

Was ist das für eine Zauberei?

Die folgende Erklärung setzt ein grundlegendes Verständnis der .NET- Bilanzkreise voraus . Das Wesentliche ist, dass Captures in .NET Regex Stapel sind - jedes neue Capture mit demselben Namen wird auf den Stapel verschoben, aber es gibt auch eine Syntax zum erneuten Abrufen von Captures aus diesen Stapeln sowie eine Syntax zum Abrufen von Captures aus einem Stapel und zum Übertragen von Captures zur gleichen Zeit auf einen anderen. Für ein vollständigeres Bild können Sie sich meine Antwort auf Stack Overflow ansehen, die alle Details abdecken sollte.

Die Grundidee ist, ein Muster wie das folgende zu finden:

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

Wo nist zwischen 2 und 22 (inklusive). Das Knifflige ist, dass alle ns und alle ms gleich sind. Da die tatsächlichen Zeichen nicht identisch sind, können wir nicht einfach einen Rückverweis verwenden.

Beachten Sie, dass der reguläre Ausdruck Zeilenumbrüche enthalten muss, die ich wie \nfolgt schreiben werde .

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

Hier ist eine vollständige C # -Funktion, nur um dies zu einem gültigen Eintrag zu machen. Es ist Zeit, dass ich einen Befehlszeilen- "Interpreter" für reguläre .NET-Ausdrücke schreibe ...

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

Besser als Java, aber Junge, das Fünffache der verschachtelten Schleifen tut weh. Das for/inkönnte durch %sSubstitution leicht komprimierbar sein , aber es würde nicht viel sparen.

Erweitert:

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

Dies ist viel länger als ein regulärer Ausdruck. Es wird einfach über jedes mögliche Quadrat in der Eingabe iteriert. Wenn es sich um ein gültiges Portal handelt, wird ein Zähler um 1 erhöht. Anschließend wird der Zähler zurückgegeben. Dies kann wahrscheinlich viel weiter golfen werden. Anregungen sind willkommen.

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

Eingerückt:

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

Volles Programm:

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

}