Considérez une grille rectangulaire à deux dimensions où chaque cellule peut être vide ( .) ou pleine ( 0).

par exemple

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

La grille est considérée comme infinie, toutes les cellules en dehors de la région représentée sont vides.

Le but est de couvrir les espaces remplis et de laisser les espaces vides ouverts à l'aide d'un ensemble de 7 briques de forme distincte qui occupent chacune 4 cellules (2 × 2) de la grille.

Ce sont les 7 briques:

• Blocs - 1 variante

  11
  11
  

• Dalles - 2 variantes

  ..
  22

  33
  ..

• Escaliers - 4 variantes

  .4
  44

  5.
  55

  66
  .6

  77
  7.

Ces briques doivent toujours s'aligner sur une grille dont les cellules sont deux fois plus larges et hautes que les cellules de la grille d'entrée. Chaque brique ne peut occuper qu'une seule cellule de cette grille plus grande, mais la grille plus petite peut être translatée (décalée vers le haut, le bas, la gauche, la droite) sous la plus grande grille pour donner plus d'options pour trouver une couverture. Ni les grilles ni les briques individuelles ne peuvent être tournées.

Donc, une façon de couvrir (aka résoudre) l'exemple ci-dessus est comme ceci:

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

^{(Les briques voisines identiques peuvent toujours provoquer une ambiguïté, mais identifier soigneusement la grille plus grande résout cela.)}

Une solution invalide pour

000000
000000

est

566774
556744

parce que les briques ne s'alignent pas toutes sur la grille plus grande et n'occupent qu'une seule cellule de celle-ci.

Une solution valable ici est de 3 blocs consécutifs:

111111
111111

Et une autre solution valable implique 6 dalles:

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

Notez donc que certaines grilles d'entrée ont plusieurs solutions .

Une solution invalide pour

00.00
00...

est

11.33
11...

parce que les briques ne s'alignent pas sur la plus grande grille. La dalle aurait besoin de se déplacer de gauche à droite, mais bien sûr, la couverture serait incomplète. Cette grille d'entrée n'a pas de solution .

Défi

Écrivez un programme qui prend (via stdin / ligne de commande) un bloc rectangulaire de texte de .et 0qui représente une grille à couvrir.

S'il existe une solution de revêtement valide, imprimez (via stdout) une solution quelconque de la même manière que ci-dessus, en remplaçant toutes 0les solutions 1par les 7briques traversantes appropriées .

S'il n'y a pas de solution, votre programme ne devrait rien produire, il suffit de se terminer normalement.

Remarques

• L'entrée et la sortie n'ont pas besoin d'avoir les mêmes dimensions rectangulaires. Votre sortie peut avoir des lignes et / ou des colonnes superflues de tous .(tant qu'elles n'invalident pas la solution).

• Il est également possible de couper les lignes et les colonnes de tous .si cela n'affecte pas les espaces remplis. par exemple

  222222
  333333
  

  est une solution valable pour

  000000
  000000
  

  Inversement, les deux colonnes vides 00..00ne pouvaient pas être supprimées car cela désorganiserait les espaces remplis.

• Vous pouvez éventuellement supposer que l'entrée a une seule nouvelle ligne de fin. Une seule nouvelle ligne de fin dans la sortie convient également, même en cas d'absence de solution.

• Les grilles qui sont complètement vides (toutes .) et la grille triviale 0 × 0 ne sont pas des cas d'entrée dont vous devez vous inquiéter. Mais la 0grille 1 × 1 l' est, comme toutes les autres grilles qui en contiennent au moins une 0. (Vous ne pouvez pas supposer que la largeur ou la hauteur de la grille d'entrée est égale!)

• Au lieu d'un programme, vous pouvez écrire une fonction qui prend l'entrée comme argument de chaîne et imprime la sortie normalement ou la renvoie sous forme de chaîne. Toute valeur falsifiée peut être retournée s'il n'y a pas de solution.

• Vous pouvez utiliser 9 caractères ASCII imprimables distincts à la place de . 0 1 2 3 4 5 6 7. N'oubliez pas de dire quelles étaient vos substitutions! Les nouvelles lignes doivent rester telles quelles.

Notation

Le code le plus court en octets gagne. Tiebreaker est le poste le plus voté.

^{Ce défi a été inspiré par des blocs , des dalles et des escaliers dans Minecraft , qui suivent les mêmes règles que celles décrites ici. Si vous aimez PPCG et Minecraft, vous voudrez peut-être consulter le serveur PPCG Minecraft .}

Python - 525 491 478 430 octets

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"

Explication: Ceci est mon premier code de golf, donc il n'est peut-être pas optimal, mais voici comment cela fonctionne. La fonction t (s) donne le résultat de la chaîne passée. D'abord, elle trouve le nombre de colonnes, puis passe par les quatre traductions distinctes possibles par 1 (aucune, gauche, haut, haut-gauche) et essaie de le résoudre pour chacun. Il examine chaque bloc 2x2 et le mappe à un numéro de bloc valide, donné par un dictionnaire, et modifie les zéros en nombre.

S'il en trouve un qui n'est pas dans le dictionnaire, il abandonne ce décalage spécifique et recommence avec le suivant. S'il passe par les 4 décalages sans trouver de solution valide, il se termine sans rien produire. a (v, i) autorise la valeur par défaut en dehors de la chaîne et ignore les caractères de nouvelle ligne. Bien qu'il puisse aboutir à des solutions partielles pendant la durée de l'exécution, il les remplacera toujours par la dernière correcte si elle existe.

Edit: Un mappage différent des caractères est utilisé:. -> d, 0 -> z, tous les autres nombres vont à eux-mêmes. Cela s'applique à la fois à l'entrée et à la sortie.