Tantangan ini didasarkan pada game Layerz.

Diberikan, pada stdin atau sebagai argumen fungsi, array sel 2D persegi panjang di mana setiap sel berisi salah satu kosong (Anda dapat memilih untuk menggunakan 0s daripada kosong tanpa penalti), 1, 2, 3, atau 4 ; temukan cara untuk membaginya menjadi wilayah yang valid (seperti yang didefinisikan di bawah) sehingga setiap sel yang tidak kosong dikandung oleh tepat satu wilayah. Kemudian, keluarkan solusi yang ditemukan dalam format apa pun yang masuk akal. Jika tidak ada solusi, baik berhenti tanpa menghasilkan output atau output nilai falsey tunggal kemudian berhenti.

Salah satu dari yang berikut ini merupakan wilayah yang valid:

• Sel tunggal yang mengandung 1
• Sel yang mengandung 2 dan persis salah satu tetangganya yang tidak kosong
• Sel yang mengandung 3 dan tepat dua tetangganya yang tidak kosong ortogonal
• Sebuah sel yang mengandung 4 dan tepatnya tiga tetangganya yang tidak kosong ortogonal

Ini adalah kode-golf , jadi jawaban tersingkat yang valid, dalam byte, menang.

Beberapa test case:

1. Yang agak sepele:

Dan ini solusinya, dengan masing-masing daerah dengan warna yang berbeda:

2. Yang lebih menarik

Yang ini memiliki lebih dari satu solusi, tetapi inilah salah satunya:

3. Yang lebih kecil, berisi yang kosong, yang tidak memiliki solusi (tergantung pada apakah Anda menggunakan salah satu dari keduanya untuk "menangkap" ketiganya, atau tiga untuk mengambil dua dari keduanya, Anda mungkin pergi dengan sepasang dua-dua atau dua yang tidak berdekatan (dan karena itu tidak dapat dikelompokkan) sendiri:

Karena kisi ini tidak memiliki solusi, program Anda harus berhenti tanpa menghasilkan keluaran apa pun ketika diberi kisi ini.

4. Yang ini (dengan 2 sel teratas bergeser ke kiri) memang memiliki solusi:

Larutan:

(Kanan bawah 2 digunakan untuk "menangkap" 3)

5. Karena kami membutuhkan test case dengan merangkak:

Satu solusi:

Saya tahu tantangan ini sudah lebih dari setahun, tetapi saya baru saja menemukan ini di "belum dijawab" dan terlihat cukup menarik bagi saya.

Dengan asumsi bahwa jumlah sel "root" adalah satu-satunya yang signifikan di setiap wilayah (dapat dikurangkan dari contoh-contoh), berikut ini adalah solusi backtracking saya:

Python 3 , 355 351 349 byte

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)

Cobalah online!

Format input adalah daftar 2D bilangan bulat, kosong sebagai nol, dan format output juga merupakan daftar 2D bilangan bulat yang mewakili satu wilayah per angka. Nomor wilayah dimulai pada satu; nol dicadangkan untuk sel kosong (seperti pada input). Jika input yang diberikan tidak dapat dipecahkan, fungsi mengembalikan nol tunggal (nilai falsy).

Misalnya, test case 5 adalah input as

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

dan hasilnya

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

Tidak disatukan, dengan komentar:

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)
 

Cobalah online!

Catatan: Ini adalah kasus khusus Set Packing yang terkenal sebagai NP-complete. Masalah khusus ini memiliki ukuran set terbatas (maks. 4) dan terdapat algoritma perkiraan untuk menemukan set packing "baik" dalam waktu polinomial, tetapi mereka tidak menjamin set seting maksimum yang dimungkinkan (yang sangat diperlukan dalam masalah ini).