Considere una cuadrícula bidimensional rectangular donde cada celda puede estar vacía ( .) o llena ( 0).

p.ej

..00....
0000....
.00000..
000...00
..000000
000.00..

La cuadrícula se considera infinita, todas las celdas fuera de la región representada están vacías.

El objetivo es cubrir los espacios llenos y dejar los espacios vacíos abiertos utilizando un conjunto de 7 ladrillos de formas distintas que ocupan 4 celdas (2 × 2) de la cuadrícula.

Estos son los 7 ladrillos:

• Bloques - 1 variante

  11
  11
  

• Losas - 2 variantes

  ..
  22

  33
  ..

• Escaleras - 4 variantes

  .4
  44

  5.
  55

  66
  .6

  77
  7.

Estos ladrillos siempre deben alinearse con una cuadrícula cuyas celdas son dos veces más anchas y altas que las celdas de la cuadrícula de entrada. Cada ladrillo solo puede ocupar una celda de esta cuadrícula más grande, pero la cuadrícula más pequeña se puede traducir (desplazada hacia arriba, abajo, izquierda, derecha) debajo de la cuadrícula más grande para dar más opciones para encontrar una cubierta. Ni las rejillas ni los ladrillos individuales pueden rotarse.

Entonces, una forma de cubrir (también conocido como resolver) el ejemplo anterior es así:

..11....
2211....
.47733..
447...22
..771133
227.11..

^{(Los ladrillos vecinos idénticos aún pueden causar ambigüedad, pero la identificación cuidadosa de la cuadrícula más grande lo resuelve).}

Una solución inválida para

000000
000000

es

566774
556744

porque no todos los ladrillos se alinean con la cuadrícula más grande ni solo ocupan una celda de ella.

Una solución válida aquí es 3 bloques seguidos:

111111
111111

Y otra solución válida involucra 6 losas:

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

Tenga en cuenta que algunas cuadrículas de entrada tienen múltiples soluciones .

Una solución inválida para

00.00
00...

es

11.33
11...

porque los ladrillos no se alinean con la cuadrícula más grande. La losa necesitaría moverse hacia la izquierda o hacia la derecha por una, pero luego, por supuesto, la cubierta estaría incompleta. Esta cuadrícula de entrada no tiene solución .

Desafío

Escriba un programa que tome (a través de stdin / línea de comando) un bloque rectangular de texto de .'sy 0' que representa una cuadrícula que se cubrirá.

Si hay una solución válida recubrimiento, impresión (a través de stdout) cualquier una solución de la misma manera que anteriormente, en sustitución de todos 0's con el apropiado 1a través de 7ladrillos.

Si no hay solución, su programa no debería generar nada, simplemente finalizar en silencio normalmente.

Notas

• La entrada y la salida no necesitan tener las mismas dimensiones rectangulares. Su salida puede tener filas y / o columnas extrañas de todos .(siempre que no invaliden la solución).

• También está bien recortar filas y columnas de todos .si no afecta los espacios rellenos. p.ej

  222222
  333333
  

  es una solución válida para

  000000
  000000
  

  Por el contrario, las dos columnas vacías 00..00no se pudieron eliminar, ya que eso desorganizaría los espacios rellenos.

• Opcionalmente, puede suponer que la entrada tiene una nueva línea final. Una nueva línea final en la salida también está bien, incluso en el caso de que no haya solución.

• Las cuadrículas que están completamente vacías (todas .) y la cuadrícula trivial 0 × 0 no son casos de entrada de los que deba preocuparse. Pero la 0cuadrícula 1 × 1 es, al igual que todas las otras cuadrículas que contienen al menos una 0. (¡No puede suponer que el ancho o la altura de la cuadrícula de entrada es par!)

• En lugar de un programa, puede escribir una función que tome la entrada como un argumento de cadena e imprima la salida normalmente o la devuelva como una cadena. Cualquier valor falso puede ser devuelto si no hay solución.

• Puede usar 9 caracteres ASCII imprimibles distintos en lugar de . 0 1 2 3 4 5 6 7. ¡Solo asegúrese de decir cuáles fueron sus sustituciones! Las nuevas líneas deben permanecer como están.

Puntuación

El código más corto en bytes gana. Tiebreaker es la publicación más votada.

^{Este desafío se inspiró en bloques , losas y escaleras en Minecraft , que siguen las mismas reglas descritas aquí. Si disfrutas de PPCG y Minecraft, es posible que desees consultar el servidor de Minecraft PPCG .}

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"

Explicación: Este es mi primer código de golf, por lo que podría no ser óptimo, pero así es como funciona. La función t (s) da el resultado para la cadena que se pasa. Primero, encuentra el número de columnas, luego pasa por las cuatro posibles traducciones distintas en 1 (ninguna, izquierda, arriba, arriba-izquierda) e intenta resolverlo para cada uno. Mira cada bloque de 2x2 y lo asigna a un número de bloque válido, dado por un diccionario, y cambia los ceros al número.

Si encuentra uno que no está en el diccionario, abandona ese desplazamiento específico y comienza de nuevo con el siguiente. Si pasa por los 4 desplazamientos sin encontrar una solución válida, termina sin generar nada. a (v, i) permite el valor predeterminado fuera de la cadena e ignora los caracteres de nueva línea. Aunque puede terminar con soluciones parciales a lo largo de la duración de la ejecución, siempre las anulará con la correcta final si existe.

Editar: se utiliza una asignación diferente de caracteres:. -> d, 0 -> z, todos los demás números van a sí mismos. Esto se aplica tanto a la entrada como a la salida.