Diese Herausforderung basiert auf dem Spiel Layerz.

Gegeben, auf stdin oder als Funktionsargument, ein rechteckiges 2D-Array von Zellen, wobei jede Zelle entweder ein Leerzeichen (Sie können 0 anstelle von Leerzeichen ohne Strafe verwenden), eine 1, eine 2, eine 3 oder eine 4 enthält ; Finden Sie eine Möglichkeit, es in gültige Regionen (wie unten definiert) zu unterteilen, sodass jede nicht leere Zelle in genau einer Region enthalten ist. Geben Sie dann die gefundene Lösung in einem angemessenen Format aus. Wenn es keine Lösung gibt, stoppen Sie entweder, ohne eine Ausgabe zu erzeugen, oder geben Sie einen einzelnen Falsey-Wert aus, und stoppen Sie dann.

Jedes der folgenden Elemente stellt eine gültige Region dar:

• Eine einzelne Zelle mit einer 1
• Eine Zelle mit einer 2 und genau einem ihrer nicht leeren orthogonalen Nachbarn
• Eine Zelle mit einer 3 und genau zwei nicht leeren orthogonalen Nachbarn
• Eine Zelle, die 4 und genau drei ihrer nicht leeren orthogonalen Nachbarn enthält

Dies ist Codegolf , daher gewinnt die kürzeste gültige Antwort in Bytes.

Einige Testfälle:

1. Eine eher triviale:

Und das ist die Lösung, mit jeder Region in einer anderen Farbe:

2. Interessanter

Dieser hat mehr als eine Lösung, aber hier ist eine davon:

3. Ein kleineres, das Leerzeichen enthält und keine Lösung hat (je nachdem, ob Sie eines der beiden verwenden, um die drei zu "erfassen", oder die drei, um zwei der beiden zu nehmen, bleibt entweder ein Paar nicht benachbarter (und daher nicht gruppierbarer) Zweien oder eine einzelne Zwei für sich):

Da dieses Raster keine Lösungen enthält, sollte Ihr Programm angehalten werden, ohne dass eine Ausgabe erfolgt, wenn dieses Raster angegeben wird.

4. Diese (wobei die obersten 2 um eine Zelle nach links verschoben sind) hat jedoch eine Lösung:

Lösung:

(Die untere rechte 2 wird verwendet, um die 3 "einzufangen")

5. Weil wir einen Testfall mit ein paar Vieren brauchten:

Eine Lösung:

Ich weiß, dass diese Herausforderung über ein Jahr alt ist, aber ich fand sie einfach "unbeantwortet" und sah für mich ziemlich interessant aus.

Angenommen, die Nummer der "Root" -Zelle ist die einzige signifikante in jeder Region (aus den Beispielen ableitbar), dann ist hier meine Backtracking-Lösung:

Python 3 , 355 351 349 Bytes

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)

Probieren Sie es online!

Das Eingabeformat ist eine 2D-Liste von Ganzzahlen, Leerzeichen als Null, und das Ausgabeformat ist auch eine 2D-Liste von Ganzzahlen, die eine Region pro Zahl darstellen. Die Regionsnummer beginnt bei eins. Null ist für leere Zellen reserviert (wie bei der Eingabe). Wenn die angegebene Eingabe nicht lösbar ist, gibt die Funktion eine einzelne Null zurück (falscher Wert).

Beispielsweise wird der Testfall 5 als eingegeben

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

und die Ausgabe ist

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

Ungolfed, mit Kommentaren:

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)
 

Probieren Sie es online!

Hinweis: Dies ist ein Sonderfall der Set-Packung, die bekanntermaßen NP-vollständig ist. Dieses spezielle Problem hat eine begrenzte Satzgröße (max. 4) und es gibt Approximationsalgorithmen, um eine "gute" Satzpackung in Polynomzeit zu finden, aber sie garantieren nicht die maximal mögliche Satzpackung (die in diesem Problem unbedingt erforderlich ist).