To wyzwanie opiera się na grze Layerz.

Biorąc pod uwagę, jako argument stdin lub jako funkcję, prostokątny układ 2D komórek, w którym każda komórka zawiera albo puste (możesz użyć zer zamiast pustych miejsc bez kary), 1, 2, 3 lub 4 ; znaleźć sposób na podzielenie go na prawidłowe regiony (jak zdefiniowano poniżej), tak aby każda niepusta komórka była zawarta w dokładnie jednym regionie. Następnie wypisz znalezione rozwiązanie w dowolnym rozsądnym formacie. Jeśli nie ma rozwiązania, zatrzymaj się bez wytworzenia wyjścia lub wyjmij jedną wartość falsey, a następnie zatrzymaj.

Dowolne z poniższych stanowi prawidłowy region:

• Pojedyncza komórka zawierająca 1
• Komórka zawierająca 2 i dokładnie jeden z niepustych ortogonalnych sąsiadów
• Komórka zawierająca 3 i dokładnie dwa z niepustych ortogonalnych sąsiadów
• Komórka zawierająca 4 i dokładnie trzy z niepustych, ortogonalnych sąsiadów

To jest golf golfowy , więc wygrywa najkrótsza ważna odpowiedź w bajtach.

Niektóre przypadki testowe:

1. Raczej banalny:

Oto rozwiązanie, w którym każdy region ma inny kolor:

2. Bardziej interesujący

Ten ma więcej niż jedno rozwiązanie, ale oto jedno z nich:

3. Mniejszy, zawierający spacje, który nie ma żadnych rozwiązań (w zależności od tego, czy użyjesz jednej z dwójek, aby „złapać” trójkę, czy trójki, aby wziąć dwie dwójki, albo zostaniesz z para nieprzylegających [i dlatego nierozgrupowalnych] dwójek lub pojedynczych dwóch):

Ponieważ ta siatka nie ma rozwiązań, twój program powinien zatrzymać się bez generowania żadnych wyników, gdy otrzyma tę siatkę.

4. Ta (z górną 2 przesuniętą jedną komórką w lewo) ma jednak rozwiązanie:

Rozwiązanie:

(Prawy dolny 2 służy do „przechwytywania” 3)

5. Ponieważ potrzebowaliśmy skrzynki testowej z kilkoma czwórkami:

Jedno rozwiązanie:

Wiem, że to wyzwanie ma ponad rok, ale właśnie znalazłem to w „bez odpowiedzi” i wyglądało to dla mnie całkiem interesująco.

Zakładając, że liczba komórek „root” jest jedyną znaczącą w każdym regionie (można to wywnioskować z przykładów), oto moje rozwiązanie cofania:

Python 3 , 355 351 349 bajtów

from itertools import*
def f(a):
 D=len(a[0])+1;S={D*r+c for r in range(len(a))for c in range(D-1)if a[r][c]};s=[{x,*t}for x in S for t in combinations({x-D,x-1,x+1,x+D}&S,a[x//D][x%D]-1)]
 def B(s,S,d=1):
  if{0}>S:return a
  if[]==s:return 0
  h,*t=s
  if h<=S:
   for x in h:a[x//D][x%D]=d
  return h<=S and B(t,S-h,d+1)or B(t,S,d)
 return B(s,S)

Wypróbuj online!

Format wejściowy to dwuwymiarowa lista liczb całkowitych, spacje zerowe, a format wyjściowy to również dwuwymiarowa lista liczb całkowitych reprezentujących jeden region na liczbę. Numer regionu zaczyna się od pierwszego; zero jest zarezerwowane dla pustych komórek (jak na wejściu). Jeśli podanego wejścia nie można rozwiązać, funkcja zwraca pojedyncze zero (wartość falsy).

Na przykład przypadek testowy 5 jest wprowadzany jako

[[2,3,2],
 [3,4,3],
 [0,4,0],
 [3,3,3],
 [2,3,2],
 [0,3,0]]

i wynik jest

[[1,1,1],
 [2,2,2],
 [0,2,0],
 [3,4,5],
 [3,4,5],
 [0,4,0]]

Niegolfowany, z komentarzami:

from itertools import*
def f(a):
 # Rows, cols, fake-cols to prevent neighbors wrap around
 R,C=len(a),len(a[0]);D=C+1
 # All valid cells represented as integers
 S={D*r+c for r in range(R) for c in range(C) if a[r][c]}
 # All valid regions rooted at each cell
 s=[{x,*t} for x in S for t in combinations({x-D,x-1,x+1,x+D}&S,a[x//D][x%D]-1)]
 # Start backtracking
 return backtrack(a,s,S,D)

# a: array to fill in the region numbers
# s: current candidates of regions
# S: current remaining cells to cover
# D: constant from f
# d: recursion depth == group number in the result
def backtrack(a,s,S,D,d=1):
 # Empty S: the board is correctly covered, return the result
 if not S:return a
 # Empty s: no more candidate regions to use, return false
 if not s:return 0
 h,*t=s
 # h is not a subset of S: h is not a valid cover, try with the rest using same depth
 if not h<=S:return backtrack(a,t,S,D,d)
 # h is a valid cover, write d to the cells in h
 for x in h:a[x//D][x%D]=d
 return backtrack(a,t,S-h,D,d+1)or backtrack(a,t,S,D,d)
 

Wypróbuj online!

Uwaga: Jest to specjalny przypadek Pakowania Zestawów, który jest znany jako NP-complete. Ten konkretny problem ma ograniczony rozmiar zestawu (maks. 4) i istnieją algorytmy aproksymacyjne do znajdowania „dobrego” upakowania zestawu w czasie wielomianowym, ale nie gwarantują maksymalnego możliwego upakowania zestawu (co jest ściśle wymagane w tym problemie).