Rozważ prostokątną dwuwymiarową siatkę, w której każda komórka może być pusta ( .) lub pełna ( 0).

na przykład

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

Siatka jest uważana za nieskończoną, wszystkie komórki poza przedstawionym regionem są puste.

Celem jest zakrycie wypełnionych przestrzeni i pozostawienie pustych przestrzeni otwartych za pomocą zestawu 7 wyraźnie ukształtowanych klocków, z których każda zajmuje 4 komórki (2 × 2) siatki.

Oto 7 cegieł:

• Bloki - 1 wariant

  11
  11
  

• Płyty - 2 warianty

  ..
  22

  33
  ..

• Schody - 4 warianty

  .4
  44

  5.
  55

  66
  .6

  77
  7.

Cegły te muszą zawsze być wyrównane do siatki, której komórki są dwa razy szersze i wyższe niż komórki siatki wejściowej. Każda cegła może zajmować tylko jedną komórkę tej większej siatki, ale mniejszą siatkę można przełożyć (przesunąć w górę, w dół, w lewo, w prawo) pod większą siatką, aby uzyskać więcej opcji znalezienia osłony. Ani kraty, ani pojedyncze cegły nie mogą być obracane.

Tak więc jednym ze sposobów pokrycia (czyli rozwiązania) powyższego przykładu jest następujący:

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

^{(Identyczne sąsiadujące cegły mogą nadal powodować niejednoznaczność, ale dokładne zidentyfikowanie większej siatki rozwiązuje ten problem).}

Nieprawidłowe rozwiązanie

000000
000000

jest

566774
556744

ponieważ cegły nie wszystkie wyrównują się do większej siatki, ani nie zajmują tylko jednej jej komórki.

Prawidłowym rozwiązaniem są tutaj 3 bloki z rzędu:

111111
111111

Inne ważne rozwiązanie obejmuje 6 płyt:

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

Należy pamiętać, że niektóre siatki wejściowe mają wiele rozwiązań .

Nieprawidłowe rozwiązanie

00.00
00...

jest

11.33
11...

ponieważ cegły nie wyrównują się z większą siatką. Płyta musiałaby przesuwać się w lewo lub w prawo o jeden, ale wtedy oczywiście osłona byłaby niepełna. Ta siatka wejściowa nie ma rozwiązania .

Wyzwanie

Napisz program, który pobiera (za pomocą linii stdin / wiersza poleceń) prostokątny blok tekstu .i 0reprezentujący siatkę, która ma zostać pokryta.

Jeżeli nie jest ważne rozwiązanie pokrycia, druku (poprzez wyjścia) dowolnego jednego roztworu w taki sam sposób, jak wyżej, zastępując wszystkie 0„S z odpowiednio 1poprzez 7cegły.

Jeśli nie ma rozwiązania, twój program nie powinien nic wypisywać, po prostu cicho się normalnie kończy.

Notatki

• Dane wejściowe i wyjściowe nie muszą mieć takich samych prostokątnych wymiarów. Twój wynik może zawierać niepotrzebne wiersze i / lub kolumny wszystkich .(o ile nie unieważniają rozwiązania).

• Można również przycinać wiersze i kolumny wszystkich ., jeśli nie wpłynie to na wypełnione pola. na przykład

  222222
  333333
  

  jest poprawnym rozwiązaniem

  000000
  000000
  

  I odwrotnie, dwóch pustych kolumn 00..00nie można było usunąć, ponieważ spowodowałoby to nieporządek w wypełnionych przestrzeniach.

• Opcjonalnie możesz założyć, że dane wejściowe mają pojedynczy znak nowej linii. Pojedynczy końcowy znak nowej linii jest również w porządku, nawet w przypadku braku rozwiązania.

• Siatki całkowicie puste (wszystkie .) i banalna siatka 0 × 0 nie są przypadkami wejściowymi, o które musisz się martwić. Ale 0siatka 1 × 1 jest, podobnie jak wszystkie inne siatki, które zawierają co najmniej jedną 0. (Nie możesz zakładać, że szerokość lub wysokość siatki wejściowej jest równa!)

• Zamiast programu możesz napisać funkcję, która pobiera dane wejściowe jako argument łańcucha i wypisuje dane wyjściowe normalnie lub zwraca je jako ciąg znaków. Każda wartość fałszowania może zostać zwrócona, jeśli nie ma rozwiązania.

• Możesz użyć dowolnych 9 różnych drukowalnych znaków ASCII zamiast . 0 1 2 3 4 5 6 7. Po prostu powiedz, jakie były twoje zamiany! Nowe linie muszą pozostać bez zmian.

Punktacja

Najkrótszy kod w bajtach wygrywa. Tiebreaker to najwyżej oceniany post.

^{Wyzwanie to zostało zainspirowane klockami , płytami i schodami w grze Minecraft , które są zgodne z tymi samymi zasadami opisanymi tutaj. Jeśli lubisz PPCG i Minecraft, możesz wypróbować PPCG Minecraft Server .}

Python - 525 491 478 430 bajtów

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"

Objaśnienie: To jest mój pierwszy golfowy kod, więc może nie być optymalny, ale oto jak to działa. Funkcja t (s) podaje wynik dla przekazanego ciągu. Najpierw wyszukuje liczbę kolumn, a następnie przechodzi przez cztery możliwe różne tłumaczenia o 1 (brak, lewo, góra, góra lewo) i próbuje je rozwiązać dla każdego. Sprawdza każdy blok 2x2 i odwzorowuje go na prawidłowy numer bloku podany przez słownik i zmienia zera na liczbę.

Jeśli znajdzie takiego, którego nie ma w słowniku, porzuca to określone przesunięcie i zaczyna od następnego. Jeśli przejdzie przez wszystkie 4 przesunięcia bez znalezienia prawidłowego rozwiązania, zakończy się bez wypisania niczego. a (v, i) dopuszcza wartość domyślną poza ciągiem i ignoruje znaki nowej linii. Chociaż w trakcie przebiegu może kończyć się częściowymi rozwiązaniami, zawsze zastąpi je ostatecznym poprawnym, jeśli istnieje.

Edycja: używane jest inne mapowanie znaków:. -> d, 0 -> z, wszystkie inne liczby idą do siebie. Dotyczy to zarówno wejścia, jak i wyjścia.