Obróć sznurek na lewą stronę

21

Zrównoważony ciąg to ciąg nawiasów, ()dzięki czemu każdy nawias można dopasować do drugiego. Bardziej rygorystycznie są to struny łączone przez tę gramatykę:

S → (S)S | ε

Możemy obrócić ciąg „na lewą stronę” przez:

  • Przełączanie wszystkich wystąpień (i )ze sobą

  • Przenoszenie znaków od przodu sznurka do tyłu, aż sznurek zostanie ponownie zrównoważony.


Zróbmy przykład.

Zaczynamy od zbalansowanego ciągu:

(()(())())

Następnie zmieniamy pareny, aby zrobić

))())(()((

Następnie przesuwaj postacie z przodu łańcucha na tył łańcucha, aż łańcuch zostanie zrównoważony.

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

To nasz wynik!


Pamiętaj, że niektóre ciągi znaków można odwrócić na wiele sposobów, na przykład ciąg

(()())

Po wywróceniu na lewą stronę może być:

()(())

lub

(())()

Jednak każdy ciąg ma co najmniej jedno rozwiązanie .

Zadanie

Napisz program, który pobierze zbalansowany ciąg znaków jako wejście i wyjście tego łańcucha wywróconego na lewą stronę. W przypadkach, gdy może istnieć wiele prawidłowych wyników, potrzebujesz tylko jednego z nich. Można użyć innego typu nawiasów ( <>, []lub {}) jeśli sobie tego życzą.

To zawody w dlatego powinieneś dążyć do zminimalizowania rozmiaru kodu źródłowego, mierzonego w bajtach.

Przypadki testowe

(()())     -> ()(()), (())()
(()(())()) -> (()(())())
((())())() -> (()(()()))
Kreator pszenicy
źródło
Czy jest pewne, że zawsze istnieje rozwiązanie?
Luis Mendo
@LuisMendo Tak, udowodniłem to. Jeśli chcesz zobaczyć dowód, możesz wysłać mi ping na czacie.
Wheat Wizard
Dzięki. Wystarczy mi to wiedzieć. Może powinieneś napisać to do wyzwania, w przeciwnym razie musisz zdefiniować, co wydrukować, jeśli nie ma rozwiązania
Luis Mendo
powiązane
officialaimm

Odpowiedzi:

9

Haskell , 124 120 119 117 113 110 109 106 105 104 101 98 bajtów

4 bajty zapisane dzięki bartavelle!

3 bajty zapisane dzięki Zgarb

1 bajt zaoszczędzony dzięki Peterowi Taylorowi

Oto rozwiązanie, które wypracowałem w Haskell. W tej chwili jest ok, całkiem niezłe dzięki pomocy, którą otrzymałem, ale chcę to skrócić, więc opinie i sugestie są mile widziane.

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 _='('

Wypróbuj online!

Wyjaśnienie

Ten program definiuje 4 funkcje, pierwsza (!)określa, czy łańcuch jest zrównoważony. Jest zdefiniowany w następujący sposób:

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

Ta kontrola zakłada, że ​​dane wejściowe mają taką samą liczbę otwartych i zamkniętych części, dzięki sugestii Petera Taylora.

Kolejny graz obróci łańcuch.

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

Mamy więc, dktóry po prostu bierze paren i odzwierciedla go

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

Wreszcie mamy funkcję, którą się zajmujemy. Tutaj używamy bezcelowej reprezentacji until(!0)gzłożonej z map d, która odwzorowuje ddane wejściowe i obowiązuje, gdopóki wynik nie zostanie zrównoważony. Jest to dokładny proces opisany w pytaniu.

until(!0)g.map d
Kreator pszenicy
źródło
1
Możesz skrobić kilka bajtów g x@(a:b)|x!0=x|1>0=g$b++[a]i usunąć pareny dla d '('=')'.
bartavelle,
@bartavelle Usunięcie parens dla dpowoduje błąd kompilatora, uwierz mi próbowałem. Ale pierwsza sugestia jest mile widziana. Dzięki!
Wheat Wizard
1
Można zapisać kolejny bajt !, ponieważ nie trzeba obsługiwać przypadki, w których ciąg ma nierówną liczbę otwartych i zamkniętych nawiasach, więc można zamienić dwa pierwsze przypadki i mają_!1=1<0 []!_=0<1
Peter Taylor
1
Użyj, untilaby skrócić g: TIO
Zgarb
2
Myślę, że nie powinno być przyzwoite oszczędności poprzez dmapę '('do (-1)i nic innego 1, a następnie dwa najdłuższe przypadki !mogą być łączone (i:a)!x=a!(x+i). Struktura najwyższego poziomu wymaga następnie przeróbki, aby wprowadzić ją map dw untilstan, i muszę biec, więc nie mam teraz czasu, aby dowiedzieć się, jakie kombinatory są potrzebne, aby skleić to wszystko razem.
Peter Taylor
7

SOGL V0.12 , 12 11 bajtów

↔]»:l{Ƨ()øŗ

Wypróbuj tutaj!

Wyjaśnienie:

↔            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

Uwaga: l{można go zastąpić ( dla 10 bajtów, ale niestety nie jest zaimplementowany.

dzaima
źródło
Czy na pewno działa dublowanie postaci? Nie wiem dokładnie, co to znaczy, ale moja intuicja podpowiada mi, że odwraca również kolejność postaci, które, jak sądzę, nie działałyby.
Wheat Wizard
1
@Olmman Miało to na celu odwrócenie znaków, ale nie robi tego (co oszczędza bajt tutaj!). Jest w składzie V0.13 do zmiany koryta. Przykład
dzaima
5

CJam (20 znaków)

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

Demo online

lub dla tej samej liczby znaków

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

Demo online

Sekcja

Dwie wersje mają wspólny nagłówek i stopkę

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

Następnie bit pośrodku oczywiście oblicza, jak daleko trzeba się obrócić. Obaj używają oceny i polegają na (tym, że są operatorem dekrementacji CJam i )operatorem inkrementacji.

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
źródło
3

JavaScript (ES6), 111 105 bajtów

(Zapisano 2 bajty dzięki @CraigAyre, 2 bajty dzięki @PeterTaylor, 2 bajty dzięki @Shaggy.)

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

Nie golfowany:

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``
)

Przypadki testowe:

Rick Hitchcock
źródło
3

Siatkówka , 46 38 bajtów

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

Wypróbuj online! Link zawiera przypadki testowe. Edycja: Zapisano 8 bajtów przy pomocy @MartinEnder. Pierwszy etap po prostu transponuje nawiasy, podczas gdy drugi etap szuka najdłuższego sufiksu, który jest prawidłowym zrównoważonym prefiksem, który najwyraźniej jest wystarczającym warunkiem pełnego zrównoważenia obrotu. Równoważenie jest wykrywane za pomocą grup bilansujących. Konstrukt ((\()|(?<-4>\)))+pasuje do dowolnej liczby (s plus dowolnej liczby )s, o ile widzieliśmy już ( <-4>) tyle (s. Ponieważ szukamy tylko poprawnego prefiksu, nie musimy dopasowywać pozostałych )s.

Neil
źródło
Zwykle zamiast powtarzać oba nawiasy, po prostu umieszczasz je na przemian, co oszczędza bajt ((\()|(?<-2>\))). Ale twoja próba właśnie zainspirowało mnie znaleźć zupełnie nowe podejście, które pozwala zaoszczędzić kolejne dwa: (?<-1>(\()*\))+. To z pewnością przyda się w przyszłości, więc dziękuję. :)
Martin Ender
Jeszcze krótsze jest określenie obrotu przez dopasowanie pierwszego sufiksu, przez który można dotrzeć do końca łańcucha bez uzyskania ujemnej głębokości stosu: tio.run/…
Martin Ender
@MartinEnder Początkowo próbowałem alternatywy, ale nie mogłem jej w tym czasie zadziałać, ale nie widzę, jak to (?<-1>(\()*\))+działa, ponieważ wydaje się, że chce wyskoczyć ze 1stosu, zanim faktycznie coś dopasuje ...
Neil
@MartinEnder Tak się składa, że ​​wersja alternatywna wydaje się być golfistą, jeśli chodzi o dopasowanie zrównoważonych prefiksów.
Neil
1
Rzeczywiste wyskakiwanie odbywa się na końcu grupy, a nie na początku. Dobra uwaga z alternatywą, aby uniknąć duplikatu \(*.
Martin Ender,
2

PHP, 110 108 bajtów

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

Uruchom jako potok -nRlub przetestuj go online .

awaria

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
Tytus
źródło
2

Python 3 , 112 103 101 bajtów

-2 bajty dzięki @ Mr.Xcoder

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

Wypróbuj online!

ovs
źródło
101 bajtów ? Nie jestem pewien, czy to działa
Mr. Xcoder,
2

Oktawa, 62 bajty

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

Wypróbuj online!

Funkcja, która pobiera ciąg jako dane wejściowe i drukuje wszystkie wyniki.

Wyjaśnienie:

           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
źródło
2

Mathematica, 78 bajtów

""<>{"(",")"}[[2ToCharacterCode@#-81//.x_/;Min@Accumulate@x<0:>RotateLeft@x]]&
alephalpha
źródło
1

JavaScript (ES6), 97 bajtów

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

Działa poprzez rekurencyjne obracanie łańcucha wejściowego, aż jego transpozycja zostanie zrównoważona, a następnie transpozycja.

Neil
źródło
Po prostu piękna.
Rick Hitchcock,
1

APL (Dyalog Unicode) , 35 30 bajtów

Grał w golfa nowe podejście dzięki @ Adám

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

Wypróbuj online!

Gra w golfa jest w toku.

Wyjaśnienie

'()'⍳⎕              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
źródło
0

Python 2 , 99 bajtów

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]

Wypróbuj online!

W formie funkcji dla łatwych przypadków testowych:

Python 2 , 108 bajtów

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]

Wypróbuj online!

Stosuje to nieco inne podejście - zamiast rekurencyjnego obracania struny, jeśli myślimy o parenach jako o zwiększaniu i zmniejszaniu pewnego licznika bilansu, wtedy zrównoważony łańcuch nigdy nie może mieć całkowitej sumy przyrostów - ubytków, które są mniejsze niż 0.

Więc bierzemy

(()(())())

odwróć parens:

))())(()((

i przekonwertować na listę sum przyrostów / spadków:

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

-3 to minimum przy indeksie 4 (oparte na zerach); więc chcemy przesunąć się o ten indeks + 1. Gwarantuje to, że skumulowany przyrost / spadek nigdy nie będzie mniejszy niż 0; i sumuje się do 0.

Chas Brown
źródło
Na moim telefonie, więc nie mogę przetestować, ale czy mógłbyś to zrobić r=0,zamiast r=[0]?
Cyoce
Jeśli masz zamiar z @ sugestią Cyoce, będziesz musiał wymienić r+=[r[-1]+2*b-1]z r+=r[-1]+2*b-1,tak dobrze
OVS
0

Clojure, 118 bajtów

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

Zwraca ciąg znaków, więc nazwałbym to tak:

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

Najpierw odwraca nawiasy, a następnie zapętla tak długo, jak skumulowana suma liczby nawiasów spadnie w pewnym momencie sekwencji.

NikoNyrh
źródło
0

pieprzenie mózgu , 82 bajty

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

Wypróbuj online!

Wyjaśnienie

Po każdym odczytaniu znaku licznik jest modyfikowany w następujący sposób:

  • Licznik zaczyna się od 0.
  • Po każdym )licznik zwiększa się o 1.
  • Po każdym (licznik zmniejsza się o 1, chyba że licznik wynosił 0, w którym to przypadku licznik pozostaje niezmieniony.

Każdy prefiks jest poprawnym sufiksem zbalansowanego łańcucha (po inwersji) wtedy i tylko wtedy, gdy licznik ma wartość 0. Ten kod używa najdłuższego takiego prefiksu do utworzenia wyniku.

,[                   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
źródło