Drehen Sie eine Schnur um

21

Eine ausgeglichene Zeichenfolge ist eine Folge von Klammern, ()sodass jede Klammer mit einer anderen übereinstimmen kann. Strenger sind dies die Zeichenketten, die von dieser Grammatik umspannt werden:

S → (S)S | ε

Wir können eine Zeichenfolge "von links" drehen, indem wir:

  • Alle Vorkommen von (und )miteinander wechseln

  • Verschieben von Zeichen von der Vorderseite der Zeichenfolge nach hinten, bis die Zeichenfolge wieder ausgeglichen ist.


Lass uns ein Beispiel machen.

Wir beginnen mit der ausgeglichenen Saite:

(()(())())

Wir tauschen dann die Parens um zu machen

))())(()((

Verschieben Sie dann die Zeichen von der Vorderseite der Zeichenfolge zur Rückseite der Zeichenfolge, bis die Zeichenfolge ausgeglichen ist.

))())(()((
)())(()(()
())(()(())
))(()(())(
)(()(())()
(()(())())

Das ist unser Ergebnis!


Beachten Sie, dass einige Zeichenfolgen auf mehrere Arten umgedreht werden können, z. B. die Zeichenfolge

(()())

Wenn umgekehrt, kann entweder sein:

()(())

oder

(())()

Jeder String hat jedoch mindestens eine Lösung .

Aufgabe

Schreiben Sie ein Programm, um eine ausgeglichene Zeichenfolge als Eingabe und Ausgabe zu verwenden. In Fällen, in denen es mehrere gültige Ausgaben geben kann, müssen Sie nur eine davon ausgeben. Sie können eine andere Klammer Typ verwenden ( <>, []oder {}) , wenn Sie dies wünschen.

Da dies ein Wettbewerb ist, sollten Sie versuchen, die Größe Ihres Quellcodes, gemessen in Bytes, zu minimieren.

Testfälle

(()())     -> ()(()), (())()
(()(())()) -> (()(())())
((())())() -> (()(()()))
Weizen-Assistent
quelle
Ist garantiert, dass es immer eine Lösung gibt?
Luis Mendo
@ LuisMendo Ja, das habe ich bewiesen. Wenn Sie den Beweis sehen möchten, können Sie mich gerne im Chat anpingen.
Weizen-Assistent
Vielen Dank. Es reicht mir, das zu wissen. Vielleicht sollten Sie es in die Herausforderung schreiben, sonst müssten Sie definieren, was ausgegeben werden soll, wenn keine Lösung
Luis Mendo
related
officialaimm

Antworten:

9

Haskell , 124 120 119 117 113 110 109 106 105 104 101 98 Byte

4 Bytes gespart dank bartavelle!

3 Bytes gespart dank Zgarb

1 Byte gespart dank Peter Taylor

Hier ist eine Lösung, die ich in Haskell ausgearbeitet habe. Es ist jetzt in Ordnung, dank einiger Hilfe, die ich erhalten habe, ziemlich gut, aber ich versuche, dies zu verkürzen, daher sind Feedback / Vorschläge willkommen.

until(!0)g.map d
_!1=1<0
('(':a)!x=a!(x-1)
(_:a)!x=a!(x+1)
_!_=1>0
g(a:b)=b++[a]
d '('=')'
d _='('

Probieren Sie es online!

Erläuterung

Dieses Programm definiert 4 Funktionen, wobei die erste (!)bestimmt, ob eine Saite ausgeglichen ist. Es ist wie folgt definiert:

_!1=1<0
('(':a)!x=a!(x-1)
(_:a)!x=a!(x+1)
_!_=1>0

Bei dieser Überprüfung wird angenommen, dass die Eingabe dank eines Vorschlags von Peter Taylor die gleiche Anzahl offener und geschlossener Parens aufweist.

Der nächste gdreht die Saite einmal.

g(a:b)=b++[a]

Dann haben wir, dwas einfach ein Paren nimmt und es spiegelt

d '('=')'
d _='('

Endlich haben wir die Funktion, mit der wir uns befassen. Hier verwenden wir eine punktfreie Darstellung von until(!0)gkomponiert mit map d, die dauf die Eingabe abgebildet und angewendet wird , gbis das Ergebnis ausgeglichen ist. Dies ist der genaue Vorgang, der in der Frage beschrieben wird.

until(!0)g.map d
Weizen-Assistent
quelle
1
Sie können ein paar Bytes g x@(a:b)|x!0=x|1>0=g$b++[a]verschrotten und die Parens entfernen d '('=')'.
Bartavelle
@bartavelle Das Entfernen der Parens für dverursacht einen Compilerfehler, glauben Sie mir, ich habe es versucht. Aber der erste Vorschlag ist willkommen. Vielen Dank!
Weizen-Assistent
1
Sie können ein weiteres Byte speichern, !da Sie keine Fälle behandeln müssen, in denen die Zeichenfolge eine ungleiche Anzahl offener und geschlossener Klammern enthält. Sie können also die ersten beiden Fälle tauschen und haben_!1=1<0 []!_=0<1
Peter Taylor
1
Verwenden Sie until, um zu verkürzen g: TIO
Zgarb
2
Ich denke, es sollte eine anständige Ersparnis geben, indem man eine dKarte '('an (-1)und irgendetwas anderes anfertigt 1, und dann können die zwei längsten Fälle von !zu kombiniert werden (i:a)!x=a!(x+i). Die Struktur der obersten Ebene muss dann überarbeitet werden, um map ddie untilBedingung zu erfüllen, und ich muss rennen, damit ich jetzt keine Zeit habe, herauszufinden, welche Kombinatoren erforderlich sind, um alles zusammenzukleben.
Peter Taylor
7

SOGL V0.12 , 12 11 Bytes

↔]»:l{Ƨ()øŗ

Probieren Sie es hier aus!

Erläuterung:

↔            mirror characters
 ]           do ... while the top of stack is truthy
  »            put the last letter at the start
   :           duplicate it
    l{         length times do
      Ƨ()        push "()"
         ø       push ""
          ŗ      replace ["()" with ""]
             if the string left on stack is empty (aka all matched parentheses could be removed), then stop the while loop

Hinweis: l{könnte durch ( für 10 Byte ersetzt werden, ist aber leider nicht implementiert.

dzaima
quelle
Sind Sie sicher, dass das Spiegeln der Zeichen funktioniert? Ich weiß nicht genau, was das bedeutet, aber meine Intuition sagt mir, dass es auch die Reihenfolge der Zeichen umkehrt, was meiner Meinung nach nicht funktionieren würde.
Weizen-Assistent
1
@Olmman Es war beabsichtigt, die Zeichen umzukehren, aber nicht (was hier ein Byte speichert!). Es ist in der Aufstellung von V0.13, die Talsohle zu wechseln. Beispiel
Dzaima
5

CJam (20 Zeichen)

q1f^0X${~_}%_:e>#)m<

Online-Demo

oder für die gleiche Zeichenanzahl

q1f^_,,{0W$@<~}$W=m<

Online-Demo

Präparation

Die beiden Versionen haben eine gemeinsame Kopf- und Fußzeile

q1f^    e# Read input and toggle least significant bit of each character
        e# This effectively swaps ( and )

m<      e# Stack: swapped_string index
        e# Rotates the string to the left index characters

Dann berechnet das Bit in der Mitte offensichtlich, wie weit gedreht werden muss. Beide verwenden die Auswertung und sind darauf angewiesen (, der CJam-Dekrementierungsoperator und )der Inkrementierungsoperator zu sein.

0X$     e# Push 0 and a copy of the swapped string
{~_}%   e# Map: evaluate one character and duplicate top of stack
        e# The result is an array of the negated nesting depth after each character
_:e>    e# Copy that array and find its maximum value
#       e# Find the first index at which that value occurs
)       e# Increment

vs

_,,     e# Create array [0 1 ... len(swapped_string)-1]
{       e# Sort with mapping function:
  0W$@  e#   Rearrange stack to 0 swapped_string index
  <~    e#   Take first index chars of swapped_string and evaluate
}$      e# The result is an array of indices sorted by the negated nesting depth
W=      e# Take the last one
Peter Taylor
quelle
3

JavaScript (ES6), 111 bis 105 Byte

(2 Bytes gespart dank @CraigAyre, 2 Bytes dank @PeterTaylor, 2 Bytes dank @Shaggy.)

s=>(r=[...s].map(c=>'()'[c<')'|0])).some(_=>r.push(r.shift(i=0))&&!r.some(c=>(i+=c<')'||-1)<0))&&r.join``

Ungolfed:

s=>(
  r=[...s].map(c=>'()'[c<')'|0]),  //switch "(" and ")"
  r.some(_=>(
    r.push(r.shift(i=0)),          //move last element to beginning of array, initialize i
    !r.some(c=>(i+=c<')'||-1)<0)   //check if balanced (i should never be less than 0)
  )),
  r.join``
)

Testfälle:

Rick Hitchcock
quelle
3

Netzhaut , 46 38 Bytes

T`()`)(
(.*?)(((\()|(?<-4>\)))+)$
$2$1

Probieren Sie es online! Link enthält Testfälle. Bearbeiten: 8 Bytes mit Hilfe von @MartinEnder gespeichert. Die erste Stufe transponiert einfach die Klammern, während die zweite Stufe nach dem längsten Suffix sucht, bei dem es sich um ein gültiges ausgeglichenes Präfix handelt. Dies ist anscheinend eine ausreichende Bedingung, um die Rotation vollständig auszugleichen. Der Abgleich wird über Bilanzkreise ermittelt. Das Konstrukt ((\()|(?<-4>\)))+entspricht einer beliebigen Anzahl von (s plus einer beliebigen Anzahl von )s, solange wir bereits ( <-4>) so viele (s gesehen haben. Da wir nur nach einem gültigen Präfix suchen, müssen wir nicht mit den verbleibenden )s übereinstimmen .

Neil
quelle
Normalerweise wiederholen Sie nicht beide Klammern, sondern setzen sie abwechselnd ein, wodurch ein Byte gespart wird ((\()|(?<-2>\))). Aber Ihr Versuch inspiriert mich nur einen völlig neuen Ansatz zu finden, der zwei weitere spart: (?<-1>(\()*\))+. Dies wird sich in Zukunft sicherlich als nützlich erweisen. Vielen Dank. :)
Martin Ender
Es ist noch kürzer, die Drehung zu bestimmen, indem Sie das erste Suffix abgleichen, durch das Sie das Ende der Zeichenfolge erreichen können, ohne eine negative Stapeltiefe zu erhalten
Martin Ender
@MartinEnder Ich habe ursprünglich versucht, eine Abwechslung zu finden, konnte sie aber zu diesem Zeitpunkt nicht zum Laufen bringen, aber ich kann nicht sehen, wie sie (?<-1>(\()*\))+überhaupt funktioniert, da sie vom 1Stapel zu springen scheint, bevor sie tatsächlich mit irgendetwas übereinstimmt ...
Neil
@MartinEnder Wie es scheint, scheint die Alternativversion Golfspieler zu sein, wenn es darum geht, ausgeglichene Präfixe abzugleichen.
Neil
1
Das eigentliche Poppen findet am Ende der Gruppe statt, nicht am Anfang. Guter Punkt mit dem Wechsel, um das Duplikat zu vermeiden \(*.
Martin Ender
2

PHP, 110 108 Bytes

for($s=$argn;;$p?die(strtr($s,"()",")(")):$s=substr($s,1).$s[$i=0])for($p=1;$p&&$c=$s[$i++];)$p-=$c<")"?:-1;

Laufen Sie als Pipe mit -nRoder testen Sie es online .

Nervenzusammenbruch

for($s=$argn;               # import input
    ;                       # infinite loop
    $p?die(strtr($s,"()",")(")) # 2. if balanced: invert, print and exit
    :$s=substr($s,1).$s[$i=0]   #    else: rotate string, reset $i to 0
)                               # 1. test balance:
    for($p=1;                   # init $p to 1
        $p&&$c=$s[$i++];)       # loop through string while $p is >0
        $p-=$c<")"?:-1;             # increment $p for ")", decrement else
Titus
quelle
2

Python 3 , 112 103 101 Bytes

-2 Bytes dank @ Mr.Xcoder

k=y=input().translate(' '*40+')(')
while k:
 k=y=y[1:]+y[0]
 for _ in y:k=k.replace('()','')
print(y)

Probieren Sie es online!

ovs
quelle
101 Bytes ? Nicht sicher, ob es funktioniert
Mr. Xcoder
2

Oktave, 62 Bytes

@(s)")("(x=hankel(s,shift(s,1))-39)(all(cumsum(2*x'-3)>=0)',:)

Probieren Sie es online!

Eine Funktion, die die Zeichenfolge als Eingabe verwendet und alle Ergebnisse druckt.

Erläuterung:

           hankel(a,shift(a,1))                                % generate a matrix of n*n where n= length(s) and its rows contain incresing circulraly shifted s
         x=...                 -39                             % convert matrix of "(" and ")" to a mtrix of 1 and 2
    ")("(x                        )                            % switch the parens
                                               2*x'-3          % convert [1 2] to [-1 1]
                                        cumsum(      )         % cumulative sum along the rows
                                    all(              >=0)'    % if all >=0
                                   (                       ,:) % extract the desired rows
rahnema1
quelle
2

Mathematica, 78 Bytes

""<>{"(",")"}[[2ToCharacterCode@#-81//.x_/;Min@Accumulate@x<0:>RotateLeft@x]]&
Alephalpha
quelle
1

JavaScript (ES6), 97 Byte

f=(s,t=s,u=t.replace(')(',''))=>u?t==u?f(s.slice(1)+s[0]):f(s,u):s.replace(/./g,c=>c<')'?')':'(')

Arbeitet durch rekursives Drehen der Eingabezeichenfolge, bis die Transponierung ausgeglichen ist, und anschließendes Transponieren.

Neil
quelle
Einfach schön.
Rick Hitchcock
1

APL (Dyalog Unicode) , 35 30 Bytes

Ein neuer Ansatz dank @ Adám

1⌽⍣{2::01∊⍎⍕1,¨⍺}')('['()'⍳⎕]

Probieren Sie es online!

Golfen ist im Gange.

Erläuterung

'()'⍳⎕              Find the index of each character of the input in the string '()'
                    (this is 1-indexed, so an input of '(())()' would give 1 1 2 2 1 2)
')('[...]           Find the index of the vector in the string ')('
                    This essentially swaps ')'s with '('s and vice versa
                   On this new string, do:
 1                   rotate it one to the left
                    Until this results in 1:
 1,¨⍺                 Concatenate each element of the argument with a 1
                      This inserts 1 one before each parenthesis
                     Stringify it
                     And evaluate it, if the parentheses are balanced, this produces no errors
 1                   Check if 1 belongs to evaluated value
                      If the parentheses were not matches during ⍎, this causes a syntax error
 2::0                 This catches a syntax error and returns 0
                      Essentially this code checks if the brackets are balanced or not
Kritixi Lithos
quelle
0

Python 2 , 99 Bytes

r=[0];S=''
for c in input():b=c>'(';r+=[r[-1]+2*b-1];S+=')('[b]
n=r.index(min(r))
print S[n:]+S[:n]

Probieren Sie es online!

In Funktionsform für einfache Testfälle:

Python 2 , 108 Bytes

def f(s):
 r=[0];S=''
 for c in s:b=c>'(';r+=[r[-1]+2*b-1];S+=')('[b]
 n=r.index(min(r))
 return S[n:]+S[:n]

Probieren Sie es online!

Dies verwendet einen etwas anderen Ansatz - anstatt den String rekursiv zu drehen, wenn wir die Parens als Inkrementieren und Dekrementieren eines Balance-Zählers betrachten, darf ein ausgeglichener String niemals eine Gesamtsumme von Inkrementen haben - Dekremente, die kleiner als 0 sind.

Also nehmen wir

(()(())())

Invertiere die Eltern:

))())(()((

und konvertiere es in eine Liste von Summen von Inkrementen / Dekrementen:

[-1,-2,-1,-2,-3,-2,-1,-2,-1,0]

-3 ist das Minimum bei Index 4 (nullbasiert); also wollen wir uns um diesen Index + 1 verschieben. Dies garantiert, dass das kumulative Inkrement / Dekrement niemals kleiner als 0 ist; und wird zu 0 summieren.

Chas Brown
quelle
Auf meinem Handy kann ich also nicht testen, aber könntest du r=0,stattdessen tun r=[0]?
Cyoce
Wenn Sie mit @ Cyoce Vorschlag gehen, müssen Sie ersetzen r+=[r[-1]+2*b-1]mit r+=r[-1]+2*b-1,als auch
ovs
0

Clojure, 118 Bytes

#(loop[s(map{\(\)\)\(}%)](let[s(conj(vec(rest s))(first s))](if(some neg?(reductions +(map{\( 1\) -1}s)))(recur s)s)))

Gibt eine Folge von Zeichen zurück, also würde ich es so nennen:

(apply str (f "(()(())())"))
; "(()(())())"

Klammern werden zuerst umgedreht und dann wiederholt, solange die kumulative Summe der Klammernanzahl an einem bestimmten Punkt der Sequenz negativ wird.

NikoNyrh
quelle
0

Brainfuck , 82 Bytes

,[++[->->++<<]-[--->+>-<<]>-->+[-[-<<+>>>>+<<]],]+[<<]>>>[.[-]>>]<[<<]<[<<]>>[.>>]

Probieren Sie es online!

Erläuterung

Mit jedem gelesenen Zeichen wird ein Zähler wie folgt geändert:

  • Der Zähler beginnt bei 0.
  • Nach jedem )erhöht sich der Zähler um 1.
  • Nach jeder (Änderung verringert sich der Zähler um 1, es sei denn, der Zähler war 0. In diesem Fall bleibt der Zähler unverändert.

Jedes Präfix ist genau dann ein gültiges Suffix eines ausgeglichenen Strings (nach der Inversion), wenn dieser Zähler 0 ist. Dieser Code verwendet das längste Präfix, um die Ausgabe zu bilden.

,[                   Take input and start main loop
                     The cell one space right is the output cell (0 at this point),
                     and two spaces right is a copy of the previous counter value
  ++                 Add 2 to input
  [->->++<<]         Negate into output cell, and add twice to counter
  -[--->+>-<<]       Add 85 to output cell, and subtract 85 from counter
  >-->+              Subtract 2 from output cell and add 1 to counter
                     The output cell now has (81-input), and the counter has been increased by (2*input-80)
  [-[-<<+>>>>+<<]]   If the counter is nonzero, decrement and copy
,]
+[<<]                Go to the last position at which the counter is zero
>>>                  Go to following output character
[.[-]>>]             Output from here to end, clearing everything on the way
                     (Only the first one needs to be cleared, but this way takes fewer bytes)
<[<<]                Return to the same zero
<[<<]>>              Go to beginning of string
[.>>]                Output remaining characters
Nitrodon
quelle