Code Golf Asked by SuperJedi224 on October 27, 2021
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:
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:
⎕CY'dfns'
{0≡a←X⊢b←⊃⍪/{v∊⍤1⊢⍵,x[(w[⍵]-1)cmat≢x←v∩⍵(+,-)↓0 2⊤⍳2]}∘⊂¨v←⍸×w←⍵:0⋄(b+.×⍨a×+a)@v⊢w}
-4 bytes thanks to @Adám. Improvements are:
x←...⋄...cmat≢x
→ ...cmat≢x←...
(-2 bytes)(+×⊢)a
→ a×+a
(-2 bytes)⎕CY'dfns'
{0≡a←X⊢b←⊃⍪/{x←v∩⍵(+,-)↓0 2⊤⍳2⋄v∊⍤1⊢⍵,x[(w[⍵]-1)cmat≢x]}∘⊂¨v←⍸×w←⍵:0⋄(b+.×⍨(+×⊢)a)@v⊢w}
Well, who would have imagined a language having Knuth's Algorithm X as a built-in library function? Algorithm X is an algorithm designed to solve Exact Cover problems, and the challenge here is exactly this kind of problem.
Now it just becomes a matter of constructing the constraint matrix (a boolean matrix whose columns represent constraints and rows represent actions that satisfy some of the constraints). Then X solves the problem by finding the collection of rows so that 1 appears exactly once per column.
⎕CY'dfns' ⍝ Load `cmat` and `X`
f←{
⍝ v←Coordinates of nonzero positions
v←⍸×w←⍵
⍝ Given an enclosed coord, generate constraint rows
Rowgen←{
⍝ Extract 4-way neighbors that are part of the board
x←v∩⍵(+,-)↓0 2⊤⍳2
↓0 2⊤⍳2 ⍝ Fancy way to say (0 1)(1 0)
⍵(+,-) ⍝ Input coord plus/minus 1 horizontally/vertically
v∩ ⍝ Set intersection with valid coords
⍝ Boolean matrix where each row represents a possible tile placement
⍝ and 1 marks the covered cells by that tile
v∊⍤1⊢⍵,x[(w[⍵]-1)cmat≢x]
(w[⍵]-1)cmat≢x ⍝ Possible combinations of neighbors
⍵,x[ ] ⍝ Index into x and prepend ⍵
v∊⍤1⊢ ⍝ Mark covered cells as 1
}
⍝ bmat←Constraint matrix; vertical concatenation of constraint rows
bmat←⊃⍪/Rowgen∘⊂¨v
⍝ ans←Solution by Algorithm X
ans←X bmat
⍝ Return 0 if answer not found (single zero)
0≡ans:0
⍝ Mark the pieces as distinct integers starting from 1
⍝ (increasing in the order of the root cell)
(bmat+.×⍨(+×⊢)ans)@v⊢w
(+×⊢)ans ⍝ Assign distinct numbers to 1 bits
⍝ 1 0 0 1 0 1 1 .. → 1 0 0 2 0 3 4 ..
bmat+.×⍨ ⍝ Extract associated numbers for all valid cells
( )@v⊢w ⍝ Overwrite valid cells of w with ^
}
Answered by Bubbler on October 27, 2021
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:
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)
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)
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).
Answered by Bubbler on October 27, 2021
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP