Татамибари решатель

10

Фон

Tatamibari - логическая головоломка, разработанная Николи.

Tatamibari головоломка играет на прямоугольной сетке с тремя различными видами символов в нем: +, -. и |. Решатель должен разбить сетку на прямоугольные или квадратные области в соответствии со следующими правилами:

  • Каждый раздел должен содержать ровно один символ.
  • +Символ должен содержаться в квадрате.
  • |Символ должен содержаться в виде прямоугольника с высотой , большей шириной.
  • -Символ должен содержаться в виде прямоугольника с шириной большей , чем высота.
  • Четыре пьесы никогда не могут использовать один и тот же угол. (Вот как обычно размещаются японские плитки татами.)

Ниже приведен пример головоломки с решением:

Пример головоломки татамибари Пример решения головоломки Tatamibari

задача

Решите данную головоломку татамибари.

Ввод, вывод

Вход представляет собой двумерную сетку, которая представляет заданную головоломку Tatamibari. Каждая ячейка содержит один из четырех символов: +, -, |, и характер вашего выбора , чтобы представить без подсказки клетки. В тестовых случаях используется звездочка *.

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

  • Список из 4 кортежей, где каждый кортеж включает верхний индекс, левый индекс, ширину и высоту прямоугольника (или любое эквивалентное представление)
  • Числовая сетка той же формы, что и входные данные, где каждое число представляет прямоугольник
  • Список наборов координат, где каждый набор включает в себя все координаты ячеек в прямоугольнике

Если у головоломки есть несколько решений, вы можете вывести любое число (одно или несколько) ее действительных решений. У входа гарантированно есть хотя бы одно решение.

Контрольные примеры

Puzzle:
|-*
*+|
*-*
Solution:
122
134
554
=====
Puzzle:
+***
**|*
*+**
***-
Solution:
1122
1122
3322
3344
======
Puzzle:
|*+*+
*****
****-
***+|
+****
Solution:
12233
12233
44444
55667
55667
=======
Puzzle:
****-**
**-**|*
*|*****
****-**
*******
**+*|**
*****+*
One possible solution:
1122222
1133344
1155544
1155544
6667744
6667788
6667788
===========
Puzzle:
*-****|+**
+*-******|
****+*****
*-******||
**++|*****
+****-|***
-****-**+*
********-*
|*+*+|****
*-*--**+*+
Solution:
1111122334
5666622334
7777822994
7777A2299B
CCDEA2299B
CCFFFFGGHH
IIIIJJGGHH
KLLMMNGGOO
KLLMMNGGPP
QQRRSSSTPP

правила

Применяются стандартные правила . Самый короткий код в байтах побеждает.

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

Ответы:

5

Python 2 , 417 374 366 байт

Ввод списка строк, ~для не-ключ. Выводит единственное решение для stderr в формате (x_start, width, y_start, height).

R=range
k=input()
X,Y=len(k[0]),len(k)
W,H=R(X),R(Y)
Q=[[]]
for q in Q:C=[(x,y)for(a,b,c,d)in q for x in(a,a+b)for y in(c,c+d)];max(map(C.count,C+W))<4>0<all(sum(w>x-s>-1<y-t<h<[c for r in k[t:t+h]for c in r[s:s+w]if'~'>c]==['+|-'[cmp(h,w)]]for(s,w,t,h)in q)==1for x in W for y in H)>exit(q);Q+=[q+[(s,w+1,t,h+1)]for s in W for w in R(X-s)for t in H for h in R(Y-t)]

Попробуйте онлайн! Это слишком неэффективно для предложенных тестовых случаев.


Ungolfed

grid = input()
total_width = len(grid[0])
total_height = len(grid)

partitions = [[]]

for partition in partitions:
    # list the corners of all rectangles in the current partition
    corners = [(x, y)
               for (start_x, width, start_y, height) in partition
               for x in (start_x, start_x + width)
               for y in (start_y, start_y + height)]
    # if no corners appears more than three times ...
    if corners != [] and max(map(corners.count, corners)) < 4:
        # .. and all fields are covered by a single rectangle ...
        if all(
                sum(width > x - start_x > -1 < y - start_y < height
                    for (start_x, width, start_y, height) in partition) == 1
                for x in range(total_width)
                for y in range(total_height)):
            # ... and all rectangles contain a single non-~
            # symbol that matches their shape:
            if all(
                [char for row in grid[start_y: start_y + height]
                    for char in row[start_x:start_x + width] if '~' > char]
                == ['+|-'[cmp(height, width)]]
                    for (start_x, width, start_y, height) in partition):
                # output the current partition and stop the program
                exit(partition)

    # append each possible rectangle in the grid to the current partition,
    # and add each new partition to the list of partitions.
    partitions += [partition + [(start_x, width + 1, start_y, height + 1)]
                   for start_x in range(total_width)
                   for width in range(total_width - start_x)
                   for start_y in range(total_height)
                   for height in range(total_height - start_y)]

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

овс
источник