El videojuego Minecraft se trata de colocar y eliminar diferentes tipos de bloques en la red de enteros 3D que conforma el mundo virtual. Cada punto de la red puede contener exactamente un bloque o estar vacío (un bloque " aéreo " oficialmente). En este desafío, solo nos ocuparemos de un plano horizontal 2D del mundo 3D y un tipo de bloque: cofres .

Los cofres permiten a los jugadores almacenar artículos. Cuando dos cofres son adyacentes ortogonalmente en el mismo plano horizontal, sus texturas se unen y se forma un cofre doble con el doble de capacidad. No se puede hacer nada más grande que un cofre doble; no hay cofres triples ni cofres cuádruples.

Un bloque de cofre solo se puede colocar en un punto de celosía vacío si sus cuatro puntos adyacentes ortogonalmente están todos vacíos, o si exactamente uno contiene un bloque de cofre que aún no es parte de un cofre doble. Estas reglas de colocación aseguran que nunca haya ambigüedad sobre qué bloques de cofres se vinculan para formar cofres dobles.

Por ejemplo, supongamos que .es un espacio vacío y Ces un cofre: (Los números también son espacios vacíos y solo con fines de identificación).

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

• Se puede colocar un cofre en el lugar 1 porque sus 4 vecinos están vacíos.
• Se puede colocar un cofre en el lugar 2 porque el cofre vecino no es (todavía) parte de un cofre doble.
• No se puede poner un cofre en el lugar 3 porque habría ambigüedad sobre cómo se forma el cofre doble.
• No se puede colocar un cofre en el lugar 4 porque el cofre vecino ya es parte de un cofre doble.
• Se puede colocar un cofre en el lugar 5. El doble cofre adyacente en diagonal no afecta nada.

Suponiendo que el área más allá de la cuadrícula esté vacía, cambiar cada una .de las cuadrículas a *si se pudiera colocar un cofre allí resulta en esto:

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

No todos los *espacios se pueden ocupar con cofres al mismo tiempo, por supuesto, pero si solo tuviera un cofre, podría colocarse en cualquiera de ellos.

Desafío

Escriba un programa o función que abarque una cuadrícula .y C, y cambie cada uno .a *si se puede colocar un cofre allí, imprimiendo o devolviendo la cuadrícula resultante.

• La entrada puede ser desde stdin o un archivo o como un argumento de cadena a una función.

• Puede suponer que la entrada está bien formada, es decir, una cuadrícula de texto perfectamente rectangular, de al menos 1 carácter de ancho y alto, que solo contiene .y C, opcionalmente, puede suponer que hay una nueva línea final después de la última fila (y puede haber una en la salida )

• Puede suponer que la disposición de los cofres en la entrada es coherente con las reglas anteriores. Nunca habrá ambigüedades sobre qué cofres forman cofres dobles.

• Si lo desea, puede utilizar cualquiera de los tres distintos ASCII imprimibles caracteres en lugar de ., C, y *. No puede usar otra cosa en lugar de nuevas líneas.

• Todos los cofres son cofres normales. No cofres atrapados o cofres de ender .

Puntuación

El envío con la menor cantidad de bytes gana.

^{Para un desafío relacionado con Minecraft que es un poco más desafiante, prueba la detección de portal abisal .}

CJam, 82 76 66 62 58 54 bytes

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

El formato de entrada espera 0para la celda de aire y 8para una celda de cofre. La salida contiene 1todas las celdas que se pueden colocar con un Cofre.

ACTUALIZACIÓN : Se corrigió un error. Incrementado en 3 bytes :( golfed más :). 4 bytes guardados gracias a @ Sp3000

Entrada de ejemplo:

0000000800
0008008000
0000000008
0880008808
0000000000

Salida:

1111110811
1110018010
1008800108
0880088008
1008800110

Creo que he terminado de jugar golf por ahora ...

Explicación

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

Pruébalo en línea aquí

.NET Regex ( Retina ), 434 416 310 + 1 = 311 bytes

Después del último desafío que respondí en regex (el Desafío del Portal del Nether vinculado a este desafío), finalmente me propuse escribir una herramienta de línea de comandos, que actúa como un intérprete para expresiones regulares de estilo .NET, para que pueda responder preguntas con expresiones regulares sin ser cuestionados de que no son un lenguaje independiente. Lo he llamado Retina.

Ahora, este desafío no se presta muy bien para una presentación de expresiones regulares, pero solo tenía que usar Retina ahora. ;) (Además, Sp3000 me retó a hacerlo en el chat.) Así que aquí está:

Archivo Regex

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

Archivo de reemplazo

*

El archivo regex es principalmente solo la expresión regular, excepto que le `permite poner algunas opciones en el archivo, en este caso, simplemente el modo multilínea. Cuando se le dan dos archivos, Retina asume automáticamente el modo de reemplazo total. Estos dos archivos definen un programa que lee la entrada de STDIN e imprime el resultado en STDOUT.

También puede probarlo en RegexHero y RegexStorm . La expresión regular funciona con y sin línea nueva, y se usa _en lugar de .. (Aparentemente, RegexStorm ocasionalmente tiene problemas si no hay una nueva línea final, pero RegexHero parece manejar bien cualquier caso).

Hay una cantidad horrible de duplicación en la expresión regular, y tengo un par de ideas para acortarla significativamente ... Lo intentaré más tarde y luego agregaré una explicación. Mientras tanto, avíseme si puede encontrar alguna entrada que produzca un resultado incorrecto.

J, 75 73 bytes

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

Utiliza el formato en la pregunta, usando ./ */ Cpara espacio / espacio utilizable / cofre, respectivamente.

Editar: corrige un pequeño error (accidentalmente usé un toro en lugar de tratar adecuadamente los alrededores como un espacio vacío).

Explicación

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

C, 193

2 líneas innecesarias para mayor claridad. Los cambios con respecto al código no protegido incluyen: caracteres como códigos ascii en lugar de literales de caracteres; reordenamiento de v = 0, strlen y strchr para guardar caracteres (strchr es el más feo, ya que significa que un cálculo que de otro modo se realizaría una sola vez, ¡se realiza 5 veces por celda!)

Las funciones C no aceptan cadenas como argumentos ni las devuelven como valores, por lo que lo mejor que puedo hacer es lo siguiente: qes un puntero a la cadena de entrada. La función modifica la cadena y cuando la función devuelve la salida se encuentra en la cadena original.

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

Para resumir las reglas:

un cuadrado en blanco (que no contiene C o nueva línea) se puede convertir si tiene un máximo de 1 vecino con una C

... Y ese vecino no tiene vecinos con una C.

La función g contiene una función f que recurre desde la profundidad 1 a la profundidad 0. Con solo 2 niveles de recursión, una simple f(r,0)llamada recursiva servirá, ¡no hay necesidad de hacerlo f(r,d-1)!

Código no protegido en el programa de prueba

La cadena de prueba de entrada está codificada. getsy scanfno aceptará una cadena de entrada con nuevas líneas; lo cortan en pedazos en cada nueva línea.

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

Salida basada en un ejemplo de pregunta

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

JavaScript (ES6) 124 129

Usando los caracteres 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('')

Desengañado y explicado

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
}

Prueba en la consola Firefox / FireBug

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

console.log(F(a))

Salida

0000007600
0006006700
0770007706
7667076670
0770007700

Perl, 66

Los conflictos de cofres de combinación de expresiones regulares terminaron en el lado largo, por lo que esta vez no competir con CJam.

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

Utiliza 0 y 2 para espacios vacíos y de cofre en la entrada, 1 para marcar los puntos en la salida.

Intentalo aquí .

Python 2 - 281 bytes

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=''

(Las líneas 8 y 9 están pensadas con un solo carácter de tabulación, que SE convierte a 4 espacios. Cada línea en este programa tiene 0 o 1 bytes de espacios en blanco iniciales).

Entrada: 0para no cofre, 2para cofre
Ouput: 0para no cofre,2 para cofre existente, 1para posible cofre nuevo

Dios, esto es horrible. Debo estar seriamente fuera de práctica. Lancé todos los trucos que conozco y salieron ... bueno, salieron como 281 bytes, perdiendo por cada respuesta, excepto la de expresión regular , jaja. Honestamente siento que jugué un poco bien, así que supongo que mi algoritmo fue menos que ideal.

Sin golf:

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=''