12
\$\begingroup\$

This challenge is based on the game Layerz.

Given, on stdin or as a function argument, a 2D rectangular array of cells where each cell contains either a blank (you may choose to use 0s instead of blanks at no penalty), a 1, a 2, a 3, or a 4; find a way to divide it into valid regions (as defined below) such that each non-blank cell is contained by exactly one region. Then, output the solution found in any reasonable format. If there is no solution, either halt without producing output or output a single falsey value then halt.

Any of the following constitutes a valid region:

  • A single cell containing a 1
  • A cell containing a 2 and exactly one of its non-blank orthogonal neighbors
  • A cell containing a 3 and exactly two of its non-blank orthogonal neighbors
  • A cell containing a 4 and exactly three of its non-blank orthogonal neighbors

This is , so the shortest valid answer, in bytes, wins.

Some test cases:

1. A rather trivial one:

enter image description here

And this is the solution, with each region in a different color:

enter image description here

2. A more interesting one

enter image description here

This one has more than one solution, but here's one of them:

enter image description here

3. A smaller one, containing blanks, that doesn't have any solutions (depending on whether you use one of the twos to "capture" the three, or the three to take two of the twos, you're either left with a pair of nonadjacent [and therefore nongroupable] twos or a single two on its own):

enter image description here

Because this grid has no solutions, your program should halt without producing any output when given this grid.

4. This one (with the top 2 shifted one cell to the left) does have a solution though:

enter image description here

Solution:

enter image description here

(The bottom right 2 is used to "capture" the 3)

5. Because we needed a test case with some fours:

One solution:

\$\endgroup\$
  • 2
    \$\begingroup\$ It would be helpful if there were ASCII versions of the test cases so people don't have to type them all up, and the test cases should also cover 4s if those are valid input. \$\endgroup\$ – Martin Ender Nov 23 '16 at 12:12
  • 1
    \$\begingroup\$ does orthogonal neighbors means only left right up down, or also the diagonals? if only left right up down, how come the 3 is in the same region as the other two 3's? one of them is not an orthogonal neighbor. \$\endgroup\$ – Eyal Lev Nov 23 '16 at 15:50
  • \$\begingroup\$ @EyalLev Only left-right-up-down. The top right 3 and its 2 neighbors constitute the region. \$\endgroup\$ – SuperJedi224 Nov 23 '16 at 20:15
  • \$\begingroup\$ @SuperJedi224 the top right 3 and it's two neighbors constitute a valid region, yes, but those neighbors do not. doesn't a region have to be a "closed set"? i.e. every member in the region must be a valid member of that region? \$\endgroup\$ – Eyal Lev Nov 27 '16 at 11:35
3
\$\begingroup\$

I know this challenge is over an year old, but I just found this in "unanswered" and looked quite interesting to me.

Assuming that the "root" cell's number is the only significant one in each region (deducible from the examples), here is my backtracking solution:

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)

Try it online!

The input format is a 2D list of integers, blanks as zero, and the output format is also a 2D list of integers representing one region per number. The region number starts at one; zero is reserved for blank cells (as in input). If the given input is unsolvable, the function returns single zero (falsy value).

For example, the test case 5 is input as

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

and the output is

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

Ungolfed, with comments:

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)
 

Try it online!

Note: This is a special case of Set Packing which is well-known to be NP-complete. This specific problem has limited set size (max. 4) and there exist approximation algorithms to find "good" set packing in polynomial time, but they don't guarantee the maximum possible set packing (which is strictly required in this problem).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.