13
\$\begingroup\$

Consider a rectangular two-dimensional grid where each cell can either be empty (.) or full (0).

e.g.

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

    11
    11
    
  • Slabs - 2 variants

    ..
    22
    33
    ..
  • Stairs - 4 variants

    .4
    44
    5.
    55
    66
    .6
    77
    7.

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

000000
000000

is

566774
556744

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:

111111
111111

And another valid solution involves 6 slabs:

......
222222
333333
......

So note that some input grids have multiple solutions.

An invalid solution for

00.00
00...

is

11.33
11...

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.

Challenge

Write a program that takes in (via stdin/command line) a rectangular block of text of .'s and 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 1 through 7 bricks.

If there is no solution, your program should not output anything, just quietly end normally.

Notes

  • 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.

    222222
    333333
    

    is a valid solution to

    000000
    000000
    

    Conversely, the two empty columns in 00..00 could 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 0 grid 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 . 0 1 2 3 4 5 6 7. Just be sure to say what your substitutions were! Newlines must remain as is.

Scoring

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.

\$\endgroup\$
  • 3
    \$\begingroup\$ It seems the Minecraft server is not implemented in Golf script - boring :-) \$\endgroup\$ – Thomas Weller Aug 23 '15 at 22:59
  • 5
    \$\begingroup\$ @ThomasWeller It was reimplemented in CJam to save a few bytes. \$\endgroup\$ – Alex A. Aug 24 '15 at 3:28
6
\$\begingroup\$

Python - 525 491 478 430 bytes

r=range
def t(s):
 m=s.find("\n")+1
 for q in r(4):
  try:
   for i in r(-q%2,m-1,2):
    for j in r(-q/2,len(s)/m,2):
     k,g=j*m+i,""
     b=[k,k+1,k+m,k+m+1]
     for z in b:g+=a(s,z)
     for z in b:
      if a(s,z)!="d":s=s[:z]+`dict(dddd=0,zzdd=3,ddzz=2,zzzd=7,zzdz=6,zdzz=5,dzzz=4,zzzz=1)[g]`+s[z+1:]
   return s
  except:d
def a(v,i):
 try:
  if v[i]!="\n":return v[i]
  return "d"
 except:return "d"

Explanation: This is my first code golf, so it might not be optimal, but here's how it works. The function t(s) gives the result for the string passed in. First, it finds the number of columns, then goes through the four possible distinct translations by 1 (none, left, up, up-left) and tries to solve it for each one. It looks at each 2x2 block and maps it to a valid block number, given by a dictionary, and changes the zeros to the number.

If it finds one not in the dictionary, it abandons that specific offset and starts over with the next one. If it goes through all 4 offsets without finding a valid solution, it ends without outputting anything. a(v, i) allows for the default value outside the string, and ignores newline characters. Although it may end up with partial solutions through the duration of the run, it will always override them with the final correct one if it exists.

Edit: A different mapping of characters is used: . -> d, 0 -> z, all other numbers go to themselves. This applies to both input and output.

\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to PPCG! We have some tips for golfing in Python; by which I think you can save some bytes. \$\endgroup\$ – lirtosiast Jan 20 '16 at 21:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.