Prostokąty wspornika inżynierii wstecznej

24

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ść.

PhiNotPi
źródło
3
FYI „zaostrzyć” oznacza „pogorszyć coś złego”.
Paul R
@PaulR Myślę, że o to właśnie chodziło
kot
Och, OK, najwyraźniej bez względu na to, o co chodziło, przeleciał mi prosto nad głową!
Paul R
Czy możemy założyć, że każdy prostokąt ma pewną wysokość? tzn. nie może mieć znaku „ +za” w lewym górnym rogu, a następnie (bezpośrednio pod) w +lewym dolnym rogu?
Tersosauros

Odpowiedzi:

2

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.

CensoredUsername
źródło
Dostajesz nagrodę, ponieważ nie przewiduję żadnych innych odpowiedzi w ciągu <1 dnia. Dzięki za odpowiedź, kontynuuj grę w golfa!
Rɪᴋᴇʀ