Consider a rectangular two-dimensional grid where each cell can either be empty (
.) or full (
..00.... 0000.... .00000.. 000...00 ..000000 000.00..
The grid is considered infinite, all cells outside the depicted region are empty.
The goal is to cover the filled spaces and leave the empty spaces open using a set of 7 distinctly shaped bricks that each take up 4 cells (2×2) of the grid.
These are the 7 bricks:
Blocks - 1 variant
Slabs - 2 variants
Stairs - 4 variants
These bricks must always align to a grid whose cells are twice as wide and tall as the cells of the input grid. Each brick can only occupy one cell of this larger grid but the smaller grid can be translated (shifted up, down, left, right) beneath the larger grid to give more options for finding a cover. Neither of the grids nor individual bricks may be rotated.
So one way to cover (a.k.a. solve) the example above is like this:
..11.... 2211.... .47733.. 447...22 ..771133 227.11..
(Identical neighboring bricks can still cause ambiguity but carefully identifying the larger grid resolves that.)
An invalid solution for
because the bricks do not all align to the larger grid nor only occupy one cell of it.
A valid solution here is 3 blocks in a row:
And another valid solution involves 6 slabs:
...... 222222 333333 ......
So note that some input grids have multiple solutions.
An invalid solution for
because the bricks don't align to the larger grid. The slab would need to move left or right by one, but then of course the cover would be incomplete. This input grid has no solution.
Write a program that takes in (via stdin/command line) a rectangular block of text of
0's that represents a grid to be covered.
If there is a valid covering solution, print (via stdout) any one solution in the same manner as above, replacing all
0's with the appropriate
If there is no solution, your program should not output anything, just quietly end normally.
The input and output do not need to have the same rectangular dimensions. Your output can have extraneous rows and/or columns of all
.'s (as long as they don't invalidate the solution).
It's also alright to trim rows and column's of all
.'s if it won't affect the filled spaces. e.g.
is a valid solution to
Conversely, the two empty columns in
00..00could not be removed since that would disarrange the filled spaces.
You may optionally assume the input has a single trailing newline. A single trailing newline in the output is fine as well, even in the case of no solution.
Grids that are completely empty (all
.'s) and the trivial 0×0 grid are not input cases you need to worry about. But the 1×1
0grid is, as are all other grids that contain at least one
0. (You may not assume the width or height of the input grid is even!)
Instead of a program you may write a function that takes the input as a string argument and prints the output normally or returns it as a string. Any falsy value can be returned if there is no solution.
You may use any 9 distinct printable ASCII characters in place of
7. Just be sure to say what your substitutions were! Newlines must remain as is.
The shortest code in bytes wins. Tiebreaker is highest voted post.
This challenge was inspired by blocks, slabs, and stairs in Minecraft, which follow the same rules described here. If you enjoy PPCG and Minecraft, you may want to check out the PPCG Minecraft Server.