Minecraft Chest Placement

Question

The video game Minecraft is all about placing and removing different types of blocks in the 3D integer lattice that makes up the virtual world. Each lattice point can contain exactly one block or be empty (an "air" block officially). In this challenge, we will only be concerned with one horizontal 2D plane of the 3D world, and one type of block: chests.

Chests let players store items. When two chests are orthogonally adjacent in the same horizontal plane, their textures link up and a double chest with twice the capacity forms. Nothing bigger than a double chest can be made; there are no triple chests nor quadruple chests.

A chest block can only be placed in an empty lattice point if its four orthogonally adjacent points are all empty, or if exactly one contains a chest block that is not already part of a double chest. These placement rules ensure that there can never be any ambiguity about which chest blocks link to form double chests.

For example, suppose . is empty space and C is a chest: (The numbers are also empty space and just for identification purposes.)

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

• A chest can be placed in spot 1 because its 4 neighbors are empty.
• A chest can be placed in spot 2 because the neighboring chest is not (yet) part of a double chest.
• A chest can't be put in spot 3 because there would be ambiguity over how the double chest forms.
• A chest can't be placed in spot 4 because the neighboring chest is already part of a double chest.
• A chest can be placed in spot 5. The diagonally neighboring double chest doesn't affect anything.

Assuming the area beyond the grid is empty, changing every . in the grid to a * if a chest could be placed there results in this:

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

Not all of the * spaces can be occupied with chests at the same time of course, but if you only had one chest, it could be placed in any of them.

Challenge

Write a program or function that takes in a . and C grid, and changes every . to a * if a chest could be placed there, printing or returning the resulting grid.

• Input can be from stdin or a file or as a string argument to a function.

• You may assume the input is well formed - i.e. a perfectly rectangular grid of text, at least 1 character wide and tall, only containing . and C You may optionally assume there is a trailing newline after the last row (and there may be one in the output).

• You may assume the arrangement of chests in the input is consistent with the rules above. There will never be ambiguities about which chests form double chests.

• If desired, you may use any three distinct printable ASCII characters in place of ., C, and *. You may not use something else in place of newlines.

• All the chests are normal chests. Not trapped chests or ender chests.

Scoring

The submission with the fewest bytes wins.

^{For a Minecraft related challenge that's a bit more challenging, try Nether Portal Detection.}

Answer 1

CJam, 82 76 66 62 58 54 bytes

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

Input format expects 0 for air cell and 8 for a chest cell. Output contains 1 for all cells that can be placed with a Chest.

UPDATE : Fixed a bug. Increased by 3 bytes :( golfed further :) . 4 bytes saved thanks to @Sp3000

Example input:

0000000800
0008008000
0000000008
0880008808
0000000000

Output:

1111110811
1110018010
1008800108
0880088008
1008800110

I think I am done golfing for now...

Explanation

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

Try it online here

Answer 2

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

After the last challenge I answered in regex (the Nether Portal Challenge linked to in this challenge), I finally set out to write a command-line tool, which acts as an interpreter for .NET-style regular expressions, so I can answer questions with regex without being challenged that they're not a stand-alone language. I've named it Retina.

Now, this challenge doesn't lend itself very well to a regex submission, but I just had to use Retina now. ;) (Plus, Sp3000 challenged me to do so in chat.) So here it is:

Regex file

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

Replacement file

*

The regex file is mostly just the regex, except that ` lets you put a few options in the file, in this case simply multiline mode. When given two files, Retina automatically assumes replace-all mode. These two files define a program which reads the input from STDIN and prints the result to STDOUT.

You can also test it on RegexHero and RegexStorm. The regex works both with and without trailing newline, and uses _ in place of .. (Apparently, RegexStorm occasionally has problems if there is no trailing newline, but RegexHero seems to handle either case fine.)

There is a horrible amount of duplication in the regex, and I have a couple of ideas for shortening it significantly... I'll give that a try later and then add an explanation. In the meantime, let me know if you can find any inputs which yield a wrong result.

Answer 3

J, 75 73 68 bytes

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

Uses the format in the question, using ./*/C for space/usable space/chest, respectively.

Edit: fixes a small bug (I accidentally used a torus instead of properly treating the surrounding as empty space).

Explanation

## Preparation
              'C'&=;._2  NB. Map ./C to 0/1, turn into matrix
(+.0j1^i.4)              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

Answer 4

C,193

2 unnecesary newlines for clarity. Changes with respect to ungolfed code include: characters as ascii codes instead of character literals; rearrangement of v=0,strlen, and strchr to save characters (strchr is the ugliest, as it means that a calculation that would otherwise be performed once only, is performed 5 times per cell!)

C functions do not accept strings as arguments or return them as values, so the best I can do is the following: q is a pointer to the input string. The function modifies the string and when the function returns the output is found in the original string.

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

To summarize the rules:

a blank square (that does not contain C or newline) can be converted if it has max 1 neighbour with a C

...AND that neighbour has no neighbours with a C.

The function g contains a function f that recurses down from depth 1 to depth 0. With only 2 levels of recursion, a simple f(r,0) recursive call will do, there is no need for f(r,d-1)!

Ungolfed code in test program

Input test string is hardcoded. gets and scanf will not accept an input string with newlines in it; they chop it into pieces at each newline.

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

Output based on question example

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

Answer 5

JavaScript (ES6) 124 129

Using characters 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('')

Ungolfed and explained

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
}

Test In Firefox/FireBug console

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

console.log(F(a))

Output

0000007600
0006006700
0770007706
7667076670
0770007700

Answer 6

Perl, 66

The regexp matching chest conflicts ended up on the long side, so no competing with CJam this time.

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

Uses 0 and 2 for empty and chest spaces on the input, 1 to mark the spots on the output.

Try it here.

Answer 7

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

(Lines 8 and 9 are intended with a single tab character, which SE converts to 4 spaces. Every line in this program has either 0 or 1 bytes of leading whitespace.)

Input: 0 for no chest, 2 for chest
Ouput: 0 for no chest, 2 for existing chest, 1 for possible new chest

---

God, this is horrible. I must be seriously out of practice. I threw every trick I know at it and it came out... well, it came out as 281 bytes, losing to every answer except the one in regex, haha. I honestly feel like I golfed it kinda well, so I'm guessing that my algorithm was just less than ideal.

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