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

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

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

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

.......C..
.1.C2.C3..
........5C
.CC4..CC..
..........

• Сундук может быть размещен в месте 1, потому что его 4 соседа пусты.
• Сундук может быть размещен в месте 2, потому что соседний сундук (пока) не является частью двойного сундука.
• Сундук не может быть помещен в точку 3, потому что было бы двусмысленность относительно того, как формируется двойной сундук.
• Сундук не может быть помещен в точку 4, потому что соседний сундук уже является частью двойного сундука.
• Сундук может быть размещен в пятом месте. Соседний по диагонали двойной сундук ни на что не влияет.

Предполагая, что область за сеткой пуста, изменение каждого .в сетке на a, *если сундук может быть размещен там, приводит к этому:

******.C**
***C**C.**
*..***..*C
.CC.*.CC.*
*..***..**

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

Вызов

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

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

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

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

• При желании, вы можете использовать любые три различных печатаемые ASCII символы вместо ., Cи *. Вы не можете использовать что-то другое вместо новых строк.

• Все сундуки нормальные сундуки. Сундуки не в ловушке или сундуки .

счет

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

^{Для более сложной задачи, связанной с Minecraft, попробуйте Nether Portal Detection .}

CJam, 82 76 66 62 58 54 байта

qN/::~4{[8_]f/[9_]f*z{[{1$8-g)+}*]W%}%}*{_8<\2<8?}f%N*

Формат ввода рассчитан 0на воздушную ячейку и 8грудную клетку. Вывод содержит 1все ячейки, которые можно разместить с помощью сундука.

ОБНОВЛЕНИЕ : исправлена ​​ошибка. Увеличено на 3 байта :( дальше гольфом :). 4 байта сохранены благодаря @ Sp3000

Пример ввода:

0000000800
0008008000
0000000008
0880008808
0000000000

Выход:

1111110811
1110018010
1008800108
0880088008
1008800110

Я думаю, что я закончил игру в гольф на данный момент ...

объяснение

qN/::~                   "This part converts the input into array of integer array";
qN/                      "Split input on new line";
   ::~                   "Parse each character in each row as integer";

4{[8_]f/[9_]f*z{[{1$8-g)+}*]W%}%}*

4{   ...z{       W%}%}*  "Run the logic 4 times, first, columns in correct order, then,";
                         "columns in reverse order, then for rows";
  [8_]f/[9_]f*           "Convert adjacent chests represented by two 8 into two 9";
                         "This happens for all the rows in the columns iterations and";
                         "for all the columns in the rows iterations";
  {               }%     "For each row/column";
   [{        }*]         "Reduce and wrap it back in the array";
     :I8-                "Store the second number in I, remove 8 from it";
         g               "Do signum. Now we have -1 for < 8 number, 0 for 8 and 1 for > 8";
          )+I            "Increment to get 0, 1 & 2. Add it to first number and put I back";

{_8<\2<8?}f%N*           "This part converts the output from previous iterations";
                         "to 3 character based final output and prints it";
{        }f%             "Map each row using the code block";
 _8<   8?                "If the value is greater than 7, make it 8, else:";
    \2<                  "If the value is greater than 1, make it 0, else 1";
            N*           "Join the arrays using new line";

Попробуйте онлайн здесь

.NET Regex ( Retina ), 434 416 310 + 1 = 311 байт

После последнего вызова, на который я ответил в регулярном выражении (вызов портала Nether, связанный с этим вызовом), я наконец-то решил написать инструмент командной строки, который выступает в качестве интерпретатора регулярных выражений в стиле .NET, поэтому я могу отвечать на вопросы. с регулярным выражением, не оспаривая, что они не автономный язык. Я назвал это Retina.

Теперь, этот вызов не очень хорошо подходит для представления регулярных выражений, но я просто должен был использовать Retina сейчас. ;) (Плюс, Sp3000 бросил мне вызов в чате.) Так вот:

Файл регулярных выражений

m`(?<=(?=.(.)*).*)(?<=((?<=(?<2>C|C(?(1)!)(\n|(?<-1>.))*)?)C(?=(?<2>C|(\n|(?<-1>.))*(?(1)!)C)?)(()(?(6)!)|(?<=^(?(7)!)(?<-7>.)*C).*\n(.)*()(?(8)!)))?){2}_(?=(?<2>((?(10)!)()|(?(11)!)()(.)*\n.*(?=C(?<-12>.)*(?(12)!)$))(?<=(?<2>C|C(?(1)!)(\n|(?<-1>.))*)?)C(?=(?<2>C|(\n|(?<-1>.))*(?(1)!)C)?))?){2}(?<-2>)?(?(2)!)

Файл замены

*

Файл регулярных выражений - это, в основном, просто регулярное выражение, за исключением того, что `позволяет поместить в файл несколько параметров, в данном случае это просто многострочный режим. При наличии двух файлов Retina автоматически принимает режим замены всех. Эти два файла определяют программу, которая читает входные данные из STDIN и печатает результат в STDOUT.

Вы также можете проверить это на RegexHero и RegexStorm . Регулярное выражение работает как с последним переводом строки, так и без него, и использует _вместо него .. (Очевидно, у RegexStorm иногда возникают проблемы, если нет завершающего символа новой строки, но RegexHero, похоже, отлично справляется с любым из этих случаев.)

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

J, 75 73 байта

((,.|.)0 _1 0 1)(+:@](LF,@:,.~'*.C'{~>.)(2=f)+.[f]*f=.[:+/|.!.0)'C'&=;._2

Использует формат в вопросе, используя ./ */ Cдля пробела / полезного пространства / сундук, соответственно.

Редактировать: исправляет небольшую ошибку (я случайно использовал тор вместо правильного обращения с окружением как с пустым пространством).

объяснение

## Preparation
              'C'&=;._2  NB. Map ./C to 0/1, turn into matrix
((,.|.)0 _1 0 1)         NB. Compute offsets to shift into each direction
                         NB. (i.e. [[_1 0], [1 0], [0 _1], [0 1]] in any order)


## "Part B"
(2=f)+.[f]*f=.[:+/|.!.0  NB. This part computes a matrix that is 1 for cells that
                         NB. cannot contain a chest:
              [:+/|.!.0  NB. Sum of shifts: shift in each of the four cardinal
                         NB. directions (using the array above) and then sum up.
           f=.           NB. Define this function as `f`; we'll use it some more.
         ]*              NB. Multiply by the "is chest" matrix: this isolates
                         NB. double-chests.
       [f                NB. Sum of shifts--1 for double-chest neighbours.
(2=f)                    NB. Isolate cells with two neighbouring chest.
     +.                  NB. Boolean or--either two neighbouring chests or next
                         NB. to a double-chest.

## Wrap up the result
(+:@] (fmt >.) PartB)    NB. Maximum of the array from the above and twice the "is
 +:@]      >.  PartB     NB. chest" matrix--this is 0,1,2 for '*', '.' or chest,
                         NB. respectively.

## Output formatting
LF,@:,.~'*.C'{~          NB. Format output...
        '*.C'{~          NB. Map 0,1,2 to '*.C' by using the value as index
LF   ,.~                 NB. Append line feed at end of each line
  ,@:                    NB. Ravel into one line

С, 193

2 ненужных перевода строки для ясности. Изменения по отношению к негольфированному коду включают: символы как коды ascii вместо символьных литералов; перестановка v = 0, strlen и strchr для сохранения символов (strchr - самый уродливый, поскольку это означает, что вычисление, которое в противном случае было бы выполнено только один раз, выполняется 5 раз для каждой ячейки!)

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

g(char*q){int v,j,w,l;
int f(p,d){int s=0,i=w=strchr(q,10)-q+1,r;for(;w/i;i-=i-1?w-1:2)r=p+i,r>-1&r<l&&q[r]==67&&++s&&d&&f(r,0);v|=s>d;}
for(j=l=strlen(q);j--;f(j,1),46-q[j]||v||(q[j]=42))v=0;}

Подводя итог правилам:

пустой квадрат (который не содержит C или символ новой строки) может быть преобразован, если у него максимум 1 сосед с C

... И этот сосед не имеет соседей с C.

Функция g содержит функцию f, которая рекурсивно спускается с глубины 1 на глубину 0. С помощью только 2 уровней рекурсии f(r,0)подойдет простой рекурсивный вызов, в этом нет необходимости f(r,d-1)!

Разгруженный код в тестовой программе

Входная тестовая строка жестко закодирована. getsи scanfне примет входную строку с символами новой строки в ней; они разбивают его на кусочки на каждой новой строке.

char n[]=".......C..\n...C..C...\n.........C\n.CC...CC..\n..........";

g(char*q){

  int v,j,w,l;

  int f(p,d){                    //p=cell to be checked,d=recursion depth
    int s=0,i=w,r;               //sum of C's found so far=0, i=width
    for(;w/i;i-=i-1?w-1:2)       //For i in   w,1,-1,-w   = down,right,left,up
      r=p+i,                     //r=cell adjacent to p
      r>-1&r<l&&q[r]=='C'&&++s   //If r not out of bounds and equal to C, increment s...
        &&d&&f(r,0);             //...and if recursion depth not yet at zero, try again one level deeper. 
    v|=s>d;                      //If the local s exceeds d, set global v to true to indicate invalid.
  }

  w=strchr(q,10)-q+1;            //width equals index of first newline + 1                   
  l=strlen(q);                   //length of whole string;
  for(j=l;j--;)                  //for l-1 .. 0 
    v=0,                         //clear v
    f(j,1),                      //and scan to see if it should be set
    '.'-q[j]||v||(q[j]='*');     //if the character is a '.' and v is not invalid, change to '*'
}

main(){
  g(n);
  puts(n);
}

Вывод на основе примера вопроса

******.C**
***C**C.**
*..***..*C
.CC.*.CC.*
*..***..**

JavaScript (ES6) 124 129

Использование символов 0 (*), 6 (C), 7 (.)

F=s=>[for(c of(d=[o=~s.search('\n'),-o,1,i=-1],s))
   d.map(j=>t-=s[i+j]==6&&~d.some(k=>s[i+j+k]==6),t=i++)|c<7|t>i&&c
].join('')

Разгромил и объяснил

F=s=>
{
  o=~s.search('\n') // offset to prev row (~ is shorter than +1 and sign does not matter)
  d=[o,-o,1,-1] // array of offset to 4 neighbors
  i=-1
  result = '' // in golfed code, use array comprehension to build the result into an array, then join it
  for (c of s) // scan each char
  {
    t = i++ // set a starting value in t and increment current position in i
    d.forEach(j => // for each near cell, offset in j
    {         
      if (s[i+j]==6) // if cell contains a Chest, must increment t
      {  
        // In golfed code "~some(...)" will be -1(false) or -2(true), using decrement instead of increment
        if (d.some(k=>s[i+j+k]==6)) // look for another Cheast in the neighbor's neighbors
        {
          // more than one chest, position invalid
          t += 2
        }
        else
        {
          t += 1
        }
      }
    })
    if (c < 7 // current cell is not blank
        || t > i) // or t incremented more than once, position invalid
    {
       result += c // curent cell value, unchanged
    }
    else
    {
       result += 0 // mark a valid position 
    }
  }
  return result
}

Тест в консоли Firefox / FireBug

a='\
7777777677\n\
7776776777\n\
7777777776\n\
7667776677\n\
7777777777\n';

console.log(F(a))

Выход

0000007600
0006006700
0770007706
7667076670
0770007700

Perl, 66

Конфликты сундуков с регулярным выражением заканчивались на длинной стороне, так что на этот раз не конкурируйте с CJam.

#!perl -p0
/.
/;$"=".{@-}";s%0%s/\G0/2/r!~/2((.$")?2(.$")?|2$"|$"2)2/s*1%eg

Использует 0 и 2 для пустых и сундуков на входе, 1 для отметки мест на выходе.

Попробуй это здесь .

Python 2 - 281 байт

f=lambda x,y:sum(m[y][x-1:x+2])+m[y-1][x]+m[y+1][x]
m=[];o=''
try:
 while 1:m+=[map(int,'0%s0'%raw_input())]
except:a=len(m[0]);l=len(m);m+=[[0]*a]
for y in range(l*2):
 for x in range(1,a-1):
    if y<l:m[y][x]*=f(x,y)
    else:o+=`2if m[y-l][x]else +(f(x,y-l)<5)`
 if y>=l:print o;o=''

(Строки 8 и 9 предназначены с одним символом табуляции, который SE преобразует в 4 пробела. Каждая строка в этой программе имеет либо 0, либо 1 байт начального пробела.)

Вход: 0для сундука нет, 2для сундука
Ouput: 0для сундука нет, 2для существующего сундука, 1для возможного нового сундука

Боже, это ужасно Я должен быть серьезно из практики. Я бросил каждый трюк, который я знаю, и это получилось ... ну, это вышло как 281 байт, проиграв на каждый ответ, кроме одного в регулярное выражение , хаха. Честно говоря, я чувствую, что играю в гольф это довольно хорошо, поэтому я предполагаю, что мой алгоритм был просто не идеален.

Ungolfed:

def f(x,y):
    """Given x,y coords of the board, return the sum of that point and all
    adjacent points.
    """
    return (sum(board[y][x-1:x+2]) # (x-1,y) + (x,y) + (x+1,y)
            + board[y-1][x]
            + board[y+1][x])
board=[]
output=''
try:
    while True:
        row = '0%s0' % raw_input() # line from stdin with a leading and trailing 0
        board.append(map(int, row)) # convert to list of ints
except:
    pass # exception is thrown when stdin is empty

board_width = len(board[0])
board_height = len(board)

board.append([0]*board_width) # new row of all 0s

for y in xrange(board_height*2):
    # board_height multiplied by 2 so we can use this loop to simulate two
    for x in xrange(1,board_width-1):
        if y < board_height: # "first loop"
            board[y][x] *= f(x,y) # multiply everything on the board by itself + sum
                                  # of neighbours
                                  # empty cells (0) stay 0 no matter what
                                  # lone chests (2 surrounded by 0) become 2*2==4
                                  # double chests (2 touching another 2) are weird:
                                  # - one chest becomes 2*(2+2)==8
                                  # - the other chest becomes 2*(2+8)==20
        else: # "second loop"
            if board[y - board_height][x] != 0:
                output += '2' # anything not equal to 0 is an existing chest
            else:
                valid = f(x, y - board_height) < 5 # if the sum of neighbours > 4, the
                                                   # current cell is either beside a
                                                   # double chest or more than one
                                                   # single chest
                output += '01'[valid]
    if y >= board_height: # only print during the "second loop"
        print output
        output=''