Todo programador sabe que los rectángulos □son realmente divertidos. Para exacerbar esta diversión, estos diagramas lindos y difusos se pueden transformar en grupos de paréntesis entrelazados.

Este desafío es el inverso de mi anterior .

Digamos que tiene un grupo de rectángulos entrelazados como este:

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

Notas adicionales:

• No +habrá dos s adyacentes.
• Nunca dos rectángulos compartirán un borde o esquina
• Solo habrá como máximo un borde vertical en cada columna

El primer paso es mirar el borde más a la izquierda de cualquier rectángulo. Asigne uno de los cuatro tipos de soporte ({[<. Elijo [.

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

Ahora mira el segundo rectángulo más a la izquierda. Como se superpone a un [rectángulo, debe ser de un tipo diferente. Elijo (.

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

El siguiente rectángulo más a la izquierda no se cruza con ningún rectángulo anterior, sino que anida dentro del anterior. Elijo asignarlo (nuevamente. Normalmente es una buena suposición asignar un rectángulo del mismo tipo que anida dentro si es posible, pero a veces es necesario retroceder.

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

Este próximo rectángulo puede asignarse [nuevamente.

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

El siguiente rectángulo es divertido. Se cruza con ay (un [rectángulo, por lo que podría llamarlo un {rectángulo (o <pero a nadie le gustan).

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

Los dos últimos rectángulos no son tan malos. Pueden ser de dos tipos diferentes.

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

Leyendo los rectángulos, entiendo [(]([{))}]<{}>. Esta sería una salida posible para la entrada anterior. Aquí hay una lista de muchas opciones posibles, no exhaustivas:

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

Entrada

Rectángulos de arte ASCII, en el supuesto de que no sean ambiguos (véanse las notas anteriores) y que se puedan convertir correctamente en una cadena de corchetes. Puede suponer que no hay espacios finales o rellenados a un rectángulo, con una nueva línea opcional. No habrá espacios en blanco principales.

Salida

Cualquiera de las cadenas de paréntesis válidas que obedecen las restricciones de intersección de los rectángulos. Aparte de una nueva línea final opcional, no debe haber otros caracteres que los corchetes. La regla principal es, si dos cuadrados se cruzan, entonces se les debe asignar diferentes tipos de corchetes.

Gol

Esto es código-golf, (falta de) cantidad sobre calidad.

Python 3, 519 bytes

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

Aquí hay un primer intento de solución. El algoritmo utilizado simplemente mira las esquinas en el diagrama, abusando del hecho de que solo una línea vertical puede ocurrir en una columna y, por lo tanto, el primero y el último + en una columna deben ser las esquinas de un rectángulo. Luego recoge todos los rectángulos y realiza una búsqueda ingenua (y algo no determinista) de grupos sin colisiones. No estoy seguro de si esto siempre encontrará la solución más óptima, pero funcionó para todos los ejemplos que probé hasta ahora. Alternativamente, podría ser reemplazado por una búsqueda de fuerza bruta para la menor cantidad de grupos.

Entrada: una cadena que contiene el arte ascii. Sin nueva línea final, y todas las líneas deben rellenarse a la misma longitud utilizando espacios. También está completamente bien que no pongas ninguno de los | o 's allí ya que solo mira las esquinas.

Como el golf es bastante simple (solo minimización de espacios en blanco y cambio de nombre variable en su mayoría) probablemente podría ser más corto, pero como no hay otras respuestas sobre esto, lo dejaré así por ahora.