Сгруппируйте эти клетки!

12

Эта задача основана на игре Layerz.

Учитывая, в stdin или в качестве аргумента функции, 2D прямоугольный массив ячеек, где каждая ячейка содержит либо пробел (вы можете использовать 0 вместо пробелов без штрафа), 1, 2, 3 или 4 ; найдите способ разделить его на допустимые области (как определено ниже) так, чтобы каждая непустая ячейка содержалась ровно в одной области. Затем выведите найденное решение в любом приемлемом формате. Если решения не существует, либо прекратите работу, не создавая выходных данных, либо выведите одно значение фальси, затем остановите.

Любое из следующего составляет допустимый регион:

  • Отдельная ячейка, содержащая 1
  • Ячейка, содержащая 2 и ровно один из ее непустых ортогональных соседей
  • Ячейка, содержащая 3 и ровно два из ее непустых ортогональных соседей
  • Ячейка, содержащая 4 и ровно три из ее непустых ортогональных соседей

Это , поэтому самый короткий действительный ответ в байтах выигрывает.

Некоторые тестовые случаи:

1. Довольно тривиально:

введите описание изображения здесь

И это решение, где каждый регион имеет свой цвет:

введите описание изображения здесь

2. Более интересный

введите описание изображения здесь

У этого есть более одного решения, но вот одно из них:

введите описание изображения здесь

3. Меньший, содержащий пробелы, который не имеет никаких решений (в зависимости от того, используете ли вы одну из двойок, чтобы «захватить» тройку, или тройку, чтобы взять две из двойок, у вас либо останется пара несмежных (и, следовательно, не группируемых) пар или две пары самостоятельно):

введите описание изображения здесь

Поскольку эта сетка не имеет решений, ваша программа должна останавливаться без вывода каких-либо данных при наличии этой сетки.

4. Этот (с двумя верхними смещенными на одну ячейку влево) имеет решение, хотя:

введите описание изображения здесь

Решение:

введите описание изображения здесь

(Внизу справа 2 используется для «захвата» 3)

5. Потому что нам нужен был тестовый пример с несколькими четверками:

Одно из решений:

SuperJedi224
источник
2
Было бы полезно, если бы существовали ASCII-версии тестовых примеров, чтобы людям не приходилось их все печатать, и тестовые примеры также должны охватывать 4s, если они являются действительными входными данными.
Мартин Эндер
1
означает ортогональные соседи только слева направо вверх или диагонали? если только слева направо вверх, то почему 3 находится в той же области, что и два других 3? один из них не является ортогональным соседом.
Эяль Лев
@EyalLev Только влево-вправо-вверх-вниз. Верхний правый 3 и 2 его соседа составляют регион.
SuperJedi224
@ SuperJedi224 справа вверху 3, и это два соседа составляют действительный регион, да, но эти соседи этого не делают. регион не должен быть «закрытым»? т.е. каждый член в регионе должен быть действительным членом этого региона?
Эяль Лев

Ответы:

3

Я знаю, что этому вызову больше года, но я нашел это в «без ответа» и выглядел довольно интересным для меня.

Предполагая, что номер «корневой» ячейки является единственным значимым в каждой области (выводим из примеров), вот мое решение для отслеживания:

Python 3 , 355 351 349 байт

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)

Попробуйте онлайн!

Входной формат представляет собой двумерный список целых чисел, пробелы равны нулю, а выходной формат также представляет собой двумерный список целых чисел, представляющих одну область на число. Номер региона начинается с единицы; ноль зарезервирован для пустых ячеек (как на входе). Если данный вход неразрешим, функция возвращает один ноль (ложное значение).

Например, тестовый пример 5 вводится как

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

и вывод

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

Ungolfed, с комментариями:

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)
 

Попробуйте онлайн!

Примечание. Это особый случай комплектной упаковки, которая, как известно, является NP-полной. Эта конкретная проблема имеет ограниченный размер набора (макс. 4) и существуют алгоритмы аппроксимации, чтобы найти «хорошую» упаковку наборов за полиномиальное время, но они не гарантируют максимально возможную упаковку наборов (что строго необходимо в этой задаче).

фонтанчик для питья
источник