Reverse Engineer Bracket Rechtecke

24

Jeder Programmierer weiß, dass Rechtecke wirklich Spaß machen. Um diesen Spaß zu verschärfen, können diese niedlichen und unscharfen Diagramme in Gruppen von verwobenen Klammern umgewandelt werden.

Diese Herausforderung ist das Gegenteil von meiner vorherigen .

Angenommen, Sie haben eine Gruppe von ineinandergreifenden Rechtecken wie folgt:

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

Zusätzliche Bemerkungen:

  • Es +werden niemals zwei nebeneinander sein
  • Keine zwei Rechtecke werden jemals eine Kante oder Ecke teilen
  • In jeder Spalte wird es immer höchstens eine vertikale Kante geben

Der erste Schritt besteht darin, den äußersten linken Rand eines Rechtecks ​​zu betrachten. Weisen Sie ihm einen von vier Klammertypen zu ({[<. Ich wähle [.

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

Schauen Sie sich nun das zweite Rechteck ganz links an. Da es ein [Rechteck überlappt , muss es von einem anderen Typ sein. Ich wähle (.

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

Das nächste am weitesten links stehende Rechteck schneidet kein vorheriges Rechteck, sondern verschachtelt sich innerhalb des vorherigen. Ich entscheide mich, es (erneut zuzuweisen . Normalerweise ist es ratsam, einem Rechteck den gleichen Typ zuzuweisen wie dem, in dem es verschachtelt ist, wenn möglich, aber manchmal ist ein Zurückverfolgen erforderlich.

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

Dieses nächste Rechteck kann erneut zugewiesen [werden.

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

Dieses nächste Rechteck macht ein bisschen Spaß. Es schneidet sowohl ein Rechteck (als auch ein [Rechteck, also könnte ich es ein {Rechteck nennen (oder <aber niemand mag diese).

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

Die letzten beiden Rechtecke sind nicht so schlimm. Sie können von zwei verschiedenen Typen sein.

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

Ich lese die Rechtecke ab [(]([{))}]<{}>. Dies wäre eine mögliche Ausgabe für die obige Eingabe. Hier ist eine Liste mit vielen möglichen Optionen, die nicht vollständig sind:

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

Eingang

ASCII-Art-Rechtecke, unter der Annahme, dass sie eindeutig sind (siehe Hinweise oben) und ordnungsgemäß in eine Reihe von Klammern umgewandelt werden können. Sie können entweder keine nachgestellten Leerzeichen oder ein Rechteck mit optionalen nachgestellten Zeilenumbrüchen annehmen. Es wird kein führendes Leerzeichen geben.

Ausgabe

Beliebige der gültigen Klammerzeichenfolgen, die die Schnittmengenbeschränkungen der Rechtecke einhalten. Abgesehen von einem optionalen nachgestellten Zeilenumbruch sollten keine anderen Zeichen als eckige Klammern verwendet werden. Die Hauptregel lautet: Wenn sich zwei Quadrate schneiden, sollten ihnen unterschiedliche Klammertypen zugewiesen werden.

Tor

Das ist Code-Golf, (Mangel an) Quantität über Qualität.

PhiNotPi
quelle
3
Zu Ihrer Information: "Verschärfen" bedeutet "eine schlechte Sache verschlimmern".
Paul R
@ Paul Ich glaube, das war der Punkt
Katze
Oh, ok, was auch immer der Punkt war, es ging mir direkt über den Kopf!
Paul R
Können wir annehmen, dass jedes Rechteck eine gewisse Höhe hat? dh es kann kein +für die linke obere Ecke haben, und dann (direkt darunter) das +für die linke untere Ecke?
Tersosauros

Antworten:

2

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

Hier ist ein erster Lösungsversuch. Der verwendete Algorithmus untersucht nur die Ecken im Diagramm und missbraucht dabei die Tatsache, dass in einer Spalte nur eine vertikale Linie auftreten kann. Daher müssen das erste und das letzte + in einer Spalte die Ecken eines Rechtecks ​​sein. Es sammelt dann alle Rechtecke und führt eine naive (und etwas nicht deterministische) Suche nach kollisionsfreien Gruppen durch. Ich bin mir nicht sicher, ob dies immer die optimale Lösung sein wird, aber es hat für alle Beispiele funktioniert, die ich bisher ausprobiert habe. Alternativ könnte es durch eine Brute-Force-Suche nach der geringsten Anzahl von Gruppen ersetzt werden.

Eingabe: Ein String, der die ASCII-Kunst enthält. Keine abschließenden Zeilenumbrüche, und alle Zeilen müssen mit Leerzeichen auf die gleiche Länge aufgefüllt werden. Es ist auch völlig in Ordnung, wenn Sie keine der | 's oder -'s dort hineinstecken, da es nur um die Ecken geht.

Da das Golfen recht einfach ist (meistens nur Whitespace-Minimierung und variable Umbenennung), könnte es möglicherweise kürzer sein, aber da es noch keine anderen Antworten gibt, lasse ich es vorerst so.

CensoredUsername
quelle
Sie bekommen das Kopfgeld, weil ich in <1 Tag keine anderen Antworten sehe. Vielen Dank für Ihre Antwort. Spielen Sie weiter!
22.