Permainan video Minecraft adalah tentang menempatkan dan menghapus berbagai jenis blok dalam kisi integer 3D yang membentuk dunia virtual. Setiap titik kisi dapat berisi tepat satu blok atau kosong ( blok " udara " secara resmi). Dalam tantangan ini, kita hanya akan peduli dengan satu bidang 2D vertikal dari dunia 3D, dan satu jenis blok: obsidian .

Ketika obsidian membentuk garis besar persegi panjang kosong di bidang vertikal, portal bawah dapat dibuat. Kotak kosong mungkin ukuran mulai dari 2 unit lebar 3 unit tinggi hingga 22 unit lebar 22 unit tinggi. Sudut-sudut persegi panjang tidak perlu dibatasi di obsidian, hanya sisi.

Sebagai contoh, anggaplah Xobsidian dan .kekosongan: (Jumlahnya hanya untuk tujuan identifikasi dan juga kosong.)

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

Kisi ini berisi 3 portal yang valid:

• Portal 1 adalah 2 oleh 3 unit, benar-benar kosong, dan berbatasan dengan obsidian. Karena itu sah.
• Portal 2 adalah 4 oleh 3, benar-benar kosong, dan berbatasan dengan obsidian. Karena itu sah.
• Portal 3 tidak sepenuhnya kosong. Karena itu tidak valid.
• Portal 4 adalah 3 oleh 3, benar-benar kosong, dan berbatasan dengan obsidian. Karena itu sah.
• Portal 5 adalah 3 oleh 2 unit, yang terlalu kecil. Karena itu tidak valid.
• Portal 6 kehilangan bagian perbatasan. Karena itu tidak valid.

Tantangan

Tulis program atau fungsi yang menampilkan representasi string dari grid obsidian dan kekosongan, dan mencetak atau mengembalikan jumlah portal yang valid di bawah ini.

• Input dapat dari argumen stdin atau file atau fungsi.

• Anda dapat berasumsi bahwa input selalu terbentuk dengan baik - yaitu kisi teks persegi panjang sempurna, setidaknya 1 karakter lebar dan tinggi, hanya berisi Xdan .. Anda dapat mengasumsikan bahwa ada baris baru setelah baris terakhir.

• Jika diinginkan, Anda dapat menggunakan dua karakter ASCII yang dapat dicetak untuk menggantikan Xdan ..

• Obsidian mungkin berada di perbatasan grid. Apa pun di luar perbatasan dianggap kosong.

Input contoh - output harus 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

Mencetak gol

Kiriman dengan byte paling sedikit menang.

Perl, 81 86

Menggunakan lebih dari satu regexp.

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

Regexp untuk lebar tertentu dari portal jauh lebih sederhana daripada yang generik: X{$m}..{$n}(X\.{$m}X.{$n}){3,22}.X{$m}mana madalah lebar portal dan nadalah total width - 1 - m. Regexp harus dimasukkan ke dalam pernyataan ke depan dengan lebar nol (?=...)karena pertandingan mungkin tumpang tindih. Kemudian saya mengulangi 21 kali pengaturan regexp ini $ndan $.. "@-"mengevaluasi untuk memulai posisi pertandingan terakhir ( /.\n/) yang merupakan total lebar - 1. $.digunakan sebagai variabel lain seperti yang diinisialisasi 1ketika digunakan dengan -p0.

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

Pengenalan pola seni ASCII 2D? Kedengarannya seperti pekerjaan untuk regex! (Tidak.)

Saya tahu ini akan memulai diskusi tanpa akhir lagi tentang apakah pengiriman regex adalah program yang valid atau tidak, tapi saya ragu ini akan mengalahkan APL atau CJam, jadi saya tidak melihat ada salahnya. (Yang sedang berkata, mereka benar - benar lulus ujian keras kami untuk "Apa itu bahasa pemrograman?" .)

Ini membutuhkan input saat string harus dicocokkan, dan hasilnya adalah jumlah kecocokan yang ditemukan. Ini digunakan _sebagai pengganti ., karena saya harus melarikan diri dari yang terakhir. Ini juga membutuhkan baris baru tambahan.

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

Anda dapat mengujinya secara langsung di RegexHero atau RegexStorm ). Pertandingan akan menjadi baris obsidian atas portal. Jika Anda dapat menemukan kasus uji yang gagal, beri tahu saya!

Apa sihir ini?

Penjelasan berikut mengasumsikan pemahaman dasar tentang kelompok penyeimbang .NET . Intinya adalah bahwa tangkapan adalah tumpukan di .NET regex - setiap tangkapan baru untuk nama yang sama didorong ke tumpukan, tetapi ada juga sintaksis untuk menangkap tangkapan dari tumpukan itu lagi, serta sintaksis untuk menangkap tangkapan dari satu tumpukan dan mendorong tangkapan ke yang lain pada saat yang sama. Untuk gambar yang lebih lengkap, Anda dapat melihat jawaban saya di Stack Overflow yang harus mencakup semua detail.

Ide dasarnya adalah untuk mencocokkan pola seperti:

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

Di mana nberada antara 2 dan 22 (inklusif). Yang sulit adalah membuat semua ndan semua mmenjadi sama. Karena karakter sebenarnya tidak akan sama, kita tidak bisa hanya menggunakan referensi-ulang.

Perhatikan bahwa regex harus menyematkan baris baru, yang akan saya tulis seperti \nberikut ini.

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

Ini adalah fungsi C # lengkap, hanya untuk menjadikan ini entri yang valid. Sudah waktunya saya menulis command-line "interpreter" untuk .NET regular expressions ...

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 byte

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

Lebih baik daripada Jawa, tapi bocah lingkaran berleher lima itu sakit. The for/inmungkin sedikit kompresibel menggunakan %ssubstitusi, tapi itu tidak akan menghemat banyak.

Diperluas:

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 byte

Ini jauh lebih lama daripada ekspresi reguler. Ini hanya mengulangi setiap kuadrat yang mungkin dalam input. Jika itu adalah portal yang valid, itu menambah penghitung dengan 1. Itu kemudian mengembalikan penghitung. Ini mungkin bisa bermain golf lebih jauh. Setiap saran dipersilahkan.

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

Bertakuk:

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

Program lengkap:

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

}