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.
Write a program or function that takes in a
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
CYou 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
*. You may not use something else in place of newlines.
The submission with the fewest bytes wins.
For a Minecraft related challenge that's a bit more challenging, try Nether Portal Detection.