12
1
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 code-golf, so the shortest valid answer, in bytes, wins.
Some test cases:
1. A rather trivial one:
And this is the solution, with each region in a different color:
2. A more interesting one
This one has more than one solution, but here's one of them:
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):
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:
Solution:
(The bottom right 2 is used to "capture" the 3)
5. Because we needed a test case with some fours:
One solution:
2It 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
4
s if those are valid input. – Martin Ender – 2016-11-23T12:12:04.5071does 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. – Eyal Lev – 2016-11-23T15:50:12.687
@EyalLev Only left-right-up-down. The top right 3 and its 2 neighbors constitute the region. – SuperJedi224 – 2016-11-23T20:15:41.923
@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? – Eyal Lev – 2016-11-27T11:35:29.573