Każdy programista wie, że prostokąty □są naprawdę zabawne. Aby zaostrzyć tę zabawę, te urocze i rozmyte diagramy można przekształcić w grupy przeplatanych nawiasów.

To wyzwanie jest odwrotnością mojego poprzedniego .

Załóżmy, że masz grupę blokujących się prostokątów:

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

Dodatkowe uwagi:

• Nigdy nie +będzie dwóch sąsiadujących ze sobą
• Żadne dwa prostokąty nigdy nie będą miały krawędzi ani narożnika
• W każdej kolumnie będzie zawsze tylko jedna pionowa krawędź

Pierwszym krokiem jest spojrzenie na lewą krawędź dowolnego prostokąta. Przypisz jeden z czterech typów wsporników ({[<. Wybiorę [.

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

Teraz spójrz na drugi prostokąt najbardziej po lewej stronie. Ponieważ zachodzi na [prostokąt, musi być innego typu. Wybiorę (.

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

Następny prostokąt znajdujący się najbardziej po lewej stronie nie przecina się z żadnym poprzednim prostokątem, ale zagnieżdża się w poprzednim. Wybieram przypisanie go (ponownie. Zazwyczaj dobrym pomysłem jest przypisanie prostokąta tego samego typu co to, co jest zagnieżdżone, jeśli to możliwe, ale czasami konieczne jest cofnięcie.

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

Ten następny prostokąt można przypisać [ponownie.

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

Ten następny prostokąt jest trochę zabawny. Przecina on zarówno prostokąt, jak (i [prostokąt, więc mógłbym nazwać go {prostokątem ( <ale nikomu się to nie podoba).

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

Dwa ostatnie prostokąty nie są takie złe. Mogą być dowolnych dwóch różnych typów.

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

Czytam prostokąty [(]([{))}]<{}>. Byłby to jeden z możliwych wyników dla powyższego wejścia. Oto lista wielu możliwych opcji, które nie są wyczerpujące:

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

Wkład

Prostokąty ASCII-art, przy założeniu, że są jednoznaczne (patrz uwagi powyżej) i można je poprawnie przekształcić w ciąg nawiasów. Możesz założyć, że nie ma spacji końcowych lub jest wypełniony prostokątem, z opcjonalnym końcowym znakiem nowej linii. Nie będzie wiodących białych znaków.

Wydajność

Dowolny prawidłowy ciąg nawiasów, który spełnia ograniczenia przecięcia prostokątów. Poza opcjonalnym końcowym znakiem nowej linii nie powinno być innych znaków niż nawiasy. Główną zasadą jest, że jeśli dwa kwadraty przecinają się, należy im przypisać różne typy nawiasów.

Cel

To jest golf golfowy (brak) ilości ponad jakość.

Python 3, 519 bajtów

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

Oto pierwsza próba rozwiązania. Zastosowany algorytm czysto patrzy na rogi na schemacie, nadużywając faktu, że tylko jedna pionowa linia może wystąpić w kolumnie, a zatem pierwszy i ostatni + w kolumnie muszą być narożnikami prostokąta. Następnie zbiera wszystkie prostokąty i przeprowadza naiwne (i nieco niedeterministyczne) wyszukiwanie grup bezkolizyjnych. Nie jestem pewien, czy to zawsze znajdzie najbardziej optymalne rozwiązanie, ale zadziałało we wszystkich przykładach, które próbowałem do tej pory. Alternatywnie można go zastąpić poszukiwaniami siłowymi dla najmniejszej liczby grup.

Dane wejściowe: ciąg zawierający sztukę ascii. Brak nowej linii i wszystkie linie muszą być wypełnione do tej samej długości za pomocą spacji. Jest również całkowicie w porządku, gdy nie umieszczasz żadnego z nich, ponieważ patrzy tylko na rogi.

Ponieważ gra w golfa jest dość prosta (po prostu minimalizacja białych znaków i zmienna zmiana nazwy) może być prawdopodobnie krótsza, ale ponieważ nie ma na to innych odpowiedzi, na razie zostawię to w ten sposób.