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

Этот вызов обратен моему предыдущему .

Допустим, у вас есть группа взаимосвязанных прямоугольников, например:

   +------------+
   |            |
+--+-+     +----+-+
|  | |     |    | |
|  | | +---+--+ | |
|  | | |   |  | | |
+--+-+ | +-+--+-+-+-+
   |   | | |  | | | |
   |   | | |  | | | |
   |   | | |  | | | |    +-+
   |   +-+-+--+ | | |    | |
   |     | |    | | |  +-+-+-+
   +-----+-+----+ | |  | | | |
         | |      | |  | +-+ |
         | +------+ |  |     |
         |          |  |     |
         +----------+  +-----+

Дополнительные замечания:

• Нет двух +с никогда не будет смежным
• Никакие два прямоугольника никогда не разделят ребро или угол
• В каждом столбце будет только самое большее одно вертикальное ребро

Первый шаг - посмотреть на крайний левый край любого прямоугольника. Назначьте один из четырех типов скобок ({[<. Я выбираю [.

   +------------+
   |            |
[--+-]     +----+-+
[  | ]     |    | |
[  | ] +---+--+ | |
[  | ] |   |  | | |
[--+-] | +-+--+-+-+-+
   |   | | |  | | | |
   |   | | |  | | | |
   |   | | |  | | | |    +-+
   |   +-+-+--+ | | |    | |
   |     | |    | | |  +-+-+-+
   +-----+-+----+ | |  | | | |
         | |      | |  | +-+ |
         | +------+ |  |     |
         |          |  |     |
         +----------+  +-----+

Теперь посмотрите на второй левый прямоугольник. Поскольку он перекрывает [прямоугольник, он должен быть другого типа. Я выбираю (.

   (------------)
   (            )
[--(-]     +----)-+
[  ( ]     |    ) |
[  ( ] +---+--+ ) |
[  ( ] |   |  | ) |
[--(-] | +-+--+-)-+-+
   (   | | |  | ) | |
   (   | | |  | ) | |
   (   | | |  | ) | |    +-+
   (   +-+-+--+ ) | |    | |
   (     | |    ) | |  +-+-+-+
   (-----+-+----) | |  | | | |
         | |      | |  | +-+ |
         | +------+ |  |     |
         |          |  |     |
         +----------+  +-----+

Следующий крайний левый прямоугольник не пересекается ни с одним предыдущим прямоугольником, но вкладывается в предыдущий. Я решил назначить это (снова. Обычно целесообразно назначить прямоугольник того же типа, что и вложенный в него, если это возможно, но иногда требуется возврат.

   (------------)
   (            )
[--(-]     +----)-+
[  ( ]     |    ) |
[  ( ] (---+--) ) |
[  ( ] (   |  ) ) |
[--(-] ( +-+--)-)-+-+
   (   ( | |  ) ) | |
   (   ( | |  ) ) | |
   (   ( | |  ) ) | |    +-+
   (   (-+-+--) ) | |    | |
   (     | |    ) | |  +-+-+-+
   (-----+-+----) | |  | | | |
         | |      | |  | +-+ |
         | +------+ |  |     |
         |          |  |     |
         +----------+  +-----+

Этот следующий прямоугольник может быть назначен [снова.

   (------------)
   (            )
[--(-]     +----)-+
[  ( ]     |    ) |
[  ( ] (---+--) ) |
[  ( ] (   |  ) ) |
[--(-] ( [-+--)-)-+-]
   (   ( [ |  ) ) | ]
   (   ( [ |  ) ) | ]
   (   ( [ |  ) ) | ]    +-+
   (   (-[-+--) ) | ]    | |
   (     [ |    ) | ]  +-+-+-+
   (-----[-+----) | ]  | | | |
         [ |      | ]  | +-+ |
         [ +------+ ]  |     |
         [          ]  |     |
         [----------]  +-----+

Этот следующий прямоугольник довольно забавный. Он пересекает и a, (и [прямоугольник, поэтому я мог бы назвать его {прямоугольником (или <никому не нравящемуся).

   (------------)
   (            )
[--(-]     {----)-}
[  ( ]     {    ) }
[  ( ] (---{--) ) }
[  ( ] (   {  ) ) }
[--(-] ( [-{--)-)-}-]
   (   ( [ {  ) ) } ]
   (   ( [ {  ) ) } ]
   (   ( [ {  ) ) } ]    +-+
   (   (-[-{--) ) } ]    | |
   (     [ {    ) } ]  +-+-+-+
   (-----[-{----) } ]  | | | |
         [ {      } ]  | +-+ |
         [ {------} ]  |     |
         [          ]  |     |
         [----------]  +-----+

Последние два прямоугольника не так уж и плохи. Они могут быть двух разных типов.

   (------------)
   (            )
[--(-]     {----)-}
[  ( ]     {    ) }
[  ( ] (---{--) ) }
[  ( ] (   {  ) ) }
[--(-] ( [-{--)-)-}-]
   (   ( [ {  ) ) } ]
   (   ( [ {  ) ) } ]
   (   ( [ {  ) ) } ]    {-}
   (   (-[-{--) ) } ]    { }
   (     [ {    ) } ]  <-{-}->
   (-----[-{----) } ]  < { } >
         [ {      } ]  < {-} >
         [ {------} ]  <     >
         [          ]  <     >
         [----------]  <----->

Считывая прямоугольники, я получаю [(]([{))}]<{}>. Это будет один из возможных выходных данных для вышеуказанного ввода. Вот список многих возможных вариантов, не исчерпывающий:

[(]([{))}]<{}>
<(>(<{))}>{()}
{<}[{(]>)}[<>]
any of the 4! permutations of ([{<, you get the idea...

вход

Прямоугольники ASCII-art, исходя из предположения, что они однозначны (см. Примечания выше) и могут быть надлежащим образом преобразованы в строку скобок. Вы можете предполагать, что либо нет завершающих пробелов, либо добавлен прямоугольник с необязательным завершающим символом новой строки. Там не будет ведущих пробелов.

Выход

Любая из допустимых строк скобок, которая подчиняется ограничениям пересечения прямоугольников. Кроме необязательного завершающего символа новой строки, в скобках не должно быть других символов. Основное правило: если два квадрата пересекаются, то им должны быть назначены разные типы скобок.

Цель

Это код-гольф, (недостаток) количество за качество.

Python 3, 519 байт

def c(i):
 a,b,c,d={},0,[],{}
 for e in map("".join,zip(*i.split("\n"))):
  if"+"in e:
   f=e.index("+"),e.rindex("+")
   if f in a:j=a.pop(f);d[j]=f+(d[j],len(c));c.append(j)
   else:a[f]=b;d[b]=len(c);c.append(b);b+=1
 g,h={},0
 while d:
  i={list(d)[0]};
  for j,(k,l,m,n)in d.items():
   for(o,p,q,r)in(d[v]for v in i):
    if not(m>r or n<q or k>p or l<o or(q<m<n<r and o<k>l<p)):break
   else:i.add(j)
  for j in i:del d[j];g[j]=h
  h+=1
 s,u=set(),""
 for t in c:u+="[{(<]})>"[g[t]+4*(t in s)];s.add(t)
 return u

Вот первая попытка решения. Используемый алгоритм просто рассматривает углы на диаграмме, злоупотребляя тем фактом, что в столбце может быть только одна вертикальная линия, и поэтому первый и последний + в столбце должны быть углами прямоугольника. Затем он собирает все прямоугольники и выполняет наивный (и несколько недетерминированный) поиск групп без столкновений. Я не уверен, что это всегда найдет самое оптимальное решение, но оно работало для всех примеров, которые я пробовал до сих пор. В качестве альтернативы он может быть заменен перебором наименьшего количества групп.

Вход: строка, содержащая ascii art. Никакого завершающего символа новой строки нет, и все строки должны быть дополнены до одинаковой длины пробелами. Это также совершенно нормально, если вы не помещаете туда ни один из «или», поскольку он просто смотрит на углы.

Поскольку игра в гольф довольно проста (только минимизация пробелов и в основном переименование переменных), она, вероятно, может быть короче, но поскольку пока нет других ответов на этот вопрос, я пока оставлю это так.