Видеоигра Minecraft - это все о размещении и удалении различных типов блоков в трехмерной целочисленной решетке, которая составляет виртуальный мир. Каждая точка решетки может содержать ровно один блок или быть пустой (официально « воздушный » блок). В этой задаче мы будем иметь дело только с одной вертикальной двухмерной плоскостью трехмерного мира и одним типом блока: обсидианом .

Когда обсидиан формирует контур пустого прямоугольника в вертикальной плоскости, может быть создан нижний портал . Пустой прямоугольник может быть любого размера от 2 единиц в ширину до 3 единиц в высоту до 22 единиц в ширину и 22 единицы в высоту. Углы прямоугольника не должны быть ограничены обсидианом, только стороны.

Например, предположим, что Xэто обсидиан и .пустота: (числа приведены только для идентификации и также пусты).

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

Эта сетка содержит 3 действительных портала:

• Портал 1 составляет 2 на 3 единицы, абсолютно пустой и окаймлен обсидианом. Поэтому это действительно.
• Портал 2 4 на 3, полностью пустой и окаймлен обсидианом. Поэтому это действительно.
• Портал 3 не совсем пустой. Поэтому это неверно.
• Портал 4 - 3 на 3, полностью пустой и граничит с обсидианом. Поэтому это действительно.
• Портал 5 составляет 3 на 2 единицы, что слишком мало. Поэтому это неверно.
• На портале 6 отсутствует часть границы. Поэтому это неверно.

Вызов

Напишите программу или функцию, которая принимает в этих строковых представлениях сетки обсидиана и пустоты и печатает или возвращает количество имеющихся действительных порталов.

• Ввод может быть из стандартного ввода или аргумента файла или функции.

• Вы можете предположить, что входные данные всегда правильно сформированы - то есть идеально прямоугольная сетка текста, шириной не менее 1 символа и высотой, содержащая только Xи .. При желании вы можете предположить, что после последней строки есть завершающий символ новой строки.

• При желании вы можете использовать любые два различных печатаемых символа ASCII вместо Xи ..

• Обсидиан может находиться на границах сетки. Все, что находится за пределами границ, считается пустым.

Пример ввода - вывод должен быть 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

счет

Представление с наименьшим количеством байтов выигрывает.

Perl, 81 86

Использование более одного регулярного выражения.

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

Регулярное выражение для определенной ширины портала намного проще, чем общее: X{$m}..{$n}(X\.{$m}X.{$n}){3,22}.X{$m}где mширина портала и nесть total width - 1 - m. Регулярное выражение должно быть помещено в прямое утверждение нулевой ширины, (?=...)потому что совпадения могут перекрываться. Затем я повторяю 21 раз по этому параметру регулярного выражения $nи $.. "@-"оценивает начальную позицию последней функции match ( /.\n/), которая имеет общую ширину - 1. $.используется в качестве другой переменной, к которой она инициализируется 1при использовании с -p0.

Regex (.NET flavour), 182 181 145 132 126 114 104 100 98 97 96 байт

2D ASCII искусство распознавания образов? Похоже, работа для регулярных выражений! (Это не так.)

Я знаю, что это снова вызовет бесконечные дискуссии о том, являются ли регулярные выражения действительными программами или нет, но я сомневаюсь, что это все равно превзойдет APL или CJam, поэтому я не вижу никакого вреда. (Это , как говорится, они делают пройти наш твердолобый тест на «Что такое язык программирования?» .)

Это принимает входные данные в качестве строки для сопоставления, и результатом является количество найденных совпадений. Это использует _вместо ., потому что я должен был бы избежать последнего. Это также требует завершающей новой строки.

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

Вы можете проверить это в прямом эфире в RegexHero или RegexStorm ). Матчи будут верхними обсидиановыми рядами порталов. Если вы можете найти тестовый случай, когда он не проходит, пожалуйста, дайте мне знать!

Что это за колдовство?

Следующее объяснение предполагает базовое понимание балансирующих групп .NET . Суть в том, что захваты - это стеки в регулярном выражении .NET - каждый новый захват с тем же именем помещается в стек, но есть также синтаксис для повторного захвата захватов из этих стеков, а также синтаксис для захвата захватов из одного стека и push-захватов. на другого в то же время. Чтобы получить более полную картину, вы можете взглянуть на мой ответ о переполнении стека, который должен охватить все детали.

Основная идея состоит в том, чтобы соответствовать шаблону, как:

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

Где nмежду 2 и 22 (включительно). Хитрость в том, чтобы все nи все mбыли одинаковыми. Поскольку действительные символы не будут одинаковыми, мы не можем просто использовать обратную ссылку.

Обратите внимание, что регулярное выражение имеет встроенные символы новой строки, которые я напишу, как показано \nниже.

(                     # 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 байт

Вот полная функция C #, только для того, чтобы сделать эту запись действительной. Пришло время написать "интерпретатор" командной строки для регулярных выражений .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 байт

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, но мальчишке пятерка вложенных петель повредит. for/inМожет быть слегка сжимаемым с помощью %sзамены, но это не спасло бы много.

Expanded:

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 байта

Это намного длиннее, чем регулярное выражение. Он просто перебирает все возможные квадраты на входе. Если это действительный портал, он увеличивает счетчик на 1. Затем он возвращает счетчик. Это может быть, вероятно, гораздо дальше. Любые предложения приветствуются.

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

Отступ:

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

Полная программа:

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

}