Chaque programmeur sait que les rectangles □sont vraiment amusants. Pour exacerber ce plaisir, ces diagrammes mignons et flous peuvent être transformés en groupes de supports entrelacés.

Ce défi est l'inverse de mon précédent .

Disons que vous avez un groupe de rectangles imbriqués comme ceci:

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

Notes complémentaires:

• Aucun deux +ne sera jamais adjacent
• Deux rectangles ne partageront jamais un bord ou un coin
• Il n'y aura jamais plus d'un bord vertical dans chaque colonne

La première étape consiste à regarder le bord le plus à gauche de n'importe quel rectangle. Attribuez-lui l'un des quatre types de support ({[<. Je choisis [.

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

Regardez maintenant le deuxième rectangle le plus à gauche. Puisqu'il chevauche un [rectangle, il doit être d'un type différent. Je choisis (.

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

Le rectangle le plus à gauche suivant ne coupe aucun rectangle précédent, mais s'emboîte dans le précédent. Je choisis de l'attribuer à (nouveau. Il est normalement judicieux d'attribuer un rectangle du même type que celui dans lequel il est imbriqué si possible, mais parfois un retour en arrière est nécessaire.

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

Ce rectangle suivant peut être attribué à [nouveau.

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

Ce prochain rectangle est un peu amusant. Il coupe à la fois un (et un [rectangle, donc je pourrais l'appeler un {rectangle (ou <mais personne n'aime ça ).

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

Les deux derniers rectangles ne sont pas si mauvais. Ils peuvent être de deux types différents.

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

En lisant les rectangles, je comprends [(]([{))}]<{}>. Ce serait une sortie possible pour l'entrée ci-dessus. Voici une liste de nombreuses options possibles, non exhaustives:

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

Contribution

Rectangles de type ASCII, en supposant qu'ils sont sans ambiguïté (voir les notes ci-dessus) et peuvent être correctement convertis en une chaîne de crochets. Vous pouvez supposer qu'il n'y a aucun espace de fin ou être complété par un rectangle, avec une nouvelle ligne de fin facultative. Il n'y aura pas d'espace blanc de premier plan.

Sortie

L'une des chaînes de parenthèses valides qui obéit aux restrictions d'intersection des rectangles. Hormis une nouvelle ligne de fin facultative, il ne doit pas y avoir d'autres caractères que des crochets. La règle principale est que si deux carrés se croisent, il faut leur affecter différents types de parenthèses.

Objectif

C'est le code-golf, (manque de) quantité plutôt que qualité.

Python 3, 519 octets

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

Voici une première tentative de solution. L'algorithme utilisé regarde uniquement les coins du diagramme, abusant du fait qu'une seule ligne verticale peut apparaître dans une colonne, et donc le premier et le dernier + dans une colonne doivent être les coins d'un rectangle. Il recueille ensuite tous les rectangles et effectue une recherche naïve (et quelque peu non déterministe) de groupes sans collision. Je ne sais pas si cela trouvera toujours la solution la plus optimale, mais cela a fonctionné pour tous les exemples que j'ai essayés jusqu'à présent. Alternativement, il pourrait être remplacé par une recherche par force brute pour le moins de groupes.

Entrée: une chaîne contenant l'art ascii. Pas de nouvelle ligne de fin, et toutes les lignes doivent être remplies à la même longueur en utilisant des espaces. Il est également tout à fait correct de ne pas y mettre de ou de car il ne fait que regarder les coins.

Comme le golf est assez simple (juste la minimisation des espaces et le changement de nom des variables principalement), il pourrait probablement être plus court, mais comme il n'y a pas d'autres réponses à ce sujet, je vais le laisser comme ça pour l'instant.